TRANSIT ROUTING SYSTEM FOR PUBLIC TRANSPORTATION TRIP PLANNING

• US 20130197794A1
• Filed: 03/12/2013
• Published: 08/01/2013
• Est. Priority Date: 11/11/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bast, Hannah, Carlsson, Erik, Eigenwillig, Arno, Geisberger, Robert, Harrelson, Chris, Raychev, Veselin, Viger, Fabien
• Granted Patent: US 8,738,286 B2
• Time in Patent Office: Days
• US Class Current: 701/410
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3423 Multimodal routing, i.e. combining two or more modes of transportation, where the modes can be any of, e.g. driving, walking, cycling, public transport
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

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.

Claims

1. A computer-implemented method for determining a public transit route of a journey from a starting location to a target location, the public transit route using one or more public transportation systems, each public transportation system having public transportation vehicles, the method executed by a computer and comprising:

storing transfer patterns for the one or more public transportation systems, each stored transfer pattern describing a route between a pair of transit stations associated with the one or more public transportation systems and comprising at least one transfer between the public transportation vehicles of the one or more public transportation systems at transit stations located between the pair of transit stations;

storing information describing locations of transit stations of the one or more public transportation systems;

receiving from a client device a request for a public transit route from the starting location to the target location, the public transit route to include directions from the starting location to the target location using the one or more public transportation systems;

determining transit stations of the one or more public transportation systems that each have a location within a threshold distance of the starting location based on the stored locations of transit stations thereby generating a source station list, the source station list comprising the transit stations within the threshold distance of the starting location;

determining transit stations of the one or more public transportation systems that each have a location within a threshold distance of the target location based on the stored locations of transit stations thereby generating a target station list, the target station list comprising the transit stations within the threshold distance of the target location;

for each pair wise combination of transit stations that includes one source station from the source station list and one target station from the target station list, retrieving from the stored transfer patterns a stored transfer pattern that describes transfers of public transportation vehicles of the one or more public transportation systems at intermediate transit stations between the source station and the target station in the pair wise combination;

for each retrieved transfer pattern, determining at least one public transit route from the source station to the target station that is an instantiation of the transfer pattern at a specific time; and

transmitting information describing the at least one public transit route to the client device.

2. The method of claim 1, wherein the starting location is a current geographic location of a user of the client device.

3. The method of claim 1, wherein the target location is a geographic location of a destination desired by the user of the client device.

4. The method of claim 1, wherein the starting location or the target location is a geographic location of a transit station.

5. The method of claim 1, wherein the request further comprises at least one of a time of departure from the starting location or a time of arrival at the target location.

6. The method of claim 1, wherein retrieving from the stored transfer patterns the stored transfer pattern comprises:

retrieving one or more transfer suffixes that describe a sequenced pair of stations that precede a station associated with each transfer pattern suffix; and

concatenating the one or more suffixes to generate the stored transfer pattern.

7. The method of claim 1, further comprising:

generating a query graph by representing the stored transfer pattern of each pair wise combination of transit stations of the one or more public transportation systems as a sequence of nodes connected by arcs in an order described by the stored transfer pattern.

8. The method of claim 7, wherein determining at least one public transit route from the source station to the target station that is an instantiation of the transfer pattern at a specific time comprises:

expanding the query graph by representing each node in the query graph as a station node that represents a public transportation vehicle of the one or more public transportation systems being boarded at a transit station associated with the station node and an onboard node that represents a public transportation vehicle of the one or more public transportation systems that remains boarded during an arrival of a transit vehicle at a transit station associated with the onboard node;

determining one or more direct connection routes from the source station to each subsequent station, wherein a direct connection route describes a route from the source station to a subsequent station and a schedule of stops at intermediate transit stations between the source station and the subsequent 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 station associated the stored transfer pattern.

9. The method of claim 8, further comprising:

determining one or more direct connections from the source station to at least one subsequent station of the source station;

determining one or more direct connections from the at least one subsequent station to the target station; and

concatenating the one or more direct connections from the source 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 station in order to form a route from the source station to the target station; and

connecting a series of nodes in the expanded query graph with arcs to represent the formed route.

10. The method of claim 8, wherein determining at least one public transit route from the source station to the target station that is an instantiation of the transfer pattern at a specific time comprises:

calculating the at least one route by applying a Pareto-Dijkstra computation to the expanded query graph to determine the at least one route from the source station to the target station based upon multi-dimensions of cost, wherein the multi-dimensions of cost comprise of time duration between a pair of stations and a penalty.

11. The method of claim 10, 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.

12. The method of claim 8, wherein determining at least one public transit route from the source station to the target station that is an instantiation of the transfer pattern at a specific time comprises:

calculating the at least one route by applying a Dijkstra computation to the expanded query graph to determine the at least one route from the source station to the target station based upon a single dimension of cost, wherein the single dimension of cost comprises one of total time to complete the trip from the source station to the target station, transfers required to reach the target station from the source station, or monetary cost.

13. The method of claim 8, wherein determining at least one public transit route from the source station to the target station that is an instantiation of the transfer pattern at a specific time comprises applying a goal-directed search to determine the at least one route, wherein the goal-directed search is an A* search algorithm.

