Time independent transit routing

• US 8,977,495 B1
• Filed: 10/27/2011
• Issued: 03/10/2015
• Est. Priority Date: 10/27/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Raychev, Veselin, Hurand, Mathilde Claire
• Primary Examiner(s): Nguyen, John Q
• Assistant Examiner(s): KIM, KYUNG J
• Application Number:
  US13/283,447
• Time in Patent Office: 1,230 Days
• Field of Search: 701/527
• US Class Current: 701/527
• 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

The subject matter of this specification can be implemented in, among other things, a method that includes receiving information identifying a start point and an end point in a transit system. The method further includes identifying transit routes between the start point and the end point. Each of the transit routes has one or more portions and each of the portions has one or more modes of transportation. The method further includes calculating a duration for each transit route in the transit routes. The duration is based on average amounts of time spent riding the modes of transportation in the portions of the transit route. The duration is based on a representation of an amount of time spent waiting for the modes of transportation in the portions of the transit route. The method further includes identifying one or more of the transit routes as optimal based on having shortest durations.

Claims

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

receiving information that identifies a start point and an end point in a transit system;

identifying transit routes between the start point and the end point, wherein each of the transit routes has one or more portions and each of the portions has one or more modes of transportation;

calculating a duration, within a daily period of operation, for each transit route in the transit routes, wherein the duration is representative of an amount of time spent getting from the start point to the end point using the transit route, wherein the duration is based on average amounts of time spent riding the modes of transportation in the portions of the transit route and an amount of time spent waiting for the modes of transportation in the portions of the transit route, wherein the representation of the amount of time spent waiting is based on numbers of trips that the modes of transportation make for the portions of the transit route for the daily period of operation, and wherein the duration is calculated based on an amount of time spent riding the modes of transportation for the specified portion, an amount of time spent riding a specified mode of transportation in the modes of transportation, and a number of trips by the specified mode of transportation, without accounting for any specific departure or arrival time and date of individual transit routes; and

identifying, irrespectively of any specific departure or arrival time and date of individual transit routes, an optimal one or more of the transit routes based on the optimal one or more of the transit routes having a shortest duration among the transit routes.

2. The method of claim 1, further comprising providing the one or more of the transit routes that are optimal to a computing device for presentation to a user.

3. The method of claim 2, wherein the numbers of trips that the modes of transportation make are for the daily period of operation of the modes of transportation.

4. The method of claim 3, wherein identifying the one or more of the transit routes that are optimal further comprises identifying one or more of the transit routes that have a least number of transfers in addition to having the shortest durations.

5. The method of claim 4, wherein the representation of the amount of time spent waiting is further based on an amount of time in the daily period of operation of the modes of transportation of each portion of each transit route divided by a sum of the numbers of trips for the modes of transportation of the portion.

6. The method of claim 5, wherein the average amounts of time spent riding the modes of transportation is a weighted average based on the numbers of trips for the modes of transportation.

7. The method of claim 6, wherein the duration for each transit route is further based on an amount of time spent getting to the modes of transportation in the transit route other than while riding the modes of transportation.

8. The method of claim 7, further comprising, prior to receiving the information that identifies the start point and the end point in the transit system, calculating and storing for each transit route in the transit routes one or more of:

the duration of the transit route, the amount of time in the daily period of operation of the modes of transportation in the portions of the transit route, the numbers of trips that the modes of transportation make for the portions of the transit route, the average amounts of time spent riding the modes of transportation in the portions of the transit route, and the representations of the amount of time spent waiting for the modes of transportation in the portions of the transit route.

9. A computer-implemented system for transit route planning, the system comprising:

a memory that stores data representing transit routes in a transit system, wherein each of the transit routes has one or more portions and each of the portions has one or more modes of transportation;

an interface that receives, from a computing device, data that identifies a start point and an end point in the transit system;

a route identification module that identifies one or more of the stored transit routes as going from the start point to the end point;

a route calculation module that calculates a duration, within a daily period of operation, for each transit route in the identified transit routes, wherein the duration is representative of an amount of time spent getting from the start point to the end point using the transit route, wherein the duration is based on average amounts of time spent riding the modes of transportation in the portions of the transit route and a representation of an amount of time spent waiting for the modes of transportation in the portions of the transit route, wherein the representation of the amount of time spent waiting is based on numbers of trips that the modes of transportation make for the portions of the transit route for the daily period of operation, and wherein the duration is calculated based on an amount of time spent riding the modes of transportation for the specified portion, an amount of time spent riding a specified mode of transportation in the modes of transportation, and a number of trips by the specified mode of transportation, without accounting for any specific departure or arrival time and date of individual transit routes; and

a route optimization module that identifies, irrespectively of any specific departure or arrival time and date of individual transit routes, an optimal one or more of the identified transit routes based on the optimal one or more of the identified transit routes having a shortest duration among the transit routes.

10. The system of claim 9, wherein the route optimization module provides the one or more of the identified transit routes that are optimal to the computing device through the interface.

11. The system of claim 10, wherein the numbers of trips that the modes of transportation make are for the daily period of operation of the modes of transportation.

