METHODS AND SYSTEMS FOR DYNAMICALLY ADAPTIVE ROAD NETWORK HIERARCHY AND ROUTING

• US 20110113155A1
• Filed: 04/09/2009
• Published: 05/12/2011
• 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: Kuznetsov, Tsia, Sandler, Llya, Suranyi, Edward
• Granted Patent: US 9,448,081 B2
• Time in Patent Office: Days
• US Class Current: 709/241
• 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 routing on a road network, comprising:

pre-processing routing data for one or more environmental profiles integrated into a hierarchy of roads in a database;

computing short cuts for the one or more environmental profiles;

merging the short cuts for the one or more environmental profiles into the database;

identifying one or more portions of a 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;

dynamically adding links describing the sequence of locations to the hierarchy of roads in the database; and

performing cluster-routing to approximate routing travel costs based on real-time traffic data.

2. The method of claim 1, wherein performing cluster routing to approximate routing travel costs based on real-time traffic data comprises:

partitioning the road network into a logical cluster tree;

storing travel time for each cluster to a neighboring cluster;

substituting heuristics to estimate cost from a node to the center of the opposite wave front by the approximate cost of travel, in the direction of routing, between a node'"'"'s cluster and the cluster of the center of the opposite wave;

computing a cost for each link, which is propagating from a destination wave front node, from a time interval based on cluster-approximated arrival time at that node, and

when nodes from opposing wave fronts make connections, approximate costs on the target wave are substituted by a newly computed cost of an actual path from an origin.

3. The method of claim 1, wherein the short cuts for the one or more profiles are merged into the database.

4. The method of claim 3, wherein a node has the maximum priority of the value of the node among the one or more profiles merged into the database.

5. The method of claim 1, wherein time intervals with a non-meaningful rate of change are compressed into fewer environmental profiles.

6. The method of claim 5, wherein a cross-reference table maps road network IDs as used by a traffic data provider into road network IDs as used by routing software.

7. The method of claim 6, wherein the cross-reference table is used to identify which nodes and links in the existing road network need to be modified in response to real-time data.

8. The method of claim 7, wherein the modified links, based on real-time data, enable a path finding algorithm to adjust to real-time traffic conditions by integrating externally provided detours.

9. The method of claim 2, wherein the road network is partitioned into a cluster tree with a subdivision criteria.

10. The method of claim 9, wherein the subdivision criteria is a function of road density per square mile, traffic congestion factor, frequency of travel, or a similar criteria.

11. The method of claim 9, wherein travel time from a cluster to one or more neighboring clusters is stored.

12. The method of claim 11, wherein cluster to cluster travel time is at least one of pre-computed and dynamically maintained from real-time data probes.

13. The method of claim 9, wherein heuristics to estimate cost from a node to the center of the opposite wave front are substituted by the approximate cost of travel, in the direction of routing, between the node'"'"'s cluster and the cluster where the center of the opposite wave front belongs.

14. The method of claim 13, wherein when nodes from opposing wave fronts make connections, approximate costs on the target wave are substituted by a newly computed cost of an actual path from an origin.

15. A non-transitory computer readable storage medium storing instructions for, when executed on a computer device, computing routing on a road network according to the method of claim 1.

16. A system, comprising:

a module for pre-processing routing data for one or more environmental profiles integrated into a hierarchy;

a module for dynamically adding links to the hierarchy in response to real-time data on traffic conditions; and

a system for cluster-routing to approximate routing travel costs based on real-time traffic data.

17. A method for computing routing on a road network, comprising:

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 path-finding algorithm to adjust to the real-time data.

18. The method of claim 17, wherein the real-time data includes traffic conditions.

19. The method of claim 17, wherein a cross-reference table maps road network IDs as used by a traffic data provider into road network IDs as used by routing software.

20. The method of claim 19, wherein the cross-reference table is used to identify which nodes and links in the existing road network need to be modified in response to real-time data.

21. The method of claim 17, wherein real-time data on traffic conditions is supplied by an external source.

22. The method of claim 17, wherein a single stretch of a road can result in multiple links being added at different levels of a hierarchy.

23. The method of claim 17, wherein new links are supplied to the path-finding algorithm in the same way as existing links.

24. The method of claim 17, wherein the real time data includes integrating externally provided detours.

25. The method of claim 17, wherein a single detour can result in multiple links being added at different levels of a hierarchy, equipped with a proper priority and compounded as appropriate for each level.

26. The method of claim 17, further comprising:

incrementally compiling one or more profiles into an already existing branch of a hierarchy when large parts of a network have modified traversal times.

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

28. A method for improving computation of travel-time optimized routing on a road network, comprising:

a) partitioning the road network into a logical cluster tree;

b) storing travel time for each cluster to a neighboring cluster;

c) substituting heuristics to estimate cost from a node to the center of the opposite wave front by the approximate cost of travel, in the direction of routing, between a node'"'"'s cluster and the cluster of the center of the opposite wave;

d) computing a cost for each link, which is propagating from a destination wave front node, from a time interval based on cluster-approximated arrival time at that node, and

e) when nodes from opposing wave fronts make connections, approximate costs on the target wave are substituted by a newly computed cost of an actual path from an origin.

29. The method of claim 28, further comprising using the A* algorithm.

30. The method of claim 28, wherein historical, real-time, and predictive traffic information enables a driver to save time by selecting the route that requires the least time and increase travel-time accuracy.

31. The method of claim 28, wherein real-time data on traffic conditions comprises data formatted as RDS TMC, AGORA-C, VICS, or another location referencing method.

32. The method of claim 28, further comprising partitioning the road network into a logical cluster tree with a subdivision criteria.

33. The method of claim 28, wherein the subdivision criteria is a function of road density per square mile, traffic congestion, frequency of travel, or a similar criteria.

34. The method of claim 28, wherein cluster to cluster travel time is at least one of pre-computed from historical or predictive data, and dynamically maintained from real-time data probes.

35. The method of claim 28, wherein run-time probe data is used to calculate how long it takes a vehicle to cross from a cluster to a neighboring cluster or from a node'"'"'s cluster to the target wave cluster.

36. A non-transitory computer readable storage medium storing instructions for, when executed on a computer device, improving computation of time-optimized routing on a road network according to the method set out in claim 28.

37. A method for improving computation of travel-time optimized routing on a road network, comprising:

a) partitioning the road network into a quad tree;

b) storing travel time for each quad to a neighboring quad;

c) substituting heuristics to estimate cost from a node to the center of the opposite wave front by the approximate cost of travel, in the direction of routing, between a node'"'"'s quad and the quad of the center of the opposite wave;

d) computing a cost for each link, which is propagating from a destination wave front node, from a time interval based on quad-approximated arrival time at that node, and

e) when nodes from opposing wave fronts make connections, approximate costs on the target wave are substituted by a newly computed cost of an actual path from an origin.

38. The method of claim 37, further comprising using the A* algorithm.

39. The method of claim 37, wherein real-time data on traffic conditions comprises data formatted as RDS TMC, AGORA-C, VICS, or another location referencing method

40. The method of claim 37, wherein quad to quad travel time is pre-computed from historical or predictive data, and/or dynamically maintained from real-time data probes.

41. The method of claim 37, further comprising partitioning the road network into a logical cluster tree with a subdivision criteria as a function of road density per square mile, traffic congestion, frequency of travel, or a similar criteria.