具有时间限制的图形路径规划算法（路线规划，旅行计划等）

Question

我有一组公交/火车等交通站点的数据库，其中包含每个日期的到达和出发时间等信息。我正在寻找一种方法来搜索两个位置间最快（最短/最便宜/换乘最少）的行程。我希望未来可以自由选择位置，并使用OpenStreetMap数据进行步行、起点/终点到站点的导航，但目前我只想在数据库中查找两个站点之间的路径。

问题是我似乎找不到关于这个主题的太多信息，例如this Wikipedia page页面上有很多文字，但没有任何有用的信息。

我发现了Google Transit使用的GTFS格式。虽然我的城市没有提供公共数据源（甚至没有私人数据源），但我已经拥有了GTFS中包含的所有重要信息，并且转换将是微不足道的。

还有一些基于GTFS的软件，例如OpenTripPlanner，可以使用OpenStreetMap进行行人/汽车/自行车路线规划。

然而，路线代码并没有很好地记录文档（至少从我所发现的情况来看），而且我不需要整个软件。

我所需要的只是一些有关可用算法、它们的性能以及可能的伪代码的概述。

所以，问题是：给定一个停靠站点、路线和到达/离开/旅行时间的列表，如何轻松地找到从站点A到站点B的最快路径？

- lacop

Answer 1

1. 将问题建模为图形。每个车站都是一个顶点，每辆公交车/火车都是一条边。
2. 创建一个函数w：Edges->R，表示每条边的时间/金钱/...。
3. 现在，您有一个典型的最小路径问题，可以通过Dijkstra算法解决，该算法从给定源找到所有顶点的最小路径。

(*) 对于'最少转换'，您的权重实际上是每个边缘的1，因此您甚至可以通过运行BFS或甚至是双向 BFS来优化此过程，就像我在这个post中所解释的那样[它是为社交距离而解释的，但实际上是相同的算法]。

---

编辑
关于您在评论中提到的图表[用于计时]的非静态性质，您可以使用距离向量路由算法，它实际上是为动态图设计的，并且是Bellman Ford算法的分布式变体。
算法思想：

• 定期，每个顶点向其邻居发送其“距离向量” [该向量指示从发送顶点到每个其他顶点的“成本”有多少]
• 其邻居尝试更新其路由表[通过哪个边缘最好地移动到每个目标]
• 对于您的情况，每个节点都知道到达其邻居的最快方式[旅行时间+等待时间]，并将此数字添加到距离向量中的每个条目中，以便了解如何以及需要多长时间才能到达目的地。当公交车离开时，应重新计算所有节点[从此源]的旅行时间，并将新向量发送给其邻居

- amit

---

除非您隐瞒了进一步优化的限制条件，否则您不会比Dijkstra算法更快。对于除时间以外的度量标准，您需要制定一个“权重”，它是时间、成本和麻烦的组合。您可能还需要让用户确定这些权重并动态重新计算，或者有几个预设的场景（100％时间，100％便宜，50/50/0，40/40/20等），并保留Dijkstra查找表的缓存版本。 - corsiKa

如果我没漏看什么，这种方法是行不通的。Dijkstra 算法适用于只有空间域的“静态”图形，但是这里有时间域。例如，如果你乘坐一辆需要1分钟的公交车到达一个节点，那么与乘坐需要5分钟的公交车时所经过的边将会不同。你可能会错过一辆公交车，导致权重变大因为你必须等待。此外，有些边缘可能会因为你以某种方式到达节点（错过了当天的最后一班公交车），而消失，但是如果你以另一种方式到达，则会存在这些边缘。据我所知，Dijkstra 算法无法处理此类情况，如果我有误请纠正我。 - lacop

@albwq：Dijkstra算法无法处理顶点中的“等待”以等待下一班公交车，您说得对。但是，它适用于您要求的另外两个标准：成本和转换次数。[请参见我关于优化转换次数的最后一节]。 - amit

@albwq：我编辑了我的答案，并添加了一个关于处理动态网络的算法的简短描述[和链接]。 - amit

看起来很有趣，我打算试一试。谢谢。 - lacop

对于迷路的访客，我的翻译如下：几乎所有传统算法在时间依赖图上都会失败，尤其是带有等待时间的情况。一种快速灵活且实际有效的解决方案是RAPTOR。 - dube