我正在开发一个可以查找公交线路的脱机 C# 应用程序。我可以提取时间表/巴士/路线数据。我正在寻找适用于基本数据的最简单解决方案。
什么算法可以用来查找从“A”号站点到“B”号站点的路线？有没有为C#/Java准备的开源解决方案？数据库的谷歌GTFS格式适合简单的解决方案吗？http://code.google.com/transit/spec/transit_feed_specification.html
感谢您的任何帮助。我被困在这个。我不知道从哪里开始 - 如何存储数据以及如何找到路线。我知道Dijkstra / A *，但我只在不依赖于时间的图表上使用它们......
您正在处理的问题不是一项微不足道的任务。如此之多，它有一个名字：混合整数非线性规划问题（MINLP）。用一位作者的话说（Deb 1998）：
“当用数学公式化时，时间调度问题成为具有大量资源和服务相关约束的混合整数非线性规划问题（MINLP）。尽管过去曾尝试使用经典优化技术找到简化模型的最佳时间表（Bookbinder & DCsilets， 1992;Kikuchi & Parameswaran， 1993），据观察，即使对于小型交通网络来说，这也是一项极其艰巨的任务。困难主要由于变量和约束的大量，变量的离散性以及目标函数和约束中涉及的非线性。
在Deb的论文中，他提出了一种遗传算法。
您的另一个选择是使用模拟。只是为了把一些东西扔出去，你可以马上尝试 - 选择成千上万的随机路线，从你的起点开始，并钓出那些在到达目的地方面运作良好的路线。
想象一下这样的算法：您正在尝试找到从站点A到站点B的最快路线，从特定时间开始。你雇佣了1000人，并用四分之一的武器武装他们。你告诉他们每次有机会上下车时都要掷硬币。头，下车（或者上车，如果已经下车的话）。尾巴，保持（或继续等待，如果关闭）。他们每个人都有一个索引卡，记下他们所做的选择。你去B点，等待第一个人出现并拿走他的卡。
这里有一个关于公共交通路由算法的广泛出版物列表（30多个），这些算法是由开源（Java）OpenTripPlanner项目的贡献者随着时间的推移而编译的：
https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography
OpenTripPlanner是多模式路由引擎，还包括自行车和步行 - 来自上面的链接：
这是一个文章，论文和书籍的列表，这些文章，论文和书籍启发并告知了现有的OTP路由引擎和一些正在进行的实验。目前，OpenTripPlanner使用单个时间依赖性（而不是时间扩展）图，其中包含街道和交通网络。仅步行和仅骑自行车旅行通常使用具有欧几里得启发式或收缩层次结构的A *算法进行规划。步行+运输或自行车+运输行程是使用 MOA* 算法的变体来规划的，该算法具有用于路径修剪的 epsilon 支配性，以及用于队列排序的 Tung-Chew 启发式（提供聚合权重下限的图形）。
上面的路由参考书目包括以下类别的算法和相关工作的参考：
如果您发现列表中没有的新内容，请随时将其添加到wiki中！
至于其他开源公共交通路由库 - 还有Bliksem Labs的RRRR项目：
https://github.com/bliksemlabs/rrrr
从上面的链接：
RRRR（通常发音为R4）是RAPTOR公共交通路由算法的C语言实现。它是Bliksem旅程规划和乘客信息系统的核心路由组件。该项目的目标是在大面积地理区域（例如BeNeLux或整个欧洲）生成帕累托最优路线集，从而改善现有更灵活替代方案的资源消耗和复杂性。该系统最终应支持旅行计划中反映的实时车辆/行程更新，并能够直接在没有互联网连接的移动设备上运行。
OpenTripPlanner和RRRR都使用GTFS数据。
