一种针对公共交通站点调度问题的端到端解决方案

《ACM Transactions on Cyber-Physical Systems》：An End-to-End Solution for Public Transit Stationing and Dispatch Problem

提出基于非近视序列决策程序（SMDP）和蒙特卡洛树搜索（MCTS）的动态调度框架，优化公共交通过剩车辆的停放与派发，最大化乘客服务量并减少空驶里程。通过生成模型模拟乘客流动和事故概率，结合实时数据管道开发Vectura仪表板，实现高效决策支持。实验表明该框架在真实场景中乘客服务量提升2%，空驶里程减少42%。

　　公共公交交通系统为现代社区的许多部分提供了关键的运输服务，因此准时性和维护可靠的服务质量至关重要。然而，由于拥挤、车辆故障和道路事故等突发事件，常常导致服务质量下降。尽管交通管理部门会保留有限数量的备用车辆并在发生故障时调度这些车辆来缓解受影响的路线，但这一过程通常是临时的，并且需要依赖人工经验和直觉来在不确定性中分配资源。本文描述了一种使用非短期的顺序决策程序来解决这个问题的方法，以回答两个相互关联的决策问题：（a）是否应该预判问题并主动将公交车辆停放在高可能性发生中断的区域；（b）决定是否以及选择哪辆车调度到特定的问题。我们的方法是在与WeGo Public Transit，一家位于田纳西州纳什维尔的公共交通机构合作开发的，将系统建模为半马尔可夫决策问题（SMDP），并利用蒙特卡洛树搜索（MCTS）解决，展示了在这些决策问题上如何以最大化整体奖励（即服务的人数）的方式得出答案。我们从生成模型中采样许多可能的未来情景，每个情景都被分配到一个树中并使用根部并行化进行处理。我们通过真实世界和扩展数据，从田纳西州的两家交通机构验证了我们的方法。实验表明，该框架可以服务更多乘客，减少空驶里程。最后，我们介绍了Vectura，这是一个为交通调度员提供完整系统视图并访问我们开发工具的仪表板。

随着城市的发展，公众对高效、可靠的公共交通系统的需求也在增加。在新冠疫情之后，公共交通的乘客量正在恢复，现在已经超过了疫情前水平的70%。然而，这种恢复给交通机构带来了新的压力，因为它们越来越多地面临由拥挤、车辆故障和交通相关事件引起的运营中断。这些中断不仅降低了服务质量，还削弱了公众信任，并可能逆转疫情期间的乘客增长。在2022年，WeGo Public Transit运营了大约100辆公交车，每天每辆公交车平均有15次行程，以服务成千上万的乘客。那一年，该机构记录了超过6500次服务中断，这些中断由天气、机械故障或事故引起。当发生中断时，机构通常依靠有限的替代车辆储备，这些车辆可能停放在车库或城市各处的站点。调度这些有限资源的任务通常由人工操作人员根据直觉和经验进行，这导致了短期的决策，没有考虑整个系统的影响或未来的不确定性。

我们称之为“固定线路公共交通系统的动态调度和派遣问题”。传统方法假设固定时间表和常规间隔，以确保广泛覆盖。然而，这些假设在现实条件下的随机中断和高度变化的需求下失效。尽管之前的研究提出了动态路线、空驶和跳站策略，但大多数现有方法要么过于简化决策空间，要么忽略下游影响，或者需要计算资源，这限制了实时应用的可能性。此外，很少有方法明确建模不确定性，或者提供与现有调度员工作流程无缝集成的工具。在实践中解决这个问题需要在高度动态的决策空间中进行推理。状态空间包括所有车辆的实时位置和状态、计划和中断的行程，以及时间变化的乘客需求。动作空间同样复杂，包括派遣、空驶和车辆重新分配，所有这些都在运营约束下进行。这些挑战因中断的随机性质和极端事件的罕见性而加剧，这限制了学习型方法如深度强化学习的有效性。这些方法通常需要大量的训练数据，难以处理稀疏奖励，并且在高维、组合环境中缺乏鲁棒性。鉴于这些限制，我们转向了基于搜索的方法：我们将问题建模为半马尔可夫决策过程（SMDP），并使用蒙特卡洛树搜索（MCTS）进行求解。MCTS能够通过模拟未来场景并评估长期结果，实现高效、非短期的规划，因此非常适合这种复杂、不确定性较高的环境。

