Incremental route calculation

• US 5,712,788 A
• Filed: 02/09/1995
• Issued: 01/27/1998
• Est. Priority Date: 02/09/1995
• Status: Expired due to Term

• Current Assignee: TomTom International BV (TomTom NV)
• Original Assignee: Zexel Corporation
• Inventors: Desai, Simon Peter, Liaw, Jeff Jyh-Min, Tamai, Haruhisa
• Primary Examiner(s): Chin, Gary
• Application Number:
  US08/385,611
• Time in Patent Office: 1,083 Days
• Field of Search: 364/443, 364/444.2, 364/449.3, 364/449.5, 73/178 R, 340/988, 340/990, 340/995
• 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

Method and apparatus for determining a route from a source location to a final destination using a vehicle navigation system having a map database. At least one intermediate destination is determined from the map database, each intermediate destination being at the other end of an intermediate route from the source location. A cost value is calculated for each intermediate destination. A best intermediate destination is selected from the at least one intermediate destination, the cost value corresponding to the best intermediate destination being lower than the cost values corresponding to any other intermediate destinations. The intermediate route corresponding to the best intermediate destination is then communicated to the user of the vehicle navigation system while a remainder route to the final destination is determined.

Claims

1. A method for determining a route from a source location to a final destination using a vehicle navigation system having a map database, wherein the map database comprises a plurality of roads stored therein, each road having a hierarchy level associated therewith, the source location corresponding to a source road having a first hierarchy level, the method comprising the steps of:

determining at least one intermediate destination candidate from the map database, each intermediate destination candidate being at one end of an intermediate route from the source location, wherein the step of determining at least one intermediate destination candidate comprises the steps of;

exploring possible routes from a first road segment connected to the source location until a connecting road is encountered having a second hierarchy level, the connecting road having an access point associated therewith and the second hierarchy level being greater than the first hierarchy level;

designating the access point to the connecting road as the at least one intermediate destination candidate; and

repeating the exploring and designating steps for each road segment connected to the source location;

calculating a cost value for each intermediate destination candidate;

selecting an intermediate destination, the cost value corresponding to the intermediate destination being lower than the cost values corresponding to any other intermediate destination candidates;

communicating the intermediate route corresponding to the intermediate destination to a user of the vehicle navigation system; and

determining a remainder route to the final destination.

2. The method of claim 1 wherein the steps of selecting an intermediate destination and communicating the intermediate route occur only when the step of determining a remainder route requires more than a timeout period.

3. The method of claim 1 further comprising the steps of:

(A) determining at least one next intermediate destination candidate from the map database, each next intermediate destination candidate being at one end of a next intermediate route from a previously determined intermediate destination;

(B) calculating a cost value for each next intermediate destination candidate;

(C) selecting a next intermediate destination, the cost value corresponding to the next intermediate destination being lower than the cost values corresponding to any other next intermediate destination candidates;

(D) communicating the next intermediate route corresponding to the next intermediate destination to a user of the vehicle navigation system;

(E) repeating steps (A)-(D) until the remainder route has been determined.

4. The method of claim 3 wherein the steps of selecting a next intermediate destination and communicating the next intermediate route occur only when the step of determining a remainder route requires more than a timeout period.

5. The method of claim 1 wherein the step of communicating the intermediate route comprises displaying a series of vehicle maneuvers to the user, each maneuver corresponding to a portion of the intermediate route corresponding to the intermediate destination.

6. A method for determining a route from a source location to a final destination using a vehicle navigation system having a map database, the method comprising the steps of:

determining at least one intermediate destination candidate from the map database, each intermediate destination candidate being at one end of an intermediate route from the source location, each intermediate route comprising at least one node and at least one road segment in the map database connecting the source location and the intermediate destination candidate corresponding to the intermediate route, each node having a node cost associated therewith, and each road segment having a segment cost associated therewith;

calculating a cost value for each intermediate destination candidate by;

(A) combining the segment and node costs for the road segments and nodes in a first intermediate route, thereby generating a route cost;

(B) determining a heuristic cost for a first intermediate destination candidate associated with the first intermediate route, the heuristic cost corresponding to a first distance between the first intermediate destination candidate and the final destination;

(C) combining the route cost for the first intermediate route with the heuristic cost for the first intermediate destination candidate, thereby generating a first cost value for the first intermediate destination candidate; and

(D) repeating steps (A)-(C) for any remaining intermediate destination candidates;

selecting an intermediate destination, the cost value corresponding to the intermediate destination being lower than the cost values corresponding to any other intermediate destination candidates;

communicating the intermediate route corresponding to the intermediate destination to a user of the vehicle navigation system; and

determining a remainder route to the final destination.

7. The method of claim 6 wherein the segment cost associated with each road segment corresponds to an estimate of a time interval required for traversing the road segment.

8. The method of claim 6 wherein the node cost associated with each node corresponds to an estimate of a time interval required for traversing the node.

9. The method of claim 6 wherein the first distance corresponds to a substantially straight-line distance between the first intermediate destination candidate and the final destination.

10. The method of claim 6 wherein the steps of selecting an intermediate destination and communicating the intermediate route occur only when the step of determining a remainder route requires more than a timeout period.

11. The method of claim 6 further comprising the steps of:

(A) determining at least one next intermediate destination candidate from the map database, each next intermediate destination candidate being at one end of a next intermediate route from a previously determined intermediate destination;

(B) calculating a cost value for each next intermediate destination candidate;

(C) selecting a next intermediate destination, the cost value corresponding to the next intermediate destination being lower than the cost values corresponding to any other next intermediate destination candidates;

(D) communicating the next intermediate route corresponding to the next intermediate destination to a user of the vehicle navigation system;

(E) repeating steps (A)-(D) until the remainder route has been determined.

12. The method of claim 11 wherein the steps of selecting a next intermediate destination and communicating the next intermediate route occur only when the step of determining a remainder route requires more than a timeout period.

13. The method of claim 6 wherein the step of communicating the intermediate route comprises displaying a series of vehicle maneuvers to the user, each maneuver corresponding to a portion of the intermediate route corresponding to the intermediate destination.

14. A method for determining a route from a source location to a final destination using a vehicle navigation system having a map database, the map database comprising a plurality of roads stored therein, each road having a hierarchy level associated therewith, the source location corresponding to a source road having a first hierarchy level, the method comprising the steps of:

selecting an intermediate destination from the map database, the intermediate destination being at one end of a corresponding intermediate route from the source location, the step of selecting an intermediate destination comprising the steps of;

exploring possible routes from a road segment connected to the source location until a connecting road is encountered having a second hierarchy level, the connecting road having an access point associated therewith and the second hierarchy level being greater than the first hierarchy level; and

designating the access point to the connecting road as the intermediate destination;

communicating the intermediate route corresponding to the intermediate destination to a user of the vehicle navigation system; and

determining a remainder route to the final destination.