Route generation in a vehicle navigation system

• US 5,938,720 A
• Filed: 01/15/1997
• Issued: 08/17/1999
• Est. Priority Date: 02/09/1995
• Status: Expired due to Term

• Current Assignee: TomTom Incorporated (TomTom NV)
• Original Assignee: Visteon Technologies LLC (Visteon Corporation)
• Inventors: Tamai, Haruhisa
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): DONNELLY, ARTHUR D
• Application Number:
  US08/784,204
• Time in Patent Office: 944 Days
• Field of Search: 701/200, 701/201, 701/202, 701/208, 701/209, 701/210, 701/211, 340/988, 340/990, 34/995, 73/178 R
• 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

Methods and apparatus for generation of a route from a source location to a final destination are described. According to one embodiment, a two-ended search is performed based on the principles of the A* algorithm. That is, two routes are simultaneously generated, one from the source to the destination, and one from the destination to the source. According to another embodiment, a route generation algorithm determines when to stop searching for route candidates. The algorithm searches a map database for a first number of iterations thereby generating a first route candidate. After generation of the first route candidate, searching of the map database is terminated after a second number of additional iterations. A best route candidate is then selected as the route.

Claims

1. A method for determining a route from a first location to a second location using a vehicle navigation system, the method comprising the steps of:

searching a map database for a first number of iterations thereby generating a first route candidate connecting the first and second locations, the first route candidate comprising a plurality of road segments;

after generation of the first route candidate, terminating searching the map database after a second number of additional iterations, the second number of additional iterations resulting in at least a portion of a second route candidate beginning at the first location and comprising a plurality of road segments; and

automatically selecting a best route candidate as the route without user intervention.

2. The method of claim 1 wherein the second number is determined with reference to a distance between the first and second locations.

3. The method of claim 1 wherein the second number is determined with reference to the first number.

4. The method of claim 1 further comprising the step of, where the second number of additional iterations has not yet occurred, terminating the searching step after a second number of route candidates has been generated.

5. The method of claim 1 wherein the second number is reduced by a bonus amount for each additional route candidate generated after the generation of the first route candidate.

6. The method of claim 1 wherein the searching step comprises searching the map database beginning from the first location.

7. The method of claim 6 wherein the searching step also comprises searching the map database beginning from the second location.

8. A method for determining a route from a first location to a second location using a vehicle navigation system, the method comprising the steps of:

searching a map database for a plurality of iterations thereby generating at least one route candidate, the searching initially including road segments of a plurality of ranks;

during the searching step, identifying a first road segment having a first rank associated therewith;

in response to the identifying step, excluding from subsequent iterations of the searching step all other road segments having ranks associated therewith below the first rank; and

selecting a best route candidate as the route.

9. The method of claim 8 further comprising the step of executing a first number of iterations of the searching step after the first road segment is identified and before performing the excluding step.

10. The method of claim 9 wherein the first number is determined with reference to a distance between the first and second locations.

11. A method for determining a route using a vehicle navigation system, the route comprising a plurality of contiguous road segments, the method comprising the steps of:

determining whether a search region encompasses a portion of the map database characterized by a grid pattern, the grid pattern relating to a density and an orientation of road segments in the portion of the map database;

where the search region does not encompass the portion of the map database characterized by the grid pattern, expanding the search region to search the map database for the contiguous road segments, the search region being characterized by a shape and including a first plurality of route candidates; and

where the search region encompasses the portion of the map database characterized by the grid pattern, altering the shape of the search region by adjusting cost values in the map database such that the search region includes additional route candidates with fewer turns as compared to the first plurality of route candidates.

12. A method for connecting a first route generated by a vehicle navigation system to a second route generated by the vehicle navigation system, the method comprising the steps of:

generating the first and second routes, the first and second routes being connected at a connection point forming a combined route;

generating a third route from a source point on the first route near the connection point to a destination point on the second route near the connection point; and

replacing a portion of the combined route between the source and destination points with the third route.

13. A method for connecting a first route generated by a vehicle navigation system to a second route generated by the vehicle navigation system, the method comprising the steps of:

generating the first and second routes;

connecting the first and second routes at a connection point forming a combined route;

determining whether the first and second routes intersect at an intersection point; and

where the first and second routes intersect, removing unnecessary portions of the combined route coupled to the intersection point.

14. A method for generating a partial route in a vehicle navigation system prior to generation of a complete route between an origin and a destination, the method comprising the steps of:

