algorithm - 仅通过公共(public)交通找到最佳路线的策略？

Question

寻找汽车的路线非常简单:您存储所有道路的加权图，您可以使用 Djikstra's algorithm [1].公交路线不太明显。对于公共(public)汽车，您必须表示诸如“等待 10 分钟等待下一类公共(public)汽车”或“步行一个街区到另一个公共(public)汽车站”之类的东西，并将这些输入到您的寻路算法中。

对于汽车来说，这甚至并不总是那么简单。在一些城市，一些道路是单向的，只在早上进城，单向在晚上只出城。一些先进的 GPS 知道如何在高峰时段避开繁忙的路线。

您将如何有效地表示这种时间相关图并找到路径？不需要可证明的最佳解决方案；如果旅行者想准时到达，他们会买辆车。 ;-)

[1] 在示例中提到的一个很棒的算法，因为每个人都听说过它，尽管 A* 是此应用程序更可能的选择。

Answer 1

我参与了瑞典斯德哥尔摩公共(public)交通的一个行程规划系统的开发。它基于 Djikstra 算法，但在访问系统中的每个节点之前终止。今天，当每个站点都有可靠的坐标可用时，我想 A* 算法会是最佳选择。

定期从多个数据库中提取有关即将到来的流量的数据，并将其编译成加载到我们搜索服务器集群内存中的大表。

成功算法的一个关键是使用基于行程和等待时间乘以不同权重的路径成本函数。在瑞典语中称为“kresu”时间，这些加权时间反射(reflect)了这样一个事实，例如，一分钟的等待时间通常相当于两分钟的旅行时间“不方便”。

KRESU 权重表

• x1 - 旅行时间
• x2 - 在站点之间行走
• x2 - 等站在旅途中。停在屋檐下，有商铺等可以稍微搞定较轻的重量和拥挤的车站调高算法。
• 首站等待时间的权重是交通强度的函数，可以在 0.5 到 3 之间。

数据结构

面积您的旅程可以开始或结束的命名区域。公交车站可以是一个有两个车站的区域。具有多个站台的较大车站可以是一个区域，每个站台一个站点。数据:姓名、停靠点

停止包含所有公共(public)汽车站、火车站和地铁站的数组。请注意，您通常需要两个站点，每个方向一个，因为过马路或步行到另一个站台需要一些时间。数据:名称、链接、节点

链接您可以从该站点步行到达的其他站点列表。数据:其他站点，步行到其他站点的时间

线路/旅游您在公共(public)汽车上有一个号码和一个目的地。公共(public)汽车从一站出发，在到达目的地的途中经过几站。数据:号码、姓名、目的地

节点通常你有一个时间表，它应该在巡回赛的第一站和最后一站停留的时间最少。每次公共(public)汽车/火车经过一个站点时，您都​​会向数组中添加一个新节点。该表每天可以有数百万个值。数据:线路/行程、站点、到达时间、出发时间、误差范围、行程中的下一个节点

搜索与用于存储到达那里的方式和路径成本的节点数组大小相同的数组。数据:与前一个节点的反向链接(如果节点未访问则不设置)，路径成本(未访问的无限)