2

I'm trying to implement a system of reading coach timetables to plan a journey.

Here's my scenario:
I'd like to just enter a travel date, a start station and an end station, but to get from A to B, there could be 3 or 4 connecting journeys involved, and I'd like to return several options, ordered by total time required. My database set up has a table for stations, a table for journeys and a table for journey instances (i.e. containing inclusive dates of operation of journeys).

I've got a good implementation in c# of Dijkstra's algorithm, but I find it's limited as I can't figure out how to include time for waiting at bus stations for connecting journeys, and the fact that many journeys can go from one station to another at different times is adding to the confusion. I also have to take into account if the journey takes a day or even 2 to complete, which has proved troublesome. Is Dijkstra's worth persevering with here, or does anyone know of something else that might be better suited?

I'm using asp.net MVC3, C# and EF4, but it's not so much code I'm after here - more just a point in the right direction of the process I'd be best using, as this is well beyond anything I've done before. (I possibly bit off more than I could chew when I volunteered for this project!) If anyone could offer some advice, or a link to some documentation that could help with this situation, that would help enormously. Thanks

e-on
  • 1,547
  • 8
  • 32
  • 65

2 Answers2

3

First off: good on you for volunteering on an ambitious project. Secondly: this may be a tad challenging, and judging from another StackOverflow post linked below: NP-Complete.

Dijkstra's algorithm finds single-source shortest paths on a static graph, but that's not what you're doing in this problem. Since the vertices in such a graph will probably exist in overlapping temporal spaces, the fastest bus from a1 to a2 may leave at 12:00 pm, but the fastest bus from a2 to a3 may leave at 11:59 am the same day. That's a non-starter.

Obviously, you've thought about this, but an abstract way of looking at the problem is that you're not trying to find the shortest path in a graph, but you're trying to find the shortest path in what is effectively three-dimensional space (time as the third dimension). A brute force approach (which is nonetheless fine for small graphs) could be implemented as a breadth first search, assuming you topologically order the nodes according to time.

Related link is here: Bus public transport algorithm

Some reading on the topic:

May the Force be with you.

Community
  • 1
  • 1
Brandon
  • 308
  • 1
  • 2
  • 10
  • Hi Brandon - thanks very much. Currently reading through the paper on Multi Modal Route Planning found on the SO link you added above. Will report back later... – e-on Feb 23 '12 at 10:19
0

It is indeed possible to modify Dijkstra to find the quickest route from station A to station B, also taking into account the departure time and required waiting at intermediate stations. It is not, as the other answer claims, NP-complete. In the following, I'm going to assume the bus schedule is periodic (ie. repeats indefinitely), but it should actually suffice to, for each time of day, for each bus stop and for and each line (journey) visiting the bus stop, quickly find the next departure (journey instance).

We model the problem as a directed multigraph: The bus stops are vertices of my graph, and an edge in my graph is a trip from one bus stop to another by some bus line. An edge is formally a tuple (u_a, u_b, id, f, w, r) where

  • u is the source vertex
  • v is the destination vertex
  • id is the journey id (needed to retrieve an actual solution - left as an exercise)
  • f is the first departure time
  • w is the travel time
  • r is the repeat interval (We assume f < r, but this can be fixed if needed)

For each vertex, we will (as in normal Dijkstra), maintain at least two values: Firstly, we will remember whether we have processed this vertex yet or not. Secondly, we will maintain the earliest currently known arrival time for this location, including information about which edge was the last one used to obtain this potential arrival time. For the startpoint, the earliest arrival time is initially the desired departure time, and for all other vertices the initial arrival time is infinity.

Dijkstra may then proceed as normal: Greedily pick the unprocessed vertex with the earliest arrival time, say vertex u with arrival time t. Then process this vertex: For each of its out-edges, calculate the earliest time it is possible to reach the destination vertex v: t' = t + ((r + f - (t % r)) % r) + w (think about it; if f >= (t % r), then f - (t % r) is the waiting time). If t' is smaller than or equal to the arrival time already known for v, set the arrival time of v to t' and add this edge to the set of possible source edges to obtain this arrival time (if it was strictly smaller, delete all others first).

Try it out in practice here: https://open.kattis.com/problems/shortestpath2

tor
  • 636
  • 3
  • 7
  • 18