在不确定性条件下实现地铁列车实时重新调度：一种混合机器学习与整数线性规划（L形模型）的方法

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：Real-time metro train rescheduling under uncertainties: A hybrid machine learning and integer L-shaped approach

地铁列车调度问题在产业5.0背景下提出风险厌恶型两阶段随机规划模型，结合机器学习预测子问题目标值以提升实时响应效率，并通过整数L-shaped方法分解求解大规模问题。

　　

作者：苏博毅、王方生、苏帅、安德烈亚·达里亚诺、王志凯、唐涛

深圳技术大学城市交通与物流学院，中国深圳，518118

摘要

地铁列车在运行过程中不可避免地会遇到故障，从而导致服务中断或紊乱。考虑到故障类型（如延误、停运和救援）以及这些中断或紊乱持续时间的不确定性，本文研究了工业4.0背景下的实时列车调度问题。本文构建了一个风险规避的两阶段随机规划模型，为每种可能的不确定性情况生成调度方案，并确保其无缝过渡。在第一阶段，调度决策不依赖于具体的不确定性情况，例如派遣备用列车的数量以及在处理故障时是否需要缩短列车运行时间。第二阶段采用所有适用于地铁线路的调度措施，并进行额外的调度决策。为了将人为因素纳入决策过程，利用平均条件风险价值（MCVaR）标准来反映调度员对风险管理的保守态度。在传统的整数L形框架下，该模型被分解为一个第一阶段的主问题和几个第二阶段的子问题。为了适应工业4.0的技术进步，采用监督机器学习来预测子问题的目标值，而不是直接求解它们，从而能够快速添加近似最优解并提高计算效率。在北京市亦庄地铁线上进行了数值实验。计算结果表明，与GUROBI相比，所提出的解决方案方法将平均计算时间减少了99.02%；与实际策略相比，开发的随机模型将平均目标值降低了22%以上，有助于发展智能且具有韧性的地铁系统。

引言

地铁系统是人口密集城市中重要的交通组成部分，为通勤者和旅客提供快速高效的服务（Shi等人，2023年；Wang等人，2024b年）。其在安全性、便利性和高容量方面的优势推动了乘客需求的稳定增长，因此需要不断扩展网络并增加服务频率。然而，这种增长也加剧了基础设施和设备的磨损，增加了意外故障的发生概率。作为复杂的跨学科系统，地铁运营极易受到各种故障引起的干扰和紊乱，其中列车（物理设备）是常见的故障源（Su等人，2022年；Zhu等人，2023年）。处理列车故障必然会导致当前服务的延误，这种延误通常会超过预留的缓冲时间。因此，这种延误会波及后续列车，甚至反向行驶的列车，使得原有的列车时刻表和列车运行计划变得不可行。在这种情况下，列车调度（包括列车时刻表调整和列车资源重新分配）成为调度员的一项关键任务。随着工业4.0的到来，通过智能列车调度提高地铁系统的韧性和实时响应能力已成为研究重点。

列车故障引起的干扰和紊乱可以分为三种主要类型：延误、停运和救援。在列车发生故障时，司机首先尝试识别故障设备并采取纠正措施（如重启）。如果列车恢复正常状态，则只会出现一次延误，这属于延误情况（即干扰）（Corman等人，2017年）。然而，如果故障持续存在且无法在合理时间内解决，则必须将故障列车撤出服务，从而导致停运或救援情况，这两种情况都属于紊乱（Zheng等人，2023年）。在停运情况下，故障列车仍能施加牵引力和制动力，可以自行返回车场。相比之下，当故障列车失去施加牵引力或制动力的能力时，就需要另一列车的协助才能返回。显然，在故障发生时准确预测故障持续时间和最终情况类型是不现实的，因为这些因素取决于具体的故障设备以及故障处理的效率和效果（如图1所示）。迄今为止，已经提出了许多数学模型和解决方法来处理确定性干扰或紊乱下的列车调度问题（Binder等人，2021年；Dollevoet等人，2015年；Pellegrini等人，2019年；Tang等人，2025年；Veelenturf等人，2016年；Wang等人，2024a年），最近也有少数研究开始探讨这些情况的持续时间不确定性（Sch?n和K?nig，2018年）。据我们所知，目前还没有研究专注于同时优化调度措施，以应对干扰或紊乱的持续时间和情况不确定性，尤其是由列车故障引起的干扰或紊乱。

