# Patent

## Title
Diversified route planning for public transportation network

## 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.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This application cross-references to U.S. patent application Ser. No. 14/840,064, titled “ROUTE PLANNER FOR TRANSPORTATION SYSTEMS” that is concurrently filed and assigned to the same assignee as this application, which is herein incorporated by reference for all purposes.
TECHNICAL FIELD
The present disclosure relates to computer systems, and more specifically, to a framework for generating diversified public transport route plans based on user preference.
BACKGROUND
A public transportation network forms an important part of a metropolitan area. Numerous people living in the metropolitan area rely on public transportation for various purposes. For example, regular users rely on public transportation for work or school commute while others rely on it for transportation from one location to another, such as meeting with friends, going to dinner or watching a movie.
Typically, the transportation network includes a number of services, such as different types of transports, for example, trains, buses, or trolleys. Furthermore, numerous services or lines make up the transportation network, particularly in a large or developed metropolitan area. Such an extensive network may offer a user of the network numerous options to reach his/her destination. This makes it complicated for the user to select an appropriate option based on time and the user's preferences. For example, the user may prefer a shorter travel time over less transfers. In some instances, the user may require additional options with different schedules due to inability time constraints.
The present disclosure is directed to a transportation route planner which takes into consideration various criteria and provides diversified k shortest paths.
SUMMARY
A framework for recommending public transportation routes of a transportation network to a user is described herein. In accordance with one aspect, the framework includes a computer-implemented method. The method includes providing a transportation graph comprising nodes corresponding to stations of the transportation network. The nodes are connected by edges. The edges include cost information and transport schedules. Input parameters from a user query on a user device are received. The input parameters include an origination node ns, a destination node nd and a departure time tdep. K routes are generated to suggest to the user based on the input parameters using k shortest paths. The k routes are displayed on a display of the user device of the user.
In another aspect, a route planning system for generating suggested routes of a transportation network is disclosed. The system includes a repository module. The repository module includes a graph engine unit. The graph engine unit includes a data structure representing a transportation graph. The transportation graph includes nodes corresponding to stations of the transportation network. The nodes are connected by edges. The edges include cost information and transport schedule. The system also includes a service module. The service module includes a routing service unit for generating routes to a user based on a user query, which includes ns, nd and tdep. The routing service unit generates the routes using k shortest paths. The system also includes an output module. The output module includes application program interface units which are included by applications on a user device.
In yet another aspect, a non-transitory computer-readable medium having stored thereon a program code is disclosed. The program code is executable by a computer for planning routes for a transportation network. An in-memory time dependent transportation graph comprising nodes corresponding to stations of the transportation network is provided. The nodes are connected by edges. The edges include cost information and transport schedule. Input parameters from a user query on a user device are received. The input parameters include an origination node ns, a destination node nd and a departure time tdep. K routes are generated to suggest to the user based on the input parameters using k shortest paths. The k routes are displayed on a display of the user device of the user.
With these and other advantages and features that will become hereinafter apparent, further information may be obtained by reference to the following detailed description and appended claims, and to the figures attached hereto.



BRIEF DESCRIPTION OF THE DRAWINGS
Some embodiments are illustrated in the accompanying figures, in which like reference numerals designate like parts, and wherein:
FIG. 1a shows a simplified diagram of an exemplary route planning framework;
FIG. 1b shows an embodiment of a user interface (UI) of the route planning system;
FIG. 1c shows an expanded routes suggestion panel of an embodiment of the UI of the route planning system;
FIG. 2 shows a process for generating a time dependent transportation graph;
FIG. 3a shows a simple time dependent graph;
FIGS. 3b-3d show various stages of generating a transportation graph;
FIG. 4 shows a process for generating alternate routes using a relaxed multi-criteria (RMC) technique;
FIG. 5 shows a process for generating alternate routes using diversified k shortest paths; and
FIG. 6 shows a screen short of experimental results using the diversified k shortest paths technique.



