Efficient route planning in public transportation networks

1. A method of selecting a path to reach a destination in a transportation network, the method comprising:

receiving, by a processing device, information related to a public transportation network including a plurality of stops, wherein each of the stops comprises at least one associated link with another one of the stops;

receiving, by the processing device, from a user via a user interface, a request to determine one or more routes to a destination within the transportation network, wherein the request comprises a selection of a primary mode of transit;

receiving, from a global positioning service, a point of origin;

identifying an alternate mode of transit and a configuration parameter;

determining, by the processing device, a plurality of routes through the transportation network between the point of origin and the destination using an iterative process without reference to a graph representation of the network, so that:

each of the plurality of routes comprises a first stop reachable via the alternate mode of transit without violating the configuration parameter, and

a departure time for each of the plurality of routes satisfies timing information provided by the user, wherein the timing information comprises at least a start time;

selecting, from the determined routes, a shortest path so that the shortest path corresponds to a route from the plurality of routes having an earliest arrival time at the destination;

selecting, from the determined routes, an alternative path so that the alternative path corresponds to a route having an arrival time that is no more than a threshold amount later than the earliest arrival time; and

generating, by the processing device, an output comprising the shortest path and the alternative path.

2. The method of claim 1 , wherein determining the plurality of routes comprises:

scanning at least one route from a first departure time;

determining a set of subsequently reachable stops from each first stop, and a possible arrival time for each subsequently reachable stop; and

repeating the scanning and determining until either a maximum number of iterations has been reached or no new subsequently reachable stops are identified.

3. The method of claim 2 , further comprising storing, by the processing device in a computer readable medium operably connected to the processing device, a portion of each route between the origin and the destination in which the subsequently reachable stop can be reached within a threshold time, while not retaining in the computer readable medium any routes in which the subsequently reachable stop cannot be reached within a threshold time.

4. The method of claim 1 , wherein the alternate mode of transit comprises walking, and the configuration parameter comprises a maximum walking time, a maximum walking distance, or both.

5. The method of claim 1 , further comprising storing, by the processing device, route information for a stop being scanned in a cache for access during a next iteration of the iterative process.

6. The method of claim 1 , wherein receiving the request to determine one or more routes between an origin and a destination within the transportation network further comprises receiving an alternate origin, and the method further comprises:

including, in the plurality of routes, at least one route between the alternate origin and the destination; and

when selecting the alternative path, selecting as the alternative path a route from the alternate origin to the destination.

7. The method of claim 1 , wherein selecting the alternative path comprises:

identifying at least one trip that makes up the shortest path; and

excluding the identified trip from the alternative path.

8. The method of claim 1 , further comprising returning the output to the user using one or more of the following:

email;

text; or

via a graphical user interface.

9. The method of claim 1 , wherein receiving the request to determine one or more routes between an origin and a destination within the transportation network further comprises receiving a departure time from the point of origin, and the method further comprises:

determining an earliest trip from the point of origin after the departure time using a binary search.

10. A system for selecting a path to reach a destination in a transportation network, the system comprising:

a processing device; and

a computer-readable storage medium containing information relating to a public transportation network including a plurality of stops, wherein each of the stops comprises at least one associated link with another one of the stops;

a computer-readable storage medium containing programming instructions that, when executed, cause the processing device to:

receive from a user, via a user interface, a request to determine one or more routes to a destination within the transportation network, wherein the request comprises a selection of a primary mode of transit;

receive, from a global positioning service, a point of origin;

identify an alternate mode of transit and a configuration parameter;

determine a plurality of routes through the transportation network between the point of origin and the destination using an iterative process without reference to a graph representation of the network, so that:

each of the plurality of routes comprises a first stop reachable via the alternate mode of transit without violating the configuration parameter, and

a departure time for each of the plurality of routes satisfies timing information provided by the user, wherein the timing information comprises at least a start time;

select, from the determined routes, a shortest path so that the shortest path corresponds to a route from the plurality of routes having an earliest arrival time at the destination;

select, from the determined routes, an alternative path so that the alternative path corresponds to a route having an arrival time that is no more than a threshold amount later than the earliest arrival time; and

generate an output comprising the shortest path and the alternative path.

11. The system of claim 10 , wherein the instructions to determine the plurality of routes comprise instructions to:

scan at least one route from a first departure time;

determine a set of subsequently reachable stops from each first stop, and a possible arrival time for each subsequently reachable stop; and

repeat the scanning and determining until either a maximum number of iterations has been reached or no new subsequently reachable stops are identified.

12. The system of claim 11 , further comprising instructions that cause the processing device to store, in a computer readable medium operably connected to the processing device, a portion of each route between the origin and the destination in which the subsequently reachable stop can be reached within a threshold time, while not retaining in the computer readable medium any routes in which the subsequently reachable stop cannot be reached within a threshold time.

13. The system of claim 10 , wherein the alternate mode of transit comprises walking, and the configuration parameter comprises a maximum walking time, a maximum walking distance, or both.

14. The system of claim 10 , further comprising storing, by the processing device, route information for a stop being scanned in a cache for access during a next iteration of the iterative process.

15. The system of claim 10 , wherein the instructions to receive the request to determine one or more routes between the point of origin and a destination within the transportation network further comprises instructions to enable the system to receive an alternate origin, and in response to receiving an alternate origin:

include, in the plurality of routes, at least one route between the alternate origin and the destination; and

when selecting the alternative path, select as the alternative path a route from the alternate origin to the destination.

16. The system of claim 10 , wherein the instructions to select the alternative path comprise instructions to:

identify at least one trip that makes up the shortest path; and

exclude the identified trip from the alternative path.

17. A method of selecting a path to reach a destination in a transportation network, the method comprising:

receiving, by a processing device, information related to a public transportation network including a plurality of stops, wherein each of the stops comprises at least one associated link with another one of the stops;

receiving, by the processing device, a request from a user, via a user interface, to determine one or more routes to a destination within the transportation network, wherein the request comprises a selection of a primary mode of transit;

receiving, from a global positioning service, a point of origin;

identifying an alternate mode of transit and a configuration parameter;

determining, by the processing device, a plurality of routes through the transportation network between the point of origin and the destination by:

scanning at least one route from a first departure time, wherein each route comprises a first stop,

determining a set of subsequently reachable stops from each first stop, and a possible arrival time for each subsequently reachable stop, and

repeating the scanning and determining until either a maximum number of iterations has been reached or no new subsequently reachable stops are identified, wherein:

each of the plurality of routes comprises a first stop reachable via the alternate mode of transit without violating the configuration parameter, and

a departure time for each of the plurality of routes satisfies timing information provided by the user, wherein the timing information comprises at least a start time;

selecting, from the determined routes, a shortest path so that the shortest path corresponds to a route from the plurality of routes having an earliest arrival time at the destination;

identifying at least one trip that makes up the shortest path;

selecting, from the determined routes, an alternative path so that the alternative path excludes the identified trip and corresponds to a route having an arrival time that is no more than a threshold amount later than the earliest arrival time; and

generating, by the processing device, an output comprising the shortest path and the alternative path.

18. The method of claim 17 , wherein receiving the request to determine one or more routes between the point of origin and a destination within the transportation network further comprises receiving an alternate origin, and the method further comprises:

including, in the plurality of routes, at least one route between the alternate origin and the destination; and

when selecting the alternative path, selecting as the alternative path a route from the alternate origin to the destination.