这个问题难以解决，原因如下：首先，不确定性使得调度措施的优化变得非常复杂。例如，持续时间不确定性使得是否需要缩短后续列车运行时间的决策变得复杂。一方面，如果缩短运行时间后故障很快得到解决，则无需取消行程；另一方面，如果不采取缩短运行时间的措施而故障处理时间较长，交通拥堵区域会扩大，导致严重的列车延误。同时，情况不确定性也使得关于派遣备用列车数量的决策变得复杂。如果派遣了一些备用列车，但最终发现只是延误情况，那么多余的响应会增加运营成本。相反，如果没有派遣备用列车而情况恶化为停运或救援，那么在运行中的列车资源短缺将降低服务频率（Wagenaar等人，2017年）。此外，引入综合调度措施并考虑调度员的保守决策态度会引入非线性因素，显著增加模型的复杂性。鉴于列车调度的实时要求和NP难度，即使在确定性干扰或紊乱下设计高效的解决方案也颇具挑战性（Pan等人，2024年）。

为了解决上述问题，本文开发了一个风险规避的两阶段随机规划模型和一种混合机器学习与整数L形解决方法。在模型的第一阶段，优化不依赖于具体不确定性情况的调度决策。基于这些第一阶段的决策，第二阶段进一步调整列车时刻表和列车资源分配，以恢复正常运营。将平均条件风险价值（MCVaR）标准纳入目标函数，以减轻预期的负面影响和极端情况下的尾部风险（即长时间和严重情况）。为了便于计算，使用线性化技术将随机规划模型转换为等效的混合整数线性规划（MILP）形式。通过Laporte和Louveaux（1993年）提出的整数L形方法，该模型被分解为一个第一阶段的主问题和几个第二阶段的子问题。由于子问题重复求解，采用监督机器学习来预测它们的目标值，从而大大提高了计算效率。基于北京市亦庄地铁线的实际数据进行数值实验，验证了该模型和解决方法的有效性。

本文的其余部分安排如下：第2节回顾相关文献并强调我们的贡献；第3节详细描述研究问题并概述关键建模假设；第4节构建风险规避的两阶段随机规划模型，并将其转换为等效的MILP形式；第5节介绍混合机器学习与整数L形方法以实现实时模型求解；第6节展示实验的计算结果；第7节总结本文并讨论未来研究方向。

文献综述

文献综述

< />

问题描述

如图2所示，研究了一个典型的地铁系统，包括车站、站台、轨道段和车场。车站集合表示为：$P=\{1,2,\; \dots ,P\}$ 其中每个车站都有两个站台，支持双向运行。$P^{\text{turn}}?P$ 这些车站配备了轨道段，使列车能够改变运行方向。$P^{\text{depot}}?P$ 这些车站与车场相连，使备用列车能够进入主线提供服务。

数学建模

本节构建了风险规避的两阶段随机规划模型。首先提供相关符号，然后详细介绍运营约束。接着使用MCVaR标准定义目标函数。

解决方法

尽管转换后的等效MILP模型可以直接用商业求解器求解，但由于存在多种不确定性情况，模型规模较大，导致计算时间较长，无法满足实时要求。Laporte和Louveaux（1993年）提出的整数L形方法为具有L形块结构和整数第二阶段决策变量的两阶段随机规划问题提供了一种有效的求解方法。

数值实验

本节介绍了在北京亦庄地铁线上进行的数值实验，以验证所提出的数学模型和解决方法的有效性。算法使用PyCharm Community Edition 2022.2.2实现，优化任务通过GUROBI 11.0执行。所有实验都在配备Intel Core i9-9900K处理器（运行频率3.6 GHz）和128 GB系统内存的Windows计算机上进行。

结论

本文在工业4.0背景下研究了列车故障下的地铁列车调度问题。考虑到干扰或紊乱的情况和持续时间不确定性，构建了一个风险规避的两阶段随机规划模型，并将其转换为等效的MILP形式。为了满足列车调度的实时要求，提出了一种混合机器学习与整数L形方法。为了验证该方法的有效性，...

作者贡献声明

苏博毅：撰写——原始稿件、软件开发、方法论。 王方生：撰写——原始稿件、软件开发、方法论。 苏帅：撰写——审稿与编辑、监督、资金获取、概念构思。 安德烈亚·达里亚诺：撰写——审稿与编辑、监督、方法论。 王志凯：验证、软件开发。 唐涛：撰写——审稿与编辑、监督、资金获取。

利益冲突声明

作者声明他们没有已知的财务利益或个人关系可能影响本文的研究工作。