searching a map database to generate a plurality of partial route candidates, each of the partial route candidates having a travel cost and a heuristic cost associated therewith, each of the partial route candidates beginning at the origin and not reaching the destination;

terminating the searching step where the travel cost associated with at least one of the partial route candidates reaches a first threshold value; and

selecting as the partial route one of the partial route candidates having the lowest heuristic cost associated therewith.

15. The method of claim 14 wherein the first threshold value is determined with reference to the distance between the first and second locations.

16. The method of claim 14 wherein the terminating step comprises terminating the searching step where the travel costs associated with all of the partial route candidates reach the first threshold value.

17. The method of claim 14 wherein the first threshold value is set such that a limited access road entrance is included in at least one of the partial route candidates.

18. The method of claim 17 wherein total costs associated with limited access roads are reduced to favor use of the limited access roads in route generation, the total cost comprising a sum of travel and heuristic costs associated with the limited access roads.

19. The method of claim 17 wherein a second threshold value is determined with reference to the distance between the first and second locations, and the method further comprises the step of, where the second threshold value is less than the first threshold value, truncating the at least one of the partial route candidates such that the travel cost associated therewith does not exceed the second threshold value.

20. The method of claim 14 wherein the vehicle navigation system operates in a mode in which selected travel costs are adjusted to generate adjusted travel costs for route generation purposes, the method further comprising the step of, while the vehicle navigation system is operating in the mode, keeping track of the selected travel costs for partial route termination purposes.

21. The method of claim 20 wherein the mode comprises a freeway mode in which the vehicle navigation system decreases travel costs associated with freeways to favor use of freeways for route generation.

22. The method of claim 20 wherein the mode comprises a surface street mode in which the vehicle navigation system increases travel costs associated with freeways to favor use of surface streets for route generation.

23. A method for terminating partial route generation in a vehicle navigation system, the partial route comprising a plurality of contiguous road segments stored in a map database, the method comprising the steps of:

searching the map database for the contiguous road segments;

terminating partial route generation upon selecting as part of the partial route a first road segment having access to a limited access road, the limited access road having two directions associated therewith;

identifying a second road segment in the partial route from which access to both directions of the limited access road is possible; and

removing any of the contiguous road segments in the partial route beyond the second road segment.

24. A method for terminating partial route generation in a vehicle navigation system, the partial route comprising a plurality of contiguous road segments stored in a map database, the method comprising the steps of:

expanding a search region to search the map database for the contiguous road segments, the contiguous road segments including road segments of a plurality of ranks;

upon selecting as part of the partial route a first road segment comprising a portion of a first limited access road, terminating expansion of the search region along the first limited access road;

continuing expansion of the search region in at least one other direction until a second limited access road is encountered; and

terminating expansion of the search region upon encountering the second limited access road.

25. A method for providing route guidance using a vehicle navigation system, comprising the steps of:

generating a route from a first location to a second location;

generating a first plurality of maneuver instructions for a first plurality of maneuvers corresponding to a first portion of the route;

communicating the first plurality of maneuver instructions via a user interface; and

generating a second plurality of maneuver instructions for a second plurality of maneuvers corresponding to a remainder of the route during communication of the first plurality of maneuver instructions.

26. The method of claim 25 wherein the route comprises a first partial route from the first location to an intermediate location and a second partial route from the intermediate location to the second location, the first partial route comprising the first portion of the route, and wherein generation of the first plurality of maneuver instructions occurs before generation of the second partial route begins.

27. A method for determining a route from a first location to a second location using a vehicle navigation system, the method comprising the steps of:

searching a map database thereby generating at least one route candidate, the map database comprising a first plurality of road segments;

during the searching step, dynamically adjusting a cost associated with each of a second plurality of road segments to favor inclusion of a particular link class of road segment in the route, the second plurality of road segments comprising a subset of the first plurality of road segments; and

selecting a best route candidate as the route.

28. The method of claim 27 wherein the cost associated with each of the second plurality of road segments comprises a heuristic cost which relates to the distance between the associated one of the second plurality of road segments and the second location, and a travel cost which relates to the time required to traverse the associated one of the second plurality of road segments.

29. The method of claim 28 wherein the step of dynamically adjusting the cost comprises adjusting the heuristic costs associated with each of the second plurality of road segments.

30. The method of claim 28 wherein the step of dynamically adjusting the cost comprises reducing the cost associated with each of the second plurality of road segments by a discount value, the discount value for each of the second plurality of road segments being determined with reference to the travel cost associated therewith.