TRANSIT ROUTING SYSTEM FOR PUBLIC TRANSPORTATION TRIP PLANNING

• US 20110112759A1
• Filed: 04/01/2010
• Published: 05/12/2011
• Est. Priority Date: 11/11/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Raychev, Veselin, Geisberger, Robert, Viger, Fabien, Eigenwillig, Arno, Bast, Hannah, Harrelson, Chris, Carlsson, Erik
• Granted Patent: US 8,417,409 B2
• Time in Patent Office: Days
• US Class Current: 701/202
• 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 computing optimal public transportation transfer patterns between transit stations, the method executed by a computer system and comprising:

for each stored public transit trip that describes a source station and a target station, retrieving a stored transit route that describes a schedule of one or more stops at transit stations by a transit vehicle during the public transit trip from the source station to the target station;

generating a transit graph by representing each stored public transit trip'"'"'s retrieved route as a sequence of a plurality of nodes connected by arcs, each node in the transit graph representing an event occurring at a transit station made by a transit vehicle associated with the transit trip;

for each pair of transit stations represented in the transit graph;

calculating from the transit graph at least one optimal transfer pattern that describes an optimal transit route of one or more transfers at transit stations between the pair of stations represented in the transit graph; and

storing the at least one optimal transfer pattern for each pair of transit stations.

2. The method of claim 1, wherein each node in the transit graph represents either a station node representing a transit vehicle that can be boarded at a station associated with the station node or an onboard node that represents a transit vehicle that remains boarded during an arrival of a transit vehicle at a station associated with the onboard node.

3. The method of claim 1, wherein each arc is one of either a boarding arc describing a transit vehicle being boarded at a station, an alighting arc describing a transit vehicle being exited at the station, a waiting arc describing a person waiting at the station, or a transit arc describing staying onboard the transit vehicle upon arrival at the station.

4. The method of claim 1, further comprising generating a cost for each arc describing a price to travel from a first station to a second station connected by the arc based at least in part on time duration to travel from the first station to the second station and an associated penalty.

5. The method of claim 4, wherein the penalty is based on a monetary cost, a number of transit vehicle transfers required to reach the second station from the first station, and walking costs from the first station to the second station.

6. The method of claim 1, further comprising generating one or more tables that include information about each arc and each node in the transit graph.

7. The method of claim 1, further comprising determining which stations from the transit graph are representative of global stations, wherein a global station is a station where a transit vehicle transfer often occurs during a long distance trip.

8. The method of claim 7, wherein determining which stations from the transit graph are representative of global stations comprises:

for each station in the transit graph, determining a number of transit vehicle transfers that occur at the station, wherein a transit vehicle transfer describes a first transit vehicle at the station being exited by a person and a second transit vehicle located at the station being boarded by the person; and

selecting the global stations based at least in part on the number of transit vehicle transfers that occur at each station.

9. The method of claim 7, wherein determining which stations from the transit graph are representative of global stations comprises:

for each station in the transit graph, grouping nodes that describe a transit vehicle being boarded at the station to form a station node group of nodes associated with the station and grouping nodes associated with different routes that have the same sequence of preceding stations in the transit graph to form an onboard node group of nodes associated with the station;

for each pair of stations in the transit graph, determining whether at least one pair of nodes associated with the pair of stations are connected by an arc in the transit graph;

for each pair of groups of nodes, adding arcs between a pair of groups of nodes associated with a pair of stations responsive to at least one pair of nodes associated with the pair of stations in the transit graph being connected by an arc;

for each arc between a pair of groups of nodes, assigning a cost based at least in part on a minimum cost associated with a pair of nodes that belong to the pair of groups of nodes, the pair of nodes connected by an arc in the transit graph;

determining optimal paths from a plurality of station node groups based on cost;

for each station node group described in the optimal paths, determining a score based on a number of different station node groups that precede the station node group in the optimal path; and

determining the global stations based at least in part on the scores for each station node group.

10. The method of claim 1, further comprising determining from the transit graph direct connection trips, wherein a direct connection trip is a trip from a source station to a target station with no transit vehicle transfers at intermediate stations between the source station and the target station.

11. The method of claim 1, wherein determining from the transit graph direct connection trips comprises:

for each possible pair of source station and target station in the transit graph, determining a set of trips in the transit graph that connects a node associated with the source station to a node associated with the target station, wherein each trip in the set comprises the same sequence of nodes that represent stops that are made by a transit vehicle during the trip; and

storing the set of trips.

