公交运输算法

Question

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

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

感谢任何帮助。我卡在这里了。我不知道从哪里开始-如何存储数据以及如何找到路线。我知道Dijkstra / A *，但我仅在非时间相关的图上使用过它们...

- Daniel Novak

---

OSRM 是一个基于 C++ 的开源路由引擎，用于计算最短路径。您可能会发现它很有用。 - rafa.pereira

Answer 1

你正在处理的问题并不是一项琐碎的任务，它有一个名字:混合整数非线性规划问题(MINLP)。用一位作者(Deb 1998)的话来说:

"当数学公式化时，时间调度问题变成了一个具有大量资源和服务相关约束条件的混合整数非线性规划问题(MINLP)。尽管过去曾试图使用经典优化技术(如Bookbinder & DCsilets，1992;Kikuchi & Parameswaran，1993)寻找简化模型的最佳时间表，即使对于小型运输网络而言，这仍是一项极其困难的任务。主要原因是变量和约束条件数量巨大，变量的离散性以及目标函数和约束条件中涉及的非线性性造成的困难。"

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

你的另一个选择是使用模拟。只是为了立刻提供一些可以尝试的东西——选择数千条从起点开始的随机路径，并找出能够相对顺利到达目的地的路径。

将算法想像成这样：你要找到从站点A到站点B的最快路线，从某个时间点开始。雇用1,000人，并给他们一个硬币进行翻转。告诉他们每次有机会上下车时都要翻转硬币。正面朝上，下车(或上车，如果已经下车)。反面朝上，停留在车上(或继续等待，如果已经下车)。他们每个人都有一张索引卡，在行进过程中写下所做的选择。你到达B点并等待第一个人出现并拿走他的卡片。

- Pete

---

这是非常流行的“车辆路径问题”，它是NP-完全问题。找到最优解可能，但不太可能。一种<插入计算智能算法>可以工作，成功的程度各不相同，唯一的因素是“解决方案应该有多正确”。 - gpampara

我不明白为什么在给定起始时间的情况下找到从A到B的路径应该比Dijkstra实现的O(n)更慢。只有在考虑公交容量并想要安排多个人的路线时，事情才会变得复杂。 - CodesInChaos

Answer 2

有一份包含30多篇公共交通路线算法的出版物清单，这份清单是由开源（Java）OpenTripPlanner项目的贡献者们随着时间的推移编制而成的：

https://docs.opentripplanner.org/en/latest/Bibliography/

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

这是一份启发和指导现有OTP路由引擎和一些正在进行的实验的文章、论文和书籍列表。目前， OpenTripPlanner使用一个单一的时间依赖（而不是时间扩展）的图，其中包含街道和公共交通网络。仅步行和仅骑自行车的旅行通常使用具有欧几里得启发式或收缩分层的A *算法进行规划。步行+公共交通或骑自行车+公共交通的旅行使用带有epsilon支配的MOA *算法进行规划以进行路径修剪，并使用Tung-Chew启发式（提供聚合权重下限的图）进行队列排序。

上面的路由参考书目包括以下算法类别和相关工作的参考文献:

• 路径搜索加速技术
• 多目标 Pareto 最短路径
• 资源受限制的路由
• Contraction and Transfer Patterns
• 基于时间表的路由
• ALT 和度量嵌入
• 校准和实施细节
• Post-Dijkstra 公共交通路由

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

关于其他开源公共交通路线规划库，还有Bliksem Labs的RRRR项目：

https://github.com/bliksemlabs/rrrr

从上面的链接：

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

OpenTripPlanner和RRRR都使用GTFS数据。

- Sean Barbeau

Answer 3

请阅读：

多模式路径规划。 卡尔斯鲁厄理工大学信息学院，2009年硕士论文。 在线文献链接：http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf

铁路路线的部分同样适用于公交路线。

要点：将空间和时间扩展为单个图的朴素方法在大型网络中不起作用。有更聪明的解决方案。

- Jakob Erdmann

Answer 4

我想分享一下我对这个问题的最终解决方案。这是一个大学项目的一部分，所以可能不完全适合实际使用。它必须在 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 次换乘（需要在旅途中更换公交车）。计算只需几秒钟。但是我必须将整个数据库加载到内存（字典）中以加快查询速度，因为查询速度太慢。

