Systems and methods for generating a plurality of trip patterns

• US 9,273,970 B2
• Filed: 05/14/2013
• Issued: 03/01/2016
• Est. Priority Date: 05/14/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Graells, Albert, Pech, Lucien
• Primary Examiner(s): Shafi, Muhammad
• Assistant Examiner(s): ALSOMIRI, MAJDI A
• Application Number:
  US13/894,025
• Publication Number:
  US 20150168149A1
• Time in Patent Office: 1,022 Days
• Field of Search: 701/400, 701/413, 701/416, 701/420, 701527-533, 701/540, 340/531, 340/539.1, 340/539.11, 340/988, 340/990, 340/994, 340/995.1, 340/995.19, 713/190, 370/238
• US Class Current: 1/1
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• 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 22/002 for cycles
• CPC Class Codes: G01C 22/02 by conversion into electric waveforms and subsequent integration, e.g. using tachometer generator G01C22/002, G01C22/004, G01C22/006 take precedence
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data

Abstract

Systems and methods for generating a plurality of trip patterns are provided. One exemplary method includes receiving transit graph data describing a plurality of nodes respectively corresponding to a plurality of transit stations and a plurality of arcs respectively connecting the plurality of nodes. The method also includes performing a plurality of identification iterations. Each identification iteration includes determining an optimal transit trip connecting an origin node to a destination node based on a cost model. Each identification iteration also includes revising the cost model based on the determined optimal transit trip, such that the arc costs associated with one or more arcs associated with the optimal transit trip are increased. Each optimal transit trip can have an associated trip pattern describing a sequence of nodes traversed by such optimal transit trip. One exemplary system can include a transit planning platform that includes a trip pattern identification module.

Claims

1. A computer-implemented method of determining a plurality of trip patterns, the method comprising

receiving, by one or more computing devices, transit graph data describing a plurality of nodes respectively corresponding to a plurality of transit stations and a plurality of arcs respectively connecting the plurality of nodes and respectively corresponding to transportation between the plurality of transit stations;

performing, by one or more computing devices, a plurality of identification iterations, each identification iteration comprising;

determining an optimal transit trip connecting an origin node to a destination node based on a cost model providing an arc cost for each of the plurality of arcs; and

revising the cost model based on the determined optimal transit trip, such that the arc costs associated with one or more arcs associated with the optimal transit trip are increased;

wherein each subsequent identification iteration determines the optimal transit trip based on the cost model as revised by the immediately preceding identification iteration such that a plurality of optimal transit trips are determined, each optimal transit trip having an associated trip pattern describing a sequence of nodes traversed by such optimal transit trip and wherein the trip pattern associated with each optimal transit trip comprises a sequence of one or more pairs of solution nodes;

revising, by one or more computing devices, the cost model based on the determined optimal transit trip, wherein revising the cost model comprises increasing the arc cost associated with each arc connecting, nodes corresponding to the same stations as one of the pairs of solution nodes; and

displaying to a user, by the one or more computing devices, one or more of the determined optimal transit trips.

2. The computer-implemented method of claim 1, wherein the arc cost associated with each arc connecting nodes corresponding to the same stations as one of the pairs of solution nodes is increased by an amount that is proportional to a duration associated with such arc.

3. The computer-implemented method of claim 1, wherein:

the optimal transit trip determined at each iteration comprises a plurality of solution arcs respectively connecting a plurality of pairs of solution nodes; and

revising the cost model based on the determined optimal transit trip comprises increasing the arc cost associated with each arc connecting nodes corresponding to the same stations as the pair of solution nodes connected by the solution arc having the arc cost of greatest magnitude.

4. The computer-implemented method of claim 1, wherein:

the optimal transit trip determined at each iteration comprises a plurality of solution arcs, each solution arc having a duration and connecting a pair of solution nodes; and

revising the cost model based on the determined optimal transit trip comprises increasing the arc cost associated with each arc connecting nodes corresponding to the same stations as the pair of solution nodes connected by the solution arc having the duration of greatest magnitude.

5. The computer-implemented method of claim 1, wherein:

the optimal transit trip determined at each iteration comprises a plurality of solution arcs, each solution arc corresponding to a portion of one of a plurality of a transit lines; and

revising the cost model based on the determined optimal transit trip comprises identifying at least one transit line associated with at least one solution arc and increasing the arc cost associated with each arc corresponding to the identified at least one transit line.

6. The computer-implemented method of claim 1, wherein:

the optimal transit trip determined at each iteration comprises a plurality of solution arcs, each solution arc corresponding to transportation provided by one of a plurality of transit providers; and

revising the cost model based on the determined optimal transit trip comprises identifying at least one transit provider associated with at least one solution arc and increasing the arc cost associated with each arc corresponding to the identified transit provider.

7. The computer-implemented method of claim 1, wherein:

the optimal transit trip determined at each iteration comprises a plurality of solution arcs, each solution arc corresponding to one of a plurality of modes of transportation; and

