Guidebook Transit Routing

• US 20140343852A1
• Filed: 05/14/2013
• Published: 11/20/2014
• Est. Priority Date: 05/14/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Pech, Lucien, Graells, Albert
• Granted Patent: US 9,217,647 B2
• Time in Patent Office: Days
• US Class Current: 701/540
• 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

Abstract

Systems and methods for recommending time independent or “guidebook” transit routes between an origin and a destination are provided. A score is generated for each transit route. The score can be used to evaluate and prioritize the transit routes so that one or more transit routes can be recommended to a user. The score can be computed based on characteristics of a trip duration function generated for the transit route. The trip duration function specifies a trip cost (e.g. a trip duration) for the transit route as a function of time (such as departure time or arrival time) over the time interval. The trip duration function can be a piecewise linear function with one or more linear trip segments. Each linear trip segment models the trip cost, including waiting time, of a transit trip associated with the transit route over at least a portion of the time interval.

Claims

1. A computer-implemented method of transit route planning, comprising:

identifying a plurality of time independent transit routes between an origin and a destination, each of the time independent transit routes comprising a plurality of trips over a time interval, each of the time independent transit routes comprising one or more modes of transportation;

generating a trip duration function for each of the plurality of time independent transit routes, the trip duration function specifying a trip cost as a function of time over the time interval, the trip duration function being a piecewise linear function comprising a plurality of linear trip segments, each linear trip segment modeling the trip cost, including waiting time, of one of the plurality of trips in the time independent transit route as a function of time;

computing, with a processing device, a score for each of the plurality of time independent transit routes based at least in part on an average cost of the time independent transit route over the time interval, the average cost being calculated using the trip duration function; and

storing the score for each of the plurality of time independent transit routes in a memory.

2. The computer-implemented method of claim 1, wherein the scores for the plurality of time independent transit routes prioritize the time independent transit routes with smaller average costs.

3. The computer-implemented method of claim 2, wherein the method comprises:

receiving a request for transit routes between the origin and the destination;

accessing the score for each of the plurality of time independent transit routes; and

selecting one or more of the plurality of time independent transit routes to respond to the request based on the score for each of the plurality of time independent transit routes.

4. The computer-implemented method of claim 1, wherein the trip duration function specifies the trip cost for the time independent transit route as a function of departure time over the time interval.

5. The computer-implemented method of claim 4, wherein one or more of the plurality of linear trip segments has a slope of −

1 to model the trip cost, including waiting time, of one of the plurality of trips as a function of departure time.

6. The computer-implemented method of claim 1, wherein the trip duration function specifies the trip cost for the time independent transit route as a function of arrival time over the time interval.

7. The computer-implemented method of claim 6, wherein one or more of the plurality of linear trip segments has a slope of 1 to model the trip cost, including waiting time, of one of the plurality of trips as a function of arrival time.

8. The computer-implemented method of claim 1, wherein the plurality of trips for at least one of the plurality of time independent transit routes comprises a frequency based transit trip.

9. The computer-implemented method of claim 8, wherein one of the plurality of linear trip segments of the trip duration function models the frequency based transit trip as a constant trip cost over at least a portion of the time interval.

10. The computer-implemented method of claim 1, wherein the average cost of the time independent transit route over the time interval is computed by determining an area between the trip duration function and a horizontal axis and dividing the area by a span of the time interval.

11. The computer-implemented method of claim 1, wherein the trip cost is based at least in part on a trip duration.

12. The computer-implemented method of claim 1, wherein the trip cost is based at least in part on a trip duration and a penalty.

13. The computer-implemented method of claim 12, wherein the penalty is based at least in part on walking time or walking distance associated with the time independent transit route.

14. The computer-implemented method of claim 12, wherein the penalty is based at least in part on the number of transfers or pricing associated with the time independent transit route.

15. A computing system for transit route planning, the computing system comprising at least one processor and a memory, the system comprising:

a transit route identification module implemented by the at least one processor, the transit route identification module configured to identify a plurality of time independent transit routes between an origin and a destination, each of the time independent transit routes comprising a plurality of trips over a time interval, each of the transit routes comprising one or more modes of transportation;

a route calculation module implemented by the processor, the route calculation module configured to generate a trip duration function for each of the plurality of time independent transit routes, the route calculation module further configured to determine an average cost of each time independent transit route based on the trip duration function for the time independent transit route; and

a route ranking module implemented by the processor, the route ranking module configured to compute a score for each of the plurality of time independent transit routes based on the average cost determined for the time independent transit route using based on the trip duration function, the route ranking module further configured to store the score in the memory;

wherein the trip duration function for each time independent transit route specifies a trip cost for the time independent transit route as a function of time over the time interval, the trip duration function being a piecewise linear function comprising a plurality of linear trip segments, each linear trip segment modeling the trip cost, including waiting time, of one of the plurality of trips in the time independent transit route as a function of time.

16. The computing system of claim 15, wherein the scores for the plurality of time independent transit routes prioritize the time independent transit routes with smaller average costs.

17. The computing system of claim 15, wherein the system further comprises an interface for receiving a request for transit routes between the origin and the destination, the system comprising a route selection module configured to select one or more of the plurality of time independent transit routes to respond to the request based on the score for each of the

18. The computing system of claim 15, wherein the trip cost is based at least in part on a trip duration and a penalty.

19. A computer-program product comprising a non-transitory computer readable storage medium storing computer-readable instructions for transit route planning, the instructions when executed by a processor, cause the processor to perform operations, the operations comprising:

receiving a request for transit routes between an origin and a destination;

identifying a plurality of time independent transit routes between the origin and the destination, each of the time independent transit routes comprising a plurality of trips over a time interval, each of the time independent transit routes comprising one or more modes of transportation;

accessing an average cost over the time interval for each of the plurality of time independent transit routes, the average cost for each of the plurality of time independent transit routes being calculated using a trip duration function associated with the time independent transit route; and

selecting one or more of the plurality of time independent transit routes to respond to the request based on the average cost for each of the plurality of time independent transit routes;

wherein the trip duration function associated with each time independent transit route specifies a trip cost for the time independent transit route as a function of time over the time interval, the trip duration function being a piecewise linear function comprising a plurality of linear trip segments, each linear trip segment modeling a trip cost, including waiting time, of one of the plurality of trips in the time independent transit route as a function of time.

20. The computer-program product of claim 19, wherein the average cost is computed by determining an area between the trip duration function and a horizontal axis and dividing the area by a span of the time interval.