我有一个数据库,包含公共(public)汽车/火车/...站点以及每个日期的到达/离开时间等等。我正在寻找一种方法来搜索两个位置之间最快(最短/最便宜/最少转换)的行程。我希望将来有任意位置,使用 OpenStreetMap 数据在站点之间以及从站点到起点/终点之间行走,但是目前我只想在数据库中找到两个站点之间的路径。
问题是我似乎找不到关于这个主题的太多信息,例如 this Wikipedia page有很多文本,其中绝对没有有用的信息。
我发现的是 GTFS格式,用于 Google Transit .虽然我所在的城市不提供公共(public)数据馈送(甚至不提供私有(private)数据馈送),但我已经拥有 GTFS 包含的所有重要信息并且进行转换将是微不足道的。
有一些基于 GTFS 的软件,比如 OpenTripPlanner还可以使用 OpenStreetMap 进行行人/汽车/自行车路线规划.
但是,路由代码没有很好的记录(至少从我发现的),我不需要整个东西。
我正在寻找的只是对我可以使用的算法、它们的性能的一些很好的概述,也许还有一些伪代码。
因此,问题是,给定停靠站、路线和到达/离开/行驶时间列表,我如何轻松找到从 A 站到 B 站的最快路径?
最佳答案
- 将您的问题建模为 graph .每个站将是一个顶点,并且 每辆公共(public)汽车/火车都是一个边缘。
- 创建一个函数
w:Edges->R
,指示每条边的时间/金钱/...。 - 现在,你有一个典型的最小路径问题,可以通过 Dijkstra algorithm , 它找到从给定源到所有顶点的最小路径。
(*) 对于“最少转换”,每条边的权重实际上为 1,因此您甚至可以通过运行 BFS 来优化它甚至 bi-directional BFS 而不是 dijkstra,正如我在此 post 中解释的那样[解释为社交距离,其实是同一个算法]。
编辑
作为对您在评论中提到的图表的非静态性质[时间]的编辑[对于价格和转换次数,我上面提到的仍然适用,因为这些图表是静态的],您可以使用一个distance vector routing algorithm ,这实际上意味着适用于动态图,并且是 Bellman Ford algorithm 的分布式变体.
算法思路:
- 周期性地,每个顶点发送它的“距离向量”到它的 neighbors [向量表示从发送顶点到每个其他顶点的“成本”。
- 它的邻居尝试更新它们的路由表[最好通过哪条边移动到每个目标]
- 对于您的情况,每个节点都知道到达其邻居的最快方式是什么,[行程时间 + 等待时间] 并且它 [顶点/站点] 将此数字添加到距离向量中的每个主条目,以便知道如何以及需要多少时间才能到达目的地。当一辆公共(public)汽车离开时,应该重新计算所有节点的行程时间[from this source],并将新向量发送给它的邻居
关于algorithm - 具有时间限制的图上的寻路(路线、行程规划等)算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7245840/