仅通过公共交通找到最佳路线的策略？

Question

寻找汽车的路线非常简单:您存储所有道路的加权图表,您可以使用Djikstra的算法 [1].公交路线不太明显.使用总线,您必须表示诸如"等待下一班车10分钟"或"将一个街区走到另一个公共汽车站"之类的事情并将其提供给您的寻路算法.

这对汽车来说甚至都不简单.在一些城市,一些道路在早上单向进入城市,而在晚上仅单向进入城市.一些先进的GPS知道如何在高峰时段避开繁忙的路线.

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

[1]一个很好的算法在一个例子中提到,因为每个人都听说过它,虽然A*是这个应用程序的一个更有可能的选择.

Answer 1

我参与了瑞典斯德哥尔摩公共交通的一个journy计划系统的开发.它基于Djikstra的算法,但在系统中访问每个节点之前终止.今天,当每个站点都有可靠的坐标时,我猜A*算法就是选择.

有关即将到来的交通的数据定期从几个数据库中提取出来,并编译成加载到我们搜索服务器集群内存中的大型表.

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

KRESU重量表

• x1 - 旅行时间
• x2 - 在站点之间行走
• x2 - 在旅途中等待.在屋顶下停车,有商店等可以获得稍低的重量和拥挤的站点来调整算法.
• 第一站等待时间的重量是交通强度的函数,可以在0.5到3之间.

数据结构

区域 您可以开始或结束旅程的命名区域.巴士站可能是一个有两个站点的区域.具有多个平台的较大站可以是一个区域,每个平台具有一个停靠点.数据:名称,停止区域

停止 所有公共汽车站,火车站和地铁站的阵列.请注意,您通常需要两个停靠点,每个方向一个停靠点,因为穿过街道或步行到另一个平台需要一些时间.数据:名称,链接,节点

链接 从此站点步行可以到达的其他站点列表.数据:其他停止,步行到其他停止的时间

线路/旅游 您在公共汽车和目的地有一个号码.巴士在一站开始,经过几站到达目的地.数据:数字,名称,目的地

节点 通常你有一个时间表,它在巡回赛的第一站和最后一站的时间最短.每次公共汽车/火车通过停靠时,您都会向阵列添加新节点.该表每天可以有数百万个值.数据:线路/巡视,停止,到达时间,出发时间,误差范围,巡回中的下一个节点

搜索 阵列的大小与用于存储如何到达目的地的路径数量的节点数组相同.数据:与上一节点的反向链接(如果未访问节点则未设置),路径成本(未访问的无限)

Answer 2

您所谈论的内容比数学模型更复杂,这些数学模型可以用简单的数据结构(如图形)和"简单"算法(如Djikstra's)来描述.您要求的是一个更复杂的问题,如自动化物流管理领域遇到的问题.

考虑它的一种方法是你问一个多维问题,你需要能够计算:

1. 距离优化
2. 时间优化
3. 路线优化
4. "时间范围"优化(如果它是5:25并且公共汽车仅在7:00出现,则选择另一条路线.)

鉴于所有这些情况,您可以尝试使用复杂的多层数据结构进行确定性建模.例如,您仍然可以使用加权的二维图来表示现有的潜在路线,其中每个节点还包含一个有限状态自动机,它根据时间值向路径添加权重偏差(因此通过在5:25跨越一个节点)如果您的模拟在7:00越过它,则会得到不同的值.)

但是,我认为在这一点上你会发现自己的模拟越来越复杂,当建议转移到现实世界时,很可能无法提供最佳路线的"很好"近似.事实证明,当遇到真实世界的混沌行为和动态时,软件和数学建模和模拟充其量只是一个弱工具.

我的建议是使用替代策略.我会尝试使用遗传算法,其中个人的DNA计算出潜在的路线,然后我会创建一个适应度函数,以更"易于维护"的查找表方式编码成本和权重.然后我会让遗传算法试图收敛于公共交通路线查找器的近似最优解.在现代计算机上,诸如此类的GA可能会表现得相当好,并且它应该至少相对于现实世界的动态性.

我认为大多数做这种事情的系统都采用"简单的方法",只需做一些像A*搜索算法,或类似于贪婪的成本加权有向图行走的东西.需要记住的是,公共交通的用户不知道自己的最佳路线是什么就可以了,所以90%的最优解仍然将是对于一般情况下的最佳解决方案.

Answer 3

从公共交通领域了解一些数据点:

1. 每次转会都会导致10分钟的罚款(除非是定时转账).也就是说,精神上涉及一辆需要40分钟的单车的行程大致相当于需要转机的30分钟行程.
2. 大多数人愿意步行到公共汽车站的最大距离是1/4英里.火车站/轻轨约1/2英里.
3. 距离与公共交通车手无关.(只有时间很重要)
4. 频率很重要(如果连接错过多长时间直到下一个总线).如果替代方案被搁置一小时以进行下一次快递,骑手将更喜欢更频繁的服务选项.
5. 铁路比公交车有更高的偏好(更有信心火车将来往并朝着正确的方向前进)
6. 支付新票价是一个很大的打击.(加上约15-20分钟的罚款)
7. 总行程时间也很重要(以上罚款)
8. 连接有多无缝？骑车人是否必须在火车站穿过繁忙的街道？或者它只是走下火车,步行4步到公交车？
9. 越过繁忙的街道 - 转移的另一个重大损失 - 可能会错过连接,因为无法快速穿过街道.

Answer 4

如果行程的每一段的成本都是及时测量的，那么唯一的复杂之处就是将时间表考虑在内——这只是将每个节点的成本更改为当前时间 t 的函数，其中 t 只是总行程时间，所以far（假设计划被标准化为从 t=0 开始）。

因此，节点 A 的成本不是 10 分钟，而是 f(t) 的成本定义为：

• t1 = nextScheduledStop(t); //获取t时刻或之后的下一站时间
• baseTime for leg = 10 //例如10分钟的行程
• 返回 (t1-t)+baseTime

因此，等待时间被动态地包含在每条腿的成本中，而公交车站之间的步行只是具有恒定时间成本的弧线

使用这种表示，您应该能够直接应用 A* 或 Dijkstra 算法