Route planner for transportation systems

Patent metadata

Field	Value
Publication number	US-9726502-B2
Application number	US-201514840064-A
Country	US
Kind code	B2
Filing date	Aug 31, 2015
Priority date	Aug 31, 2015
Publication date	Aug 8, 2017
Grant date	Aug 8, 2017

Abstract

A computer-implemented technology for planning routes is described herein. In accordance with one aspect, travel data of commuters of a transportation network are provided. Continuous distributions of travel time and waiting time are generated from the travel data. The continuous distributions of travel time and waiting time are associated to a transportation graph of the transportation network. The transportation graph includes nodes corresponding to stops of the transportation network and edges interconnecting the nodes. Travel time and waiting time are associated as costs of the edges in the transportation graph. In response to receiving input parameters, expected costs of candidate routes in the transportation graph are determined in accordance with a modified multi criteria shortest path technique. The modified multi criteria shortest path technique invokes a subroutine to retrieve accurate costs of routes based at least on the costs of the edges in the transportation graph. Route recommendations are provided based on the expected costs of the candidate routes.

First claim

The invention claimed is:

1. A route planning system, comprising:
a non-transitory memory device for storing computer readable program code; and
a processor device in communication with the memory device, the processor device being operative with the computer readable program code to perform steps including
providing historical travel data of commuters of a transportation network;
for a number of time intervals in a day, generating travel time and waiting time distributions from the travel data;
generating continuous distributions of travel time and waiting time by linearizing the travel time and waiting time distributions for the time intervals;
associating the travel time and waiting time continuous distributions to a transportation graph of the transportation network, the transportation graph comprises nodes corresponding to stops of the transportation network and edges interconnecting the nodes, wherein estimated travel time and waiting time derived from the continuous distributions are associated as costs of the edges in the transportation graph;
in response to receiving input parameters, determining expected costs of candidate routes in the transportation graph in accordance with a modified multi criteria shortest path technique, wherein the modified multi criteria shortest path technique invokes a subroutine to retrieve accurate costs of routes based at least on the costs of the edges in the transportation graph; and
outputting route recommendation based on the expected costs of the candidate routes.

2. The system of claim 1 wherein the processor device is operative with the computer readable program code to generate the transportation graph based on static transport data.

3. The system of claim 1 wherein:
the nodes of the transportation graph comprises two types of nodes, the two types of nodes includes a transfer node and a route node, wherein a stop S of the transportation network corresponds to a single transfer node t S and multiple route nodes r S l 1 , . . . , r S l k , where l k denotes a transport service line and k denotes the total number of transport service lines serving the stop; and
the edges of the transportation graph comprises three types of edges, wherein a first type of edge is from a transfer node to a route node which corresponds to a boarding process,
a second type of edge is from a route node to a transfer node which corresponds to an alighting process, and
a third type of edge is from a route node to another route node which corresponds to a traveling process.

4. The system of claim 3 wherein:
the cost of the first type of edge corresponding to the boarding process is associated with the estimated waiting time;
the cost of the second type of edge corresponding to the alighting process is 0; and
the cost of the third type of edge corresponding to the traveling process is associated with the estimated travel time.

5. The system of claim 4 wherein the processor device is operative with the computer readable program code to:
receive input parameters from a user query on a user device, wherein the input parameters include a source node n s , a destination node lid and a departure time t;
the modified multi criteria shortest path technique determines the candidate routes by identifying one or more nodes and costs to reach the one or more nodes from the source node n s , and selecting a node n u with the lowest cost.

6. The system of claim 5 wherein the associated costs of the edges in the transportation graph comprises means and variance of travel time.

7. The system of claim 5 wherein selecting the node n u further comprises analysing the node n u by
invoking the subroutine to retrieve the accurate costs of each outgoing edges from the node n u to neighbouring nodes n u ; and
performing a dominance analysis on the returned accurate costs for each of the neighbouring nodes n v .

8. The system of claim 7 wherein the subroutine retrieves the accurate costs of the outgoing edges by:
determining whether one of the current node n u being analyzed and a neighbouring node n v is a transfer node;
in response to determining the node n u is a transfer node and a neighbouring node n v is a route node, identifying a boarding process, and calculating an accurate cost c v based at least on a waiting time associated to the outgoing edge from the node n u to the neighbouring node n v .

9. The system of claim 7 wherein the subroutine retrieves the accurate costs of the outgoing edges by:
determining whether one of the current node n u being analyzed and a neighbouring node n v is a transfer node;
in response to determining that the current node n u being analyzed and a neighbouring node n v are not transfer nodes; iteratively tracing back to find a last non-transfer node; and
calculating an accurate cost c v based at least on a travel time associated to the outgoing edge from the last non-transfer node to the neighbouring node n v .

10. A computer-implemented method for planning routes of a transportation network comprising:
providing travel data of commuters of a transportation network;
generating continuous distributions of travel time and waiting time from the travel data;
associating the continuous distributions of travel time and waiting time to a transportation graph of the transportation network, the transportation graph comprises nodes corresponding to stops of the transportation network and edges interconnecting the nodes, wherein travel time and waiting time are associated as costs of the edges in the transportation graph;
in response to receiving input parameters, determining expected costs of candidate routes in the transportation graph in accordance with a modified multi criteria shortest path technique, wherein the modified multi criteria shortest path technique invokes a subroutine to retrieve accurate costs of routes based at least on the costs of the edges in the transportation graph; and
providing route recommendation based on the expected costs of the candidate routes.

11. The method of claim 10 wherein the travel data comprises historical travel data of commuters of a public transportation system.

12. The method of claim 10 comprising:
receiving input parameters from a user query on a user device, wherein the input parameters include a source node n s , a destination node lid and a departure time t;
the modified multi criteria shortest path technique determines the candidate routes by identifying one or more nodes and costs to reach the one or more nodes from the source node n s , and selecting a node n u with the lowest cost.

13. The method of claim 12 wherein
the associated costs of the edges in the transportation graph are multi-dimensional, wherein the multi-dimensional costs comprises means and variance of travel time;
the selected node n u with the lowest cost comprises one of lowest means and variance of travel time.

14. The method of claim 13 wherein analysing the node n u comprises:
invoking the subroutine to retrieve the accurate costs of each outgoing edges from the node n u to neighbouring nodes n v ; and
performing a dominance analysis on the returned accurate costs for each of the neighbouring nodes n v .

15. The method of claim 13 wherein the transportation graph comprises:
transfer nodes corresponding to stops of the transportation network, wherein a transfer node corresponds to a single stop of the transportation network;
route nodes corresponding to transport service lines of the transportation network, wherein a route node of a transport service line is associated wit

Assignees

• Sap Se

Inventors

• Ni Peng
• VO Hoang Tam
• Dahlmeier Daniel Hermann Richard
• Cai Wentong

Classifications

• G01C21/3446

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G08G1/0125

  Traffic data processing · CPC title

• G01C21/20 Primary

  Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) · CPC title

• G01C21/3453 Primary

  Special cost functions, i.e. other than distance or default speed limit of road segments · CPC title

• G06Q10/04

  Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202) · CPC title