Methods and systems for dynamically adaptive road network hierarchy and routing

• US 9,448,081 B2
• Filed: 04/09/2009
• Issued: 09/20/2016
• Est. Priority Date: 06/24/2008
• Status: Active Grant

• Current Assignee: Tomtom North America Incorporated (TomTom NV)
• Original Assignee: Tomtom North America Incorporated (TomTom NV)
• Inventors: Sandler, Ilya, Kuznetsov, Tsia, Suranyi, Edward
• Primary Examiner(s): Tarcza, Thomas
• Assistant Examiner(s): GOLDMAN, RICHARD A
• Application Number:
  US12/736,783
• Publication Number:
  US 20110113155A1
• Time in Patent Office: 2,721 Days
• US Class Current: 1/1
• 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 system and method for computing routing on a road network are described. One embodiment includes pre-processing routing data for one or more environmental profiles integrated into a hierarchy, dynamically adding links to the hierarchy in response to real-time data on traffic conditions, and cluster-routing to approximate routing travel costs based on realtime traffic data A further embodiment includes a) identifying one or more portions of a road network as being more preferable than normal based on real-time data, b) expressing the one or more portions of the road network as a sequence of locations comprising a uniquely identifiable path, c) using the sequence of locations comprising a uniquely identifiable path to add one or more links to an already constructed hierarchical network of roads, and d) enabling a pathfinding algorithm to adjust to the real-time data.

Claims

1. A method for computing a navigable route on a road network represented by an electronic map, the method comprising:

identifying, by a processor, one or more portions of the road network as being more preferable than normal based on real-time data;

expressing, by the processor, the one or more portions of the road network as a sequence of locations comprising a uniquely identifiable path;

accessing, by the processor, the electronic map, wherein the electronic map comprises a hierarchical network having a plurality of levels and comprising a plurality of nodes and links at each level;

using the sequence of locations comprising the uniquely identifiable path to modify the hierarchical network by adding one or more links between nodes at one or more levels of the hierarchical network, the adding comprising promoting the one or more links within the hierarchical network so that the one or more links are made available for use by a path-finding algorithm for determining routes from origins to destinations when using links from corresponding levels of the hierarchical network;

enabling, by the processor, the path-finding algorithm to determine a route from an origin to a destination using the hierarchal network modified with the added one or more links, such that the route is adjusted according to the real-time data; and

outputting, by the processor, the determined route.

2. The method of claim 1, wherein the real-time data includes traffic conditions.

3. The method of claim 1, wherein a cross-reference table maps road network IDs as used by a traffic data provider into road network IDs as used by the processor.

4. The method of claim 3, wherein the cross-reference table is used to identify, based on the real-time data, nodes and links in the hierarchical network that are to be modified.

5. The method of claim 1, wherein the real-time data comprises data about traffic conditions that is supplied by an external source.

6. The method of claim 1, wherein using the sequence of locations comprising the uniquely identifiable path to modify the hierarchical network by adding the one or more links between the nodes at the one or more levels of the hierarchical network comprises adding links to two or more levels of the hierarchical network.

7. The method of claim 1, wherein the one or more links that are added to the one or more levels of the hierarchical network are supplied to the path-finding algorithm in a same way as other links from the one or more levels of the hierarchical network.

8. The method of claim 1, wherein the real time data includes externally provided detours.

9. The method of claim 1, wherein adding the one or more links between the nodes at the one or more levels of the hierarchical network comprises:

associating the one or more links with corresponding priorities; and

compounding the one or more links based on a type of compounding associated with the one or more levels.

10. The method of claim 1, wherein the electronic map further comprises, integrated into the hierarchical network, preprocessed routing data computed using one or more environmental profiles.

11. The method of claim 10, wherein the preprocessed routing data computed using the one or more environmental profiles is merged and used in the route determination.

12. The method of claim 1, wherein each link has an assigned cost representing a speed of traversal on the link or a time required to traverse to the link.

13. The method of claim 1, wherein the path-finding algorithm determines routes from origins to destinations using links from only a subset of the levels of the hierarchical network.

14. A computer readable storage medium storing instructions for computing routing on a road network according to the method set out in claim 1.

15. A non-transitory computer-readable medium which stores a set of instructions that, when executed by a processor, causes the processor to perform a method for computing a navigable route on a road network represented by an electronic map, the method comprising:

identifying one or more portions of the road network as being more preferable than normal based on real-time data;

expressing the one or more portions of the road network as a sequence of locations comprising a uniquely identifiable path;

accessing the electronic map, wherein the electronic map comprises a hierarchical network having a plurality of levels and comprising a plurality of nodes and links at each level;

using the sequence of locations comprising the uniquely identifiable path to modify the hierarchical network by adding one or more links between nodes at one or more levels of the hierarchical network, the adding comprising promoting the one or more links within the hierarchical network so that the one or more links are made available for use by a path-finding algorithm for determining routes from origins to destinations when using links from corresponding levels of the hierarchical network;

enabling the path-finding algorithm to determine a route from an origin to a destination using the hierarchal network modified with the added one or more links, such that the route is adjusted according to the real-time data; and

outputting, by the processor, the determined route.