revising the cost model based on the determined optimal transit trip comprises identifying at least one mode of transportation associated with at least one solution arc and increasing the arc cost associated with each arc corresponding to the identified mode of transportation.

8. The computer-implemented method of claim 1, wherein performing a plurality of identification iterations further comprises ceasing to perform identification iterations when the optimal transit trip determined by the previous identification iteration has a duration greater than a threshold duration, the threshold duration having been determined based on the first optimal transit trip determined at the first identification iteration.

9. The computer-implemented method of claim 1, further comprising:

forming a second transit graph based on selected of the plurality of trip patterns; and

performing at least one graph traversal algorithm with respect to the second transit graph.

10. The computer-implemented method of claim 9, further comprising adding one or more supplemental arcs to the second transit graph prior to performing the at least one graph traversal algorithm, the one or more supplemental arcs corresponding to walking routes between transit stations.

11. A non-transitory computer-readable medium storing instructions that when executed by one or more processors cause the one or more processors to perform operations comprising:

receiving transit graph data describing a plurality of arcs that correspond to transportation between transit stations, the plurality of arcs respectively interconnecting a plurality of nodes that respectively correspond to departure or arrival of the transportation at the transit stations;

defining a cost model such that a plurality of arc costs are respectively associated with the plurality of arcs;

determining a first shortest path between an origin node and a destination node based on the cost model, the first shortest path including one or more first solution arcs respectively connecting one or more pairs of first solution nodes;

revising the cost model to increase the arc cost associated with each arc connecting nodes corresponding to the same stations as one of the pairs of first solution nodes;

determining a second shortest path between the origin node and the destination node based on the revised cost model; and

displaying to a user at least one of the first shortest path and the second shortest path.

12. The computer-readable medium of claim 11, wherein revising the cost model to increase the arc cost associated with each arc connecting nodes corresponding to the same stations as one of the pairs of first solution nodes comprises increasing the arc cost associated with each arc connecting nodes corresponding to the same stations as one of the pairs of first solution nodes by an amount that is proportional to a duration associated with such arc.

13. The computer-readable medium of claim 11, storing further instructions for performing operations comprising, prior to determining the second shortest path:

identifying one or more transit lines respectively associated with the one or more first solution arcs; and

revising the cost model to increase the arc cost associated with each arc corresponding to the one or more transit lines.

14. The computer-readable medium of claim 11, storing further instructions for performing operations comprising:

determining a first trip pattern based on the first shortest path, the first trip pattern comprising a first sequence in which the first shortest path traverses the first pairs of solution nodes; and

determining a second trip pattern based on the second shortest path, the second trip pattern comprising a second sequence in which the second shortest path traverses one or more pairs of second solution nodes.

15. The computer-readable medium of claim 11, wherein:

the second shortest path includes one or more second solution arcs respectively connecting one or more pairs of second solution nodes; and

the computer-readable medium stores further instructions for performing operations comprising, after determining the second shortest path, building a directed graph comprising the one or more first solution arcs and the one or more second solution arcs.

16. A computing system comprising a memory and a processor, the computing system being configured to identify a plurality of trip patterns by performing operations comprising:

storing first transit graph data describing a first plurality of nodes interconnected by a first plurality of arcs;

performing a plurality of iterations to respectively determine a plurality of shortest paths between an origin and a destination according to a cost model respectively providing a plurality of arc costs for the first plurality of arcs;

wherein the cost model is revised following each iteration to increase one or more arc costs respectively associated with one or more arcs traversed by the shortest path determined in the previous iteration and wherein each iteration determines the shortest path based on the cost model as revised by the immediately preceding iteration such that a plurality of shortest paths are determined, each shortest path having an associated trip pattern describing a sequence of nodes traversed by such shortest path and wherein the trip pattern associated with each shortest path comprises a sequence of one or more pairs of solution nodes;

revising the cost model based on the determined shortest path, wherein revising the cost model comprises increasing the arc cost associated with each arc connecting nodes corresponding to the same nodes as one of the pairs of solution nodes; and

displaying to a user one or more of the determined shortest paths.

17. The computing system of claim 16, being configured to perform further operations comprising:

generating, based on the plurality of shortest paths, second transit graph data comprising a second plurality of nodes interconnected by a second plurality of arcs;

performing at least one graph traversal algorithm with respect to the second transit graph data; and

identifying the plurality of trip patterns based on the plurality of shortest paths and the performance of the at least one graph traversal algorithm.

18. The computing system of claim 17, wherein performing at least one graph traversal algorithm with respect to the second transit graph data comprises identifying all possible paths between a second origin and a second destination of the second transit graph data.

19. The computing system of claim 16, being configured to perform further operations comprising:

identifying a first plurality of trip patterns based on the plurality of shortest paths; and

identifying a second plurality of trip patterns by merging selected of the first plurality of trip patterns.