12. The system of claim 11, wherein the route optimization module further identifies the one or more of the identified transit routes that are optimal based on having a fewest number of transfers.

13. The system of claim 12, wherein the representation of the amount of time spent waiting is further based on an amount of time in the daily period of operation of the modes of transportation of each portion of each transit route divided by a sum of the numbers of trips for the modes of transportation of the portion.

14. The system of claim 13, wherein the average amounts of time spent riding the modes of transportation is a weighted average based on the numbers of trips for the modes of transportation.

15. The system of claim 14, wherein the duration for each transit route is further based on an amount of time spent getting to the modes of transportation in the transit route other than while riding the modes of transportation.

16. The system of claim 15, wherein, prior to receiving the information that identifies the start point and the end point in the transit system, the route calculation module calculates and stores for each transit route in the stored transit routes one or more of:

the duration of the transit route, the amount of time in the daily period of operation of the modes of transportation in the portions of the transit route, the numbers of trips that the modes of transportation make for the portions of the transit route, the average amounts of time spent riding the modes of transportation in the portions of the transit route, and the representations of the amount of time spent waiting for the modes of transportation in the portions of the transit route.

17. A computer-readable medium comprising instructions that, when executed by a computer, cause the computer to perform a method for transit route planning, the method comprising:

receiving information that identifies a start point and an end point in a transit system;

identifying transit routes between the start point and the end point, wherein each of the transit routes has one or more portions and each of the portions has one or more modes of transportation;

calculating a duration, within the daily period of operation, for each transit route in the transit routes, wherein the duration is representative of an amount of time spent getting from the start point to the end point using the transit route, wherein the duration is based on a representation of an amount of time spent waiting for and riding the modes of transportation in the portions of the transit route the amount of time spent waiting is based on numbers of trips that the modes of transportation make for the portions of the transit route for the daily period of operation, and wherein the duration is calculated based on an amount of time spent riding the modes of transportation for the specified portion, an amount of time spent riding a specified mode of transportation in the modes of transportation, and a number of trips by the specified mode of transportation, without accounting for any specific departure or arrival time and date of individual transit routes; and

identifying, irrespectively of any specific departure or arrival time and date of individual transit routes, an optimal one or more of the transit routes based on the optimal one or more of the transit routes having a shortest duration among the transit routes.

18. The computer-readable medium of claim 17, wherein identifying the one or more of the transit routes that are optimal further comprises identifying one or more of the transit routes that have a least number of transfers in addition to having the shortest durations.

19. The computer-readable medium of claim 17, wherein the numbers of trips that the modes of transportation make are for the daily period of operation of the modes of transportation.

20. The computer-readable medium of claim 19, wherein the representation of the amount of time spent waiting is further based on an amount of time in the daily period of operation of the modes of transportation of each portion of each transit route divided by a sum of the numbers of trips for the modes of transportation of the portion.

21. The computer-readable medium of claim 17, wherein the duration is based on average amounts of time spent riding the modes of transportation in the portions of the transit route, and wherein the average amounts of time spent riding the modes of transportation is a weighted average based on the numbers of trips for the modes of transportation.

22. A computer-implemented system for transit route planning, the system comprising:

a memory that stores data representing transit routes in a transit system, wherein each of the transit routes has one or more portions and each of the portions has one or more modes of transportation;

an interface that receives, from a computing device, data that identifies a start point and an end point in the transit system;

a route identification module that identifies one or more of the stored transit routes as going from the start point to the end point;

a route calculation module that calculates a duration, within a daily period of operation, for each transit route in the identified transit routes, wherein the duration is representative of an amount of time spent getting from the start point to the end point using the transit route, wherein the duration is based on a representation of an amount of time spent waiting for and riding the modes of transportation in the portions of the transit route the amount of time spent waiting is based on numbers of trips that the modes of transportation make for the portions of the transit route for the daily period of operation, and wherein the duration is calculated

based on an amount of time spent riding the modes of transportation for the specified portion, an amount of time spent riding a specified mode of transportation in the modes of transportation, and a number of trips by the specified mode of transportation, without accounting for any specific departure or arrival time and date of individual transit routes; and

a route optimization module that identifies, irrespectively of any specific departure or arrival time and date of individual transit routes, an optimal one or more of the identified transit routes based on the optimal one or more of the identified transit routes having a shortest duration among the transit routes.

23. The system of claim 22, wherein the route optimization module further identifies the one or more of the identified transit routes that are optimal based on having a fewest number of transfers.

24. The system of claim 22, wherein the numbers of trips that the modes of transportation make are for the daily period of operation of the modes of transportation.

25. The system of claim 24, wherein the representation of the amount of time spent waiting is further based on an amount of time in the daily period of operation of the modes of transportation of each portion of each transit route divided by a sum of the numbers of trips for the modes of transportation of the portion.

26. The system of claim 22, wherein the duration is based on average amounts of time spent riding the modes of transportation in the portions of the transit route, and wherein the average amounts of time spent riding the modes of transportation is a weighted average based on the numbers of trips for the modes of transportation.