Method and system for route calculation in a navigation application

• US 6,487,497 B2
• Filed: 08/01/2001
• Issued: 11/26/2002
• Est. Priority Date: 03/25/1998
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: McDonough, William, Voloshin, Oleg, Wang, Yaoguang, Khavakh, Asta
• Primary Examiner(s): Issing, Gregory C.
• Application Number:
  US09/920,493
• Publication Number:
  US 20010047241A1
• Time in Patent Office: 482 Days
• Field of Search: 701/208, 701/209, 340/995
• US Class Current: 701/209
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968

Abstract

A program and method for route calculation for use with a navigation system and used with a map database that represents a road network in a geographic region. A route calculation program is adapted to find at least one solution route between a first location on a road network and a second location on the road network. The route calculation program includes a first search tree associated with the first location and a second search tree associated with the second location. Each search tree is adapted to hold gates. Each of the gates represents a physical position on the road network and a direction from the position to another location along a path on the road network. The route calculation program also includes at least one priority queue associated with one of the search trees. The priority queue assigns a priority to one of the gates in the associated search tree based upon an evaluation using a search algorithm. The gate identified as having a higher priority than any other gate in its respective search tree is expanded to determine one or more successor gates thereof. Each of these successor gates so formed is compared to the gates in the other search tree. The process of growing at least one of the search trees by expanding the gate in the search tree that has a higher priority than any other gate in the search tree is continued until a gate in one search tree corresponds to at least one gate in the other search tree.

Claims

1. In a route calculation program, a computer readable locus data structure means for use with a map database, wherein the map database includes a plurality of data records representing road segments in a geographic region, wherein said computer readable locus data structure means identifies a location along one of said road segments, said computer readable locus data structure means comprising:

a first portion that identifies one of said road segments along which the location can be accessed;

a second portion that identifies a subsegment of the road segnent identified in said first portion, wherein said subsegment corresponds to a position between endpoints of the road segment identified in the first portion via which the location can be accessed in a desired direction; and

a third portion that identifies a side of the road segment identified in said first portion, wherein said side corresponds to a side of the road segment identified in said first portion via which the location can be accessed at the subsegment represented by the second portion.

2. In a route calculation program, a computer readable waypoint data structure means for use with a map database, wherein the map database includes a plurality of data records representing segments of roads in a geographic region, said computer readable waypoint data structure means adapted to identify a waypoint wherein said waypoint represents a location along a route to be calculated by the route calculation program and through which said route is constrained to pass, wherein said waypoint represents one of an origin, a destination, and an intermediate stop along said route, and further wherein said computer readable waypoint data structure means is adapted to provide for defining access from or to said waypoint, wherein said waypoint data structure means comprises:

at least one locus data structure means as set forth in claim 1.

3. The invention of claim 1 wherein the first portion of the computer readable locus data structure means identifies the one of said road segments by a segment identifier.

4. The invention of claim 1 wherein the first portion of the computer readable locus data structure means identifies the one of said road segments by an identifier associated with the data record that represents the one of said road segments.

5. The invention of claim 1 wherein the second portion of the computer readable locus data structure means identifies the subsegment as one of an equal number of subsegments into which each of said road segments in the geographic region is divided.

6. The invention of claim 1 wherein said computer readable locus data structure means is stored on a computer readable medium.

7. The invention of claim 1 wherein the computer readable locus data structure means is derived from a street address.

8. A method of operating a navigation system to identify a location in a geographic region, wherein said navigation system uses a map database that includes a plurality of data records that represent road segments in the geographic region, the method comprising the steps of:

identitying one road segment along which said location is accessible in a desired direction of travel;

identifying a subsegment corresponding to a position along said one road segment at which said location is accessible in said desired direction of travel;

identifying a side of said one road segment at which said location is accessible in said desired direction of travel; and

identifying one endpoint of the one road segment by which the location is accessible in said desired direction of travel.

9. The method of claim 8 wherein the one road segment is identified by a segment identifier.

10. The method of claim 8 wherein the one road segment is identified by an identifier associated with a data record that represents the one road segent.

11. The method of claim 8 wherein the subsegment is identified as one of a number of subsegments into which said road segment is divided.

12. The method of claim 8 wherein the location is derived from a street address.

13. The method of claim 8 wherein the location corresponds to a destination of a route.

14. In a route calculation program, a computer readable locus data structure means for use with a map database, wherein the map database includes a plurality of data records representing road segments in a geographic region, wherein said computer readable locus data structure means identifies a location along one of said road segments, said computer readable locus data structure means comprising:

a first portion that identifies one of said road segments along which the location can be accessed;

a second portion that identifies a spot along the road segment identified in said first portion, wherein said spot corresponds to a position between endpoints of the road segment identified in the first portion via which the location can be accessed in a desired direction; and

a third portion that identifies a side of the road segment identified in said first portion, wherein said side corresponds to a side of the road segment identified in said first portion via which the location can be accessed at the spot represented by the second portion.

15. The invention of claim 14 wherein the first portion of the computer readable locus data structure means identifies the one of said road segments by a segment identifier.

16. The invention of claim 14 wherein the first portion of the computer readable locus data structure means identifies the one of said road segments by an identifier associated with the data record that represents the one of said road segments.

17. The invention of claim 14 wherein the second portion of the computer readable locus data structure means identifies the spot as one of an equal number of subsegments into which each of said road segments in the geographic region is divided.

18. The invention of claim 17 wherein said equal number is 256.

19. The invention of claim 14 wherein said computer readable locus data structure means is stored on a computer readable medium.

20. The invention of claim 14 wherein the computer readable locus data structure means is derived from an address.