DETAILED DESCRIPTION
In the following description, for purposes of explanation, specific numbers, materials and configurations are set forth in order to provide a thorough understanding of the present frameworks and methods and in order to meet statutory written description, enablement, and best-mode requirements. However, it will be apparent to one skilled in the art that the present frameworks and methods may be practiced without the specific exemplary details. In other instances, well-known features are omitted or simplified to clarify the description of the exemplary implementations of the present framework and methods, and to thereby better explain the present framework and methods. Furthermore, for ease of understanding, certain method steps are delineated as separate steps; however, these separately delineated steps should not be construed as necessarily order dependent in their performance.
A framework is provided for generating public transport route plans. In one embodiment, the framework generates diversified public transport route plans which improvise user satisfaction. For example, the route plans are based on user preferences. User preferences may include various preference criteria, such as travel time between starting and ending stations, time at the starting station, time at the ending station, number of transfers between the starting and ending stations, as well as preferential intermediate stations. Other preference criteria may also be useful.
The route planning is based on current schedules of public transport systems. For example the route planning is based on current schedules of different public transport systems within an area of interest. The area of interest can encompass any area of interest. For example, the area of interest may encompass a metropolitan area, such as a city. The area of interest may be larger, such as across cities, states, or even countries. Other types of areas of interests may also be useful. The public transport systems may include different transportation systems of a transportation network. For example, the public transport systems may be buses, trains, and/or subways of different transportation systems.
FIG. 1 shows a simplified block diagram of an exemplary embodiment of a route planning system 100. The route planning system 100, for example, may have a distributed architecture, such as a client-server architecture. In a distributed architecture, a server 105 is accessible by client or user devices 120. Other types of architectures may also be useful.
In the distributed architecture, the server may include one or more computers. A computer includes a memory and a processor. Various types of computers may be employed for the server. For example, the computer may be a mainframe, a workstation as well as other types of processing devices. The memory of a computer may include any memory or database module. The memory may be volatile or non-volatile types of non-transitory computer-readable media such as magnetic media, optical media, random access memory (RAM), read-only memory (ROM), removable media, or any other suitable local or remote memory component.
In case the server includes more than one computer, they are connected through a communication network such as an internet, intranet, local area network (LAN), wide area network (WAN) or a combination thereof. The servers, for example, are part of the same private network. The servers may be located in single or multiple locations. Other configurations of servers may also be useful.
As for client or user devices, they may be any computing devices. A computing device, for example, includes a local memory and a processor. The computing device may further include a display. The display may serve as an input and output component of the user device. In some cases, a keyboard or pad may be included to serve as an input device. The memory may be volatile or non-volatile types of non-transitory computer-readable media such as magnetic media, optical media, RAM, ROM, removable media, or any other suitable memory component. Various types of processing devices may serve as user devices. For example, the user devices may include a personal computer 122 or a smart phone 124. Other types of user devices, such as laptops or tablet personal computers (PCs) may also be useful.
The user devices may communicate with the server through a communication network, such as the internet, intranet, LAN, WAN or a combination thereof. Other type of networks may also be useful. In some cases, the network may be a cloud. A user may connect to the server using a user device. The user device may be referred to as the client side while the server may be referred to as the server side.
As shown, the route planning system includes a route planner 130. The route planner, for example, resides in the server. The route planner, in one embodiment, includes a repository module 140, a service module 150 and an output module 160. In one embodiment, the route planner may be implemented as a Spring Boot Application. Implementing the route planner using other types of applications may also be useful.
The repository module, in one embodiment, includes various repository units for developing a transportation graph from data stored in a database 180. The database, for example, may be a relational database or Structured Query Language (SQL)-based database. In one embodiment, the database includes in-memory, such as SAP HANA database from SAP SE. Other types of databases may also be useful. In one embodiment, the repository module includes a façade unit 142, a data access unit 144 and a graph engine unit 146. Providing the repository module with other units may also be useful. The various repository units may be in-memory to the route planner system. For example, the repository units are internal to the route planner system or application. Other configurations of the repository units may also be useful.
The graph engine unit, in one embodiment, uploads transportation data corresponding to the transportation network. The transportation data contains information of a transportation network of a geographical area of interest. The geographical area of interest, for example, may be of any scale. For example, the area of interest may encompass a metropolitan area, such as a city and its surrounding areas. Other sized areas of interest, such as, cities, counties, states, or countries, may also be useful.
The transportation network, for example, may be include various services. For example, the transportation network may include bus services, train services, other types of transportation services or a combination thereof. The network may include numerous services or lines. The transportation data contains information, such as routing, stations/stops and schedules across different service or lines of the transportation network. For example, the transportation data may contain routing, stations/stops, and schedules of different bus service lines of the transportation network. A station may refer to a station or stop of a service line, such as a train station of a train service line, a bus stop of a bus line, a trolley stop of a trolley line.
The transportation data may take into account multiple travel calendars. For example, the transportation data may have different schedules for different calendar days. Different service schedules may be implemented for different types of days, such as work days, weekends and public holidays. Holidays may be grouped along with weekends. Other configuration of calendars may also be useful.
The graph engine analyzes the transportation data and generates a transportation graph of the transportation network. In one embodiment, the graph engine generates a time-dependent transportation graph of the transportation network. For example, a data structure representing the time-dependent transportation graph is generated. Other types of transportation graphs may also be useful. For example, a time expanded transportation graph may also be useful. The transportation graph contains transportation information, such as routing, stations, and schedules (e.g., arrival and departure times at stations) of a transportation network. Depending on the data contained in the database, the transportation graph may include different types of transportation services and/or different calendar schedules.
The data structure of the transportation graph, in one embodiment, includes an in-memory data structure. For example, the data structure is part of the route planner system or application. This improves performance of the system.
In one embodiment, the transportation graph is derived from publicly available transit data 107. The transit data may be obtained, for example, through the internet. Other techniques for obtaining the transit data may also be useful. The transit data, for example, is provided by the transportation service provider. The system includes a pre-processor 170 which processes the transit data. The transit data may be in, for example, a standard format such as the General Transit Feed Specification (GTFS3) format. Other types of formats may also be useful. In one embodiment, the pre-processor parses the transit data to obtain schedule and station information. The pre-processor may be tailored to the format of the transit data. The pre-processor may be a general pre-processor with different modules for pre-processing different formats of transit data. Other types of pre-processors may also be useful. The pre-processed data is stored in the database for use by the graph engine.
In one embodiment, the repository module includes the data access unit 144. The data access unit maintains the information of stations, such as station names and geolocations. Other station information, such as addresses, may also be useful. Geolocation information may be obtained from map data. The map data may be provided or obtained from a map data service. In one embodiment, the map data service may be OpenStreetMap (OSM). Other map data services may also be useful. The map data service may be accessed through the internet 105. The geolocations of the stations may be obtained by looking up the names or addresses from OSM. To interface with the map data service, the façade unit 142 is provided in the repository. For example, an OSM façade unit is provided for accessing the geocoding function in OSM. For example, the façade unit accesses the OSM to get the nearest geolocation corresponding to a nearest address or station name input by the user as a user query. The user may query the address and/or station name using a user interface (UI) of the system.
The service module includes various service units to generate route plans for a user. In one embodiment, the service module includes a reverse geocoding unit 152, a routing service unit 154 and a caching unit 156. Providing other service units may also be useful.
The routing unit is the core unit of the service module which is used to generate relevant routes based on information from the user provided in a query. The query, for example, may be provided using a UI. The information provided may include origination, destination, departure time at origination and expected arrival time at destination. The origin and destination location may be provided as text input, such as a street name, address, station name or a combination thereof. Other types of information, such as a zip code may also be useful. As for time, it may include date and time. Other types of information may also be provided by the user. The UI may include various types of command for navigating the route planner application. Some information may be obtained automatically. Such information may be based on the location and time of query of the user. For example, the user may indicate that the current time may be the departure time of the query and the origination station may be the nearest station at the current location of the user. This can be obtained from native functions of the device, such as time and global positioning system (GPS) functions.
The reverse geocoding service finds the nearest station given the geolocation of the user. For example, the reverse geocoding service issues spatial queries on the station data maintained in the database based on geocoding of the origination location. As for the caching service unit, it is employed to improve system performance. For example, frequent locations queried by the user are cached to avoid the latency of external geocoding process. Also, frequent queries from the users (including origin, destination, and departure time) are also cached for later use. This avoids re-computing the results.
The output module includes application program interface (API) units which are exposed to the client applications. For example, the API units are invoked by applications on the user device, such as native mobile applications and web applications with responsive user interfaces to provide optimal viewing experiences across a wide range of devices, such as personal computers (PCs), laptops, smart phones, tablet computers as well as other types of devices. The API units, for example, are Representational State Transfer (REST) API units. Other types of API units may also be useful. In one embodiment, the output module includes stations API unit 162 and routes API unit 164. The stations API unit gets information of stations while the routes API unit gets routes based on a query.
FIG. 1b shows a simplified exemplary embodiment of a UI 109. As shown, the UI includes various panes for entering information for and displaying information of the route planning system as well as a command bar 119 for navigation purposes. In one embodiment, the UI includes a trip information panel 129, a routes suggestion panel 139 and a map panel 149. Providing the UI with other panels as well as other functions may also be useful.
The trip information panel provides various input boxes for providing the trip information. For example, a start (origination) location, an end (destination) location, date/time input box are provided. In one embodiment, the date/time box includes a time type selection box for selecting the time type. For example, the type selection box includes a drop down menu for the user to select the time type, such as departure time or arrival time. For example, a user may select the departure time of the route from the origination point to the destination point or the desired arrival time at the destination point. In one embodiment, the default departure time is the current time and the default origination is the current location when such input boxes are left blank. For example, the current time and current location are related to the time and place of the query. A search command button 133 is provided to initiate the search based on the trip information. For convenience, the UI includes a swap button 131 to swap the origination and destination locations.
As for the route suggestion panel, it provides different route suggestions for the user based on the trip information. For example, after the user clicks on the search button, the system returns the suggested routes to the user. The routes, for example, may indicate the stations, transfers, and walking components as well as the amount of time for the trip. The format that a suggested route is displayed may display the different types of components in sequence and the total time of the trip. For example, a trip may include a walking component to station A from the current location, taking service line 1 to station B, transfer to line 2 to station C with a total travel time of x minutes.
The map panel may initially display a map of the area w the user is located. This may include a pin indicating the location of the user. A user may select one of the suggested routes by clicking on it in the routes suggestion panel. This may cause the map to display the route on the map. For example, the route from the origination to the destination is displayed.
FIG. 1c shows the route suggestion panel 139 of the UI in greater detail. As shown, the route suggestion panel shows suggested routes from a search based on the trip information provided by the user. The suggestion panel, for example, may return k number of routes to the user. In one embodiment, k is equal to 5. Providing other numbers for k may also be useful. The route suggestion includes walking, service and connection components as well as the total amount of time of the trip from the origination to destination. The routes may be sorted by arrival time (earliest arrival time first) and then by departure time (latest departure time first).
When a user clicks on a suggested route, the UI displays an expanded view 179 with details of the selected route. For example, the selected route is “Walk—RNV 7—Transfer—RNV 71—RNV 70—Walk (39 min)” This indicates that the user is walking to station O to take line RNV 71 to station B. At station B, the user transfers to line RNV 70 to station C. At station C, the user walks to the destination. The total travel time is 39 minutes. The expanded view displays each segment of the route. For example, the service line, mode of transportation, origination station, destination station, departure time, arrival time, waiting time and total time of each segment may be displayed. A scroll bar 181 may be provided to enable a user to scroll to view all information of the selected route.
As discussed, the graph engine generates or builds the transportation graph from public transit data, such as service schedules and station information. In one embodiment, the graph engine generates or builds a time-dependent transportation graph from public transit data such as service schedules and station information. Other types of transportation graphs, such as time expanded graphs may also be useful. Using the transportation graph, the system generates route plans based on user preference. For example, the service module generates route plans using the transportation graph of the repository module to generate route plans based on user preference.
FIG. 2 shows a simple time dependent graph 200 generated by, for example, the graph engine. As shown, two bus lines, Line A (lA) and Line B (lB), is traveling between two stations, Stop 1 and Stop 2. For example, both bus lines have Stop 1 and Stop 2 as common stations. However, the bus lines may deviate beyond Stops 1 and 2. The various stations of the transportation network may be referred to as nodes. A node may be designated with a unique designation.
Since Stop 1 and Stop 2 have multiple services lA and lB, they are transfer nodes t1 and t2. For example, a passenger may transfer from lA to lB or vice-versa at Stop 1 or Stop 2. Within a service line, Stop 1 and Stop 2 are considered route nodes r1 and r2. For example r1lA and r2lA are route nodes of line lA between Stop 1 and Stop 2 and r1lB and r2lB are route nodes of line lB between Stop 1 and Stop 2. In the case of a transfer node, there are route nodes for each line. For example at Stop 1, it includes a transfer node t1 and route nodes r1lA and r1lB. Likewise, Stop 2 includes transfer node t2 and route nodes r2lA and r2lB.
As an example, a user may query route plans from Stop O (origin) to Stop E (end). In the case that Stop O is served by x number of lines, at least x number of routes which may be provided. There may be more than x number of routes since intermediate stops between Stop O and Stop E may include transfer nodes which allow a passenger to transfer to another line to reach Stop O.
Nodes of the transportation graph are connected by edges. There are at least three different types of edges than can be used to connect nodes. The edges, for example, may include Transfer edges, Alight edges and Route edges. A Transfer edge may be represented by Transfer[ct, ctr], an Alight edge may be represented as Alight[ct, ctr], and a Route edge may be represented as Route[ct, ctr]. As shown, an edge includes two parameters. The parameters are cost parameters. The first parameter ct of the edge is an associated time cost while the second parameter ctr is a transfer cost. The cost parameters are time-dependent. For parameter ctr, if a transfer is made, it is incremented from 0 to 1.
In the case of a Transfer edge, it connects a transfer node and a route node. The cost c, in the case of a transfer edge, is the wait time at the stop or transfer node. The time cost ct may be represented by the wait time w. For example, the Transfer edge for a transfer at Stop 1 from Line A to Line B can be represented as follows:

