复杂铁路调车场景优化：精确算法与迭代启发式协同的编组调度框架
一、研究背景与问题提出
1.1 铁路列车调度中的挑战
在铁路网络中，列车调度决定着每个列车单元何时运行何种任务。铁路运营者需要在既定的时刻表下，为每列列车指派适当的滚动式列车单元（即编组），并保证旅客需求与运营成本之间的平衡。然而，现实运营常会遇到基础设施中断（例如线路封锁或设备故障）导致的障碍。当轨道、车站或列车单元因事故或维修而不可用时，原定计划需要调整——这便是列车调度重排问题。
传统上，这类调度调整往往由调度员手工完成。这种方式难以同时考虑复杂的约束，如列车编组、调车作业（shunting）、列车容量和头程间隔要求，且缺乏对基础设施可用性的系统建模。文章指出，以往研究多将列车编组调整与基础设施调车分开处理，而现实中二者紧密关联。
1.2 研究目标
作者旨在开发一个既保证基础设施可行性，又能高效生成滚动式列车重排方案的统一框架。核心目标包括：
构建组合模型（composition model）：在满足编组容量与乘客需求条件下，优化列车编组变化、（解）挂操作等，尽量减少车厢公里数、乘客座位短缺小时数和取消列车数。 建立基础设施模型：基于事件–活动网络的约束，确保每次调车作业满足站内轨道和道岔的可用性，并考虑最小头程间隔。 设计解算策略：提出精确算法与迭代启发式相结合的框架，在保证解的可行性前提下，提高求解速度并缩小最优性差距。 验证方法有效性：通过七个包括全封锁的实例检验框架在荷兰铁路网络上的表现，并分析不同参数设置下的灵敏度。
二、方法与算法
本文首次在滚动式列车重排中系统引入基础设施可行性约束，通过精确算法与启发式协同，实现复杂铁路环境下的可执行编组调整。论文提出的框架包含两大核心部分：列车编组模型和基础设施可用性模型。二者分别优化列车编组与调车作业，并通过精确算法和迭代启发式进行结合。
2.1 列车编组模型（Composition Model）
该模型采用混合整数规划形式，以最小化运营成本和乘客服务损失为目标。其目标函数由多项加权和组成：
其中：
为需调度的列车集合， 为可选的编组集合。 – 为各项成本权重，分别对应车厢行驶里程、乘客座位短缺时间、取消列车数、库存不平衡惩罚、新增挂操作、新增解挂操作以及采用与原计划不同编组的惩罚。 表示列车 使用编组 时产生的车厢公里数， 表示乘客座位短缺小时数， 表示列车 的取消与否（二值变量，1 表示取消）， 与 分别为新增挂与解挂操作数量， 表示在车站 对于列车类型 的库存差额， 表示列车 是否采用不同编组。
主要约束包括：
单一编组选择：对每趟列车必须选择唯一的编组。 相邻列车编组一致性：若在某一站进行编组变化，前后列车的编组选择需满足（拆、挂）一致。 计算挂/解挂操作数：约束 (5)-(6) 定义挂与解挂操作数量。 库存平衡：约束 (7)-(8) 计算每个站在各时段的编组库存，以及最终库存与初始库存差异。 惩罚变量定义：约束 (9)-(13) 将新挂、解挂和不同编组等二值变量与物理变量联系起来。 初始状态与扰动前限制：约束 (14)-(15) 固定扰动发生前的编组，并保证各站初始库存正确。 变量域：约束 (16)-(21) 定义决策变量为二进制或非负实数。
2.2 基础设施可用性模型（Infrastructure Model）
为了保证调车作业在站内轨道与道岔的可行性，作者采用事件–活动网络 (event–activity network) 建模。关键思想是：
将每个列车的到发、调车作业抽象为“事件”，轨道间的运动抽象为“活动”，构建有向图 。 驾驶活动 (drive) 连接一个基础设施点到下一点的到发事件，表示列车运行。 停靠活动 (dwell) 连接到站后和离站前的事件，体现乘客上下车。 调车活动 (shunt) 表示列车或车厢的调车运动（进出车场），并遵守最小头程间隔 (headway) 约束。 约束：确保同一轨道或道岔上的不同列车满足最小头程时间差，保证在允许的时间窗口内调车成功。
2.3 精确算法与迭代启发式框架
论文提出两种求解策略：
精确算法：采用类似于组合 Benders 分解的方法，将编组模型与基础设施模型通过列生成或逻辑连结。该方法能保证全局最优性，但计算量大。
迭代启发式：交替执行编组模型和基础设施模型。每一轮迭代：
先在忽略基础设施约束的情况下优化编组，得到一个建议调车计划。 将该计划输入基础设施模型，检查各调车是否可行。若某些调车不可行，则向编组模型添加约束，禁止这些组合；然后重新优化，直至所有建议调车均可行或达到迭代上限。
该启发式模拟了现实中先由编组调度员提出方案，再由基础设施调度员审查的过程，可在较短时间内取得可行解，并有较小的最优性差距。
三、数据与实例设置
论文使用七个包含全封锁实例的荷兰铁路网络案例。每个实例在固定时段（早上 8:00–10:00）封锁某段线路，需重排列车调度与调车计划。实例特点包括：
封锁的位置和持续时间已知。 车站和列车分为Sprinter（短途）和Intercity（长途）两类，但只对 Intercity 调度重排。 允许调车和编组变化的车站包括 Utrecht Centraal (Ut) 与 Rotterdam Centraal (Rtd) 等7站，并对每个实例建模其内部轨道和道岔结构。
下图展示了三个不同的荷兰列车编组示例，分别由 ICM-III（3节车厢）和 ICM-IV（4节车厢）单元组合而成。
下图展示了调车运动路径示意图，蓝色虚线为调车运动在站内轨道间移动的路径。
下图展示了七个全封锁实例的位置与可调车站点分布，彩色线段表示封锁区间。
四、实验结果与分析
4.1 实例结果概述
作者在七个实例上比较了精确算法与迭代启发式，并与不允许调车的基准方案进行对比。主要发现：
启发式在运行时间和解质量间实现平衡：平均运行时间通常在几百秒以内，比精确方法快，但仍能达到 0% 的最优性差距或极小差距。 调车动作显著减少车厢行驶公里数及座位短缺：通过调车和编组调整，乘客座位短缺小时数下降约300小时，整体运营成本改善显著。 实例差异性分析：不同实例的封锁位置和时间影响调车机会。例如在 Utrecht Centraal 大站封锁时，启发式在第一迭代中提出9个调车动作，5个可行；第二迭代再修正为6个，其中5个与前一轮一致，新增1个调车动作。
4.2 权重与偏移灵敏度分析
作者进一步检验了模型关键参数设置对结果的影响。 试验显示，较低的不同编组惩罚权重（）会鼓励更多编组调整与调车操作，从而显著降低座位短缺与库存不平衡；而较高权重则倾向保持原计划稳定，虽减少调车次数，但会略微增加服务缺口。
在允许列车偏移时间方面，适度放宽最大偏移（如1–2分钟）能使更多调车动作具备可行性，提升整体灵活度与乘客服务水平；若完全禁止偏移，则调车机会明显受限。
综合结果表明，论文建议根据调度目标（稳定性 vs 服务质量）灵活设定参数，以在运营可行性与乘客满意度之间取得平衡。
五、挑战与应对
5.1 建模复杂性
主要难点在于将编组优化与基础设施可行性结合。编组模型涉及百万级决策变量和约束；基础设施模型需细致建模站内轨道及道岔，并考虑最小头程间隔与调车延误，易导致规模爆炸。为解决此问题，作者采取以下策略：
组合 Benders 分解：通过在精确算法中分阶段求解，先生成候选编组，再验证基础设施可行性。 迭代启发式：将二者拆开交替求解，通过逐步加切约束逼近可行解，从而缩减单次求解规模。
5.2 参数设置与权重选择
目标函数中权重选择影响解的偏好。作者根据荷兰铁路运营者 NS 的经验，将车厢行驶公里和座位短缺等权重设定为相近量级，对取消列车和库存不平衡赋予更高惩罚值。在灵敏度分析中进一步调整权重，帮助调度员根据实际需求平衡运营与服务目标。
5.3 基础设施模型精细度
建立基础设施模型时，如何在保证关键特征准确的同时减少复杂度是一大难点。作者仅在允许调车的站点建模站内轨道和道岔，并假设站外列车运行时间可通过小偏移解决。此简化使模型可在几分钟内求解，同时保证调车可行性。
六、结论与管理启示
论文构建了一个兼顾精确性与计算效率的列车重排框架，在解决基础设施可用性约束和列车编组优化方面取得显著成果。主要贡献包括：
统一建模：提出混合整数规划与事件–活动网络结合的模型，首次系统考虑调车与基础设施限制，填补了既有研究空白。 双层求解策略：通过精确算法确保整体最优性，通过迭代启发式提升计算效率与可行性，适应实际调度场景。 实例验证：在荷兰铁路七个全封锁实例上获得平均19% 的目标改进；启发式实现的调车方案显著降低座位短缺与运营成本。 权重与灵敏度分析：揭示权重设置与允许偏移对解的影响，为调度员提供调优依据。
管理启示：
数据驱动决策：应持续收集列车运行与基础设施利用数据，为模型提供准确输入，提高调度计划可靠性。 合理设定目标权重：调度员需根据运营目标（如成本节约、乘客体验）调整模型权重，实现多目标间的平衡。 动态更新与迭代：实际运行中建议采用迭代启发式框架，实时更新基础设施可用性和列车状态，快速生成可行的重排方案。 推广至其他网络：虽然本文聚焦荷兰铁路，但框架可推广到其他国家或城市轨道交通，尤其是在轨道有限且调车频繁的场景。
希望本次解读能帮助读者深入理解滚动式列车调度重排的建模与求解方法，为进一步研究与实践提供参考，也为铁路调度系统的智能化与可行性分析提供了方法论基础。
文章须知
推文编辑：单子叶
责任编辑：弓仪长
原文链接：https://doi.org/10.1016/j.trb.2025.103189
