Adjusting Dijkstra for transit routing——最小化路线变化
Adjusting Dijkstra for transit routing — minimize route changes
我正在做一个小项目，涉及在公交系统上寻找最佳路线。我建立了一个图表，其中停靠点是顶点，边缘用停靠点之间的时间加权。
虽然我会尝试使用 Dijkstra 的变体来找到最佳路线。在寻找要考虑的下一条边时，该算法仅查看出发时间晚于行程当前时间的边。图中有几个部分，公交车同时到达和离开同一系列的停靠站。为了防止不必要地切换总线，我在选择最佳边缘时增加了路由更改的成本。这出奇地好，而且速度非常快。
我遇到的问题是选择第一班车。考虑以下情况：
Dijkstra 更喜欢乘坐 A 路公交车，因为它先到达 2 号站。如果你要停止 2 那太好了。但如果你要停 3，Bus B 是更好的选择，而且两者的总费用是相同的。我认为我无法避免 Dijkstra 的贪婪本性，但它对其他一切都非常有效，如果不需要，我不想丢弃它。
有没有人知道可以解决正确选择第一站的问题的好的解决方案（或者可能在事后调整它？）。或者，是否有更好的算法供人们用于此类问题？
听起来您需要将传输成本添加到图表中。
我想到的第一件事可能不是最好的解决方案是在停靠点周围添加额外的节点。所以你会
而不是 StopB
B站-A站下车
停止-B
B站上车B
您必须对每一站的所有公交车执行此操作。
可能有更好的选择。这是我在 2 分钟内想到的第一件事。
您可以在按如下方式构造的较大图上使用普通 Dijkstra：
- 节点由三元组描述
(L, T, B)。每次公交车 B 在时间 T 到达或离开位置 L 时，创建一个节点 (L, T, B).
- 为每个公交线路段创建一条有向边。也就是说，如果公交车
B在时间T1从位置L1出发，在时间T2到达位置L2，添加边(L1, T1, B) -> (L2, T2, B) ，成本 T2 - T1（或任何其他合理的成本，可能取决于票价）。
- 添加对应于 "staying on the bus at a stop" 的边。如果公交车
B 在时间 T1 到达位置 L，然后在时间 T2 从同一位置出发，请添加边 (L, T1, B) -> (L, T2, B)，成本为 T2 - T1.
- 添加对应于 "switching buses" 的边。如果满足以下条件，则添加一条从
N1 = (L, T1, B1) 到 N2 = (L, T2, B2) 且成本 T2 - T1 + epsilon 的有向边：
N1 是一个 "arrival" 节点（总线 B1 在时间 T1 到达 L）N2 是一个 "departure" 节点（公交车 B2 在时间 T2 从 L 出发）T1 < T2 和 B1 != B2
在此图中，一条路径的成本是总时间加上 c * epsilon，其中 c 是总线变化的次数。 epsilon表示切换总线的"cost"。例如，如果有人同样喜欢 "stay on the bus" 和 "switch buses but save 2 minutes"，那么 epsilon 应该是 2 分钟。
您还可以通过将不等式 T1 < T2 修改为 T1 + S < T2 来添加 "minimum switching time" S。这将排除 T1 和 T2 非常接近以至于某人无法及时合理地切换总线的边缘。
另一个提案
而不是添加节点。你可以只是更多的边缘。而不是像下面这样表示巴士路线 (A -> B -> C)：
A -> B
A -> C
B -> C
对于每条边，您都会增加上车和下车所需的成本时间。
答案真的很有帮助。我最终做了一些不同的事情，但受到这里的想法的启发。基本上每个站点都有 'exits' 分配给每条公交路线，边缘从站点引出。为了让公共汽车 A 到达第 3 站，它需要进入第 2 站，然后从 'B' 出口离开。进入车站的边缘会产生额外费用。如果路线匹配，公交车可以免费绕过车站。所以公共汽车 'B' 永远不需要进入第 2 站去第 3 站，但公共汽车 A 需要。
这允许任何一辆公共汽车成为到达第 2 站的最短路线，并允许两辆公共汽车到达第 3 站。但是如果你要从第 1 站去第 3 站，从公共汽车 B 开始将是最便宜的路线，因为它不需要经过车站，产生额外的费用。
我正在做一个小项目，涉及在公交系统上寻找最佳路线。我建立了一个图表，其中停靠点是顶点，边缘用停靠点之间的时间加权。
虽然我会尝试使用 Dijkstra 的变体来找到最佳路线。在寻找要考虑的下一条边时，该算法仅查看出发时间晚于行程当前时间的边。图中有几个部分，公交车同时到达和离开同一系列的停靠站。为了防止不必要地切换总线，我在选择最佳边缘时增加了路由更改的成本。这出奇地好，而且速度非常快。
我遇到的问题是选择第一班车。考虑以下情况：
Dijkstra 更喜欢乘坐 A 路公交车，因为它先到达 2 号站。如果你要停止 2 那太好了。但如果你要停 3，Bus B 是更好的选择，而且两者的总费用是相同的。我认为我无法避免 Dijkstra 的贪婪本性，但它对其他一切都非常有效，如果不需要，我不想丢弃它。
有没有人知道可以解决正确选择第一站的问题的好的解决方案（或者可能在事后调整它？）。或者，是否有更好的算法供人们用于此类问题？
听起来您需要将传输成本添加到图表中。
我想到的第一件事可能不是最好的解决方案是在停靠点周围添加额外的节点。所以你会
而不是 StopBB站-A站下车 停止-B B站上车B
您必须对每一站的所有公交车执行此操作。
可能有更好的选择。这是我在 2 分钟内想到的第一件事。
您可以在按如下方式构造的较大图上使用普通 Dijkstra：
- 节点由三元组描述
(L, T, B)。每次公交车B在时间T到达或离开位置L时，创建一个节点(L, T, B). - 为每个公交线路段创建一条有向边。也就是说，如果公交车
B在时间T1从位置L1出发，在时间T2到达位置L2，添加边(L1, T1, B) -> (L2, T2, B)，成本T2 - T1（或任何其他合理的成本，可能取决于票价）。 - 添加对应于 "staying on the bus at a stop" 的边。如果公交车
B在时间T1到达位置L，然后在时间T2从同一位置出发，请添加边(L, T1, B) -> (L, T2, B)，成本为T2 - T1. - 添加对应于 "switching buses" 的边。如果满足以下条件，则添加一条从
N1 = (L, T1, B1)到N2 = (L, T2, B2)且成本T2 - T1 + epsilon的有向边：N1是一个 "arrival" 节点（总线B1在时间T1到达L）N2是一个 "departure" 节点（公交车B2在时间T2从L出发）T1 < T2和B1 != B2
在此图中，一条路径的成本是总时间加上 c * epsilon，其中 c 是总线变化的次数。 epsilon表示切换总线的"cost"。例如，如果有人同样喜欢 "stay on the bus" 和 "switch buses but save 2 minutes"，那么 epsilon 应该是 2 分钟。
您还可以通过将不等式 T1 < T2 修改为 T1 + S < T2 来添加 "minimum switching time" S。这将排除 T1 和 T2 非常接近以至于某人无法及时合理地切换总线的边缘。
另一个提案
而不是添加节点。你可以只是更多的边缘。而不是像下面这样表示巴士路线 (A -> B -> C)：
A -> B
A -> C
B -> C
对于每条边，您都会增加上车和下车所需的成本时间。
答案真的很有帮助。我最终做了一些不同的事情，但受到这里的想法的启发。基本上每个站点都有 'exits' 分配给每条公交路线，边缘从站点引出。为了让公共汽车 A 到达第 3 站，它需要进入第 2 站，然后从 'B' 出口离开。进入车站的边缘会产生额外费用。如果路线匹配，公交车可以免费绕过车站。所以公共汽车 'B' 永远不需要进入第 2 站去第 3 站，但公共汽车 A 需要。
这允许任何一辆公共汽车成为到达第 2 站的最短路线，并允许两辆公共汽车到达第 3 站。但是如果你要从第 1 站去第 3 站，从公共汽车 B 开始将是最便宜的路线，因为它不需要经过车站，产生额外的费用。