Transfer[w1lA,1],

where,

w1lA=the wait time for the connecting line at the connecting station (e.g., from lB to lA at Stop 1), and
ctr=1.
Likewise, the transfer edge at Stop 1 from Line A to Line B is Transfer[w1lB, 1] and transfer edges at Stop 2 can be Transfer[w2lA, 1] and Transfer[w2lB, 1].
The wait time is the amount of time that a passenger waits at the connecting station until the connecting transport arrives. The wait time may be determined by subtracting the following equation:

w=tc−ta,

where

ta=the arrival time of the current transport on which the passenger is at the connecting station, and
tc=the departure time of the connecting transport from the connecting station.
The arrival and departure times are maintained by the transportation graph. This information, for example, is derived from the transit data, such as the pre-processed transit data.
An Alight edge is an edge which indicates that a passenger is getting off the transport. In the Alight edge, the cost and transfer number parameters are zero. This is because there are no wait times and no transfers to a connecting train. As such, parameters ct and ctr are zero, as represented by Alight[0,0]. A passenger may alight and leave the station. For example, the passenger has reached his/her destination. In other cases, the passenger may alight and connect to another service. This will be represented by an Alight edge at the station and a Transfer edge connecting to the other service.
In the case of a Route edge, it is an edge which indicates that a passenger is in route between two stations, such as a previous station and a next station. For the Route edge, the cost c is the travel time T between the previous and next stations. For example, c can be T which may be calculated using the following equation:

