公交车公共交通算法

Question

我正在开发一个可以找到公交路线的离线C#应用程序.我可以提取时间表/公交车/路线数据.我正在寻找可以使用基本数据的最简单的解决方案.

什么算法可用于查找从公交车站"A"到公交车站"B"的路线？是否有针对C#/ Java的开源解决方案？数据库的谷歌GTFS格式是否适用于简单的解决方案？http://code.google.com/transit/spec/transit_feed_specification.html

谢谢你的帮助.我坚持这个.我不知道从哪里开始 - 如何存储数据以及如何查找路径.我知道Dijkstra/A*但我只在不依赖于时间的图表上使用它们...

Answer 1

您正在处理的问题不是一项微不足道的任务.这么多,有一个名称:混合整数非线性规划问题(MINLP).用一位作者的话来说(Deb 1998):

"当数学公式化时,时间调度问题变成具有大量资源和服务相关约束的混合整数非线性规划问题(MINLP).尽管过去曾尝试使用简化模型找到最佳时间表经典优化技术(Bookbinder&DCsilets,1992; Kikuchi&Parameswaran,1993),观察到即使对于小型运输网络来说这也是一项极其困难的任务.困难主要是由于变量和约束的大量,离散性质变量,以及目标函数和约束中涉及的非线性."

在Deb的论文中,他提出了一种遗传算法.

您的另一个选择是使用模拟.只是为了扔东西你可以立即尝试 - 从你的起源选择成千上万的随机路线,并剔除那些在到达目的地时工作得相当好的路线.

想象这样的算法:你试图找到从A站到B站的最快路线,从某个时间开始.你雇佣了1000个人并用四分之一的武器来翻转.你告诉他们每次有机会上下车时都要翻硬币.下车,下车(或上车,如果已经下车).尾巴,保持(或等待,如果关闭).他们每个人都有一张索引卡,可以记下他们所做的选择.你去B点等待第一个人出现并拿走他的卡.

Answer 2

有关公共交通路由算法的大量出版物（超过30种）已经由开放源代码（Java）OpenTripPlanner项目的贡献者随着时间的推移进行了编译：

https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography

OpenTripPlanner是多模式路由引擎，还包括自行车和步行-来自上面的链接：

这是启发，告知现有OTP路由引擎和一些正在进行的实验的文章，论文和书籍的列表。当前，OpenTripPlanner使用包含街道和公交网络的单个时间相关（而不是时间扩展）图。通常使用具有欧几里得启发式或收缩式层次结构的A *算法计划仅步行和仅自行车旅行。计划使用MOA *算法的变体计划步行+过客或自行车+过境旅行，该算法以epsilon占优势进行路径修剪，并使用Tung-Chew启发式方法（该图提供了总权重的下限）来进行队列排序。

上面的路由参考书目包含以下类别的算法和相关工作的参考：

• 路径搜索加速技术
• 多目标帕累托最短路径
• 资源受限的路由
• 收缩和转移方式
• 基于时间表的路由
• ALT和公制嵌入
• 校准和实施细节
• 后戴克斯特拉公共交通路线

如果您发现不在列表中的新内容，请随时将其添加到Wiki！

至于其他开放源代码的公共交通路线库，还有Bliksem Labs的RRRR项目：

https://github.com/bliksemlabs/rrrr

从上面的链接：

RRRR（通常发音为R4）是RAPTOR公共交通路由算法的C语言实现。它是Bliksem行程计划器和乘客信息系统的核心路由组件。该项目的目标是在较大的地理区域（例如，BeNeLux或整个欧洲）上生成一组帕累托最优的行程，以改善资源消耗和现有更灵活替代方案的复杂性。该系统最终应支持行程计划中反映的实时车辆/行程更新，并能够在没有Internet连接的情况下直接在移动设备上运行。

OpenTripPlanner和RRRR都使用GTFS数据。

Answer 3

读这个:

多模态路线规划.硕士论文,UniversitätKarlsruhe(TH),FakultätfürInformatik,2009.可在线获取:http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf

铁路路线部分也适用于公交路线.

它的要点:将空间和时间扩展到单个图形的天真方法对大型网络不起作用.有更智能的解决方案.

Answer 4

从概念上讲，您可以采用相同的基本算法来评估 A 和 B 之间的距离，但您应该评估时间而不是距离。如果你给它适当的输入，Dijkstra 可以做到这两点。

您习惯于将地图视为距离的度量。然而，同一张地图也可以用来衡量时间。您所需要的只是添加有关平均速度的数据，并且在特定道路上行驶特定距离所需的时间就会自行计算出来。您甚至可以根据时间来可视化地图；需要更长时间的路线将会更长。Dijkstra 并不关心它正在评估哪个，真的；它只关心找到数字最小的连续路线，而该数字是否代表长度或时间并不重要。

为了纳入速度，简单的算法只是使用白天的速度限制，并假设你从 A 到 B 时永远不必停下来；更先进的算法可以包含有关一天中的时间和交通模式的信息（这将影响您当时在该道路上行驶的平均速度）以及道路是高速公路还是地面街道（从而对停车时间做出有根据的猜测）在十字路口）。您使用的内容取决于可用的内容，但基本的 4 层或 5 层时间维度应该足以满足除绝对时间最关键的应用程序之外的所有应用程序。对于地图中每条道路的每个方向，您需要早高峰、白天、晚高峰和夜间的平均速度，可能还需要午餐时间的数据。一旦掌握了这一点，就可以对 Dijkstra 算法进行相对基本的更改，以传递一天中的某个时间并让它根据时间评估路线。