System and method for estimating impedance time through a road network

• US 6,856,893 B2
• Filed: 09/12/2003
• Issued: 02/15/2005
• Est. Priority Date: 12/11/2001
• Status: Expired due to Term

• Current Assignee: Garmin Limited
• Original Assignee: Garmin Limited
• Inventors: Childs, Michael, Beesley, Darin J.
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US10/660,835
• Publication Number:
  US 20040049338A1
• Time in Patent Office: 522 Days
• Field of Search: 701/23, 701/25, 701/200, 701/202, 701/208, 701/209, 701/117, 701/118, 340/999, 340/990, 340/995.19, 340/995.2
• US Class Current: 701/202
• 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 method for estimating an impedance time through a node at an intersection between roads in a roadway network, comprising:

identifying characteristic information for roads intersecting at a node in a roadway network, said characteristic information describing at least one feature concerning an associated road; and

estimating an impedance time associated with potential delays by traffic traveling through the node based on the characteristic information for the roads intersecting at the node.

2. The method of claim 1, wherein said identifying step comprises obtaining speed information concerning the roads intersecting at the node, said speed information constituting at least a portion of said characteristic information.

3. The method of claim 1, wherein said identifying step comprises obtaining speed categories describing speed bands associated with the roads intersecting at the node, said speed categories constituting at least a portion of said characteristic information, each speed band representing a range of speed in which traffic travels on the associated road.

4. The method of claim 1, wherein said identifying step comprises obtaining road-types for the roads intersecting at the node, the road-types constituting at least a portion of said characteristic information, the roadway network being divided into a hierarchy of road-types.

5. The method of claim 1, wherein said identifying step comprises obtaining network routing levels describing a road-type classification feature for the associated road, said road-type classification feature constituting at least a portion of the characteristic information.

6. The method of claim 1, wherein said estimating step is based in part on at least one of intersection angle information, speed information and network routing levels for the roads intersecting at the node.

7. The method of claim 1, further comprising:

obtaining a speed band associated with each road intersecting at the node, the speed band identifying a speed range in which traffic travels on the associated road; and

determining a speed differential between the speed bands, the speed differential representing a relative change between speed ranges of the roads intersecting at the node, the speed differential representing at least a portion of the characteristic information.

8. The method of claim 1, wherein each road is assigned a route level within a network routing hierarchy, the method further comprising:

determining route levels assigned to the roads intersecting at the node; and

calculating a level differential between the route levels of the roads intersecting at the node, the level differential representing at least a portion of the characteristic information.

9. A method for calculating a navigation route between first and second geographic locations through a roadway network of roads intersecting at nodes, comprising:

providing a data structure having data indicative of a roadway network of roads intersecting at intersection nodes, said data including feature data indicative of traffic characteristics for associated roads;

calculating a route impedance for a navigation route through said roadway network between first and second geographic locations based on said feature data;

determining node impedances for intersection nodes though which the navigation route travels based on said feature data, said intersection nodes representing locations along the navigation route at which roads followed by the navigation route intersect other roads; and

utilizing said node impedance and route impedance to calculate the navigation route.

10. The method of claim 9, wherein said node impedances are indicative of a potential delay that traffic experiences when traveling through an associated intersection node.

11. The method of claim 9, wherein said feature data is indicative of speed information for traffic patterns experienced by an associated road, and wherein said determining step determines said node impedances based at least in part on said speed information.

12. The method of claim 9, wherein said feature data is indicative of speed bands assigned to an associated road, and wherein said determining step determines said node impedances based at least in part on said speed bands.

13. The method of claim 9, wherein said node and route impedances represent time estimates for traveling along corresponding roads and through corresponding nodes.

14. The method of claim 9, wherein said node and route impedances represent distance estimates for traveling along corresponding roads and synthetic distance penalties for traveling through corresponding nodes.

15. A navigation device comprising:

memory for at least temporarily storing at least a portion of a data structure having data indicative of a roadway network of roads intersecting at nodes, said data structure including feature data indicative of traffic characteristics for associated roads;

a processor accessing said memory and calculating, from said data structure, a route through said roadway network between geographic locations based on data indicative of route impedances associated with selected roads in the roadway network, said processor estimating node impedances for intersection nodes through which the route travels, said processor utilizing said route impedance and node impedance to calculate the route.

16. The navigation device of claim 15, further comprising:

an input buffer for temporarily storing said portion of said data structure received from an external storage device.

17. The navigation device of claim 15, further comprising a display presenting said route to an operator.

18. The navigation device of claim 15, further comprising a wireless input/output unit configured to communicate with an external network and to receive at least said portion of said data structures over a wireless connection with the external network.

19. The navigation device of claim 15, wherein said memory stores feature data indicative of speed information concerning roads intersecting at nodes through which the route travels, said processor estimating node impedances based on said speed information.

20. The navigation device of claim 15, wherein said memory stores feature data indicative of road-types for roads intersecting at nodes through which the route travels, the roadway network being divided into a hierarchy of road-types, said processor estimating node impedances based on said road-types.

21. The navigation device of claim 15, wherein said memory stores feature data indicative of routing levels describing classifications for roads intersecting at nodes through which the route travels, said processor estimating node impedances based on said routing levels.

22. A navigation system comprising:

a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of said 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 said roads and through said nodes in said roadway network route that, while reducing an overall distance traveled by a planned route, are to be avoided in said planned route between said source and destination locations, said route calculation module avoiding said undesirable shortcuts.

23. The navigation system of claim 22, wherein said data structure stores road-type information classifying said roads within a hierarchy of route levels, said correction module identifying shortcuts along lower road-type paths passing from a first road classified with a high route level to a road classified with a lower route level and back onto said first road, said route calculation module avoiding said lower road-type paths.

24. The navigation system of claim 22, further comprising a server and a mobile unit communicating over a network with said server, said server containing at least one of said storage unit, route calculation module and correction module.

25. The navigation system of claim 22, further comprising a server, and a mobile unit communicating with said server, said server and mobile unit each including at least one of said data storage unit, route calculation module, and correction module.

26. A computer program embodied on a computer-readable medium for estimating an impedance time through a node at an intersection between roads in a roadway network, comprising:

an identification source code segment identifying characteristic information for roads intersecting at a node in a roadway network, said characteristic information describing at least one feature concerning an associated road; and

an estimation source code segment estimating an impedance time associated with potential delays by traffic traveling through the node based on the characteristic information for the roads intersecting at the node.

27. The computer program of claim 26, wherein said identification source code segment obtains speed information concerning the roads intersecting at the node, said speed information constituting at least a portion of said characteristic information.

28. The computer program of claim 26, wherein said identification source code segment obtains speed categories describing speed bands associated with the roads intersecting at the node, said speed categories constituting at least a portion of said characteristic information, each speed band representing a range of speed in which traffic travels on the associated road.

29. The computer program of claim 26, wherein said identification source code segment obtains road-types for the roads intersecting at the node, the road-types constituting at least a portion of said characteristic information, the roadway network being divided into a hierarchy of road-types.

30. The computer program of claim 26, wherein said identification source code segment obtains network routing levels describing a road-type classification feature for the associated road, said road-type classification feature constituting at least a portion of the characteristic information.

31. The computer program of claim 26, wherein said estimation source code segment is based in part on at least one of intersection angle information, speed information and network routing levels for the roads intersecting at the node.

32. The computer program of claim 26, wherein each road is assigned a route level within a network routing hierarchy, the computer program further comprising:

a source code segment determining route levels assigned to the roads intersecting at the node; and

a source code segment calculating a level differential between the route levels of the roads intersecting at the node, the level differential representing at least a portion of the characteristic information.