12. The method of claim 1, wherein calculating from the transit graph at least one optimal transfer pattern comprises:

for each possible pair wise combination of stations that describe a source station and a target station, initializing station nodes of the source station with a zero cost value;

performing a Pareto-Dijkstra search based on multi-dimensions of cost from each station node in the source station to each node at the target station to determine optimal routes in the transit graph, wherein each node of an optimal route comprises a label set specifying cost in terms of time duration and penalty;

for each node, filtering the label set to remove dominated labels, wherein a first label (d1, p1) dominates a second label (d2, p2) responsive to d1 being less than d2 and p1 being less than p2;

determining optimal paths based on the filtered label set; and

determining the transfer pattern of each of the optimal paths based upon an ordering of stations associated with the filtered label set of each of the optimal paths.

13. The method of claim 7, wherein calculating from the transit graph at least one optimal transfer pattern comprises:

for each global station in the transit graph, determining an optimal path from all nodes associated with the global station to each other node that can be reached from the global station in the transit graph; and

for each optimal path, determining a transfer pattern of the optimal path.

14. The method of claim 1, wherein calculating from the transit graph at least one optimal transfer pattern comprises:

for each possible pair wise combination of stations in the transit graph that describes a source station and a target station, determining an optimal path from each node associated with the source station to each node associated with the target station;

for each optimal path, determining a cost associated with the optimal path, wherein the cost is a function of time and penalty;

determining a dominant path from the optimal paths based at least in part on cost, wherein the dominant path describes an optimal path with a minimal cost; and

determining a transfer pattern associated with the dominant path.

15. The method of claim 7, wherein calculating from the transit graph at least one optimal transfer pattern comprises:

determining paths from nodes of non-global station to nodes of global stations in the transit graph, each path describing a trip to the global station where only a maximum number of transit vehicle transfers are made at intermediate stations along the path in order to reach the global station; and

for each determined path, determining a transfer pattern associated with the path.

16. The method of claim 7, wherein calculating from the transit graph at least one optimal transfer pattern comprises:

determining paths in the transit graph starting from nodes of non-global stations to nodes of global stations, the nodes of the global stations describing transit vehicles that remain boarded at stations associated with the nodes of the global stations;

for each determined path, determining a transfer pattern associated with the path.

17. The method of claim 7, wherein calculating from the transit graph at least one optimal transfer pattern comprises:

determining optimal paths in the transit graph starting from nodes of non-global stations to nodes of global stations,

determining a transfer pattern for each optimal path to form a set of transfer patterns; and

removing redundant transfer patterns that are implied by one or more transfer patterns in the set.

18. The method of claim 1, further comprising:

determining walking costs from a source station to a nearby station associated with the source station; and

determining walking costs from a nearby station associated with a target station to the target station.

19. The method of claim 18, wherein determining walking costs from a source station to a nearby station comprises:

for each non-global station in the transit graph, determining nearby stations in the transit graph that are within a radial distance of the non-global station; and

for each pair of non-global station and nearby station in the transit graph, assigning a cost that describes a duration of time to walk from the non-global station to the nearby station.

20. The method of claim 1, wherein storing the at least one optimal transfer pattern for each pair of transit stations comprises:

removing one or more repetitive sequences of stations in the at least one transfer pattern;

segmenting the at least one transfer pattern into one or more transfer pattern suffixes responsive to removing the one or more repetitive sequences, wherein each transfer pattern suffix describes a sequenced pair of stations that precede a station associated with the transfer pattern suffix in the at least one transfer pattern; and

storing the one or more transfer pattern suffixes.

21. A computer-implemented method for determining a public transit route of a journey from a starting location to a target location, the method executed by a computer and comprising:

receiving from a client device a request for a public transit route from the starting location to the target location;

determining transit stations 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 transit stations 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 describes a source station from the source station list and a target station from the target station list, retrieving at least one stored transfer pattern that describes transit vehicle transfers at intermediate transit stations between the source station and the target station in order to travel from the source station to the target station;

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

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

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

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

25. The method of claim 21, wherein the request further comprises a time of departure from the starting location or a time of arrival at the target location.

26. The method of claim 21, wherein retrieving at least one 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.

27. The method of claim 21, further comprising:

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

28. The method of claim 27, wherein determining at least one optimal routes 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 transit vehicle being boarded at a station associated with the station node and an onboard node that represents a transit vehicle that remains boarded during an arrival of a transit vehicle at a 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.

29. The method of claim 28, 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.

30. The method of claim 28, wherein determining at least one optimal routes 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.

