METHOD AND SYSTEM FOR TIME-DEPENDENT ROUTING

• US 20110251789A1
• Filed: 02/01/2011
• Published: 10/13/2011
• Est. Priority Date: 04/12/2010
• Status: Abandoned Application

• Current Assignee: Karlsruher Institut Fur Technologie
• Original Assignee: Karlsruher Institut Fur Technologie
• Inventors: Sanders, Peter, Geisberger, Robert
• Application Number:
  US13/018,754
• Publication Number:
  US 20110251789A1
• Time in Patent Office: Days
• US Class Current: 701/202
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management

Abstract

A method of determining a time-dependent route parameter for a transportation network, for use in an automated routing system in connection with traffic, transportation, and logistics is provided. While shortest distances from all source nodes in S to all target nodes in T are time-independent, travel times are not. The method models the transportation network and computes travel costs from an arbitrary starting node to a plurality of intermediate way-points, and from intermediate way points to the target node.

Claims

1. A method of determining a time-dependent route parameter for a transportation network, for use in an automated routing system in connection with traffic, transportation, and logistics, said method comprising the steps:

a) modelling the transportation network in the form of a graph (G) in the memory (2) of a computer system (1), said graph comprising a plurality of nodes (s, t, u, v, w), wherein said nodes correspond to starting-locations, target locations, and intermediate way-points in said transportation network, and a plurality of edges (E) interconnecting pairs of said nodes, wherein said edges indicate travel costs for travelling between respective nodes, wherein at least some of said travel costs are time-dependent quantities;

b) for at least one arbitrary starting-node (s) of said plurality of nodes and for a first set of departure times (τ

), computing and storing first travel costs for respective first routes on said graph, said first routes leading from said one starting-node to a first plurality of intermediate way-point nodes (u, v, w) of said plurality of nodes;

c) for at least one arbitrary target node (t) of said plurality of nodes and for a second set of departure times, computing and storing second travel costs for respective second routes on said graph, said second routes leading from a second plurality of intermediate way-point nodes (u, v, w) of said plurality of nodes to said one target node;

d) for a plurality of target nodes and/or starting-nodes, determining a time-dependent travel cost for at least one route on said graph between said starting-node and said target node via at least one intermediate way-point node, which at least one intermediate way-point node is comprised in both of said first and second plurality of intermediate way-point nodes, from said first travel costs and said second travel costs, and

e) for a third set of departure times (τ

), determining said time-dependent route parameter based on said time-dependent travel cost.

2. The method of claim 1, wherein

step b) comprises obtaining said first travel costs in the form of a forward travel cost profile for at least one respective route between said starting-node (s) and each intermediate way-point node (u, v, w) of said first plurality of intermediate way-point nodes, wherein a travel cost profile between two nodes is defined as comprising the time-dependent travel costs between said two nodes at least for said first set of departure times and is defined by means of a travel cost function, TCF or f(τ

), where T denotes the departure time;

step c) comprises obtaining said second travel costs in the form of a backward travel cost profile for at least one respective route between said target node (t) and each intermediate way-point node (u, v, w) of said second plurality of intermediate way-point nodes; and

step d) comprises determining said time-dependent travel cost by combining said forward travel cost profiles and said backward travel cost profiles at said at least one intermediate way-point node.

3. The method of claim 2, further comprising the steps of:

combining said forward travel cost profile and said backward travel cost profile to obtain a combined travel cost profile; and

determining said time-dependent travel cost from said combined travel cost profile.

4. The method of claim 2, wherein, in step d), said time-dependent travel cost is the minimal time-dependent travel cost.

5. The method of claim 2, wherein, in step a), said time-dependent travel costs comprise at least one of travel time, travel expenses, route toll, wear, labour costs, and other travel-related costs.

6. The method of claim 2, wherein, at least in step b) or c), a derivative quantity of the departure time (τ

) is used as input variable, wherein preferably said derivative quantity is the arrival time at said target node (t).

7. The method of claim 6, wherein any one of said first through third sets comprises a subset of all departure times (τ

), wherein said all departure times denotes all departure times within a predefined range, which is preferably infinite, e.g., under the assumption that all travel cost functions are periodical with period T, so that f(τ

+T)=f(τ

)=f(τ

+2T).

