4

假设您想从 A 点到达 B 点。您使用 Google Transit 路线，它会告诉您：

Route 1:
1. Wait 5 minutes
2. Walk from point A to Bus stop 1 for 8 minutes
3. Take bus 69 till stop 2 (15 minues)
4. Wait 2 minutes
5. Take bus 6969 till stop 3(12 minutes)
6. Walk 7 minutes from stop 3 till point B for 3 minutes.

总时间 = 5 次等待 + 40 分钟。

Route 2:
1. Wait 10 minutes
2. Walk from point A to Bus stop I for 13 minutes
3. Take bus 96 till stop II (10 minues)
4. Wait 17 minutes
5. Take bus 9696 till stop 3(12 minutes)
6. Walk 7 minutes from stop 3 till point B for 8 minutes.

总时间 = 10 次等待 + 50 分钟。

总而言之，Route 1 看起来好多了。然而，实际情况是69路公交车因为堵车晚了3分钟，结果我错过了6969路公交车。下一辆6969路公交车至少晚了30分钟，相当于5等待+70分钟（包括30米）在寒冷或炎热中等待）。如果谷歌真的宣传了这种可能性，那不是很好吗？我现在的问题是：考虑到时间表的不确定性，显示前 3 条路线的更好算法是什么？

谢谢！

4

5 回答 5

3

如何为不同类型的旅程元素添加表示不确定性水平的权重。

众所周知，都柏林市的巴士服务不及时，您可以在与都柏林巴士时刻表有关的任何事情上增加 40% 的误差，给出最好和最坏的情况。您还可以考虑高峰时段的长期交通延误。然后用户可以看到他们可能有 20% 或 80% 的机会实际建立连接。

您可以按“最可能正确”的因素对“最佳”旅程进行排序，并将此数据包含在向用户显示的结果中。

我的两分钱:)

于 2010-02-11T00:59:03.423 回答
2

对于英国铁路系统，每个换乘节点都有一个相关的“允许的最短换乘时间”。此处的路线规划器界面有一个高级选项，允许用户接受默认值或添加半小时增量。

在您的示例中，在步骤 2 中将“允许的最短转移时间”设置为 10 分钟将阻止如图所示的路线 1。当然，这意味着可能的最短行程时间会增加，但这是权衡。

于 2010-02-11T11:36:34.877 回答
1

如果考虑到不确定性，则不再有“最佳路线”，而是可以有一个“最佳策略”，使总运输时间最小化；但是，它不能表示为指令的线性序列，而更像是一个总体规划的形式，即“去公交车站X，等到10:00 公交车Y，如果它没有到达则步行到车站Z...” 众所周知，这很难呈现给用户（除了计算成本高昂）。

对于固定的指令序列，可以计算出它实际运行的概率；但是用户想要接受的确定性水平是多少？你会满足于 80% 的成功率吗？然后，当您错过其中一个连接时，纸牌屋在最坏的情况下会倒塌，例如，如果您错过每隔一小时一班的火车。

多年来，我编写了一个类似的程序来计算芬兰的长途巴士旅行，我只是报告了换乘时间，假设每辆巴士都准点。然后基本上每个换乘时间少于15分钟左右的计划都被忽略了，因为它们风险太大（有时在给定的路线上每天只有一两辆长途巴士）。

于 2010-02-11T02:15:38.260 回答
1

凭经验。记录实际到达时间与预定到达时间，并计算每个的平均值和标准偏差。在考虑可能的路线时，计算给定的一段到达时间晚到足以让您错过下一段的概率，并计算平均等待时间P(on time)*T(first bus) + (1-P(on time))*T(second bus)。如果您必须考虑多条腿，这会变得更加复杂，每条腿都可能独立迟到，并且您可能会错过多个可能的下一条腿，但一般原则是成立的。

于 2010-02-11T11:24:14.137 回答
1

灾难性故障应该是第一个检查。

当您尝试连接当天的最后一班巴士时，这一点尤其重要，这是路线的关键部分。骑手需要知道正在发生的事情，这样他就不会分心并知道风险。

之后，它可以评估最坏情况下的单次失误。

然后，如果您真的想花哨，请查看等待点所在社区或中转站的犯罪统计数据。

于 2010-02-11T11:30:44.137 回答