Method and system for route calculation in a navigation application

• US 6,298,303 B1
• Filed: 11/16/2000
• Issued: 10/02/2001
• Est. Priority Date: 03/25/1998
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia 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/714,314
• Time in Patent Office: 320 Days
• Field of Search: 701/209, 701/202
• 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. A method of providing real time traffic weighted routes using a navigation system having a route calculation program that uses a map database that includes road segment records that represent portions of roads in a road network in a geographic region, comprising the steps of:

receiving a wireless transmission indicating weightings applicable to roads in said road network;

calculating a solution route between a first location in said geographic region and a second location in said geographic region, wherein said solution route comprises a list of road segment records that was obtained by forming at least one search tree formed of a plurality of gates, wherein each gate represents a physical location on said road network and an accessible direction relative to said physical location;

identifying to which of said road segments said weightings apply;

incrementing each of said gates in said at least one search tree that corresponds to a road segment to which one of said weightings applies;

growing a search tree by expanding gates to form successor gates; and

evaluating which of said successor gates to select for further expansion using said weighted gates.

2. A method for using geographic data that represents road segments in a geographic region to calculate a route between waypoints, wherein a waypoint represents one of an origin of the route, a destination of the route, and an intermediate stop between the origin and the destination of the route, and wherein each road segment is designated as having a rank selected from a plurality of ranks, and wherein said rank of a road segment is indicative of a functional classification thereof, the method comprising the steps of:

starting from one of the waypoints, identifying portions of potential solution routes that connect to said waypoint by identifying road segments that connect to said waypoint directly and by way of other road segments;

determining a first radius from said waypoint,

suppressing consideration of road segments that have a first specified rank and that are located outside of said radius from being included as parts of said portions of potential solution routes;

wherein said first radius is determined based upon the density of road segments around said waypoint.

3. The method of claim 2 wherein said plurality of ranks includes at least three ranks, and wherein said method further comprises the steps of:

determining a second radius from said waypoint, wherein said second radius is greater than said first radius; and

suppressing consideration of road segments that have a second specified rank and that are located outside of said second radius from being included as parts of said portions of potential solution routes, wherein said second specified rank is different than said first specified rank;

wherein said second radius is determined based upon the density of road segments around said waypoint.

4. The method of claim 3 wherein said plurality of ranks includes at least four ranks, and wherein said method further comprises the steps of:

determining a third radius from said waypoint, wherein said third radius is greater than said second radius; and

suppressing consideration of road segments that have a third specified rank and that are located outside of said third radius from being included as parts of said portions of potential solution routes, wherein said third specified rank is different than said first specified rank and said second specified rank;

wherein said third radius is determined based upon the density of road segments around said waypoint.

5. A method for using geographic data that represents road segments in a geographic region to calculate a route between waypoints, wherein a waypoint represents one of an origin of the route, a destination of the-route, and an intermediate stop between the origin and the destination of the route, and wherein each road segment is designated as having a rank selected from a plurality of ranks, and wherein said rank of a road segment is indicative of a functional classification thereof, the method comprising the steps of:

starting from one of the waypoints, identifying portions of potential solution routes that connect to said waypoint by identifying road segments that connect to said waypoint directly and by way of other road segments;

as road segments are identified that connect to said waypoint by way of other segments, relating a number of road segments identified to a distance from a recently identified road to the waypoint to determining a density factor around said waypoint;

using said density factor to determine a first radius from said waypoint,

suppressing consideration of road segments that have a first specified rank and that are located outside of said radius from being included as parts of said portions of potential solution routes.