System and method for estimating impedance time through a road network

• US 20050090976A1
• Filed: 12/08/2004
• Published: 04/28/2005
• Est. Priority Date: 12/11/2001
• Status: Abandoned Application

• Current Assignee: Garmin Limited
• Original Assignee: Garmin Limited
• Inventors: Childs, Michael, Beesley, Darin J.
• Application Number:
  US11/007,834
• Publication Number:
  US 20050090976A1
• Time in Patent Office: Days
• US Class Current: 701/209
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• CPC Class Codes: G08G 1/096838 where the user preferences are taken into account or the user selects one route out of a plurality
• CPC Class Codes: G08G 1/096883 where input information is obtained using a mobile device, e.g. a mobile phone, a PDA

Abstract

A method and apparatus are provided for estimating an impedance through a node at an intersection between roads in a roadway network. The impedance may be measured in time or distance, for example. Characteristic information describes at least one feature of the intersecting roads. One or more pieces of characteristic information may impact the impedance of traffic through an intersection and are used to estimate the impedance through the node. Examples of characteristic information are speed information, road-type, network routing level, intersection angle information, one-way, and cross traffic turn information. An impedance factor, or a cost, is assigned to each piece of characteristic information. The cost may be positive if the characteristic information adds impedance to the node, or negative if the characteristic information subtracts impedance from the node.

Claims

1. A navigation system comprising:

a server including—

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of the roads at nodes,

a route calculation module calculating a planned route over the roadway network between source and destination locations based on the data structure held in the storage unit, and

a correction module for identifying undesirable shortcuts constituting predefined paths along the roads and through the nodes in the roadway network route that, while reducing an overall distance traveled by the planned route, are to be avoided in the planned route between the source and destination; and

a navigation device operable to transmit the locations to the server and receive the route from the server over a communications link.

2. The system as set forth in claim 1, wherein the route calculation module avoids the undesirable shortcuts.

3. The system as set forth in claim 1, wherein the correction module identifies ramp shortcuts along an exit ramp and entrance ramp of a road.

4. The system as set forth in claim 3, wherein the route calculation module avoids the ramp shortcuts.

5. The system as set forth in claim 1, wherein the correction module identifies neighborhood shortcuts through residential roads in the roadway network where the residential roads do not directly connect with either one of the source and destination locations.

6. The system as set forth in claim 5, wherein the route calculation module avoids the neighborhood shortcuts.

7. The system as set forth in claim 1, wherein the correction module includes a neighborhood progression module identifying when the planned route travels along residential roads located remote from the source and destination locations.

8. The system as set forth in claim 7, wherein the route calculation module updates the route to avoid residential roads that are remote from the source and destination locations based on neighborhood information received from the neighborhood progression module.

9. The system as set forth in claim 1, wherein the route calculation module adds one of a distance and time penalty to potential routes that include at least one of exit/entrance ramp shortcuts and neighborhood shortcuts.

10. The system as set forth in claim 1, the device including—

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites; and

a processor for calculating, by triangulation, a position of the device using the signals.

11. The system as set forth in claim 10, wherein the processor determines the source location using the signals and a user provides the destination location using an input.

12. The system as set forth in claim 10, wherein the device further includes a display for displaying the route.

13. A navigation system comprising:

a server including—

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of the roads at nodes,

a route calculation module calculating a planned route over the roadway network between source and destination locations based on the data structure held in the storage unit, the route calculation module avoiding the ramp shortcuts, and

a correction module for identifying undesirable shortcuts constituting predefined paths along the roads and through the nodes in the roadway network that, while reducing an overall distance traveled by the planned route, are to be avoided in the planned route between the source and destination locations, the correction module identifying ramp shortcuts along an exit ramp and entrance ramp of a road, the route calculation module avoiding the undesirable shortcuts; and

a navigation device operable to transmit the geographic locations to the server and receive the route from the server over a communications link.

14. The system as set forth in claim 13, the device including—

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites; and

a processor for calculating, by triangulation, a position of the device using the signals.