14. A computer-program product comprising a non-transitory computer-readable storage medium storing computer-executable code for determining a public transit route of a journey from a starting location to a target location, the public transit route using one or more public transportation systems, each public transportation system having public transportation vehicles, the code when executed by a computer processor performs the steps of

storing transfer patterns for the one or more public transportation systems, each stored transfer pattern describing a route between a pair of transit stations associated with the one or more public transportation systems and comprising at least one transfer between the public transportation vehicles of the one or more public transportation systems at transit stations located between the pair of transit stations;

storing information describing locations of transit stations of the one or more public transportation systems;

receiving from a client device a request for a public transit route from the starting location to the target location, the public transit route to include directions from the starting location to the target location using the one or more public transportation systems;

determining transit stations of the one or more public transportation systems that each have a location within a threshold distance of the starting location based on the stored locations of transit stations thereby generating a source station list, the source station list comprising the transit stations within the threshold distance of the starting location;

determining transit stations of the one or more public transportation systems that each have a location within a threshold distance of the target location based on the stored locations of transit stations thereby generating a target station list, the target station list comprising the transit stations within the threshold distance of the target location;

for each pair wise combination of transit stations that includes one a source station from the source station list and one target station from the target station list, retrieving from the stored transfer patterns a stored transfer pattern that describes transfers of public transportation vehicles of the one or more public transportation systems at intermediate transit stations between the source station and the target station in the pair wise combination;

for each retrieved transfer pattern, determining at least one public transit route from the source station to the target station that is an instantiation of the transfer pattern at a specific time; and

transmitting information describing the at least one public transit route to the client device.

15. The computer program product of claim 14, wherein retrieving from the stored transfer patterns the stored transfer pattern comprises:

retrieving one or more transfer suffixes that describe a sequenced pair of stations that precede a station associated with each transfer pattern suffix; and

concatenating the one or more suffixes to generate the stored transfer pattern.

16. The computer program product of claim 14, wherein the computer-readable storage medium further comprises computer-executable code that when executed by the processor:

generates a query graph by representing the stored transfer pattern of each pair wise combination of transit stations of the one or more public transportation systems as a sequence of nodes connected by arcs in an order described by the at least one stored transfer pattern.

17. The computer program product of claim 16, wherein determining at least one public transit route from the source station to the target station that is an instantiation of the transfer pattern at a specific time comprises:

expanding the query graph by representing each node in the query graph as a station node that represents a public transportation vehicle of the one or more public transportation systems being boarded at a transit station associated with the station node and an onboard node that represents a public transportation vehicle of the one or more public transportation systems that remains boarded during an arrival of a transit vehicle at a transit station associated with the onboard node;

determining one or more direct connection routes from the source station to each subsequent station, wherein a direct connection route describes a route from the source station to a subsequent station and a schedule of stops at intermediate transit stations between the source station and the subsequent 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 station associated the stored transfer pattern.

18. The computer program product of claim 14, wherein the computer-readable storage medium further comprises computer-executable code that when executed by the processor:

determines one or more direct connections from the source station to at least one subsequent station of the source station;

determines one or more direct connections from the at least one subsequent station to the target station; and

concatenates the one or more direct connections from the source 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 station in order to form a route from the source station to the target station; and

connects a series of nodes in the expanded query graph with arcs to represent the formed route.

19. The computer program product of claim 14, wherein determining at least one public transit route from the source station to the target station that is an instantiation of the transfer pattern at a specific time comprises:

calculating the at least one route by applying a Pareto-Dijkstra computation to the expanded query graph to determine the at least one route from the source station to the target station based upon multi-dimensions of cost, wherein the multi-dimensions of cost comprise of time duration between a pair of stations and a penalty.

20. A computer-system for determining a public transit route of a journey from a starting location to a target location, the public transit route using at least one public transportation system having public transportation vehicles, the method executed by a computer and comprising:

a computer processor; and

a computer-readable storage medium storing computer executable code configured to execute on the computer processor, the code when executed performs steps comprising;

storing transfer patterns for the one or more public transportation systems, each stored transfer pattern describing a route between a pair of transit stations associated with the one or more public transportation systems and comprising at least one transfer between the public transportation vehicles of the one or more public transportation systems at transit stations located between the pair of transit stations;

storing information describing locations of transit stations of the one or more public transportation systems;

receiving from a client device a request for a public transit route from the starting location to the target location, the public transit route to include directions from the starting location to the target location using the one or more public transportation systems;

determining transit stations of the one or more public transportation systems that each have a location within a threshold distance of the starting location based on the stored locations of transit stations thereby generating a source station list, the source station list comprising the transit stations within the threshold distance of the starting location;

determining transit stations of the one or more public transportation systems that each have a location within a threshold distance of the target location based on the stored locations of transit stations thereby generating a target station list, the target station list comprising the transit stations within the threshold distance of the target location;

for each pair wise combination of transit stations that includes one source station from the source station list and one target station from the target station list, retrieving from the stored transfer patterns a stored transfer pattern that describes transfers of public transportation vehicles of the one or more public transportation systems at intermediate transit stations between the source station and the target station in the pair wise combination;

for each retrieved transfer pattern, determining at least one public transit route from the source station to the target station that is an instantiation of the transfer pattern at a specific time; and

transmitting information describing the at least one public transit route to the client device.