《Expert Systems with Applications》：Scheduling extra trains to an existing timetable along a railway corridor: An ADMM-based optimisation approach
编辑推荐：
本文研究了在既有计划时刻表上增开列车路径的调度问题。每列增开列车都有一个预先指定的发车时间窗：列车可以在该时间窗内的任何时间安排发车，否则将记录为调度失败。允许对既有和增开列车路径进行修改，包括调整发车和停站时间、引入计划外停站以及在车站进行越行。目标函数最小
本文研究了在既有计划时刻表上增开列车路径的调度问题。每列增开列车都有一个预先指定的发车时间窗：列车可以在该时间窗内的任何时间安排发车，否则将记录为调度失败。允许对既有和增开列车路径进行修改，包括调整发车和停站时间、引入计划外停站以及在车站进行越行。目标函数最小化已调度增开列车的总旅行时间与既有列车时刻表偏差的加权组合。可调节的权重因子使运营者能够在准点性要求和运营灵活性之间取得平衡。研究人员将该问题表述为时空网络上的整数线性规划，并开发了一种基于交替方向乘子法的分解框架。该方法将问题分解为针对每列列车的子问题，每个子问题使用时间依赖的最短路径算法求解。通过拉格朗日乘子和惩罚参数的迭代更新来强制执行耦合约束。在真实走廊上的计算实验表明，基于交替方向乘子法的方法能在合理计算时间内获得可行解，与拉格朗日松弛下界相比，平均最优性差距为5.43%。
**论文解读：基于ADMM的铁路走廊增开列车调度优化研究**
**一、研究背景与问题**
列车运行图编制问题是铁路运营研究的核心，涉及在满足一系列运营和安全约束的前提下，为铁路网络中的列车运行确定可行的时间表。高效解决此问题对于保障铁路运营效率和服务可靠性至关重要。列车运行图编制包含两项基本任务：一是列车时刻表调度，即在给定的基础设施和运营约束下创建基线时刻表；二是列车时刻表重新调度，即调整时刻表以应对短期的变更请求和/或处理网络中的实时中断或干扰。基线时刻表通常提前数月制定，但在运营前可能因工程作业要求或意外的需求波动而需要修改，范围从简单调整列车的发车/到达时间到取消既有列车路径或增加新的列车路径。
具体到增开列车路径调度问题，它结合了基线调度和重新调度的要素：调度员必须同时为新列车生成可行路径，并管理与既有服务的冲突。与实时重新调度动态响应中断不同，增开列车路径调度处理的是运营前几天到几周内发生的战术规划，通常由节假日、重大活动或临时货运需求等预期的需求增长驱动。在此问题中，基线时刻表可被视为固定或灵活可变。本研究采用灵活方法，允许对既有列车时刻表进行受控修改。研究考虑在具有不同速度列车的通用铁路走廊背景下进行增开列车路径调度。
当前研究存在以下空白：既有研究通常采用三种方法之一：将基线时刻表视为严格固定，不允许修改；或对既有和增开列车进行顺序优化；或为增开列车预先分配理想路径并对两类列车应用相同目标。这些方法在灵活性、全局优化或实际适用性方面存在局限。因此，有必要开发一种能够同时优化两类列车、允许对既有列车进行受控修改、并具备良好计算性能的新方法。本研究旨在填补这一空白，论文发表在《Expert Systems with Applications》期刊上。
**二、研究方法概述**
研究人员为增开列车路径调度问题开发了一种基于交替方向乘子法的分解优化框架。主要技术方法包括：
1. **问题建模与时空网络表示**：研究将铁路走廊抽象为图，车站按地理顺序索引。规划时间范围被离散化为均匀的时间间隔。所有运行、停站、到达和发车时间均表示为时间间隔的整数倍。关键创新在于使用时空网络对问题进行建模。在该网络中，节点表示“车站-时间”对，弧段表示列车在不同状态间的移动，包括运行弧、停站弧、额外停站弧、接入弧、驶出弧以及人工弧。这种表示法能够捕捉时刻表的时空特征，并将复杂的约束转化为对弧段或节点的简单限制。
2. **整数线性规划模型构建**：基于时空网络，研究将增开列车路径调度问题表述为一个整数线性规划模型。决策变量为二元变量，表示列车是否选择特定弧段。目标函数是最小化既有列车时刻表偏差与增开列车旅行时间的加权和，权重可调以平衡不同运营需求。模型包含流守恒约束、车站容量约束、最大停站时间约束以及列车安全间隔和越行约束。其中，安全间隔和越行约束通过定义弧段的不相容集合来紧凑地处理。
3. **基于交替方向乘子法的分解求解算法**：针对大规模整数线性规划直接求解计算不可行的问题，研究提出了基于交替方向乘子法的分解框架。该框架的核心是将原问题中耦合多个列车的复杂约束（如车站容量、安全间隔）通过引入拉格朗日乘子松弛到目标函数中，并增加二次惩罚项以提高收敛性。通过线性化处理，最终将问题分解为每个列车独立的子问题。每个子问题是一个在时空网络中寻找最短路径的问题，可通过时间依赖的最短路径算法高效求解。交替方向乘子法通过交替执行以下步骤进行迭代：固定其他列车的路径，依次求解每个列车的最短路径子问题；然后根据当前解违反耦合约束的程度，更新拉格朗日乘子和惩罚参数。算法设置最大迭代次数作为终止条件。该方法的优势在于能利用问题的自然结构，通过分解降低计算复杂度，同时二次惩罚项有助于驱动解向可行性靠近。
**三、研究结果分析**
研究基于中国京沪高铁走廊的实际数据进行了大量计算实验，验证了所提模型和算法的有效性。
**3.1 发车时间窗与权重比的影响**
实验评估了增开列车发车时间窗宽度和目标函数权重比（ω
1:ω
2，衡量既有列车偏差与增开列车旅行时间的相对重要性）对调度性能的影响。结果表明，更宽的发车时间窗能显著减少增开列车的旅行时间，而对既有列车偏差的影响在较高权重比下趋于稳定。当权重比为1:1时，增加时间窗灵活性会以略微增加既有列车偏差为代价，换取增开列车旅行时间的减少。随着权重比提高（即更重视既有列车准点性），既有列车的偏差时间减少，增开列车的旅行时间增加，体现了两个目标之间的权衡。此外，更宽的增开列车时间窗通常能降低计算时间，因为提高了求解的可行性。
**3.2 既有列车发车时间偏移的影响**
实验考察了允许既有列车在始发站进行发车时间偏移对调度结果的影响。结果表明，适度增加既有列车的发车时间灵活性，可以有效减少其自身的时刻表偏差，并改善增开列车的旅行时间。在插入更多增开列车的拥堵场景下，这种灵活性带来的益处更为明显。然而，过大的偏移量可能不会带来额外收益。
**3.3 增开列车类型的影响**
实验比较了插入不同类型增开列车（高速、低速、混合速度）的效果。结果显示，插入同质的高速列车对既有时刻表的干扰最小，既能保持既有列车较高的准点性，也能使增开列车获得较短的旅行时间。插入低速或混合速度列车会引入更多冲突，导致既有列车偏差和增开列车旅行时间显著增加，需要更多对既有时刻表的调整。
**3.4 惩罚参数的敏感性分析**
实验对交替方向乘子法中的二次惩罚参数ρ进行了敏感性测试。发现较大的惩罚值通常有助于更快收敛到可行解，但较小的惩罚值往往能获得更好的目标函数值。这需要在运行时间和解的质量之间进行权衡。
**3.5 与商业求解器及拉格朗日松弛法的比较**
为评估算法求解质量，研究将交替方向乘子法与商业求解器Gurobi以及拉格朗日松弛法进行了对比。对于小规模算例，交替方向乘子法能得到与Gurobi相同的全局最优解。对于中等规模算例，交替方向乘子法得到的解与Gurobi验证的最优解差距很小。对于大规模算例，Gurobi在规定时间内无法收敛，而交替方向乘子法能在较短时间内给出可行解。与拉格朗日松弛法提供的下界相比，交替方向乘子法所得解的平均最优性差距为5.43%，且在保证解可行性的同时，达到了与文献中拉格朗日松弛启发式算法相当的质量。
**四、讨论与结论**
**讨论部分**指出，本研究提出的基于交替方向乘子法的框架能够有效处理增开列车路径调度这一复杂组合优化问题。通过允许对既有列车时刻表进行有限调整，并赋予增开列车灵活的发车时间窗，模型提供了应对需求波动的实用工具。计算实验证明了该方法在真实大规模场景下的可行性和效率。研究也分析了不同运营参数（如灵活性设置、列车类型、权重比）对调度结果的影响，为运营者提供了决策依据。
当前模型假设区间运行时间固定，未明确考虑因停站带来的加减速时间。未来可通过扩展时空网络，引入不同运行弧类型来建模。此外，计算实验限于单条走廊，扩展到网络层面需要进一步验证。关于可扩展性，交替方向乘子法将问题分解为可通过最短路径算法求解的列车特定子问题。对于更大规模算例，主要的计算因素是时空网络的大小和收敛所需的迭代次数。潜在的改进包括从先前解中热启动乘子以及自适应调整惩罚参数。未来工作可将车底周转整合到增开列车路径调度中，或开发包含站台分配的更详细模型以增加实际适用性。
**研究结论**：本研究解决了在双线高铁走廊既有时刻表中增开列车路径的调度问题。增开列车路径调度问题因其组合复杂性以及最小化增开列车旅行时间与保持既有服务准点性这两个相互冲突的目标而 inherently complex（本质复杂）。
研究人员将增开列车路径调度问题表述为时空网络上的整数线性规划问题，并首次在此背景下引入了基于交替方向乘子法的分解方法。该方法将整数线性规划分解为独立的、针对每列列车的子问题，这些子问题通过时间依赖的最短路径算法求解。交替方向乘子法迭代在求解这些子问题和更新拉格朗日乘子以及交替方向乘子惩罚参数之间交替进行，显著减少了计算量。
在京沪走廊包含70列既有列车和多达24列增开列车的案例中，该算法在25次迭代和10-19分钟的CPU时间内收敛，在所有实验中均生成了高质量的无冲突时刻表。通过引入不同程度的灵活性，研究发现，允许既有列车在始发站进行适度的发车时间调整，能有效减少其自身偏差和增开列车的旅行时间。此外，拓宽增开列车的发车时间窗可以减少其旅行时间，而对基线服务的影响最小——除非在目标函数中赋予两种列车类型相同的权重，在这种情况下，会观察到既有列车的偏差略有增加。最后，纳入不同速度等级的列车增加了调度复杂性。尽管如此，本研究提出的框架能够解决这些冲突，并为铁路运营者提供了一种灵活的工具，以灵活应对需求波动或意外事件。
