Re: Bus/train timetable search algorithm
- From: Alex Fraser <me@xxxxxxxxxxx>
- Date: Mon, 10 Nov 2008 19:46:08 +0000
Patricia Shanahan wrote:
Alex Fraser wrote:[snip]adamwatson@xxxxxxxxxxxxx wrote:Does anyone know of public transport routing algorithms that use a
timetable and include changing between services?
>I'm left with a depth first exhaustive search, but I feel there must
be a better way.
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.
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.
How about making the weight the difference between the departure time and given start time?
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.
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
.
- References:
- Bus/train timetable search algorithm
- From: adamwatson
- Re: Bus/train timetable search algorithm
- From: Alex Fraser
- Bus/train timetable search algorithm
- Prev by Date: Re: Which is faster?
- Next by Date: Re: A question of programming technique in C
- Previous by thread: Re: Bus/train timetable search algorithm
- Next by thread: Re: Bus/train timetable search algorithm
- Index(es):
Relevant Pages
|
