Constructing a transit transfer network from transit data

• US 8,972,185 B1
• Filed: 10/01/2012
• Issued: 03/03/2015
• Est. Priority Date: 10/01/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Viger, Fabien, Pech, Lucien
• Primary Examiner(s): Olszewski, John R
• Assistant Examiner(s): McPherson, James M
• Application Number:
  US13/632,472
• Time in Patent Office: 883 Days
• Field of Search: None
• US Class Current: 701/533
• 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/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A computer-implemented method of constructing a transit transfer network from transit data comprises processing transit data to define a plurality of transfer endpoints; determining a set of acceptable transfer durations for each of a plurality of transfers associated with the transfer endpoints; determining one or more groups of endpoints to be merged, each group comprising two or more endpoints, wherein transfers associated with the endpoints in each said group have one or more common acceptable transfer durations; and merging the endpoints in each group to form one or more merged endpoints.

Claims

1. A computer-implemented method of constructing a transit transfer network from transit data, comprising:

processing, by one or more computing device, transit data to define a plurality of transfer endpoints, including one or more source endpoints and one or more target endpoints;

determining, by the one or more computing devices, a set of acceptable transfer durations from the one or more source endpoints to the one or more target endpoints for each of a plurality of transfers associated with the transfer endpoints;

determining, by the one or more computing devices, one or more groups of source endpoints and target endpoints to be merged based at least in part on one or more sets of acceptable transfer durations, each group comprising two or more endpoints, wherein transfers associated with the endpoints in each said group have one or more common acceptable transfer durations; and

merging, by the one or more computing devices, endpoints in each group to form one or more merged source endpoints and target endpoints based at least in part on one or more sets of acceptable transfer durations wherein the one or more merged endpoints are less than the plurality of transfer endpoints resulting in fewer transfer endpoints than the plurality of transfer endpoints to form the transit transfer network.

2. A computer-implemented method as claimed in claim 1, wherein determining one or more groups of endpoints to be merged comprises determining incompatible endpoints based on sets of acceptable transfer durations, and determining one or more groups of compatible endpoints to be merged.

3. A computer-implemented method as claimed in claim 2, wherein determining one or more groups of compatible endpoints to be merged comprises:

forming an incompatibility graph of incompatible endpoints; and

carrying out a graph coloring on the incompatibility graph, wherein each group of compatible endpoints relates to a different color in the graph coloring.

4. A computer-implemented method as claimed in claim 2, wherein first and second endpoints are determined to be incompatible if it is determined that:

there is a third endpoint which is associated by transfers with both the first and second endpoints; and

there is no acceptable transfer duration that would suit both the transfer associating the first and third endpoints and the transfer associating the second and third endpoints.

5. A computer-implemented method as claimed in claim 1, wherein merging the endpoints in each group comprises intersecting sets of acceptable transfer durations for transfers associated with endpoints of the group.

6. A computer-implemented method as claimed in claim 1, wherein defining said plurality of transfer endpoints comprises defining a first set of endpoints and a second set of endpoints, wherein one of the first and second sets of endpoints comprises a set of one or more source endpoints and wherein the other of said first and second sets of endpoints comprises one or more target endpoints, comprising

determining one or more groups of endpoints of the first set to be merged, and merging the endpoints in each group to form at least one merged endpoint;

and

determining one or more groups of endpoints of the second set to be merged, and merging the endpoints in each group to form at least one merged endpoint.

7. A computer-implemented method as claimed in claim 1, wherein each set of acceptable transfer durations comprises an interval of acceptable transfer durations.

8. A computer-implemented method of constructing a transit transfer network from transit data, comprising:

defining, by one or more computing device, a plurality of transfer endpoints, including one or more source endpoints and one or more target endpoints, based on the transit information;

determining, by the one or more computing devices, incompatible endpoints based at least in part on one or more sets of acceptable transfer durations from the one or more source endpoints and one or more target endpoints for each of a plurality of transfers associated with the transfer endpoints;

selecting, by the one or more computing devices, one or more sets of source endpoints and target endpoints to be merged based at least in part on one or more sets of acceptable transfer durations such that the endpoints of each set are not incompatible; and

merging, by the one or more computing devices, the endpoints of each set to form at least one merged source endpoint and target endpoint based at least in part on one or more sets of acceptable transfer durations, wherein the merged endpoints are less than the plurality of transfer endpoints resulting in fewer transfer endpoints than the plurality of transfer endpoints to form the transit transfer network.

9. A computer-implemented method as claimed in claim 8, wherein selecting one or more sets of compatible endpoints comprises:

forming an incompatibility graph of incompatible endpoints; and

carrying out a graph coloring on the incompatibility graph to provide an assignment from endpoints to sets of compatible endpoints, wherein each set of compatible endpoints corresponds to a different color of the graph coloring.