15. The system as set forth in claim 14, wherein the processor determines the source location using the signals and a user provides the destination location using an input.

16. A navigation system comprising:

a server comprising;

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of the roads at nodes,

a route calculation module calculating a planned route over the roadway network between source and destination locations based on the data structure held in the storage unit, and

a correction module for identifying undesirable shortcuts constituting predefined paths along the roads and through the nodes in the roadway network that, while reducing an overall distance traveled by the planned route, are to be avoided in the planned route between the source and destination locations, the route calculation module avoiding the undesirable shortcuts, the correction module identifying neighborhood shortcuts through residential roads in the roadway network where the residential roads do not directly connect with either one of the source and destination locations, the route calculation module avoiding the neighborhood shortcuts; and

a navigation device operable to transmit the locations to the server and receive the route from the server over a communications link.

17. The system as set forth in claim 16, the device including—

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites; and

a processor for calculating, by triangulation, a position of the device using the signals.

18. The system as set forth in claim 17, wherein the processor determines the source location using the signals and a user provides the destination location using an input.

19. A navigation system comprising:

a server including—

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of the roads at nodes,

a route calculation module calculating a planned route over the roadway network between source and destination locations based on the data structure held in the storage unit, and

a correction module for identifying undesirable shortcuts constituting predefined paths along the roads and through the nodes in the roadway network that, while reducing an overall distance traveled by the planned route, are to be avoided in the planned route between the source and destination locations, the route calculation module avoiding the undesirable shortcuts, wherein the correction module includes a neighborhood progression module identifying when the planned route travels along residential roads located remote from the source and destination locations, the route calculation module updating the route to avoid residential roads that are remote from the source and destination locations based on neighborhood information received from the neighborhood progression module; and

a navigation device operable to transmit the locations to the server and receive the route from the server over a communications link.

20. The system as set forth in claim 19, the device including—

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites; and

a processor for calculating, by triangulation, a position of the device using the signals.

21. The system as set forth in claim 20, wherein the processor determines the source location using the signals and a user provides the destination location using an input.

22. A navigation system comprising:

a server including—

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of the roads at nodes,

a route calculation module calculating a planned route over the roadway network between source and destination locations based on the data structure held in the storage unit, and

a correction module for identifying undesirable shortcuts constituting predefined paths along the roads and through the nodes in the roadway network that, while reducing an overall distance traveled by the planned route, are to be avoided in the planned route between the source and destination, the route calculation module avoiding the undesirable shortcuts, wherein the route calculation module adds one of a distance and time penalty to potential routes that include at least one of exit/entrance ramp shortcuts and neighborhood shortcuts; and

a navigation device operable to transmit the locations to the server and receive the route from the server over a communications link.

23. The system as set forth in claim 22, the device including—

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites; and

a processor for calculating, by triangulation, a position of the device using the signals.

24. The system as set forth in claim 23, wherein the processor determines the source location using the signals and a user provides the destination location using an input.

25. A navigation server for calculating a route between source and destination locations and transmitting the route to a portable navigation device for navigating the route, the server comprising:

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of the roads at nodes;

a route calculation module calculating the route over the roadway network between the source and destination locations based on the data structure held in the storage unit, the route calculation module avoiding the ramp shortcuts; and

a correction module for identifying undesirable shortcuts constituting predefined paths along the roads and through the nodes in the roadway network that, while reducing an overall distance traveled by the route, are to be avoided in the route between the source and destination locations, the correction module identifying ramp shortcuts along an exit ramp and entrance ramp of a road, the route calculation module avoiding the undesirable shortcuts.

26. The server as set forth in claim 25, wherein the server transmits the route to the device over a wireless communications network.

27. The server as set forth in claim 25, wherein the server receives the source and destination locations from the device over a wireless communications network.

28. The server as set forth in claim 25, wherein the device includes—

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites;

a processor for calculating, by triangulation, the source location using the signals;

an input for receiving the destination location from a user; and

a display for displaying the route.

29. The server as set forth in claim 28, wherein the server also transmits to the device a map displaying the route.

