algorithm - 具有时间限制的图上的寻路(路线、行程规划等)算法

Question

我有一个数据库，包含公共(public)汽车/火车/...站点以及每个日期的到达/离开时间等等。我正在寻找一种方法来搜索两个位置之间最快(最短/最便宜/最少转换)的行程。我希望将来有任意位置，使用 OpenStreetMap 数据在站点之间以及从站点到起点/终点之间行走，但是目前我只想在数据库中找到两个站点之间的路径。

问题是我似乎找不到关于这个主题的太多信息，例如 this Wikipedia page有很多文本，其中绝对没有有用的信息。

我发现的是 GTFS格式，用于 Google Transit .虽然我所在的城市不提供公共(public)数据馈送(甚至不提供私有(private)数据馈送)，但我已经拥有 GTFS 包含的所有重要信息并且进行转换将是微不足道的。

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

但是，路由代码没有很好的记录(至少从我发现的)，我不需要整个东西。

我正在寻找的只是对我可以使用的算法、它们的性能的一些很好的概述，也许还有一些伪代码。

因此，问题是，给定停靠站、路线和到达/离开/行驶时间列表，我如何轻松找到从 A 站到 B 站的最快路径？

Answer 1

1. 将您的问题建模为 graph .每个站将是一个顶点，并且每辆公共(public)汽车/火车都是一个边缘。
2. 创建一个函数w:Edges->R，指示每条边的时间/金钱/...。
3. 现在，你有一个典型的最小路径问题，可以通过 Dijkstra algorithm , 它找到从给定源到所有顶点的最小路径。

(*) 对于“最少转换”，每条边的权重实际上为 1，因此您甚至可以通过运行 BFS 来优化它甚至 bi-directional BFS 而不是 dijkstra，正如我在此 post 中解释的那样[解释为社交距离，其实是同一个算法]。

---

编辑
作为对您在评论中提到的图表的非静态性质[时间]的编辑[对于价格和转换次数，我上面提到的仍然适用，因为这些图表是静态的]，您可以使用一个distance vector routing algorithm ，这实际上意味着适用于动态图，并且是 Bellman Ford algorithm 的分布式变体.
算法思路:

• 周期性地，每个顶点发送它的“距离向量”到它的neighbors [向量表示从发送顶点到每个其他顶点的“成本”。
• 它的邻居尝试更新它们的路由表[最好通过哪条边移动到每个目标]
• 对于您的情况，每个节点都知道到达其邻居的最快方式是什么，[行程时间 + 等待时间] 并且它 [顶点/站点] 将此数字添加到距离向量中的每个主条目，以便知道如何以及需要多少时间才能到达目的地。当一辆公共(public)汽车离开时，应该重新计算所有节点的行程时间[from this source]，并将新向量发送给它的邻居