我认为这对于大型网络不起作用。但对于单个中小型城市的公共交通运输有效。

- Daniel Novak

Answer 5

从概念上讲，您采用评估A和B之间距离的相同基本算法，但是应该评估时间而不是距离。如果提供适当的输入，Dijkstra可以完成这两个任务。

通常您将地图视为距离的度量标准。但是，同一张地图也可以作为时间的度量标准；您只需要添加关于平均速度以及覆盖特定道路的特定距离所需的时间的数据。您甚至可以按时间可视化地图；需要更长时间的路线将会更长。 Dijkstra 真的不在乎它正在评估什么； 它只关心找到连续路线中最小的数字，并且该数字代表长度或时间都无关紧要。

为了提高速度，简单的算法只使用白天的速度限制，并假设您从A到B时永远不需要停车；更先进的算法可以融合关于时间和交通模式的信息（这将影响您在该时间段内在该道路上行驶的平均速度），以及一条路是高速公路还是市区街道（因此可以对在交叉口停留的时间进行有根据的猜测）。您使用的取决于您拥有的资源，但基本的4或5层时间维度应该足以满足除了绝对最紧急的应用程序之外的所有需求。对于地图中每条路的每个方向，您需要知道早高峰、白天、晚高峰和夜间的平均速度，可能还包括午餐时间的数字。一旦您掌握了这些，将Dijkstra算法相对基本的更改，传入一个特定的时间，它将根据时间评估路线。

- KeithS

---

Dijkstra算法在这种应用中的问题在于路线时间以以下方式变化：如果您从A到B再到C有一条路线，您必须在B等待换乘。等待时间将取决于其余的时间表。然后，从B到C的路线又将取决于您选择哪个换乘，因为并非所有的换乘都会直接从B到C。 - Pete

这基本上是我面临的问题，路径成本（在我的情况下是运输时间）会随着时间而变化。你可以从A到B走一条路，需要10分钟。现在从B到C，路径将取决于当前时间+旅行时间。目前，我只尝试向前规划编程，但似乎太复杂了。我尝试谷歌了所有东西，但没有找到一个能处理根据时间表变化的路径成本的算法。谢谢你的帮助。 - Daniel Novak

编辑：我在这里找到了关于Dijkstra算法和时间表的一些有价值的东西： http://blog.eldslott.org/tag/dijkstra/ - Daniel Novak

@Daniel_sk，你的程序会（1）为我准备一个计划，让我可以打印出来带着走吗？在这种情况下，我希望它具有故障鲁棒性。（即使公交车1晚到3分钟到达B站，我仍然希望按照原计划行动。）还是你的程序（2）将成为一个互动指南（例如在我的手机上），实时告诉我应该搭哪辆公交车，哪个站点下车等等——计划会根据当前情况进行更新，而鲁棒性则不那么必要。 - emory

@Pete，传输延迟可以被建模为边缘。@Daniel_sk，你试过使用一个函数来计算（时间x距离x其他因素）的成本吗？或者你可以将边缘加权为这些值的因子，然后A*会最小化该因子。 - Trinidad

Answer 6

如果您对时间信息感兴趣，为什么不使用时间信息标记图边上的距离值，而不是它们之间的物理距离。这样，您将搜索最快的路线，而不是最短的路线。然后，您可以使用Dijkstra / A *来计算结果。

我有点不清楚您所说的时间依赖性是什么意思。如果您的意思是需要回答“在早上10点之前从x到y”的查询，则可以计算出在早上10点之前到达的公交车路线，这似乎是数据的简单过滤器。然后将Dijkstra / A *应用于数据。

- Richard Warburton

Answer 7

请尝试使用此数据模型。

公交车1到达A、B和C站。公交车2到达B、D和E站。

我会根据公交车和站点存储一个唯一的节点，并将节点之间的距离基于时间进行计算。我们会有A1、B1、C1、B2、D2和E2这些节点。在换乘的特殊情况下，将等待下一班公交车的时间视为节点之间的距离。例如，如果公交车1在比公交车2早30分钟到达B站，那么从B1到B2的旅行时间就是30分钟。

然后你就可以应用Dijkstra算法了。

- Philip Tinney