30. A portable navigation device for navigating a route between source and destination locations, the device comprising:

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites;

a processor for calculating, by triangulation, the source location using the signals;

an input for receiving indication of the destination location from a user;

a display for displaying the route between the source and destination locations; and

a transceiver for receiving the route from a server.

31. The device as set forth in claim 30, wherein the server receives the source and destination locations from the device over a wireless communications network, calculates the route between the source and destination locations, and transmits the route to the device over the network.

32. The device as set forth in claim 30, wherein the server includes—

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of the roads at nodes;

a route calculation module calculating the route over the roadway network between the source and destination locations based on the data structure held in the storage unit, the route calculation module avoiding the ramp shortcuts; and

a correction module for identifying undesirable shortcuts constituting predefined paths along the roads and through the nodes in the roadway network that, while reducing an overall distance traveled by the route, are to be avoided in the route between the source and destination locations, the correction module identifying ramp shortcuts along an exit ramp and entrance ramp of a road, the route calculation module avoiding the undesirable shortcuts.

33. The device as set forth in claim 30, wherein the server also transmits to the device a map displaying the route.

34. A navigation server for calculating a route between source and destination locations and transmitting the route to a portable navigation device for navigating the route, the server comprising:

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of the roads at nodes;

a route calculation module calculating the route over the roadway network between the source and destination locations based on the data structure held in the storage unit; and

a correction module for identifying undesirable shortcuts constituting predefined paths along the roads and through the nodes in the roadway network that, while reducing an overall distance traveled by the route, are to be avoided in the route between the source and destination locations, the route calculation module avoiding the undesirable shortcuts, the correction module identifying neighborhood shortcuts through residential roads in the roadway network where the residential roads do not directly connect with either one of the source and destination locations, the route calculation module avoiding the neighborhood shortcuts.

35. The server as set forth in claim 34, wherein the server transmits the route to the device over a wireless communications network.

36. The server as set forth in claim 34, wherein the server receives the source and destination locations from the device over a wireless communications network.

37. The server as set forth in claim 34, wherein the device includes—

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites;

a processor for calculating, by triangulation, the source location using the signals;

an input for receiving the destination location from a user; and

a display for displaying the route.

38. The server as set forth in claim 37, wherein the server also transmits to the device a map displaying the route.

39. A portable navigation device for navigating a route between source and destination locations, the device comprising:

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites;

a processor for calculating, by triangulation, the source location using the signals;

an input for receiving indication of the destination location from a user;

a display for displaying the route between the source and destination locations; and

a transceiver for receiving the route from a server.

40. The device as set forth in claim 39, wherein the server receives the source and destination locations from the device over a wireless communications network, calculates the route between the source and destination locations, and transmits the route to the device over the network.

41. The device as set forth in claim 39, wherein the server includes—

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of the roads at nodes;

a route calculation module calculating the route over the roadway network between the source and destination locations based on the data structure held in the storage unit; and

a correction module for identifying undesirable shortcuts constituting predefined paths along the roads and through the nodes in the roadway network that, while reducing an overall distance traveled by the route, are to be avoided in the route between the source and destination locations, the route calculation module avoiding the undesirable shortcuts, the correction module identifying neighborhood shortcuts through residential roads in the roadway network where the residential roads do not directly connect with either one of the source and destination locations, the route calculation module avoiding the neighborhood shortcuts.

42. The device as set forth in claim 39, wherein the server also transmits to the device a map displaying the route.

43. A navigation server for calculating a route between source and destination locations and transmitting the route to a portable navigation device for navigating the route, the server comprising:

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of the roads at nodes;

a route calculation module calculating the route over the roadway network between the source and destination locations based on the data structure held in the storage unit; and

a correction module for identifying undesirable shortcuts constituting predefined paths along the roads and through the nodes in the roadway network that, while reducing an overall distance traveled by the route, are to be avoided in the route between the source and destination locations, the route calculation module avoiding the undesirable shortcuts, wherein the correction module includes a neighborhood progression module identifying when the planned route travels along residential roads located remote from the source and destination locations, the route calculation module updating the route to avoid residential roads that are remote from the source and destination locations based on neighborhood information received from the neighborhood progression module.

