公交车公共交通算法
我正在开发一个可以找到公交路线的离线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点等待第一个人出现并拿走他的卡。
读这个：
多模态路线规划。 硕士论文，UniversitätKarlsruhe（TH），FakultätfürInformatik，2009。可在线获取： http：//i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf
铁路路线部分也适用于公交路线。
它的要点：将空间和时间扩展到单个图形的天真方法对大型网络不起作用。 有更智能的解决方案。
只想分享我对这个问题的最终方法。 这是大学项目的一部分，因此它可能不完全适合现实世界的使用。 在Windows Mobile设备上运行速度必须相当快。
我最终使用了4个表（SQLite）。 一个表保留总线列表，第二个表保留一个站列表。 另一张表保留了这些组合 – 公交车在特定车站停靠的位置以及从该车站到达的位置以及需要多长时间（分钟）。 必须存储所有组合。 最后一张表是一个简单的时间表。 对于每个站点，它列出了停在那里的每个总线和时间（我将时间存储为整数值 – 14：34是1434，以便更快地进行比较）。
我使用了双向广度优先搜索算法。 为起始站和目的站检索相邻站（可直接访问）。 如果这两个“图形”在一个站上重叠，则存在从站A到站X的路径。 例如，从A站您可以到达B，C，D，E站（通过使用特定的总线）。 从目的地站X，您可以直接到达N，C，Z。 这两个图在站C上重叠。因此存在路径A – > C – > X. 如果在第一次迭代中没有找到路径，则算法继续并再次展开图形（BFS）。
第一步没有考虑时间 – 这足以让它足够快。 您只能获得一个可能的路径列表，其中包含您必须用来获取这些路径的总线列表。 在最后一步中评估时间，您浏览可能路径列表并检查公交车是否在特定时间内行驶（增加每次停车的时间）。
在一个拥有250个车站和100多辆公共汽车/铁路的小城市，这些方法最多可以进行3次更改（您必须在旅途中更换公交车）。 计算只需几秒钟。 但是我不得不将整个数据库加载到内存（Dictionary）中以加快查询速度，这需要花费太长时间。
我认为这不适用于大型网络。 但它适用于单个中小城市的公共交通工具。
有一个关于公共传输路由算法的出版物（30多个）的广泛列表，这些出版物已经由开源（Java） OpenTripPlanner项目的贡献者随时编译：
https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography
OpenTripPlanner是多模式路由引擎，还包括自行车和步行 – 从上面的链接：
这是一篇文章，论文和书籍的列表，它们启发并通知了现有的OTP路由引擎和一些正在进行的实验。 目前，OpenTripPlanner使用单个时间相关（而不是时间扩展）图，其中包含街道和传输网络。 通常使用具有欧几里德启发式或收缩层级的A *算法来计划仅行走和仅自行车行程。 Walk + Transit或Bike + Transit旅行计划使用MOA *算法的变体，其中epsilon-dominance用于路径修剪，而Tung-Chew启发式（提供聚合权重下限的图表）用于队列排序。
上面的路由参考书目包括以下类别的算法和相关工作的参考：
- 路径搜索加速技术
- 多目标帕累托最短路径
- 资源受限的路由
- 收缩和转移模式
- 基于时间表的路由
- ALT和公制嵌入
- 校准和实施细节
- 后Dijkstra公共交通路线
如果您发现列表中没有的新内容，请随时将其添加到维基！
至于其他开源公共交通路线图书馆 – Bliksem Labs还有RRRR项目：
https://github.com/bliksemlabs/rrrr
从以上链接：
RRRR（通常发音为R4）是RAPTOR公共交通路由算法的C语言实现。 它是Bliksem旅程规划和乘客信息系统的核心路由组件。 该项目的目标是在大的地理区域（例如BeNeLux或整个欧洲）生成一组帕累托最优路线，从而改善现有更灵活的替代方案的资源消耗和复杂性。 该系统最终应支持旅行计划中反映的实时车辆/旅行更新，并且能够直接在没有互联网连接的移动设备上运行。
OpenTripPlanner和RRRR都使用GTFS数据。
从概念上讲，您使用相同的基本算法来评估A和B之间的距离，但是您应该评估时间而不是距离。 如果你给它适当的输入，Dijkstra可以做到这两点。
您习惯将地图视为距离的度量。 但是，同一张地图也可以作为时间的衡量标准; 您只需要添加有关平均速度的数据，覆盖特定道路特定距离所需的时间就会自动消失。 您甚至可以根据时间可视化地图; 需要更长时间的路线会更长。 Dijkstra并不关心它正在评估哪个，真的; 它只关心找到数量最少的连续路线，这个数字代表长度或时间是无关紧要的。
为了结合速度，天真的算法只使用白天的速度限制，并假设你从A到B时永远不必停下来; 更高级的算法可以包含有关一天中的时间和交通模式的信息（这将影响您当时在该道路上行驶的平均速度），以及道路是高速公路还是水面街道（从而对停止的时间做出有根据的猜测在十字路口）。 您使用的内容取决于您所拥有的内容，但基本的4或5层时间维度应该足以应对除绝对时间最关键的应用程序之外的所有应用程序。 对于地图中每条道路的每个方向，您需要在早上高峰，白天，晚上高峰和晚上的平均速度，也可能是午餐时间的数字。 一旦你拥有了它，这是Dijkstra算法在一天中的时间内传递并且根据时间评估路线的相对基本的变化。
如果您对时间信息感兴趣，那么为什么不使用时间信息而不是它们彼此的物理距离来标记图形边缘上的距离值。 这样您将搜索最快的路线，而不是最短的路线。 然后，您可以使用Dijkstra / A *来计算结果。
关于时间依赖你的意思，我有点不清楚。 如果你的意思是你需要回答“早上10点之前从x到y”forms的查询，那么你可以计算在上午10点之前到达的公共汽车路线，看起来像是对数据的简单过滤。 然后将Dijkstra / A *应用于数据。
试试这个作为您的数据模型。
总线1到达A，B和C站。总线2到达B，D和E站。
我将基于总线和停止存储一个唯一的节点，节点的距离基于时间。 我们将有节点A1，B1，C1，B2，D2和E2。 在传输的特殊情况下，应用等待下一个总线作为节点之间的距离。 例如，如果公共汽车1在公共汽车2前30分钟到达B站，则从B1到B2的行程时间为30分钟。
你应该能够应用Dijkstra的算法。