Diversified route planning for public transportation network

Patent metadata

Field	Value
Publication number	US-9778051-B2
Application number	US-201514840069-A
Country	US
Kind code	B2
Filing date	Aug 31, 2015
Priority date	Aug 31, 2015
Publication date	Oct 3, 2017
Grant date	Oct 3, 2017

Abstract

A route planner for a transportation network is disclosed. The route planner generates k suggested routes based on a user query using a diversified k shortest routes technique. The diversified k shortest routes techniques analyzes a transportation graph and suggests k routes to the user. The diversified k shortest routes can provide a user with options to take the next best route if they miss the optimal one. These options also include other preferences, such as less number of transfers, as long as they are reasonable in terms of total travel time. The suggested routes take into account travel calendars, as well as location-to-location queries which require geocoding and reverse geocoding capabilities. Transfers between different types of transportation services such as train and bus are also supported.

First claim

The invention claimed is:

1. A computer-implemented method performed by a computer system for recommending public transportation routes of a transportation network to a user comprising:
providing a transportation graph comprising a plurality of station nodes corresponding to stations of the transportation network, wherein each station node comprises
x unique route nodes corresponding to x number of unique transportation services servicing the station of the station node, wherein each of the x unique route nodes comprises
a first outgoing edge, the first outgoing edge is connected to a next station node of the route of the transportation service,
a first incoming edge, the first incoming edge is connected to a previous station node of the route of the transportation service,
a second outgoing edge, the second outgoing edge is connected to the previous station node of the route of the transportation service,
a second incoming edge, the second incoming edge is connected to the next station node of the route of the transportation service, and wherein
the incoming and outgoing edges are route edges,
the first incoming and outgoing edges correspond to a first direction of the route of the transportation service,
the second incoming and outgoing edges correspond to a second direction of the route of the transportation service, and
the edges include cost information and transport schedules;

receiving input parameters from a user query on a user device, wherein the input parameters include an origination node n s a destination node n d and a departure time t dep ;
generating k number of routes to suggest to the user based on the input parameters using k shortest paths; and
displaying the k number of routes on a display of the user device of the user.

2. The computer-implemented method of claim 1 wherein providing the transportation graph comprises generating the transportation graph based on public transport data.

3. The computer-implemented method of claim 2 wherein generating the transportation graph comprises pre-processing the public transport data to obtain schedule and station information.

4. The computer-implemented method of claim 2 wherein generating the transportation graph comprises pre-processing the public transport data to obtain schedule and station information based on calendar day type.

5. The computer-implemented method of claim 1 wherein each of the station nodes of the transportation graph comprises:
a transfer node:
x incoming edges to the transfer node, each of the x incoming edges is coupled to one of the x route nodes of the station node, the incoming edges are alight edges; and
x outgoing edges from the transfer node, each of the x outgoing edges are coupled to one of the x route nodes of the station node, the outgoing edges are transfer edges.

6. The computer-implemented method of claim 5 further comprises walking edges between two proximately located stations of two different transport service lines, wherein the two stations are located below a threshold distance, wherein the walking edges are transfer edges not located at the same station.

7. The computer-implemented method of claim 6 wherein:
the edges include a two-dimensional cost, the first dimension is a time cost ct and the second dimension is a transfer cost c tr ;
for transfer edges, c t =wait time of connecting transport and c tr =1;
for walking edges, c t =wait time of connecting transport taking into account transfer time and c tr =1; and
for route edges, c t =travel time and c tr =0.

8. The computer-implemented method of claim 7 wherein generating the k number of routes to suggest to the user based on the input parameters comprises diversified k shortest paths.

9. The computer-implemented method of claim 8 wherein the diversified k shortest paths comprise:
finding b number of base routes, wherein finding the b number of base routes comprises
performing an initialization which includes
setting b=b, wherein b<k,
setting i=0, wherein i denotes an initialization counter, and
setting time t i =departure time t dep , and

 finding base route r i , according from n s to n d based on t dep and calendar day type,
b=b−1,
i=i+1, and

 add base route r i , to base route list wherein
if b>0, then repeat steps from finding base route r i , and
if b is not greater then 0, then end finding b number of base routes; and

shifting the b number of the base routes in the base route list to find the k number of routes.

10. The computer-implemented method of claim 9 wherein b and k are defined parameters of the computer-implemented method.

11. The computer-implemented method of claim 7 wherein generating the k number of routes to suggest to the user based on the input parameters comprises relaxed multi-criteria (RMC) k shortest paths.

12. The computer-implemented method of claim 11 wherein the RMC k shortest paths comprise:
performing the initialization which includes
setting priority queue pq to null, pq comprises a stack of node labels, and
setting l s to equal to (n s , c s ), l s is an origination node label comprising the origination node n s and cost c s ,
load I s into pq, wherein a top node label of the stack of pq is referred to I u
which is equal to (n u , c u ); and
performing a cost analysis comprising
pop I u from p q ,
and analyzing n u comprising
obtaining a cost for each outgoing edge c v from n u ,
if the cost of c v is not dominated by c i , then add l v , which is equal to (n v , c v ), to pq, and go to checkpq, wherein I v denotes a neighboring node label, n v denotes a neighboring node of I v connected by the outgoing edge from n u , and
if the cost of c v is dominated by c u , then go to check pq, and at check pq, checking pq to determine if pq is empty,
if pq is not empty return to analyzing n u , and
if pq is empty, then terminate and return the k number of routes as suggested routes.

13. The computer-implemented method of claim 12 wherein determining if c v is dominated by c u comprises α dominance.

14. The computer-implemented method of claim 13 wherein k and α are defined parameters of the computer-implemented method.

15. The computer-implemented method of claim 7 wherein generating the k routes to suggest to the user based on the input parameters comprises:
diversified k shortest paths;
RMC k shortest paths; and
wherein the user selects one of the diversified k shortest paths and the RMC k shortest paths to generate the k number of routes.

16. A route planning system for generating suggested routes of a transportation network comprising:
a route planning server on the server side;
a user device of a user on the client side, the user device is communicatively coupled to the route planning server by a communication network, the user device includes a non-transitory computer readable storage medium containing a client route planning application; and
wherein the transportation server comprises
a processor and a non-transitory computer readable storage medium,
a repository module, wherein the repository module comprises a graph engine unit, the graph engine includes a data structure representing a transportation graph, the transportation graph comprising a plurality of station nodes corresponding to stations of the transportation network, wherein each station node comprises
x unique route nodes corresponding to x number of unique transportation services servicing the station of the station node, wherein each of the x unique route nodes comprises
a first outgoing edge, the first outgoing edge i

Assignees

• Sap Se

Inventors

• VO Hoang Tam
• Ni Peng
• Yan Chengbin

Classifications

• G06Q10/047

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• G01C21/3446

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

• G01C21/3676

  Overview of the route on the road map · CPC title

• G01C21/3453

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

• G01C21/3423 Primary

  Multimodal routing · CPC title