Systems and methods for generating a plurality of trip patterns
First Claim
1. A computer-implemented method of determining a plurality of trip patterns, the method comprisingreceiving, 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 Assignments
0 Petitions
Accused Products
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.
-
Citations
19 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15)
-
-
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. - View Dependent Claims (17, 18, 19)
-
Specification