我正在一个可以找到公交路线的离线C＃应用程序。 我可以提取时间表/巴士/路线数据。我正在寻找最基本的数据解决方案。公交公交算法
什么算法可以用来找到从公交车站“A”到公交车站“B”的路线？是否有适用于C＃/ Java的开源解决方案？ 数据库的谷歌GTFS格式是否适合简单的解决方案？ http://code.google.com/transit/spec/transit_feed_specification.html
感谢您的帮助。我坚持这一点。我不知道从哪里开始 - 如何存储数据以及如何查找路线。 我知道Dijkstra/A *，但是我只在没有时间依赖的图表上使用它们...
从概念上讲，您采用相同的基本算法来评估A和B之间的距离，但不是距离，而是您应该是评估时间。迪杰斯特拉可以做到这一点，如果你给它适当的投入。
您已经习惯将地图看作距离的度量。但是，同样的地图也可以用来衡量时间。您所需要的只是添加有关平均速度的数据，并且覆盖特定道路的特定距离所需的时间将自行消失。你甚至可以根据时间想象地图。花费更长时间的路线会更长。迪杰斯特拉并不关心它评估的是什么，真的;它只关心寻找具有最低数量的连续路线，以及该数字是代表长度还是时间并不重要。
为了融入速度，天真的算法只是使用白天的速度限制，并假设你从A到B时不必停下来;更先进的算法可以包含有关一天中的时间和交通模式的信息（这将影响您当时在该道路上行驶的平均速度），以及道路是高速公路还是地面街道（并且因此对所花费的时间进行了教育性的猜测在十字路口）。你使用什么取决于你有什么可用的，但基本的4层或5层时间尺度应该适用于除绝对时间最关键的应用程序之外的所有应用程序。对于地图中每条道路的每个方向，您需要早上急流，白天，晚上高峰和夜间的平均速度，可能还需要午餐时间。一旦你有了这些，对Dijkstra算法来说，这是一个相对基本的变化，可以在一天中的某个时间传递，并根据时间评估路由。
Dijkstra算法在这个应用程序中的问题是，路线时间以下列方式变化：如果您有从A到B到C的路线，您必须在B处等待您的转移。等待时间将取决于其余时间表。然后，从B到C的路线将依次取决于您进行的转账，因为并非所有转账都将直接从B转到C. – Pete 2010-09-02 16:06:34
这就是我面临的问题，路径成本（在我的情况下的运输时间）发生变化随着时间的推移。您可以采取从A到B的路径，需要10分钟。现在从B到C，路径将取决于当前时间+旅行时间。 在这一点上，我只是试图规划前进的编程，但它似乎太复杂了。我试图谷歌的一切，但我没有找到一个算法，将路径成本根据时间表变化的工作。感谢您的帮助。 – 2010-09-02 16:32:24
编辑：我发现了一些可能对Dijsktra +时间表有价值的东西： http://blog.eldslott.org/tag/dijkstra/ – 2010-09-02 16:47:23
如果您对时间信息感兴趣，那么为什么不使用时间信息来标记图边上的距离值，而是使用时间信息而不是物理距离。这样你将搜索最快的路线，而不是最短的路线。然后，您可以使用Dijkstra/A *来计算您的结果。
我有点不清楚你的意思是依赖于时间。如果你的意思是你需要回答表单'上午10点之前从x到y'的查询，那么你可以计算出上午10点之前到达的巴士路线，看起来像是一个简单的数据过滤器。然后将Dijkstra/A *应用于数据。
您正在处理的问题不是一项简单的任务。如此多，这是一个名字：混合整数非线性规划问题（MINLP）。在一个作者（1998 DEB）的话：
“当数学配制时， 时间调度问题成为具有的资源和服务 - 大量 一个 混合整数非线性规划问题 （MINLP）相关的 限制。虽然尝试 已经发了过去采用经典的优化 技术（书籍装订& DCsilets， 1992;菊池& Parameswaran，1993年），以找到一个简化模型 的 最优调度， 可以观察到，这是一个 极即使对于小型运输网络也是困难的任务。困难 主要出现因为大量 数量的变量和约束，变量 离散性，以及参与 目标函数 非线性和 约束。”
在Deb的一篇论文中他提出了一种遗传算法
你的其他选择是使用模拟，只是为了抛出一些东西，你可以立即尝试 - 选择成千上万的随机路线开始在你的起源，并找出合理的工作，到目的地
对此算法进行描述：您正试图从某个时刻开始，从停止A到停止B，寻找最快的路线。你雇用了1000人，并用四分之一的手臂将它们掰起来翻转。你告诉他们每次有机会上车或下车时都要抛硬币。头，下车（或上车，如果已经关闭）。尾巴，留在（或等待，如果关闭）。他们每个人都有一张索引卡，用于记录他们随时做出的选择。你去B点，等待第一个人出现并拿走他的牌。
这是一个非常受欢迎的“车辆路径问题”，它是NP-Complete。找到最佳的解决方案是可能的，尽管不太可能。一个<插入计算智能算法>可以在不同程度的成功下工作，唯一的因素是解决方案应该是“多么正确”。 – gpampara 2010-09-02 17:05:48
我不明白为什么在给定的开始时间找到从A到B的路线应该比Dijkstra实现的O（n）慢。如果你想把许多人考虑到巴士的容量，事情就会变得复杂。 – CodesInChaos 2010-11-08 14:10:40
这不是所谓的“旅行推销员难题”吗？ – MirroredFate 2011-06-24 23:01:06
试试这个作为你的数据模型。
总线1进到停止A，B和C总线2前进到停止B，d和E
我将存储一个唯一的节点基于两个总线上，并停止，随着距离的节点是基于时间。我们将有节点A1，B1，C1，B2，D2和E2。在传输的特殊情况下，等待下一个总线作为节点之间的距离。例如，如果巴士1在巴士2前30分钟到达B站，则从B1到B2的旅行时间为30分钟。
您应该能够应用Dijkstra算法。
阅读此：
多模态路线规划。 硕士论文，卡尔斯鲁厄大学（TH），Fakultät献给Informatik公司，在http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf
铁路路由，可参考2009年 网上也适用于总线布线。
它的要点：将空间和时间扩展为单个图形的幼稚方法不适用于大型网络。有更聪明的解决方案。
只是想分享我对这个问题的最后方法。这是大学项目的一部分，因此它可能不完全适合现实世界的使用。它必须相当快才能在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次更改（必须在旅程中更换公交车）。计算只需几秒钟。但我不得不将整个数据库加载到内存（字典）中以加快查询时间，因为查询时间过长。
我不认为这将适用于大型网络。但它适用于单个中小城市的公共交通工具。
有一个广泛的出版物清单（30+）上已经由贡献者编译随着时间的推移开源（JAVA）OpenTripPlanner project这里的公共交通路由算法：
https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography
OpenTripPlanner是多模式路由引擎，其中还包括自行车和步行 - 从上述链接：
这是一篇文章，论文，和书籍，已启发和通知现有的OTP路由引擎nd一些正在进行的实验。目前，OpenTripPlanner使用单个时间相关（而不是时间展开）图，其中包含街道和公交网络。通常使用具有欧几里得启发式或收缩层次结构的A *算法来计划仅步行和仅自行车旅行。步行+过境或自行车+过境旅行计划使用MOA *算法的一个变种，其中包含用于路径修剪的ε-优势和用于队列排序的Tung-Chew启发式（提供总重量下限的图）。
上面的路由书目包括算法和相关工作以下几类引用：
如果你发现新的东西，这不是在名单上，请随时将其添加到维基！
至于其他开源公共交通路由图书馆 - 也有通过Bliksem实验室的RRRR项目：
https://github.com/bliksemlabs/rrrr
从上面的链接：
RRRR（通常发音R4）是RAPTOR公共交通路由算法的C语言实现。它是Bliksem旅行计划和旅客信息系统的核心路由组件。该项目的目标是在大的地理区域（例如BeNeLux或全欧洲）生成一系列帕累托最优路线，改善现有更灵活替代品的资源消耗和复杂性。该系统最终应支持行程计划中反映的实时车辆/行程更新，并且能够直接在没有互联网连接的移动设备上运行。
OpenTripPlanner和RRRR都使用GTFS数据。
[OSRM]（http://project-osrm.org/）是一个基于C++的最短路径的开源路由引擎。你可能会觉得它很有用。 – 2015-10-23 13:13:03