Adjusting Dijkstra for transit routing — minimize route changes

Question

I am working on a small project that involves finding the best route on a bus system. I build a graph where the stops are vertices and the edges are weighted with the time between stops.

I though I would try to use a variant of Dijkstra to find the best route. When finding the next edges to consider, the algorithm only looks at edges whose departure time as after the current time along the trip. There are several parts of the graph where buses arrive and depart the same series of series of stops simultaneously. To prevent needlessly switching buses, I add a cost to route changes when selecting the best edge. This has worked surprisingly well and is quite fast.

The snag I've hit is on choosing the first bus. Consider the following scenario:

Dijkstra will favor taking bus A because it arrives at stop 2 first. If you're going to stop 2 that's great. But if you're going to stop 3, Bus B is a better choice and the total cost for both are identical. I don't think I can avoid the greedy nature of Dijkstra, but it's working so well for everything else, I don't want to discard it if I don't need to.

Does any know a good solution that can address the issue of correctly picking the first stop (or maybe adjusting it after the fact?). Alternatively is there a better algorithm that people use for this kind of problem?

Answer 1

Sounds like you need to add the cost of transfer to your graph.

First thing that comes to my mind, probably not a best solution is to add extra nodes around your stops. So instead of StopB you would have

Stop-B get off Bus-A Stop-B Stop-B get on Bus-B

You would have to do it to all the buses on for each stop.

Probably there are better options. This is first thing I could come up with in 2 minutes.

Answer 2

You can use plain Dijkstra's on a larger graph constructed as follows:

• Nodes are described by triples (L, T, B). Every time a bus B arrives or departs from location L at time T, create a node (L, T, B).
• Create a directed edge for every bus route segment. That is, if bus B departs from location L1 at time T1 and arrives at location L2 at time T2, add the edge (L1, T1, B) -> (L2, T2, B), with cost T2 - T1 (or any other reasonable cost, maybe depending on the fare).
• Add edges corresponding to "staying on the bus at a stop". If bus B arrives at a location L at time T1 and later departs from the same location at time T2, add the edge (L, T1, B) -> (L, T2, B) with cost T2 - T1.
• Add edges corresponding to "switching buses". Add a directed edge from N1 = (L, T1, B1) to N2 = (L, T2, B2) with cost T2 - T1 + epsilon if the following is true:
  • N1 is an "arrival" node (bus B1 arrives at L at time T1)
  • N2 is a "departure" node (bus B2 departs from L at time T2)
  • T1 < T2 and B1 != B2

In this graph, the cost of a path is the total time plus c * epsilon where c is the number of bus changes. epsilon represents the "cost" of switching buses. For instance, if someone equally prefers "stay on the bus" and "switch buses but save 2 minutes", then epsilon should be 2 minutes.

You can also add a "minimum switching time" S by modifying the inequality T1 < T2 to T1 + S < T2. This will exclude edges where T1 and T2 are so close that someone can't reasonably switch buses in time.