具有时间限制的图表上的寻路(路由,旅行计划......)算法

Question

我有一个公共汽车/火车/ ...站的数据库和每个日期的到达/离开时间等等.我正在寻找一种方法来搜索两个位置之间的最快(最短/最便宜/最少过渡)之旅.我希望将来有任意位置,使用OpenStreetMap数据在停靠点之间以及从停止点到开始/结束之间行走,但是暂时我只想在数据库中的两个停靠点之间找到路径.

问题是我似乎无法找到关于这个主题的更多信息,例如这个维基百科页面有很多文本,其中绝对没有有用的信息.

我发现的是Google Transit中使用的GTFS格式.虽然我的城市没有提供公共数据源(甚至不是私人数据源),但我已经掌握了GTFS包含的所有重要信息,并且进行转换将是微不足道的.

有一些基于GTFS的软件,比如OpenTripPlanner,它也可以使用OpenStreetMap进行行人/汽车/自行车路由.

但是,路由代码没有很好地记录(至少从我发现的那个),我不需要整个事情.

我正在寻找的是对我可以使用的算法,它们的性能,可能是一些伪代码的一些很好的概述.

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

Answer 1

1. 将您的问题建模为图表.每个站都是一个顶点,每个公共汽车/火车都是一个边缘.
2. 创建一个函数w:Edges->R,指示每个边缘的时间/金钱/ ....
3. 现在,您有一个典型的最小路径问题,可以通过 Dijkstra算法求解,该算法找到来自给定源的所有顶点的最小路径.

(*)对于'最小过渡',你的每个边缘的重量实际上是1,所以你甚至可以通过运行BFS甚至双向 BFS而不是dijkstra来优化它,正如我在这篇文章中所解释的那样[它被解释为社交距离,但它实际上是相同的算法].

编辑
作为你在评论中提到的[时间]的非静态性质的编辑[对于价格和转换数量,我上面提到的仍然适用,因为这些图是静态的],你可以使用距离向量路由算法,实际上意味着适用于动态图,是Bellman Ford算法的分布式变体.
算法思路:

• 周期性地,每个顶点将其"距离矢量"发送到其邻居[该向量指示从发送顶点到每个其他顶点行进多少'成本'.
• 它的邻居试图更新他们的路由表[通过哪个边缘最好移动到每个目标]
• 对于你的情况,每个节点知道什么是到达其邻居的最快方式,[旅行时间+等待时间]并且它[顶点/站]将此数字添加到距离向量中的每个主菜,以便知道如何到达目的地需要多长时间.当公共汽车离开时,应该重新计算所有节点的旅行时间[来自此来源],新的向量应该发送给它的邻居