我正在开发一个可以查找公交路线的离线 C# 应用程序。我可以提取时间表/巴士/路线数据。我正在寻找适用于基本数据的最简单的解决方案。
什么算法可以用来找到从巴士站“A”到巴士站“B”的路线？是否有适用于 C#/Java 的开源解决方案？用于数据库的 google 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 点，等待第一个人出现并拿走他的卡片。
开源 (Java) OpenTripPlanner 项目的贡献者随着时间的推移在此处编译了关于公共交通路由算法的大量出版物 (30+)：
https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography
OpenTripPlanner 是多模式路由引擎，还包括自行车和步行 - 来自上面的链接：
这是启发和告知现有 OTP 路由引擎和一些正在进行的实验的文章、论文和书籍的列表。目前，OpenTripPlanner 使用包含街道和交通网络的单一时间相关（与时间扩展相反）图。通常使用具有欧几里得启发式或收缩层次结构的 A* 算法来计划仅步行和仅骑自行车的旅行。Walk+Transit 或 Bike+Transit 行程是使用 MOA* 算法的变体来计划的，该算法具有用于路径修剪的 epsilon-dominance 和用于队列排序的 Tung-Chew 启发式（提供总权重下限的图）。
上面的路由参考书目包括以下类别的算法和相关工作的参考：
如果您发现列表中没有的新内容，请随时将其添加到 wiki！
至于其他开源公共交通路由库 - 还有 Bliksem Labs 的 RRRR 项目：
https://github.com/blksemlabs/rrrr
从上面的链接：
RRRR（通常发音为 R4）是 RAPTOR 公共交通路由算法的 C 语言实现。它是 Bliksem 旅程规划器和乘客信息系统的核心路由组件。该项目的目标是在较大的地理区域（例如比荷卢经济联盟或整个欧洲）生成一组帕累托最优路线，从而改善现有更灵活替代方案的资源消耗和复杂性。该系统最终应该支持反映在旅行计划中的实时车辆/旅行更新，并且能够直接在没有互联网连接的移动设备上运行。
OpenTripPlanner 和 RRRR 都使用 GTFS 数据。
读这个：
多式联运路线规划。硕士论文，卡尔斯鲁厄大学 (TH)，Fakultät für Informatik，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 次更改（您必须在旅途中更改公共汽车）。计算只需几秒钟。但是我不得不将整个数据库加载到内存（字典）中以加快查询速度，这需要太长时间。
我认为这不适用于大型网络。但它适用于单个中小型城市的公共交通。
从概念上讲，您采用相同的基本算法来评估 A 和 B 之间的距离，但您应该评估时间而不是距离。如果你给它适当的输入，Dijkstra 可以做到这两点。
您习惯于将地图视为距离的度量。然而，同一张地图也可以是时间的度量；您所需要的只是添加有关平均速度的数据，并且覆盖特定道路的特定距离所需的时间将自行摆脱。您甚至可以按时间可视化地图；需要更长的路线会更长。Dijkstra 并不关心它在评估哪个，真的。它只关心找到具有最小数字的连续路线，而该数字是代表长度还是时间并不重要。
为了结合速度，简单的算法简单地使用白天的速度限制，并假设你从 A 到 B 时永远不必停下来；更高级的算法可以整合有关一天中的时间和交通模式的信息（这将影响您当时在该道路上行驶的平均速度），以及道路是高速公路还是地面街道（从而对停车时间做出有根据的猜测在一个路口）。您使用什么取决于您有什么可用的，但是基本的 4 层或 5 层时间维度应该足以满足除绝对时间最关键的应用程序之外的所有应用程序。对于地图中每条道路的每个方向，您需要早高峰、白天、晚高峰和夜间的平均速度，可能还需要午餐时间的数字。一旦你有了它，它'
如果您对时间信息感兴趣，那么为什么不使用时间信息而不是它们彼此之间的物理距离来标记图形边缘上的距离值。这样，您将搜索最快的路线，而不是最短的路线。然后您可以使用 Dijkstra/A* 来计算您的结果。
我有点不清楚你所说的时间依赖是什么意思。如果您的意思是您需要回答“上午 10 点之前从 x 到 y”形式的查询，那么您可以计算上午 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 算法。