Transit routing system for public transportation trip planning

Abstract

A public transit travel planning system and methodology that uses an extensive pre-processing approach of transit information prior to query time on order to determine optimal public transit routes for journeys. At query time, since the transit information has already been processed by the system, very little computation is needed in order to fulfill the query. The system then provides users with public transit directions in response to the queries for public transit journeys.

We claim: 
     
         1 . A computer-implemented method for providing public transit directions, the method comprising:
 receiving from a client device a request for a public transit route from a starting location to a target location;   determining a plurality of starting transit stations associated with the starting location;   determining a plurality of target transit stations associated with the target location;   for pairs of the plurality of starting transit stations and the plurality of target transit stations, retrieving stored transfer patterns that describe transit vehicle transfers at intermediate transit stations between the pairs;   for at least one of the retrieved transfer patterns, determining, by one or more computer systems, a route from a starting transit station to a target transit station associated with the retrieved transfer pattern that is an instantiation of the transfer pattern at a specific time; and   transmitting information describing the route to the client device.   
     
     
         2 . The method of  claim 1 , wherein receiving from the client device the request for the public route comprises:
 receiving a current geographic location of a user of the client device as the starting location for the public transit route and an address of a destination of the user as the target location for the public transit route.   
     
     
         3 . The method of  claim 1 , wherein receiving from the client device the request for the public route comprises:
 receiving a current geographic location of a user of the client device as the starting location for the public transit route and an address of a transit station as the target location for the public transit route.   
     
     
         4 . The method of  claim 1 , wherein receiving from the client device the request for the public route comprises:
 receiving at least one of a time of departure from the starting location and a time of arrival at the target location for the public transit route from the client device.   
     
     
         5 . The method of  claim 4 , wherein determining the route from the starting transit station to the target transit station that is the instantiation of the transfer pattern at the specific time is based on at least one of the time of departure and the time of arrival received from the client device. 
     
     
         6 . The method of  claim 1 , wherein the route transmitted to the client device requires a user associated with the client device to use one or more public transportation systems to arrive at the target location from the starting location. 
     
     
         7 . The method of  claim 1 , wherein retrieving the stored transfer patterns comprises:
 retrieving one or more transfer suffixes that describe a sequenced pair of transit stations that precede a transit station associated with the transfer pattern suffix; and   concatenating the one or more transfer suffixes to generate the stored transfer pattern.   
     
     
         8 . The method of  claim 1 , further comprising:
 generating a query graph that represents the retrieved transfer pattern of each pair wise combination of transit stations as a sequence of nodes connected by arcs in an order described by the stored transfer pattern.   
     
     
         9 . The method of  claim 8 , wherein determining the route from the starting transit station to the target transit station that is an instantiation of the transfer pattern at a specific time comprises:
 representing each node in the query graph as a station node that represents a transit vehicle being boarded at a transit station associated with the station node and an onboard node that represents a transit vehicle that remains boarded during an arrival of the transit vehicle at a transit station associated with the onboard node to expand the query graph;   determining one or more direct connection routes from the starting transit station to each subsequent station, wherein a direct connection route describes a route from the starting transit station to a subsequent station and a schedule of stops at intermediate transit stations between the starting transit station and the subsequent station that are associated with the stored transfer pattern; and   for each of the one or more direct connection routes, connecting a series of nodes in the expanded query graph with arcs to represent the direct connection route, each node in the series representing a transit station associated the stored transfer pattern.   
     
     
         10 . The method of  claim 9 , further comprising:
 determining one or more direct connections from the starting transit station to at least one subsequent station of the starting transit station;   determining one or more direct connections from the at least one subsequent station to the target transit station;   concatenating the one or more direct connections from the starting transit station to the at least one subsequent station with the one or more direct connections from the at least one subsequent station to the target transit station in order to form a route from the starting transit station to the target transit station; and   connecting a series of nodes in the expanded query graph with arcs to represent the formed route.   
     
     
         11 . The method of  claim 9 , wherein determining the route from the starting transit station to the target transit station that is an instantiation of the transfer pattern at a specific time comprises:
 calculating the route by applying a Pareto-Dijkstra computation to the expanded query graph to determine the route from the starting transit station to the target transit station based upon a plurality of costs including a time duration between a pair of transit stations and a penalty.   
     
     
         12 . The method of  claim 11 , wherein the penalty is based at least in part on monetary cost, a number of public transportation vehicle transfers required to reach the target station from the source station, and walking costs. 
     
     
         13 . The method of  claim 9 , wherein determining the route from the starting transit station to the target transit station that is an instantiation of the transfer pattern at a specific time comprises:
 calculating the route by applying a Dijkstra computation to the expanded query graph to determine the route from the starting transit station to the target transit station based upon a cost, wherein the cost comprises one of a total time needed to complete the trip from the starting transit station to the target transit station, transfers between transit vehicles required to reach the target transit station from the starting transit station, and monetary cost.   
     
     
         14 . The method of  claim 9 , wherein determining the route from the starting transit station to the target transit station that is an instantiation of the transfer pattern at a specific time comprises applying a goal-directed search to determine the route, wherein the goal-directed search is an A* search algorithm. 
     
     
         15 . The method of  claim 1 , wherein the plurality of starting transit stations are located within a threshold distance from the starting location and the plurality of target transit stations are located within a threshold distance from the target location. 
     
     
         16 . A computer-program product comprising a non-transitory computer-readable storage medium storing computer-executable code for providing public transit directions, the code when executed by at least one computer processor causes the computer processor to perform steps comprising:
 receiving from a client device a request for a public transit route from a starting location to a target location;   determining a plurality of starting transit stations associated with the starting location;   determining a plurality of target transit stations associated with the target location;   for pairs of the plurality of starting transit stations and the plurality of target transit stations, retrieving stored transfer patterns that describe transit vehicle transfers at intermediate transit stations between the pairs;   for at least one of the retrieved transfer patterns, determining a route from a starting transit station to a target transit station associated with the retrieved transfer pattern that is an instantiation of the transfer pattern at a specific time; and   transmitting information describing the route to the client device.   
     
     
         17 . The computer program product of  claim 16 , wherein receiving from the client device the request for the public route comprises:
 receiving at least one of a time of departure from the starting location and a time of arrival at the target location for the public transit route from the client device.   
     
     
         18 . The computer program product of  claim 17 , wherein determining the route from the starting transit station to the target transit station that is the instantiation of the transfer pattern at the specific time is based on at least one of the time of departure and the time of arrival received from the client device. 
     
     
         19 . The computer program product of  claim 16 , wherein the non-transitory computer-readable storage medium further comprises computer-executable code that when executed by the computer processor causes the computer processor to perform further steps comprising:
 generating a query graph that represents the retrieved transfer pattern of each pair wise combination of transit stations as a sequence of nodes connected by arcs in an order described by the stored transfer pattern;   representing each node in the query graph as a station node that represents a transit vehicle being boarded at a transit station associated with the station node and an onboard node that represents a transit vehicle that remains boarded during an arrival of the transit vehicle at a transit station associated with the onboard node to expand the query graph;   determining one or more direct connection routes from the starting transit station to each subsequent station, wherein a direct connection route describes a route from the starting transit station to a subsequent station and a schedule of stops at intermediate transit stations between the starting transit station and the subsequent station that are associated with the stored transfer pattern;   for each of the one or more direct connection routes, connecting a series of nodes in the expanded query graph with arcs to represent the direct connection route, each node in the series representing a transit station associated the stored transfer pattern; and   calculating the route by applying a Pareto-Dijkstra computation to the expanded query graph to determine the route from the starting transit station to the target transit station based upon a plurality of costs including a time duration between a pair of transit stations and a penalty.   
     
     
         20 . A computer-system for providing public transit directions, the computer-system comprising:
 at least one computer processor; and   at least one computer-readable storage medium storing computer executable code configured to execute on the computer processor, the code when executed performs steps comprising:
 receiving from a client device a request for a public transit route from a starting location to a target location; 
 determining a plurality of starting transit stations associated with the starting location; 
 determining a plurality of target transit stations associated with the target location; 
 for pairs of the plurality of starting transit stations and the plurality of target transit stations, retrieving stored transfer patterns that describe transit vehicle transfers at intermediate transit stations between the pairs; 
 for at least one of the retrieved transfer patterns, determining a route from a starting transit station to a target transit station associated with the retrieved transfer pattern that is an instantiation of the transfer pattern at a specific time; and 
 transmitting information describing the route to the client device.