44. The server as set forth in claim 43, wherein the server transmits the route to the device over a wireless communications network.

45. The server as set forth in claim 43, wherein the server receives the source and destination locations from the device over a wireless communications network.

46. The server as set forth in claim 43, wherein the device includes—

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites;

a processor for calculating, by triangulation, the source location using the signals;

an input for receiving the destination location from a user; and

a display for displaying the route.

47. The server as set forth in claim 46, wherein the server also transmits to the device a map displaying the route.

48. A portable navigation device for navigating a route between source and destination locations, the device comprising:

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites;

a processor for calculating, by triangulation, the source location using the signals;

an input for receiving indication of the destination location from a user;

a display for displaying the route between the source and destination locations; and

a transceiver for receiving the route from a server.

49. The device as set forth in claim 48, wherein the server receives the source and destination locations from the device over a wireless communications network, calculates the route between the source and destination locations, and transmits the route to the device over the network.

50. The device as set forth in claim 48, wherein the server includes—

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of the roads at nodes;

a route calculation module calculating the route over the roadway network between the source and destination locations based on the data structure held in the storage unit; and

a correction module for identifying undesirable shortcuts constituting predefined paths along the roads and through the nodes in the roadway network that, while reducing an overall distance traveled by the route, are to be avoided in the route between the source and destination locations, the route calculation module avoiding the undesirable shortcuts, wherein the correction module includes a neighborhood progression module identifying when the planned route travels along residential roads located remote from the source and destination locations, the route calculation module updating the route to avoid residential roads that are remote from the source and destination locations based on neighborhood information received from the neighborhood progression module.

51. The device as set forth in claim 48, wherein the server also transmits to the device a map displaying the route.

52. A navigation server for calculating a route between source and destination locations and transmitting the route to a portable navigation device for navigating the route, the server comprising:

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of the roads at nodes;

a route calculation module calculating the route over the roadway network between the source and destination locations based on the data structure held in the storage unit; and

a correction module for identifying undesirable shortcuts constituting predefined paths along the roads and through the nodes in the roadway network that, while reducing an overall distance traveled by the route, are to be avoided in the route between the source and destination, the route calculation module avoiding the undesirable shortcuts, wherein the route calculation module adds one of a distance and time penalty to potential routes that include at least one of exit/entrance ramp shortcuts and neighborhood shortcuts.

53. The server as set forth in claim 52, wherein the server transmits the route to the device over a wireless communications network.

54. The server as set forth in claim 52, wherein the server receives the source and destination locations from the device over a wireless communications network.

55. The server as set forth in claim 52, wherein the device includes—

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites;

a processor for calculating, by triangulation, the source location using the signals;

an input for receiving the destination location from a user; and

a display for displaying the route.

56. The server as set forth in claim 55, wherein the server also transmits to the device a map displaying the route.

57. A portable navigation device for navigating a route between source and destination locations, the device comprising:

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites;

a processor for calculating, by triangulation, the source location using the signals;

an input for receiving indication of the destination location from a user;

a display for displaying the route between the source and destination locations; and

a transceiver for receiving the route from a server.

58. The device as set forth in claim 57, wherein the server receives the source and destination locations from the device over a wireless communications network, calculates the route between the source and destination locations, and transmits the route to the device over the network.

59. The device as set forth in claim 57, wherein the server includes—

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of the roads at nodes;

a route calculation module calculating the route over the roadway network between the source and destination locations based on the data structure held in the storage unit; and

a correction module for identifying undesirable shortcuts constituting predefined paths along the roads and through the nodes in the roadway network that, while reducing an overall distance traveled by the route, are to be avoided in the route between the source and destination, the route calculation module avoiding the undesirable shortcuts, wherein the route calculation module adds one of a distance and time penalty to potential routes that include at least one of exit/entrance ramp shortcuts and neighborhood shortcuts.

60. The device as set forth in claim 57, wherein the server also transmits to the device a map displaying the route.