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

您可以在构建的较大图表上使用普通 Dijkstra 模型，如下所示：

• 节点由三元组描述(L, T, B)。每当公共汽车B到达或离开某个位置L时T，创建一个节点(L, T, B)。
• 为每个公交路线段创建有向边。也就是说，如果公共汽车在时间B离开位置并在时间到达位置，则添加边缘和成本（或任何其他合理的成本，可能取决于票价）。L1T1L2T2(L1, T1, B) -> (L2, T2, B)T2 - T1
• 添加与“在车站停留在公交车上”相对应的边。如果公共汽车在某个时间B到达某个位置，然后在某个时间从同一位置出发，则添加成本优势。LT1T2(L, T1, B) -> (L, T2, B)T2 - T1
• 添加与“切换总线”相对应的边。如果满足以下条件，则 添加一条从N1 = (L, T1, B1)到N2 = (L, T2, B2)且具有成本的有向边：T2 - T1 + epsilon
  • N1是一个“到达”节点（巴士B1到达L时间T1）
  • N2是一个“出发”节点（公交车在时间B2出发）LT2
  • T1 < T2和B1 != B2

在此图中，路径的成本是总时间加上c * epsilon其中c是总线变更次数。epsilon代表切换公交车的“成本”。例如，如果有人同样喜欢“留在公交车上”和“换乘公交车但节省 2 分钟”，那么epsilon应该是 2 分钟。

您还可以通过将S不等式修改为 来添加“最小切换时间” 。这将排除和非常接近以至于某人无法及时合理地切换总线的边缘。T1 < T2T1 + S < T2T1T2