本文提出了一个基于原则的、数据驱动的框架，用于在不确定性下进行动态派遣。首先，我们介绍了在线、非短期的优化方法，用于派遣替代公交车，旨在最大化整体效用（如服务的人数），同时在实时约束下进行操作。其次，我们将问题建模为SMDP，并使用MCTS进行求解，这使得在较长的规划范围内进行高效、前瞻性的规划成为可能。第三，我们使用合成场景和多个交通机构的真实世界数据进行了广泛的评估，表明我们的方法在服务乘客数量上比使用替代停靠策略的贪婪基线提高了最多7%，并减少了42%的空驶里程。最后，我们强调了实际操作集成的重要性，开发了Vectura，一个与WeGo Public Transit共同设计的实时仪表板，支持调度员在可视化中断、监控系统性能以及将优化算法整合到日常工作中。

在这一部分，我们描述了固定线路交通系统的特点，并提出了动态停靠和派遣问题的建模方法。我们还讨论了问题的概念，引入了动作空间，并最终将问题建模为SMDP。我们提供了一个符号查找表，供参考。

固定线路公共交通依赖于一组车辆按照一致且可预测的时间表在特定路线上的运行。任何导致车辆偏离其时间表的事件或事故都可能导致乘客等待时间增加、发车间隔拥挤、干扰换乘，最终影响可靠性并削弱乘客信任。为应对这种情况，交通机构通常保留有限数量的替代公交车，这些车辆没有固定时间表，可以在发生意外事件时被部署以减轻影响。替代公交车需要被派遣到特定的站点或路线，以确保在发生中断时能够及时响应。

在这一部分，我们介绍了生成模型，用于模拟乘客到达、中断预测和车辆调度。我们使用生成模型来预测乘客在各站点的上车和下车数量，并通过这些模型生成可能的乘客到达链。此外，我们还利用统计模型来预测中断的发生可能性，从而为决策提供依据。通过这些模型，我们能够生成多个事件链，以反映交通系统中的不确定性。我们还采用根部并行化策略来处理这些事件链，从而在每个决策点上生成多个决策树，评估每个树的平均得分，最终选择得分最高的动作。

在这一部分，我们展示了我们的方法在实际交通数据中的应用效果。我们评估了我们的框架在公共交通数据中的有效性，这些数据来自美国的一个主要大都市。我们使用真实世界数据进行比较，并展示了我们的方法在服务乘客数量和减少空驶里程方面的改进。我们还介绍了一个名为Vectura的仪表板，它是一个实时数据可视化工具，旨在帮助交通调度员更有效地进行调度决策。

在这一部分，我们讨论了与现有研究的联系。我们回顾了固定线路公交系统调度的相关工作，包括静态调度和动态调度。静态调度是设计固定路线并在离线环境中进行的，而动态调度则旨在实时适应需求和系统不确定性。当前的动态调度方法主要集中在研究公交车的等待策略，以改善乘客体验。这些方法包括通过控制车辆的到达时间来减少发车间隔、乘客等待时间或其他服务指标。然而，这些方法通常不考虑车辆的重新分配策略，而我们的研究则引入了这种策略，因为它在拼车和共享出行应用中已被证明是有效的。通过结合生成模型和MCTS，我们的方法能够处理复杂的决策空间，并提供更优的调度方案。

在这一部分，我们介绍了我们的方法在实际交通系统中的应用效果。我们使用真实世界数据和合成数据进行实验，展示了我们的方法在服务乘客数量和减少空驶里程方面的优势。我们还讨论了系统在处理大规模数据时的扩展能力，以及如何在有限的计算资源下实现高效调度。通过这些实验，我们验证了我们的方法在不同交通机构和不同规模下的有效性，并展示了其在提升公共交通服务质量方面的潜力。

在这一部分，我们介绍了Vectura，这是一个与WeGo Public Transit合作开发的实时仪表板。Vectura旨在为交通调度员提供一个全面的系统视图，并通过集成的优化工具帮助他们进行决策。通过将先进的算法与直观的数据可视化相结合，Vectura使得调度员能够在日常运营中更有效地应对突发事件，提升整体服务质量。

在未来的工作中，我们提出了一些改进措施，以应对生成模型在处理分布外（Out-of-Distribution, OOD）数据时可能遇到的问题。这些改进包括使用不确定性感知的生成模型，如贝叶斯变分自编码器（Bayesian Variational Autoencoders）或归一化流（Normalizing Flows），这些模型不仅能够生成数据，还能提供校准的不确定性估计。通过引入这些模型，我们能够检测出高不确定性区域，从而识别模型预测可能不可靠的区域。此外，当检测到分布外输入时，我们建议使用保守或短期的基线策略作为回退方案，以确保系统在面对意外情况时能够平稳降级性能，而不是出现灾难性故障，从而在系统恢复到熟悉模式后实现恢复。