31. The method of claim 30 wherein the penalty is based at least in part on monetary cost, number of transit vehicle transfers required to reach the target station from the source station, and walking costs.

32. The method of claim 28, wherein determining at least one optimal routes 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.

33. The method of claim 28, wherein determining at least one optimal routes 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.

34. A computer-program product comprising a computer-readable storage medium storing computer-executable code for computing optimal public transportation transfer patterns between transit stations, the code when executed by a computer processor performs the steps of:

for each stored public transit trip that describes a source station and a target station, retrieving a stored transit route that describes a schedule of one or more stops at transit stations by a transit vehicle during the public transit trip from the source station to the target station;

generating a transit graph by representing each stored public transit trip'"'"'s retrieved route as a sequence of a plurality of nodes connected by arcs, each node in the transit graph representing an event occurring at a transit station made by a transit vehicle associated with the transit trip;

for each pair of transit stations represented in the transit graph;

calculating from the transit graph at least one optimal transfer pattern that describes an optimal transit route of one or more transfers at transit stations between the pair of stations represented in the transit graph; and

storing the at least one optimal transfer pattern for each pair of transit stations.

35. The computer-program product claim 34, wherein the computer-readable storage medium further stores computer executable code that when executed by the computer processor determines which stations from the transit graph are representative of global stations, wherein a global station is a station where a transit vehicle transfer often occurs during a long distance trip.

36. The computer-program product claim 35, wherein determining which stations from the transit graph are representative of global stations comprises:

for each station in the transit graph, determining a number of transit vehicle transfers that occur at the station, wherein a transit vehicle transfer describes a first transit vehicle at the station being exited by a person and a second transit vehicle located at the station being boarded by the person; and

selecting the global stations based at least in part on the number of transit vehicle transfers that occur at each station.

37. The computer-program product claim 35, wherein determining which stations from the transit graph are representative of global stations comprises:

for each station in the transit graph, grouping nodes that describe a transit vehicle being boarded at the station to form a station node group of nodes associated with the station and grouping nodes associated with different routes that have the same sequence of preceding stations in the transit graph to form an onboard node group of nodes associated with the station;

for each pair of stations in the transit graph, determining whether at least one pair of nodes associated with the pair of stations are connected by an arc in the transit graph;

for each pair of groups of nodes, adding arcs between a pair of groups of nodes associated with a pair of stations responsive to at least one pair of nodes associated with the pair of stations in the transit graph being connected by an arc;

for each arc between a pair of groups of nodes, assigning a cost based at least in part on a minimum cost associated with a pair of nodes that belong to the pair of groups of nodes, the pair of nodes connected by an arc in the transit graph;

determining optimal paths from a plurality of station node groups based on cost;

for each station node group described in the optimal paths, determining a score based on a number of different station node groups that precede the station node group in the optimal path; and

determining the global stations based at least in part on the scores for each station node group.

38. The computer-program product claim 34, wherein determining from the transit graph direct connection trips comprises:

for each possible pair of source station and target station in the transit graph, determining a set of trips in the transit graph that connects a node associated with the source station to a node associated with the target station, wherein each trip in the set comprises the same sequence of nodes that represent stops that are made by a transit vehicle during the trip; and

storing the set of trips.

39. The computer-program product claim 34, wherein calculating from the transit graph at least one optimal transfer pattern comprises:

for each possible pair wise combination of stations that describe a source station and a target station, initializing station nodes of the source station with a zero cost value;

performing a Pareto-Dijkstra search based on multi-dimensions of cost from each station node in the source station to each node at the target station to determine optimal routes in the transit graph, wherein each node of an optimal route comprises a label set specifying cost in terms of time duration and penalty;

for each node, filtering the label set to remove dominated labels, wherein a first label (d1, p1) dominates a second label (d2, p2) responsive to d1 being less than d2 and p1 being less than p2;

determining optimal paths based on the filtered label set; and

determining the transfer pattern of each of the optimal paths based upon an ordering of stations associated with the filtered label set of each of the optimal paths.

40. The computer-program product claim 35, wherein calculating from the transit graph at least one optimal transfer pattern comprises:

for each global station in the transit graph, determining an optimal path from all nodes associated with the global station to each other node that can be reached from the global station in the transit graph; and

for each optimal path, determining a transfer pattern of the optimal path.

41. The computer-program product of claim 34, wherein calculating from the transit graph at least one optimal transfer pattern comprises:

