Incremental route calculation
First Claim
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.
7 Assignments
0 Petitions
Accused Products
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.
191 Citations
14 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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. - View Dependent Claims (7, 8, 9, 10, 11, 12, 13)
-
-
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.
-
Specification