Tpn=tan−tdp,

where,

Tpn=travel time between the previous station and the next station
tan=arrival time at the next station, and
tdp=departure time at the previous station.
For example, a route edge from Stop 1 to Stop 2 for Line A may be represented by:

Route[T1-2lA,0]

where,

T1-2lA=the time from Stop 1 to Stop 2 on Line A, and
ctr=0.
It is understood that the travel time between stations may not be symmetrical. Furthermore, for Route edges, ctr is zero.
In one embodiment, the system maps route queries to schedule for the transportation systems based on their schedule. For example, the travel schedule is based on the travel calendar. In one embodiment, the travel calendar, for example, is mapping between a real calendar day to a travel day type, such as a weekend, normal workday or public holiday. The mapping, in one embodiment, determines the schedule of a service on that travel day. In a case where multiple systems are involved, such as across different transportation systems or across regions of the geographical area of interest, multiple travel calendars may be used. For example, different transportation systems may have respective travel calendars. The time costs of different edges take into account the different travel calendars.
The travel calendars may be taken into account automatically. For example, the different travel calendars may be implemented based on a date parameter of the query and proximity of an origination station of the requester and destination stations provided by the requester at a run time. In other cases, the user may determine the date parameter of the query as well as other parameters, such as origination and destination stations. Other configurations for applying the travel calendars appropriately may also be useful.
In some embodiments, additional types of edges may be employed. In one embodiment, the system employs additionally walking edges to improve or expand available routes for a query. A walking edge connects stations or nodes of the transportation graph which are proximately located. For example, two proximately located stations may be connected by the walking edge. For example, stations which are located below a threshold distance away may be connected by the walking edge. The distance threshold DTH may be, for example, about 300 meters. Other distance thresholds may also be useful. The distance threshold DTH may be a default threshold of the system or one which is defined by the requester. For a walking edge, a passenger may alight a transport and walk to the nearby station to catch a connecting transport. In one embodiment, walking edges may be applied to stations which can serve multiple lines, but require a passenger to walk to a different platform or location to catch the connecting transport.
In the case of a walking edge, it may be represented as Walking[ct, ctr]A walking edge may be treated similarly as a transfer edge. For example, the cost ct is the waiting cost from the current transport to the connecting transport. However, the route planner takes into account the walking time from the alighting station to the connecting station to ensure that the passenger can catch the connecting transport. Otherwise, the wait time is that for the next connecting train which the passenger can be assured to catch. To ensure that a passenger can catch the connecting train, the walking time may include an additional buffer, such as 20%. Other techniques for ensuring that a passenger catches a connecting train may also be useful.
FIG. 3a illustrates a process 300 performed by the graph engine to build a time dependent graph. The process commences as step 310. For example, the graph engine unit retrieves pre-processed transportation data in the data base. This includes information of service lines, arrival and departure times based on calendar days or day types. For example, the calendar day may be specific days or types of days, such as weekdays, weekends and holidays. Other types of calendar days may also be useful.
At step 320, the process creates a transfer node for each station of the transportation network. For example, all stations of the transportation network are represented as transfer nodes. All stations may be designated as transfer nodes, whether a station is a shared station with different service lines or unique to a service line. For example, if the network has Z number of stations, the process creates transfer nodes t1 to tZ. At step 330, the graph engine unit creates a route node for every stop that a service line travels. For example, if Line A has Y number of stops from the beginning to the end of its route, Line A has route nodes r1lA to rYlA. Assigning route nodes to a line is performed for every line of the transportation network. In one embodiment, the process analyzes transportation data and create route nodes one line at a time until all lines have been analyzed. Each route node is associated with a transfer node. For example, in the case of station 1 which is serviced by a bus Line A, bus Line A has a route node r1lA associated with transfer node t1 of station 1.
The process continues to add edges connecting nodes. In one embodiment, at step 340, the process add edges between each route node and its corresponding transfer node of the transportation network. An edge from a route node to a corresponding transfer node is an alight edge while an edge from a transfer node to a corresponding route node is a transfer edge. Edges, as discussed, includes time cost ct and transfer cost ctr parameters. Adding edges between route nodes and corresponding transfer nodes may be achieved one transfer node at a time, one line at a time until all lines have alighted and transfer edges added. For example, edges between route nodes and corresponding transfer nodes may be added for a line, one station at a time, and then continue with adding edges for the next line until all the lines have edges added to them.
In one embodiment, walking edges are also added at step 340. Walking edges are similar to transfer edges, except that it takes into account walking time and distance between the connecting stations. The walking edges may be added for stations which are proximately located. For example, the walking edges may be added between stations which are located less than a threshold distance apart.
At step 350, route edges are added to adjacent nodes of a service line. In one embodiment, route edges are added to adjacent nodes of a service line in both directions. For example, the route edges are added from station 1 to station 2 of Line A and station 2 to station 1 of Line A. The route edges may be added for each adjacent pair in both directions, one station pair at a time, one service line at a time. The time cost parameter of a transfer edge is the travel time between the adjacent stations. The route edges, in one embodiment, are based on calendar day types. For example, the edge information includes calendar type information. Once all the route edges are added for all the route nodes, the transportation graph is completed. The process terminates at step 360.
FIGS. 3b-3d show various stages of data used to generate transportation graph, as illustrated in FIG. 2. As shown in FIG. 2, two bus lines—bus Lines A and B—service two stops—Stops 1 and 2.
Referring to FIG. 3b, bus schedules and stop information obtained from the public transit data is shown. Data table 312 shows a portion of a schedule for bus Line A. As shown, bus Line A departs Stop 1 at 9:05 am and departs Stop 2 at 9:20 am during weekdays (Mon-Fri). During the weekends (Sat-Sun), bus Line A departs Stop 1 at 9:10 am and departs Stop 2 at 9:25 am. Data table 314 shows a portion of a schedule for bus Line B in a similar manner as bus Line A. Also, a data table 316 is provided which includes stop information of Stops A and B, including their geolocations represented by longitude and latitude. If the geolocations are not available from the public transport data, they can be obtained using a geolocation service unit.
FIG. 3c shows data tables of processed data stored in the database. As shown, edge data table 322 shows edge information of the transportation graph. For example, the public transport data is processed to obtain edge information. As shown, different types of edges, such as route edges, transfer edges and alight edges are shown. The edges include travel time according to calendar type days, such as weekdays and weekends. A stop information data table 324 is also included in the database. The stop information data table is similar to data table 316 in FIG. 3b. 
FIG. 3d shows in-memory data structures of the route planner system. The in-memory data structure includes a data structure 332 of the transportation graph. The data structure, for example, is a list of adjacent edges. The data structure also includes a look up table 334 of stops.
The routing service unit generates route plans for the user using the transportation graph. In one embodiment, the routing service unit generates route plans for the user using the time-dependent transportation graph based on user information and/or preferences. The route plans may be referred to as relevant alternative routes. For example, the routing service unit generates k number of alternate routes for the user to select. The k alternate routes are based on user information and/or preferences.
The routing service unit generates k number of alternate routes based on a shortest path technique. In one embodiment, the routing service unit generates alternate routes based on a diversified k shortest paths. The diversified k shortest paths, for example, employs a Dijkstra technique. The Dijkstra technique finds the shortest path between two nodes of a graph. In one embodiment, the Dijkstra technique finds the shortest path between nodes of a graph based on travel time. The Dijkstra technique is described in, for example, E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik 1, 269-271 (1959), which is herein incorporated by reference.
FIG. 4 shows an embodiment of a process 400 for generating diversified k shortest paths by, for example, the routing service unit. In one embodiment, the process employs the Dijkstra technique. At step 410, the process commences to generate a suggested route. For example, the process is initiated by a query requested by a user.
At step 420, various input parameters are provided to the process. The input parameters include origination node ns, destination node nd, departure time tdep, number of basic candidates b, and total number of expected results k. The parameters may be provided by the user. The parameters may also be provided by a combination of the user and the system. For example, parameters b and k may be provided by the system. Parameters b and k may be system configurable parameters. These parameters may be optionally provided by the user. Parameter b is less than k. For example, k may be 5 and b may be 3. Other values of k and b may also be useful. In addition, tdep and ns may be provided by the system, using current time and geo-positional data of the user at time of query, or optionally by the user.
In one embodiment, an additional parameter inc may be provided. The inc parameter is the amount of time shift for subsequent basic candidate searches. Inc may be equal to 1 second. Other time increments may also be useful. For example, inc may be 30 to 60 seconds or other values. The inc parameter may be a system configurable parameter or one provided by the user. Incrementing ti by inc enables a new base route to be found.
The process may also perform initialization. For example, various counters or registers may be initialized to their initial values. For example, an integer counter i is initialized to 0, a time register ti is initialized to tdep (ti=tdep) and a b counter is initialized to b. The time in ti counter may include date and time. For example, b is equal to 3.
At step 430, the process fines a basic route from the transportation graph using the Dijkstra technique. In one embodiment, a basic route is determined based on the time and date in the ti register. The Dijkstra technique finds the shortest path, according to time and date in the ti register, from ns to nd in the graph. This takes into account schedule based on day and day type. For example, the time of the route is determined by adding the time cost ct of all edges in the route.
At step 440, the shortest path determined by Dijkstra is added to a basic candidates list. The ti register is incremented by inc and b is decremented by 1. The process, at step 450 determines if b is greater than 0. For example, if b is greater than 0, this indicates that there are more basic routes to be determined. As such, the process returns to step 430. Otherwise, all base routes have been found. In such a case, the process continues to step 460.
At step 460, the process continues to analyze the base routes. The base routes may be analyzed by shifting the schedule to the next departure time of a transport. The shifted and non-shifted base routes are analyzed. The system selects k routes for the analysis with the shortest time as k suggested routes. A counter may be used to determine if the k routes have been reached. If the k routes have been found, the process terminates.
After the k routes are determined, the process terminates at step 470. The k routes, for example, are provided as suggested routes to the user. For example, the output module provides the suggested routes to the user.
An example of a pseudo code for the a diversified k shortest path routine is provided below:










Diversified k shortest path routine


















Input:
graph g




origin node ns




destination node nd




departure time tdep




number of basic candidates b




total number of expected results k









Output: k diversified shortest paths










/* Initial query time is departure time
*/








1
time ti = tdep


2
int i = 0


3
while i < b do










/* run Dijkstra based on travel time
*/









4

route ri = Dijkstra(g, ns, nd, ti)


5

BaseRoutes.add(ri)


6

i = i + 1


7

ti = ri(getFirstBoardingTime( ) + 1








8
end


9
results = shift schedule of BaseRoutes to get k routes.









As shown, the routine receives various input parameters, such as graph g, origin node ns, destination node nd, departure time tdep, number of basic candidates b, and total number of expected results k. The routine generates k diversified shortest paths as an output. The value b is less than the value k. For example, b may be 3 while k is 5. Other values for b and k may also be useful. The higher the values, the longer the processing time. The routine performs initialization at lines 1 and 2. For example, the time counter is set to equal tdep and the int counter i is set to 0.
There are two parts to the routine. The first part retrieves b number of base routes ri while the second part obtains k routes from the base routes. In the first part, a Dijkstra subroutine is called and executes b number of times to return b number of base routes ri. For example, as shown in line 3, a loop is performed as long as i is <b. At line 4, the Dijkstra subroutine is called, using g, ns, nd and ti as input parameters to find an optimal route ri from ns and nd in graph g based on shortest time having departure time ti. The route ri returned by Dijkstra subroutine is added to a list BaseRoutes.add(ri) at line 5. Line 6 and line 7 increments i and ti by 1. As shown, the time ti is incremented by 1 second. In some embodiments, it can be replaced by a user or system defined value inc, which can be other than 1 second. If i is ≧b, the loop ends at line 8.
After the b number of base routes are determined, the routine performs the second part to obtain k number of routes. At line 9, the routine shifts the schedule of BaseRoutes to get k routes. A loop may be employed to find the k routes. The loop may terminate once the k routes have been found.
In another embodiment, the k number of alternate routes are based a relaxed multi-criteria shortest path (RMC) technique. In the RMC technique, a relaxed dominance in the cost is employed. A cost may have d dimensions. In the present case, the cost of a route has two dimensions (e.g., d=2). The dimensions include total travel time (ct) and the number of transfers (ctr). The summation cost c of two costs c1 and c2 is equal to c1+c2, which can be defined by equation 1 below:

c[i]=c1[i]+c2[i]∀i ε[1,d]  (Equation 1).

Hence, the total cost of a route can be computed as the summation of the costs of the edges included in that route.

The relaxed dominance is an a dominance, which is (α ε (0, 1]). For example, α has a value between 0 and 1. The smaller that α is, the more relax is the constraint on time. For example, a lower value for α decreases the dominance of time cost parameter ct while conversely, a higher value for α (closer to 1) increases the dominance of the time cost factor ct. In other words, more consideration may be given to parameter ctr. The α dominance for comparison between two costs c1 and c2 can be defined using equation 2 as follows:

c1 α-dominates c2 iff c1[i]≦α*c2[i]∀i ε[1,d] and ∃m ε[1,d], so that c1[m]<α*c2[m]  (Equation 2)

where,

d=the number preference or cost dimensions (in this case, d=2, ct and ctr),
c1=the first multi-dimensional cost,
c2=the second multi-dimensional cost,
i=the index of cost dimension (in this case, i=1 to d which is 1 to 2),
m=the index cost dimension to be relaxed (in this case, either the ct or ctr constraint is relaxed).
The relaxed dominance increases the probability of finding more potential routes. For example, under strict dominance (α=1), route 1 which takes 40 minutes dominates route 2 which takes 50 minutes. However, with α set at 0.7 or less, route 1 no longer dominates route 2. As such, both route 1 and route 2 would be candidate routes whereas under strict dominance, only route 1 would be a candidate route.
FIG. 5 shows another process 500 for generating alternate routes between a source (originating) node ns and a destination node nd. As discussed, the transportation graph includes nodes which are interconnected by edges. A node label li refers to a pair structure (ni, ci) of node ni with associated cost ci. The cost ci is a multi-dimensional cost which, in one embodiment, include time cost ct and transfer cost ctr.
The process, when invoked, initializes at step 510 the various storage components for generating alternate routes. For example, a user submits a query to the system to invoke the system. The components include, in one embodiment, a priority queue pq component, a predecessor map pm component and a node cost list cl component which are initialized. The pq component determines which node label to analyze next. For example, pq is a stack which contains node labels to analyze next. The pm component tracks the predecessor of a current node label under analysis. The cl component contains a list of non-α-dominated cost for nodes analyzed in the transportation graph. The cl component sorts the nodes in ascending travel time. Initialization, for example, clears the various storage components.
At step 520, input information is provided. For example, input information includes ns, nd, α, k and tdep. The information may be provided by the user. The parameters may also be provided by a combination of the user and the system. For example, parameters α and k may be provided by the system. Parameters α and k may be system configurable parameters. These parameters may be optionally provided by the user. Parameter k, for example, may be 5. Other values of k may also be useful. As for α, it may be an appropriate value. For example, α may be about 0.7 to 0.9. Other values of α may also be useful. However, if α is too small, the run time may take too long since there may be too many options to consider. In addition, tdep and ns may be provided by the system, using current time and geo-positional data of the user at time of query, or optionally by the user.
In one embodiment, label ls is loaded in the priority queue pq. For example, at this stage, pq contains only ls, which is a pair structure (ns, cs) of node ns with associated cost cs. The label at top of the stack of pq is referred to as lu. For example, the subscript u refers to the next label or node to analyze.
At step 530, the process pops lu from pq to analyze. As discussed, lu includes node nu and cost cu. At step 540, the process obtains cost cv for each outgoing edge from nu. The subscript v refers to a next edge to node nv to compare with cost cu of node nu. For example, if there are 3 outgoing edges, each one will be analyzed. This may be achieved by loading each outgoing edge's lv into pq. For example, if nu has 3 outgoing edges to nv1, nv2 and nv3, each outgoing edge is analyzed. Each outgoing edge is analyzed one at a time. For example, nv1 is analyzed first, then nv2 and then nv3.
At step 550, each cost cv of an outgoing edge is analyzed with cu to determine if cv is dominated by cu. The dominance analysis, for example, is α dominance as described by equation 2. If cv is dominated by cu, lv is loaded into pq at step 560. All cvs which are dominated by cu are added to pq. The process continues to step 570. If no cu dominates all cvs, the process continues to step 570.
At step 570, the process determines if pq is empty. If pq is not empty, the process returns to step 530. If pq is empty, this indicates that node nd has been reached by the analysis and the process terminates at step 580. The routes which survives the analysis are potential routes. If the potential routes exceed k, the top k routes based on lowest cost are provided as suggested routes. For example, a counter may be used to determine of k number of routes have been found. The output module may provide the suggested routes to the user.
An example of a pseudo code for a relaxed multi-criteria k shortest paths is provided below:










Relaxed multi-criteria k shortest paths


















Input:
graph g




origin node ns




destination node nd




departure time tdep




dominance level α




max number of candidates k









Output: shortest paths and expected costs










/* initialization
*/










 1
priorityQueue pq = Ø



 2
predessorMap pm = Ø



 3
nodeCostList cl = Ø



 4
label ls = createLabel(ns, cs = 0)



 5
pq.insert(ls)



 6
while !pq is not empty



 7
label lu = pq.pop( )



 8
Node n   = lu.getNode( )



 9
for each outgoing edge eu,v do











10

cv = cu + eu,v.getCost(t + cu.time)



11

List<cost> costs = cl.getCosts(nv)



12

if cv is α-dominated by costs then












13

continue
|











14

end










/* cv is not dominated
*/











15

costs.put(cv)



16

costs.removeDominated( )



17

 label lv = createLabel(nv, cv)



18

 pm.put(lv, lu)



19

pq.insert(lv)










20
end



21
end










As shown, the routine receives various input parameters, such as graph g, origin node ns, destination node nd, departure time tdep, α and k. The routine generates relaxed multi-criteria k diversified shortest paths as an output. The routine performs initialization at lines 1-5. For example, the pq, pm and cl are set to Ø while ls is set with ns and c. In addition, ls is loaded into pq.
The routine, at line 6, performs an outer loop as long as pq is not empty. The loop includes popping lu off pq and getting the node of lu, which is nu. This is shown in lines 7-8. A second loop is performed within the outer loop, as shown in line 9. The second loop is performed for each outgoing edge of nu. For each outgoing edge, cost cv is obtained. If cv is not dominated, it is inserted into pq. If pq is empty, the routine terminates. As discussed, the routine finds k routes to suggest. A counter may be use to terminate the routine if the k routes have been found.
In another embodiment, the route planner may include an option for the user to select between a diversified k shortest path routine or a relaxed multi-criteria k shortest path routine. For example, the UI may include an option for the user to select between the two options.
An experiment was conducted using the route planner system using the diversified k shortest paths technique. FIG. 6 provides a screenshot 600 of the returned routes which are sorted by arrival time (earliest arrival comes first) and then by departure time (latest departure time comes first). As shown, the route planner system can provide users with options to take the next best route if they miss the first optimal one. More importantly, these options also include other preferences, e.g., less number of transfers as long as the routes are reasonable in terms of total travel time.
As described, the various modules of the evaluation system may be embodied as an application. For example, the various modules may be embodied as a software application. The modules may be integrated into a client/server or stand-alone software application. The source code or codes of the application may be compiled to create an executable code. The codes, for example, may be stored in a storage medium such as one or more storage disks. Other types of storage mediums may also be useful.
Although the one or more above-described implementations have been described in language specific to structural features and/or methodological steps, it is to be understood that other implementations may be practiced without the specific features or steps described. Rather, the specific features and steps are disclosed as preferred forms of one or more implementations.

## Claims

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 ns a destination node nd and a departure time tdep;
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 ctr;
for transfer edges, ct=wait time of connecting transport and ctr=1;
for walking edges, ct=wait time of connecting transport taking into account transfer time and ctr=1; and
for route edges, ct=travel time and ctr=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 ti=departure time tdep, and

 finding base route ri, according from ns to nd based on tdep and calendar day type,
b=b−1,
i=i+1, and

 add base route ri, to base route list wherein
if b>0, then repeat steps from finding base route ri , 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 ls to equal to (ns, cs), ls is an origination node label comprising the origination node ns and cost cs,
load Is into pq, wherein a top node label of the stack of pq is referred to Iu 
which is equal to (nu, cu); and
performing a cost analysis comprising
pop Iu from pq,
and analyzing nu comprising
obtaining a cost for each outgoing edge cv from nu,
if the cost of cv is not dominated by ci, then add lv, which is equal to (nv, cv), to pq, and go to checkpq, wherein Iv denotes a neighboring node label, nv denotes a neighboring node of Iv connected by the outgoing edge from nu, and
if the cost of cv is dominated by cu, 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 nu, 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 cv is dominated by cu 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 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, and
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,
a service module, wherein the service module comprises a routing service unit for generating routes to a user based on a user query received from the user device, the user query includes an origination node ns, a destination node nd and a departure time tdep, wherein the routing service unit generates the routes using k shortest paths, and
an output module, the output module comprises application program interface units which are exposed to the client route planning application for displaying the routes on the user device.

17. The route planning system of claim 16 wherein the routing service unit generates-routes using diversified k shortest paths.

18. The route planning system of claim 16 wherein the routing service unit generates routes using relaxed multi-criteria (RMC) k shortest paths.

19. A computer-implemented method performed by a computer system planning routes for a transportation network comprising:
providing an in-memory time dependent transportation graph comprising stations of the transportation network, wherein each station of the transportation graph is designated with a plurality of nodes, each of the nodes is designated with a unique transportation service servicing the station, the nodes are connected by edges, wherein the edges include cost information and transport schedule;
receiving input parameters from a user query on a user device, wherein the input parameters include an origination node ns, a destination node nd and a departure time tdep; and
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,

wherein generating the k routes includes diversified k shortest paths comprising:
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 is initialization counter, and
setting time ti=departure time tdep, and
finding base route ri according from ns to nd based on tdep and calendar day type,
b=b−1,
i=i+1, and
add base route ri , to base route list wherein
if b>0, then repeat steps from finding base route ri , and
if b is not greater then 0, then end finding b number of base routes; and
shifting the b number of base routes in base route list to find k number of routes.