for each possible pair wise combination of stations in the transit graph that describes a source station and a target station, determining an optimal path from each node associated with the source station to each node associated with the target station;

for each optimal path, determining a cost associated with the optimal path, wherein the cost is a function of time and penalty;

determining a dominant path from the optimal paths based at least in part on cost, wherein the dominant path describes an optimal path with a minimal cost; and

determining a transfer pattern associated with the dominant path.

42. The computer program product of claim 35, wherein calculating from the transit graph at least one optimal transfer pattern comprises:

determining paths from nodes of non-global station to nodes of global stations in the transit graph, each path describing a trip to the global station where only a maximum number of transit vehicle transfers are made at intermediate stations along the path in order to reach the global station; and

for each determined path, determining a transfer pattern associated with the path.

43. The computer program product of claim 35, wherein calculating from the transit graph at least one optimal transfer pattern comprises:

determining paths in the transit graph starting from nodes of non-global stations to nodes of global stations, the nodes of the global stations describing transit vehicles that remain boarded at stations associated with the nodes of the global stations;

for each determined path, determining a transfer pattern associated with the path.

44. The computer program product of claim 35, wherein calculating from the transit graph at least one optimal transfer pattern comprises:

determining optimal paths in the transit graph starting from nodes of non-global stations to nodes of global stations,

determining a transfer pattern for each optimal path to form a set of transfer patterns; and

removing redundant transfer patterns that are implied by one or more transfer patterns in the set.

45. The computer program product of claim 34, wherein storing the at least one optimal transfer pattern for each pair of transit stations comprises:

removing one or more repetitive sequences of stations in the at least one transfer pattern;

segmenting the at least one transfer pattern into one or more transfer pattern suffixes responsive to removing the one or more repetitive sequences, wherein each transfer pattern suffix describes a sequenced pair of stations that precede a station associated with the transfer pattern suffix in the at least one transfer pattern; and

storing the one or more transfer pattern suffixes.

46. A computer-program product comprising a 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 code when executed by a computer processor performs the steps of

receiving from a client device a request for a public transit route from the starting location to the target location;

determining transit stations 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 transit stations 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 describes a source station from the source station list and a target station from the target station list, retrieving at least one stored transfer pattern that describes transit vehicle transfers at intermediate transit stations between the source station and the target station in order to travel from the source station to the target station;

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

47. The computer program product of claim 46, wherein retrieving at least one 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.

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

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

49. The computer program product of claim 48, wherein determining at least one optimal routes 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 transit vehicle being boarded at a station associated with the station node and an onboard node that represents a transit vehicle that remains boarded during an arrival of a transit vehicle at a 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.

50. The computer program product of claim 46, 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.

51. The computer program product of claim 46, wherein determining at least one optimal routes 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.

52. A computer-system for computing optimal public transportation transfer patterns between transit stations, the system comprising:

a computer processor; and

a computer-readable storage medium storing computer program modules configured to execute on the computer processor, the computer program modules comprising;

a transit graph module configured to;

retrieve a stored transit route that describes a schedule of one or more stops at transit stations by a transit vehicle during the public transit trip from a source station to a target station for each stored public transit trip that describes the source station and the target station; and

generate a transit graph by representing each stored public transit trip'"'"'s retrieved route as a sequence of a plurality of nodes connected by arcs, each node in the transit graph representing an event occurring at a transit station made by a transit vehicle associated with the transit trip;

a transfer pattern computation module configured to for each pair of transit stations represented in the transit graph;

calculating from the transit graph at least one optimal transfer pattern that describes an optimal transit route of one or more transfers at transit stations between the pair of stations represented in the transit graph; and

storing the at least one optimal transfer pattern for each pair of transit stations.

53. A computer-system for determining a public transit route of a journey from a starting location to a target location, the method executed by a computer and comprising:

a computer processor; and

a computer-readable storage medium storing computer program modules configured to execute on the computer processor, the computer program modules comprising;

a local station determination module configured to;

receive from a client device a request for a public transit route from the starting location to the target location;

determine transit stations 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 transit stations 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;

a transfer pattern construction module configured to for each pair wise combination of transit stations that describes a source station from the source station list and a target station from the target station list, retrieve at least one stored transfer pattern that describes transit vehicle transfers at intermediate transit stations between the source station and the target station in order to travel from the source station to the target station;

a query graph analysis module configured to for each retrieved transfer pattern, determine at least one optimal route from the source station to the target station that is an instantiation of the transfer pattern at a specific time; and

a trip serving module configured to transmit information describing the at least one optimal route to the client device.