System and method for calculating an optimized route and calculation thereof

• US 6,785,608 B1
• Filed: 12/19/2001
• Issued: 08/31/2004
• Est. Priority Date: 12/19/2001
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: Milici, Mike, Tan, Xue
• Primary Examiner(s): Chin, Gary
• Application Number:
  US10/026,503
• Time in Patent Office: 986 Days
• Field of Search: 701/202, 701/209, 701/210, 340/995.21, 340/995.19
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A bounding route is calculated between two physical locations to determine a boundary value for which subsequent route calculations or portions thereof may be compared to. The bounding route may be calculated by selecting segments of roads that satisfy certain criteria. These criteria may be based on weighting factors or parameters such as the “least distance traveled” or the “least travel time.” The bounding route and the value may then provide any route calculation program with criteria used to determine whether a search at a particular location should continue. That is, if a search at a particular location has exceeded the criteria, or equivalently, the search has gone beyond the boundary, the search is stopped because it will most likely result in an un-optimal route. This process may then be an iterative one until an optimal search with a value less than the boundary value is found.

Claims

1. A method for calculating an optimal route from a first location to a second location along a road network located in a geographic region using a geographic database that represents the road network, wherein the optimal route has a characteristic optimized for a specific criterion, the method comprising the steps of:

with a relatively fast algorithm optimized for the specific criterion of the characteristic, determining a trial route from the first location to the second location using the geographic database,

determining a boundary value for the characteristic, wherein the boundary value is that value by which the characteristic of the trial route meets the criterion; and

from all possible routes between the first location and the second location that have a value for the characteristic that is less than the boundary value, selecting as the optimal route that route that has an optimal value for the characteristic.

2. The method of claim 1 wherein the characteristic is travel time and the specific criterion is least travel time.

3. The method of claim 1 wherein the characteristic is distance traveled and the specific criterion is least distance traveled.

4. The method of claim 1 wherein the characteristic is a combination of travel and distance and the specific criterion is speed.

5. The method of claim 1 wherein if one of the subsequent route calculations has exceeded the boundary value, the route calculation is stopped to pursue a potentially better route at a different location.

6. The method of claim 1 wherein the algorithm is one of the A* algorithm and the Dykstra algorithm.

7. A route calculation program for use in a navigation system, the route calculation program adapted to calculate an optimal route from a first location to a second location along a road network located in a geographic region using a geographic database that represents the road network, wherein the optimal route has a characteristic optimized for a specific criterion, the route calculation program comprising the steps of:

determining a bounding route between the first location and the second location by selecting segments of roads that have characteristics that best satisfy the specific criterion;

determining a boundary value by assessing the characteristics of each selected segment of road of the bounding route; and

selecting as the optimal route among all possible routes that has an optimal value for the characteristics of all subsequent route calculations that have a value for the characteristic that is less than the boundary value.

8. The invention of claim 7 wherein the characteristic of each segment is travel time and the criterion is least time traveled.

9. The invention of claim 7 wherein the characteristic of each segment is distance traveled and the criterion is least distance traveled.

10. The invention of claim 7 wherein the boundary value is optimized for the criterion.

11. A method for calculating an optimal route from a first location to a second location along a road network located in a geographic region using a geographic database that represents the road network, wherein the optimal route has a characteristic optimized for a specific criterion, the method comprising the steps of:

with a relatively fast algorithm optimized for the specific criterion, determining a boundary route from the first location to the second location using the geographic database,

determining a boundary value for the characteristic, wherein the boundary value is that value by which the characteristic of the boundary route meets the specific criterion; and

performing an exhaustive search of all possible routes between the first location and the second location that have a value for the characteristic that is less than the boundary value, selecting one of the all possible routes as the optimal route that has an optimal value for the characteristic.

12. The method of claim 11 wherein a node stack is generated to prioritize searched nodes and previously un-searched segments associated with the searched nodes.

13. The method of claim 12 wherein the node stack permits the algorithm to “

back-up”

to a node listed on the node stack.

14. The method of claim 11 wherein the exhaustive search comprises searching only those routes on a specific layer.