Transit routing system for public transportation trip planning

• US 8,417,409 B2
• Filed: 04/01/2010
• Issued: 04/09/2013
• Est. Priority Date: 11/11/2009
• Status: Expired due to Fees

• 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
• Primary Examiner(s): Tarcza, Thomas
• Assistant Examiner(s): Anwari, Maceeh
• Application Number:
  US12/752,980
• Publication Number:
  US 20110112759A1
• Time in Patent Office: 1,104 Days
• Field of Search: 701/202
• US Class Current: 701/25
• 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 at least one public transportation system having public transportation vehicles, the method executed by a computer and comprising:

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

storing in a second database, information describing public transit stations, including for each public transit station a location;

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 at least one public transportation system;

determining using the second database the transit stations of the at least one public transportation system that has locations within a radial distance of the starting location thereby generating a source station list that comprises the transit stations within the radial distance of the starting location;

determining using the second database transit stations of the at least one public transportation system that has locations within the radial distance of the target location thereby generating a target station list that comprises the transit stations within the radial 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 first database of stored transfer patterns a stored transfer pattern that describes transfers of public transportation vehicles of the at least one public transportation system at intermediate transit stations between the source station and the target station in the pair wise combination in order to travel from the source station to the target station;

for each retrieved transfer pattern, determining at least one optimal 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 optimal 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 the 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 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 first database of 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 at least one 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 at least one public transportation system 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 optimal 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 at least one public transportation system being boarded at a transit station associated with the station node and an onboard node that represents a public transportation vehicle of the at least one public transportation system 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 at least one 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 at least one 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;

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 optimal 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 optimal route by applying a Pareto-Dijkstra computation to the expanded query graph to determine the at least one optimal 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, 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 optimal 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 optimal route by applying a Dijkstra computation to the expanded query graph to determine the at least one optimal 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 optimal 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 optimal 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 at least one public transportation system having public transportation vehicles, the code when executed by a computer processor performs the steps of

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

storing in a second database, information describing public transit stations, including for each public transit station a location;

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 at least one public transportation system;

determining using the second database the transit stations of the at least one public transportation system that has locations within a radial distance of the starting location thereby generating a source station list that comprises the transit stations within the radial distance of the starting location;

determining using the second database transit stations of the at least one public transportation system that has locations within the radial distance of the target location thereby generating a target station list that comprises the transit stations within the radial 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 first database of stored transfer patterns a stored transfer pattern that describes transfers of public transportation vehicles of the at least one public transportation system at intermediate transit stations between the source station and the target station in the pair wise combination in order to travel from the source station to the target station;

for each retrieved transfer pattern, determining at least one optimal 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 optimal public transit route to the client device.

15. The computer program product of claim 14, wherein retrieving from the first database of 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 at least one 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 at least one public transportation system 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 optimal 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 at least one public transportation system being boarded at a transit station associated with the station node and an onboard node that represents a public transportation vehicle of the at least one public transportation system 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 at least one 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 at least one 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;

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 optimal 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 optimal route by applying a Pareto-Dijkstra computation to the expanded query graph to determine the at least one optimal 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 in a first database transfer patterns for the at least one public transportation system, each stored transfer pattern describing a route between a pair of transit stations associated with the at least one public transportation system and comprising at least one transfer between the public transportation vehicles at transit stations located between the pair of transit stations;

storing in a second database, information describing public transit stations, including for each public transit station a location;

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 at least one public transportation system;

determining using the second database the transit stations of the at least one public transportation system that has locations within a radial distance of the starting location thereby generating a source station list that comprises the transit stations within the radial distance of the starting location;

determining using the second database transit stations of the at least one public transportation system that has locations within the radial distance of the target location thereby generating a target station list that comprises the transit stations within the radial 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 first database of stored transfer patterns a stored transfer pattern that describes transfers of public transportation vehicles of the at least one public transportation system at intermediate transit stations between the source station and the target station in the pair wise combination in order to travel from the source station to the target station;

for each retrieved transfer pattern, determining at least one optimal 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 optimal public transit route to the client device.

21. The computer system of claim 20, wherein the starting location is a current geographic location of a user of the client device.

22. The computer system of claim 20, wherein the target location is the geographic location of a destination desired by the user of the client device.

23. The computer system of claim 20, wherein the starting location or the target location is a geographic location of a transit station.

24. The computer system of claim 20, wherein the request further comprises a time of departure from the starting location or a time of arrival at the target location.

25. The computer system of claim 20, wherein retrieving from the first database of 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 at least one stored transfer pattern.

26. The computer system of claim 20, wherein the code when executed performs further steps comprising:

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

27. The computer system of claim 26, wherein determining at least one optimal 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 at least one public transportation system being boarded at a transit station associated with the station node and an onboard node that represents a public transportation vehicle of the at least one public transportation system 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 at least one 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 at least one stored transfer pattern.

28. The computer system of claim 27, wherein the code when executed performs further steps comprising:

determining one or more direct connections from the source station to at least one subsequent 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.

29. The computer system of claim 27, wherein determining at least one optimal 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 optimal route by applying a Pareto-Dijkstra computation to the expanded query graph to determine the at least one optimal 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.

30. The computer system of claim 29, wherein the penalty is based at least in part on monetary cost, number of public transportation vehicle transfers required to reach the target station from the source station, and walking costs.

31. The computer system of claim 27, wherein determining at least one optimal 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 optimal route by applying a Dijkstra computation to the expanded query graph to determine the at least one optimal 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.

32. The computer system of claim 27, wherein determining at least one optimal 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 optimal route, wherein the goal-directed search is an A* search algorithm.