10. A computer-implemented method as claimed in claim 8, wherein first and second endpoints are determined to be incompatible if it is determined that:

there is a third endpoint which is associated by transfers with both the first and second endpoints; and

there is no acceptable transfer duration that would suit both the transfer associating the first and third endpoints and the transfer associating the second and third endpoints.

11. An apparatus comprising at least one processor and at least one memory storing instructions when executed by the at least one processor cause the at least one processor to:

process transit data to define a plurality of transfer endpoints, including one or more source endpoints and one or more target endpoints;

determine a set of acceptable transfer durations from the one or more source endpoints and one or more target endpoints for each of a plurality of transfers associated with the transfer endpoints;

determine one or more groups of source endpoints and target endpoints to be merged based at least in part on one or more sets of acceptable transfer durations, each group comprising two or more endpoints, wherein transfers associated with the endpoints in each said group have one or more common acceptable transfer durations; and

merge the endpoints in each group to form one or more merged source endpoints and target endpoints based at least in part on one or more sets of acceptable transfer durations wherein the one or more merged endpoints are less than the plurality of transfer endpoints resulting in fewer transfer endpoints than the plurality of transfer endpoints to form the transit transfer network.

12. An apparatus as claimed in claim 11, wherein determining one or more groups of endpoints to be merged comprises determining incompatible endpoints based on sets of acceptable transfer durations, and determining one or more groups of compatible endpoints to be merged.

13. An apparatus as claimed in claim 12, wherein determining one or more groups of compatible endpoints to be merged comprises:

forming an incompatibility graph of incompatible endpoints; and

carrying out a graph coloring on the incompatibility graph, wherein each group of compatible endpoints relates to a different color in the graph coloring.

14. An apparatus as claimed in claim 11, wherein merging the endpoints in each group comprises intersecting sets of acceptable transfer durations for transfers associated with endpoints of the group.

15. An apparatus comprising at least one processor and at least one memory storing instructions when executed by the at least one processor cause the at least one processor to

define a plurality of transfer endpoints, including one or more source endpoints and one or more target endpoints based on the transit information;

determine incompatible endpoints based at least in part on one or more sets of acceptable transfer durations from the one or more source endpoints and one or more target endpoints for each of a plurality of transfers associated with the transfer endpoints;

select one or more sets of source endpoints and target endpoints to be merged based at least in part on one or more sets of acceptable transfer durations such that the endpoints of each set are not incompatible; and

merge the endpoints of each set to form at least one merged source endpoint and target endpoint based at least in part on one or more sets of acceptable transfer durations wherein the merged endpoints are less than the plurality of transfer endpoints resulting in fewer transfer endpoints than the plurality of transfer endpoints to form the transit transfer network.

16. An apparatus as claimed in claim 15, wherein the instructions when executed by the at least one processor further cause the at least one processor to:

form an incompatibility graph of incompatible endpoints; and

carry out a graph coloring on the incompatibility graph to provide an assignment from endpoints to sets of compatible endpoints, wherein each set of compatible endpoints corresponds to a different color of the graph coloring.

17. A transit directions system comprising a query resolution module to resolve user queries for transit directions, a transit interface to receive transit data from one or more transit data providers, and a transit transfer network module to form a transit transfer network using received transit data, wherein the transit transfer network module comprises:

an endpoint definition module to define a plurality of transfer endpoints, including one or more source endpoints and one or more target endpoints based on transit data;

an incompatibilities module to determine incompatible endpoints based at least in part on sets of acceptable transfer durations from the one or more source endpoints and one or more target endpoints for each of a plurality of transfers associated with the transfer endpoints;

a set selection module to select one or more sets of source endpoints and target endpoints to be merged based at least in part on one or more sets of acceptable transfer durations such that the endpoints of each set are not incompatible; and

a conflation module to merge the endpoints of each set to form at least one merged sourced endpoint and target endpoint based at least in part on one or more sets of acceptable transfer durations wherein the merged endpoints are less than the plurality of transfer endpoints resulting in fewer transfer endpoints than the plurality of transfer endpoints to form the transit transfer network.

18. A transit directions system as claimed in claim 17, wherein the incompatibilities module is configured to form an incompatibility graph, and wherein the set selection module comprises a graph coloring module to carry out a graph coloring on the incompatibility graph.

19. A transit directions system as claimed in claim 17, wherein the transit transfer network module further comprises an interval calculation module to calculate intervals of acceptable transfer durations for transfers associated with transfer endpoints.

20. A transit directions system as claimed in claim 17, further comprising a transit graph module to form a transit graph, and a transfer arc module to determine transfer arcs between nodes of the transit graph using the transit transfer network.