Bus/train timetable search algorithm - Programming Languages

If you add dummy edges at the intermediate stages with weights of the
expected layovers, Dijkstra's algorithm should work.
For example, one could route from New Orleans to Minneapolis
vi Chicago as (with guessed-at times):

New Orleans --- 12 hrs --- Chi1 -- 4 hrs -- Chi2 -- 4 hrs -- Minn

Chi1 and Ch2 are two nodes representing Union Station arrival and
departure respectively.

john slimick
[email]slimick@pitt.edu[/email]

======================================================================

On 2008-11-06, [email]adamwatson@sogetthis.com[/email] <adamwatson@sogetthis.com> wrote:[color=blue]
> Does anyone know of public transport routing algorithms that use a
> timetable and include changing between services?
>
> A breadth first search is easy to implement for small datasets and a
> limited number of interchanges, but rapidly becomes unmanageable.
>
> Something like Dijkstra's algorithm isn't obviously applicable because
> the quickest route does not necessarily comprise of the quickest
> intermediate stages.
>
> I'm left with a depth first exhaustive search, but I feel there must
> be a better way.[/color]

[email]adamwatson@sogetthis.com[/email] wrote:[color=blue]
> Does anyone know of public transport routing algorithms that use a
> timetable and include changing between services?
>
> A breadth first search is easy to implement for small datasets and a
> limited number of interchanges, but rapidly becomes unmanageable.
>
> Something like Dijkstra's algorithm isn't obviously applicable because
> the quickest route does not necessarily comprise of the quickest
> intermediate stages.[/color]

Not only that, but the time between two stops may vary in duration.
Basically the onward journey from a node depends on the arrival time at
that node, which is a function of the starting time and route taken.
[color=blue]
> I'm left with a depth first exhaustive search, but I feel there must
> be a better way.[/color]

I think in practice an exhaustive search would often not be practical,
requiring some sort of approximation instead.

You can use the timetables to construct a graph where the edge weights
are the lower bound of the time to get between the nodes. The simplest
way would be a directed graph with one edge per unique combination of
places A and B where B immediately follows A in a timetable. An
undirected graph - with one edge where either A follows B or B follows A
- would be more compact and generally nearly equivalent, but may include
some impossible hops.

Given this, you can use Dijkstra's algorithm on the graph to find the
quickest "theoretical" route from starting point to destination. Then
tweak the graph: increase the weights of the edges traversed in the
route by some factor, remove edges, etc (I'm not sure what rules would
work best). Use Dijkstra's algorithm again to find a possible
alternative route. Repeat a few times.

From the above you can create a new, (hopefully much) smaller graph
comprising all the nodes/edges that were visited/traversed in the
quickest routes, which should be amenable to an exhaustive search -
taking into account start time, timetables, minimum connection times,
and anything else you want.

Alex

Alex Fraser wrote:[color=blue]
> [email]adamwatson@sogetthis.com[/email] wrote:
>[color=green]
>> Does anyone know of public transport routing algorithms that use a
>> timetable and include changing between services?
>>
>> A breadth first search is easy to implement for small datasets and a
>> limited number of interchanges, but rapidly becomes unmanageable.
>>
>> Something like Dijkstra's algorithm isn't obviously applicable because
>> the quickest route does not necessarily comprise of the quickest
>> intermediate stages.[/color]
>
>
> Not only that, but the time between two stops may vary in duration.
> Basically the onward journey from a node depends on the arrival time at
> that node, which is a function of the starting time and route taken.
>[color=green]
>> I'm left with a depth first exhaustive search, but I feel there must
>> be a better way.[/color]
>
>
> I think in practice an exhaustive search would often not be practical,
> requiring some sort of approximation instead.
>
> You can use the timetables to construct a graph where the edge weights
> are the lower bound of the time to get between the nodes. The simplest
> way would be a directed graph with one edge per unique combination of
> places A and B where B immediately follows A in a timetable. An
> undirected graph - with one edge where either A follows B or B follows A
> - would be more compact and generally nearly equivalent, but may include
> some impossible hops.
>
> Given this, you can use Dijkstra's algorithm on the graph to find the
> quickest "theoretical" route from starting point to destination. Then
> tweak the graph: increase the weights of the edges traversed in the
> route by some factor, remove edges, etc (I'm not sure what rules would
> work best). Use Dijkstra's algorithm again to find a possible
> alternative route. Repeat a few times.
>
> From the above you can create a new, (hopefully much) smaller graph
> comprising all the nodes/edges that were visited/traversed in the
> quickest routes, which should be amenable to an exhaustive search -
> taking into account start time, timetables, minimum connection times,
> and anything else you want.
>
> Alex[/color]