8. The method of claim 1, wherein at least some of said time-dependent travel costs are approximate travel costs.

9. The method of claim 1, wherein determining said route parameter comprises determining an actual time-dependent route in said route network.

10. The method of claim 2, wherein steps a) through c) are performed only once for a plurality of determinations of time-dependent route parameters, wherein preferably said first and seconds travel costs, or said forward and backward travel cost profiles, are electronically stored for use in subsequent determinations of time-dependent route parameters.

11. The method of claim 1, wherein at least steps a) through c) are repeated based on a change of travel costs between respective nodes (s, t, u, v, w) of said graph (G), wherein said travel costs are determined experimentally and/or on a regular basis.

12. The method of claim 1, wherein the nodes (s, t, u, v, w) of said graph (G) are arranged by using a hierarchical speedup technique, suitable hierarchical speedup techniques comprising Contraction Hierarchies, Highway Hierarchies, Reach-based Routing, Highway Node Routing, and Transit-node Routing, preferably as described in D. Delling, P. Sanders, D. Schultes, and Dorothea Wagner, “

Engineering Route Planning Algorithms”

, Algorithmics of Large and Complex Networks, Lecture Notes in Computer Science, vol. 5515, Springer 2009, pages 117-139.

13. The method of claim 1, wherein the nodes (s, t, u, v, w) of said graph (G) are arranged in the form of a time-dependent contraction hierarchy, TCH, wherein all nodes are ordered by increasing importance, and wherein individual nodes are contracted by removing them from the graph without changing minimum travel costs, e.g., shortest travel times, between remaining, more important nodes, preferably as defined in G. V. Batz, D. Delling, P. Sanders, C. Vetter, “

Time-dependent Contraction Hierarchies”

, ALENEX 2009, pages 97-104.

14. The method of claim 13, wherein said node ordering and/or construction of the TCH are performed once for a plurality of determinations of time-dependent route parameters, wherein preferably said node ordering and/or said TCH construction are electronically stored for use in subsequent determinations of time-dependent route parameters.

15. A computer-readable storage medium adapted for use in a computer system (1) with a program code for execution by the computer system (1), wherein said computer system with the program code is adapted to

a) model a transportation network in the form of a graph (G) in a memory (2) of the computer system (1), said graph comprising a plurality of nodes (s, t, u, v, w), wherein said nodes correspond to starting-locations, target locations, and intermediate way-points in said transportation network, and a plurality of edges (E) interconnecting pairs of said nodes, wherein said edges indicate travel costs for travelling between respective nodes, wherein at least some of said travel costs are time-dependent quantities;

b) for at least one arbitrary starting-node (s) of said plurality of nodes and for a first set of departure times (τ

), computing and storing first travel costs for respective first routes on said graph, said first routes leading from said one starting-node to a first plurality of intermediate way-point nodes (u, v, w) of said plurality of nodes;

c) for at least one arbitrary target node (t) of said plurality of nodes and for a second set of departure times, computing and storing second travel costs for respective second routes on said graph, said second routes leading from a second plurality of intermediate way-point nodes (u, v, w) of said plurality of nodes to said one target node;

d) for a plurality of target nodes and/or starting-nodes, determining a time-dependent travel cost for at least one route on said graph between said starting-node and said target node via at least one intermediate way-point node, which at least one intermediate way-point node is comprised in both of said first and second plurality of intermediate way-point nodes, from said first travel costs and said second travel costs, and

e) for a third set of departure times (τ

), determining said time-dependent route parameter based on said time-dependent travel cost.

16. The computer-readable storage medium of claim 15, further comprising a set of instructions that is implementable by the computer system for a user interface (8) for performing a query for a time-dependent route parameter, for use in an automated routing system in connection with traffic, transportation, and logistics, wherein said interface requires an input of at least one starting-location (s), at least one target location (t), and a departure time (τ

) from said starting-location or an arrival time at said target location.

17. A route planning system, comprising at least one computer system (1), wherein said computer system implements the computer-readable storage medium of claim 15.

18. A route planning system, comprising at least one computer system (1), wherein said computer system implements the computer-readable storage medium of claim 16.

19. The route planning system of claim 17, wherein said method and said interface are implemented on different computers in said computer system, said computer is linked via a data network (6).