I think there may be a simpler approach. For simplicity, I'm going to
use "flight" to mean a single, non-stop segment. Flight A "connects to"
flight flight B if B departs from A's destination, does so long enough
after A arrives that a passenger arriving on A could catch B, and B is
the earliest flight to B's destination that meets those conditions.

Create a graph with the following nodes:

A "flight" node for each flight.

A "start" node for the starting point.

An "end" node for each destination.

Create the following edges;

For each pair of flights A and B such that A connects to B, create an
edge connecting A's flight node to B's flight node, with weight equal to
the difference in their departure times.

For each flight A that departs from the starting node in the original
graph, create a zero weight edge from the start node to A's flight node.

For each flight A, create an edge with weight equal to A's duration from
A's flight node to the end node for its destination.

Apply Dijkstra's algorithm to the new graph.

Each path from the start node to an end node represents an itinerary
starting from the original start node, and using a series of connecting
flights to reach the node corresponding to its end. The total weight is
the total travel time for the itinerary, from departure of the first
flight to arrival of the last one, so the shortest path corresponds to
the fastest itinerary.

It is not possible to give the complexity of this approach without some
model for the number of flights as a function of the number of nodes in
the original graph.

Patricia

Patricia Shanahan wrote:[color=blue]
> Alex Fraser wrote:[color=green]
>> [email]adamwatson@sogetthis.com[/email] wrote:[color=darkred]
>>> Does anyone know of public transport routing algorithms that use a
>>> timetable and include changing between services?[/color][/color][/color]
[snip][color=blue][color=green][color=darkred]
>>> I'm left with a depth first exhaustive search, but I feel there must
>>> be a better way.[/color]
>>
>> I think in practice an exhaustive search would often not be practical,
>> requiring some sort of approximation instead.
>>
>> You can use the timetables to construct a graph where the edge weights
>> are the lower bound of the time to get between the nodes. The simplest
>> way would be a directed graph with one edge per unique combination of
>> places A and B where B immediately follows A in a timetable. An
>> undirected graph - with one edge where either A follows B or B follows
>> A - would be more compact and generally nearly equivalent, but may
>> include some impossible hops.
>>
>> Given this, you can use Dijkstra's algorithm on the graph to find the
>> quickest "theoretical" route from starting point to destination. Then
>> tweak the graph: increase the weights of the edges traversed in the
>> route by some factor, remove edges, etc (I'm not sure what rules would
>> work best). Use Dijkstra's algorithm again to find a possible
>> alternative route. Repeat a few times.
>>
>> From the above you can create a new, (hopefully much) smaller graph
>> comprising all the nodes/edges that were visited/traversed in the
>> quickest routes, which should be amenable to an exhaustive search -
>> taking into account start time, timetables, minimum connection times,
>> and anything else you want.[/color]
>
> I think there may be a simpler approach. For simplicity, I'm going to
> use "flight" to mean a single, non-stop segment. Flight A "connects to"
> flight flight B if B departs from A's destination, does so long enough
> after A arrives that a passenger arriving on A could catch B, and B is
> the earliest flight to B's destination that meets those conditions.
>
> Create a graph with the following nodes:
>
> A "flight" node for each flight.
>
> A "start" node for the starting point.
>
> An "end" node for each destination.
>
> Create the following edges;
>
> For each pair of flights A and B such that A connects to B, create an
> edge connecting A's flight node to B's flight node, with weight equal to
> the difference in their departure times.
>
> For each flight A that departs from the starting node in the original
> graph, create a zero weight edge from the start node to A's flight node.[/color]

How about making the weight the difference between the departure time
and given start time?
[color=blue]
> For each flight A, create an edge with weight equal to A's duration from
> A's flight node to the end node for its destination.
>
> Apply Dijkstra's algorithm to the new graph.[/color]

With the change above, I think this would now give you the route with
the earliest arrival based on the given start time.

I like the idea!

Alex

> For each pair of flights A and B such that A connects to B, create an[color=blue]
> edge connecting A's flight node to B's flight node, with weight equal to
> the difference in their departure times.
>
> For each flight A that departs from the starting node in the original
> graph, create a zero weight edge from the start node to A's flight node.
>
> For each flight A, create an edge with weight equal to A's duration from
> A's flight node to the end node for its destination.
>
> Apply Dijkstra's algorithm to the new graph.[/color]

This is roughly what I've come up with. The trouble is that there are
approximately 30 million "flights" for a city like London and, on
average, each "flight" connects with 8 others within a reasonable
distance/time.

It's usually possible to simplify the problem by sub-selecting a
particular time of day.