面向弹性提升的动车组运用计划优化

Resilience-Oriented Optimization of Electric Multiple Unit Operation Planning

摘要

为解决高速铁路在受外部扰动情形下，动车组运用计划弹性不足、易引发大范围延误传播的问题，提出一种面向弹性提升的动车组运用优化方法。从优化动车组接续结构角度出发，分析接续冗余时间在晚点吸收过程中的作用机理，提出基于接续冗余时间与后序列车缓冲时间的接续对弹性函数。以动车组接续网络为基础，将动车组担当列车任务过程转化为带资源约束的车辆路径问题，综合考虑动车组路径唯一性、列车被担当需求、动车段所日计划末库存需求及车站到发线容量等约束条件，构建以交路段弹性值最大化为目标的优化模型。针对模型变量规模庞大的特征，设计列生成算法进行分解求解。主问题采用线性松弛模型生成对偶信息并传递给子问题，子问题通过带资源约束的最短路径模型生成可行路径列反馈回主问题，循环迭代直至收敛。以京沪高速铁路为算例进行验证，选取某日227列列车为研究对象。结果表明，优化后的动车组运用计划在不增加动车组运用数量的前提下，交路段平均弹性值由0.851提升至0.974，增幅达14%；弹性值大于0.99的强弹性交路段比例提升至77%，低于0.5的弱弹性交路段被完全消除。进一步的灵敏度分析显示，适度增加动车组运用数量可显著改善最弱弹性交路段的运行稳定性，当额外增加2组动车组后，所有交路段的弹性值均超过0.9，但整体弹性提升的边际效益逐渐减弱，不建议在计划阶段增加运用动车组。通过适度约束最大接续时间，可以在尽可能维持交路弹性的同时，显著提高动车组周转效率。研究成果可为铁路运输部门开展动车组运用计划编制与弹性优化提供方法参考与决策支持。

Abstract

To address the problems of insufficient resilience of electric multiple unit operation planning and easy induction of large-scale delay propagation in high speed railway under external disturbances, an optimization method of electric multiple unit operation planning for resilience enhancement was proposed. From the perspective of optimizing the connection structure of electric multiple units, the action mechanism of connection buffer time in the delay absorption process was analyzed, and a resilience function of connection pair based on connection buffer time and subsequent train buffer time was proposed. Based on the electric multiple unit connection network, the process of electric multiple units serving train tasks was transformed into a vehicle routing problem with resource constraints. By comprehensively considering constraints such as uniqueness of multiple unit paths, requirements for trains to be served, inventory requirements at the end of the daily plan in multiple unit depots, and arrival and departure track capacity at stations, an optimization model aiming at maximizing the resilience value of routing sections was constructed. In view of the characteristic of massive variable scale of the model, a column generation algorithm was designed for decomposition and solution. The master problem adopted a linear relaxation model to generate dual information and transmitted it to the sub-problem, and the sub-problem generated feasible path columns through a shortest path model with resource constraints and fed them back to the master problem, iterating in loops until convergence. The Beijing-Shanghai High Speed Railway was taken as a calculation example for verification, and 227 trains on a certain day were selected as the research object. The results show that, on the premise of not increasing the application number of electric multiple units, the average resilience value of routing sections in the optimized electric multiple unit operation planning increases from 0.851 to 0.974, with an increase of 14%; the proportion of strong-resilience routing sections with a resilience value greater than 0.99 increases to 77%, and weak-resilience routing sections with a resilience value lower than 0.5 are completely eliminated. Further sensitivity analysis shows that moderately increasing the application number of electric multiple units significantly improves the operation stability of the weakest-resilience routing sections; after adding two extra sets of electric multiple units, the resilience values of all routing sections exceed 0.9, but the marginal benefit of overall resilience enhancement gradually weakens, and it is not recommended to increase the applied electric multiple units in the planning stage. By moderately constraining the maximum connection time, the EMU turnover efficiency is significantly improved while maintaining the routing resilience as much as possible. The research results provide methodological reference and decision support for railway transportation departments to carry out the compilation and resilience optimization of electric multiple unit operation planning.

Graphical abstract

关键词

高速铁路运营 / 动车组运用计划 / 弹性提升 / 列生成算法 / 接续冗余时间

Key words

High Speed Railway Operation / Electric Multiple Unit Operation Planning / Resilience Enhancement / Column Generation Algorithm / Connection Buffer Time

0　引言

高速铁路系统以其高速、安全与准点的特点成为现代交通运输体系中的核心组成部分。然而，随着我国高速铁路网的不断扩张和列车开行密度的逐步提升，列车运行的复杂性与系统耦合性显著增强。当运行图受到天气、设备故障或客流波动等因素造成的外部扰动时，列车晚点容易呈现连锁传播，导致运行秩序紊乱和运力效率下降^[1]。由于一列动车组担当的车次多，运行范围广，接续关系一旦受到影响，易在更大范围内诱发晚点扩散；同时，对动车组运用的调整也会在较大范围内影响列车的运行秩序。因此，在计划层面提升动车组运用的抗干扰能力，对于抑制晚点传播和保障按图行车至关重要。

动车组运用计划是连接列车运行图与动车组资源配置之间的关键环节，其决定了每列动车组在既定运行图下的担当车次与检修安排^[2]。既有研究通常将动车组运用相关问题转化为多商品流问题^[3]或多旅行商问题^[4]处理，优化目标多集中于最小化动车组运用数量^[5]、提高运用均衡性^[6]及减少检修次数^[7]等。在求解方法方面可分为精确算法与启发式算法2类。精确算法多借助商业求解器^[8]或采用列生成^[9]、拉格朗日松弛^[10]等分解算法以获取最优解；启发式算法则多利用蚁群算法^[11]、模拟退火^[12]、粒子群算法^[13]等智能优化方法在可接受的计算时间内求得高质量近似解。

近年来，部分学者开始关注在不确定条件下提升动车组运用计划的稳定性。王昕等^[14]将列车运行过程视为离散事件动态系统，引入Max-Plus Algebra方法建立列车运行图的状态动力学方程和列车晚点传播模型，基于案例分析得到调整列车发车次序、设置合理的交路接续冗余时间、调整晚点列车交路接续关系的措施均可有效在晚点条件下尽快恢复列车正常运行的结论。仝硕等^[15]通过相邻列车任务完成接续的概率定量刻画接续可靠性，考虑热备车接续与空车调拨，建立以最小化接续时间、空车调拨距离、接续可靠性下降率的多目标优化模型。通过蚁群算法求解的优化结果表明，考虑列车接续可靠性的动车运用计划虽然会增加空车运行里程与接续时间，但是可以有效降低接续风险。Tréfond等^[16]提出了一种优化动车运用计划鲁棒性的整数线性规划模型，引入了基于动车组运用的鲁棒性指标，包括接续时间均衡性和动车运用负载均衡性，同时考虑了空车调拨的成本最小化和避免动车不合理接续时间。仿真结果表明优化后的动车运用计划不仅在面对扰动时表现出更强的延误吸收能力，同时还能在维持低运营成本的情况下显著提升列车准点率。朱昌锋^[17]针对普速旅客列车车底在接续过程中的延误传播问题，构建了考虑车底接续延误概率的鲁棒优化模型，以最小化接续延误概率和均衡车底运用为目标，引入多目标粒子群优化算法进行求解。结果表明该方法不仅提升了车底资源的利用效率，还显著增强了车底套用方案的鲁棒性与运行稳定性。

既有研究多侧重于考虑接续冗余时间的增量与接续完成的概率提升的目标下，对动车组的交路计划稳定性进行优化。但在铁路实际生产过程中，冗余时间的增加意味着动车组占用车站到发线资源时间的延长，且空车调拨过程亦会引入潜在的晚点风险。因此研究将在不允许空车调拨与车站到发线能力限制纳入约束条件的情况下，充分考虑接续冗余时间的边际递减效应，结合前序列车晚点概率与后序列车缓冲时间，提出接续对弹性评价函数。基于动车组接续网络构建了面向弹性提升的动车组运用计划优化模型，以期寻求运输能力利用与交路弹性之间的最优平衡。最后设计并实现了基于列生成的求解算法，以京沪高速铁路(北京南—上海虹桥)为算例验证所提方法的有效性，并讨论了增加动车组运用数量与限制最大接续时间对运用计划弹性的影响。

1　问题描述与分析

1.1　接续结构的改变对交路弹性的影响

动车组接续是指同一列动车组在完成前序车次运行任务后，于车站短暂停留并完成必要作业，继续担当后序车次的过程。前序列车与后序列车的连续运行关系即为一个接续对。在接续过程中，动车组通常需进行旅客乘降、司机换端、座椅调整、车厢清扫保洁、上水、吸污、送餐、货物乘降等必要作业^[18]，完成后并不会立即投入下一车次的运行，而是等待至计划出发时刻才启动列车。此期间的等待时间即为接续冗余时间。该时间并非接续作业的必要环节，但可用于吸收前序车次的到达晚点，实现晚点在车站层面的局部消化，从而避免延误向后序列车传播。

研究将交路弹性定义为交路段中所有接续对的接续冗余时间对前序列车晚点的总吸收能力。在既定运行图条件下，通过优化动车组的接续结构，可实现接续冗余时间的合理分配与利用，从而增强交路弹性。接续结构指交路段中各接续对的衔接和组合关系。动车组接续结构优化如图1所示，在不考虑运行过程中动态改变接续关系的前提下，其优化策略主要包括以下3类。

（1）交换列车之间的接续对。车站A中当原有接续对由1—4，2—3调整为1—3，2—4时，接续结构的改变并不会改变这些接续对的总接续时间和总接续冗余时间。然而，这一结构调整会导致各接续对的接续冗余时间的变化，本质上属于接续冗余时间的再分配。通过这种方式，可将接续冗余时间在不同接续对之间进行合理、均衡地分配，使弹性不再集中于单一接续对，而是分散至多个接续对中，从而提升整体运用计划的稳定性。

（2）增加运用动车组。车站B中各接续对的接续时间普遍紧张，冗余时间不足，可通过引入额外动车组参与接续。增加一列动车组接续列车1，使原需担当列车1的动车组能够站内停留至接续列车2，而原需担当列车2的动车组则可继续担当后续其他车次。该策略能够显著增加总接续冗余时间，但其优化成本较高，主要体现在：①动车组固定成本增加，新增运用动车组将显著提升成本；②出入库走行里程增加，额外动车组需执行非载客走行，导致运用效率下降；③到发线占用增加，需额外腾出线路资源以满足停靠与接续需求。故增加运用动车组的策略需要谨慎实施。

（3）空车调拨。当结束担当列车4的动车组的修程将满或易发生晚点时，可通过空车调拨方式，将已完成列车6任务的动车组从车站B调拨至相邻车站C以接续列车7，实现异站接续。该方法在不增加动车组运用数量的前提下，提升了动车组运行的灵活性^[19]。在发生严重运行干扰下，也可通过空车调拨实现受较大影响的后序列车的正常接续^[20]。然而，该策略在空车调拨过程中可能引入晚点，同时需要承担额外的空车运行成本。由于研究旨在提升动车组运用的稳定性，不应引入额外的晚点风险，因此不考虑在计划编制阶段采用空车调拨策略。

1.2　接续弹性分析与计算

通过合理设计动车组接续结构，可以使接续冗余时间更有效地吸收列车到达晚点。然而，接续冗余时间并非越长越好。为提升运行稳定性而增加的冗余时间必然占用系统的其他资源：一方面，冗余时间的增加会导致列车长时间占用车站到发线资源；另一方面，本应用于后续接续的时间被冗余时间使用，也会间接增加所需的动车组数量。此外，冗余时间的延长对吸收晚点的概率提升具有边际递减特性，即随着冗余时间增加，能够覆盖的晚点概率增量逐渐减小^[21]。因此，接续冗余时间的总量不应被简单地作为优化目标。

晚点在运行图中的传播过程中，可通过接续冗余时间和缓冲时间予以吸收，从而避免延误进一步影响动车组的后续接续任务^[17]。假设在A车站的一组接续对中，t_{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}为前序列车到达晚点时间，t_{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{c}\mathrm{t}}为该接续对在车站的计划接续时间，t_{\mathrm{m}\mathrm{i}\mathrm{n}}为最小接续时间，t_{\mathrm{r}\mathrm{b}}为后序列车运行线的总缓冲时间，t_{\mathrm{c}\mathrm{b}}为该接续对的接续冗余时间。分析该动车组的接续结构对晚点的传播影响，接续冗余时间对晚点吸收的效果分析如图2所示。若接续对中前序列车的到达晚点时间t_{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}小于该接续对中的冗余时间t_{\mathrm{c}\mathrm{b}}，晚点可在接续过程中于A车站被完全吸收，不会影响后序列车的正常发车；若到达晚点时间t_{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}大于接续冗余时间t_{\mathrm{c}\mathrm{b}}，小于接续冗余时间t_{\mathrm{c}\mathrm{b}}和后序列车的运行线总缓冲时间t_{\mathrm{r}\mathrm{b}}之和，冗余时间虽不足以完全吸收晚点，但可在一定程度上削弱其传播，后序列车可通过赶点等运行调整措施弥补剩余晚点，从而避免对动车组在B车站的后续接续产生影响；若到达晚点时间t_{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}大于接续冗余时间t_{\mathrm{c}\mathrm{b}}和后序列车的运行线总缓冲时间t_{\mathrm{r}\mathrm{b}}之和，接续冗余时间已无法有效吸收到达晚点，可能导致影响B车站的后续动车组正常接续。

由此可见，接续结构对晚点的吸收能力不仅取决于接续冗余时间的长短，还与后序列车运行线的缓冲时间相关。这意味着在优化接续结构时，应考虑后序列车运行线自身的弹性特征。若运行线弹性较弱，则增加接续冗余时间对提升弹性的边际收益更为显著。将接续弹性定义为该接续对中接续冗余时间吸收前序列车到达晚点的能力。

采用指数分布简化描述列车到达晚点规律^[22]。对于列车i，其到达晚点概率密度函数可表示为

P\left(t\right)={\lambda }_i{\mathrm{e}}^{-{\lambda }_{i}t}(1)

式中：t表示列车到达晚点时间，min；λ为常数，代表前序列车的晚点参数。λ的值越小，列车就更易晚点。

根据此函数，可求得在接续对中接续冗余时间能够完全吸收晚点与部分吸收晚点的概率，分别如式(2)与式(3)所示。

P\left(t_{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}\le t_{\mathrm{c}\mathrm{b}}\right)={\int }_{\mathrm{0}}^{t_{\mathrm{c}\mathrm{b}}}\lambda {\mathrm{e}}^{-\lambda t}\mathrm{d}t(2)

(3)

当时，接续冗余时间仅能吸收部分晚点，起到削弱晚点传播的作用。虽然此时未能完全消除晚点，但其仍体现出接续冗余时间对晚点的部分吸收作用。为了综合评估完全吸收与有限吸收所带来的弹性收益，引入权重系数δ，用于衡量有限吸收的相对重要程度。系数δ越大，表示系统对部分吸收的收益越敏感。接续弹性在晚点概率密度函数上的体现如图3所示，展示了某接续对的前序列车晚点概率密度函数，根据接续弹性的定义可知，完全吸收部分的阴影面积与有限吸收部分的阴影面积乘权重系数δ之和即代表该接续对的接续弹性大小。由此，可按照式(4)计算接续弹性收益的评价函数。

(4)

2　考虑交路弹性的动车组运用优化模型

2.1　模型假设

（1）列车运行图为已知输入数据，不涉及对列车时刻表的调整或再优化。

（2）动车组具有统一的技术标准，能够相互兼容并执行任意车次的运输任务。

（3）动车组检修作业仅考虑一级修，允许异地检修。

（4）不考虑动车组的重联和解编。

（5）仅考虑车站到发线的能力约束，不涉及动车组在站内的具体股道分配。

2.2　动车组接续网络构建

以列车和动车段所为节点，列车间的接续关系和动车组出入动车段所的行为为边构建有向加权图。为每列动车组构建其单独对应的接续网络G_k=\left(V_k,A_k\right)，动车组接续网络示意图如图4所示。

节点集合V_k由以下3类节点组成。①虚拟起终点v_k^{\mathrm{s}}和v_k^{\mathrm{e}}，在图中分别以节点S和节点E表示，代表为交路k生成流程的开始和结束。②动车段所节点集合V_k^{\mathrm{d}}，代表交路k初始所在的出段动车段所节点和交路结束时可能回段的所有入段动车段所节点。为便于区分，图中以小写字母节点(a，b，c……)表示出段动车段所节点，以大写字母节点(A，B，C……)表示入段动车段所节点。③列车节点集合V_k^{\mathrm{t}}表示在给定运行图中需要被担当的所有列车任务，在图中以数字节点表示。对于每个列车节点i\in V_k^{\mathrm{t}}，定义其以下属性：a_i^{\mathrm{s}}与a_i^{\mathrm{t}}分别代表节点的终到车站和终到时刻，d_i^{\mathrm{s}}与d_i^{\mathrm{t}}分别代表始发车站和始发时刻。

弧集合A_k包含以下若干类型。①虚拟开始弧A_k^{\mathrm{v}\mathrm{b}}，连接虚拟起点v_k^{\mathrm{s}}与交路初始位置所对应的动车组节点v_k^{\mathrm{d}}，表示交路k生成流程的开始。②虚拟结束弧A_k^{\mathrm{v}\mathrm{s}}，连接动车组节点v_k^{\mathrm{d}}与虚拟终点v_k^{\mathrm{e}}，表示交路k生成流程的结束。③虚拟运行弧A_k^{\mathrm{v}\mathrm{r}}，连接虚拟起点v_k^{\mathrm{s}}与虚拟终点v_k^{\mathrm{e}}，表示该动车组k未被启用。④出段弧A_k^{\mathrm{o}\mathrm{u}\mathrm{t}}，连接动车组节点v_k^{\mathrm{d}}和列车节点v_k^{\mathrm{t}}。若存在弧\left(i,j\right)\in A_k^{\mathrm{o}\mathrm{u}\mathrm{t}}，表示动车组k从节点i对应的动车段所出段担当节点j对应列车任务。⑤入段弧A_k^{\mathrm{i}\mathrm{n}}，连接列车节点v_k^{\mathrm{t}}和动车组节点v_k^{\mathrm{d}}。若存在弧\left(i,j\right)\in A_k^{\mathrm{i}\mathrm{n}}，表示动车组k担当节点i对应列车任务结束后返回节点j对应的动车段所。⑥接续弧A_k^{\mathrm{c}\mathrm{o}\mathrm{n}}，连接满足列车接续规则的列车节点\left(i,j\right)\in v_k^{\mathrm{t}}。若最小接续时间为t_{\mathrm{m}\mathrm{i}\mathrm{n}}，对于接续弧的建立，需满足接续时间(d_j^{\mathrm{t}}-a_i^{\mathrm{t}}\ge t_{\mathrm{m}\mathrm{i}\mathrm{n}})和接续地点(a_i^{\mathrm{s}}=d_j^{\mathrm{s}})的要求。

接续网络中的每条路径对应一条实际的动车组交路段。例如路径[S，a，1，3，11，A，E]对应动车组自A动车段所出库，依次担当列车1、列车3和列车11后回段至A动车段所。为便于后续建模，基于动车组接续网络，将动车组当前的剩余检修修程视作车辆的剩余载货量，将列车任务视为需服务的客户点，从而将动车组交路问题转化为一种带资源约束的车辆路径问题(CVRP)。即在不超过动车组一级修周期的情况下，为每列动车组k安排一条从虚拟起点到虚拟终点的可行路径，使得所有列车均有恰当的动车组担当，且交路计划的总弹性最优。

2.3　模型构建

2.3.1　目标函数

面向弹性提升的动车组交路优化的核心目标，是在使用最少资源下最大化系统运行稳定性，即以最少的动车组实现具备较强弹性的交路计划。故目标函数如式(5)所示。

\mathrm{m}\mathrm{a}\mathrm{x}Y=\sum _{k\in K}\sum _{p\in P_k}{c}_p{f}_p^k(5)

式中：P_k为动车组k的可行路径集合；f_p^k为0-1决策变量，当动车组k使用路径p时取值为1，否则为0；c_p表示路径p的交路段弹性，由该路径中所有列车接续对弹性乘积计算所得，反映该交路段整体的晚点吸收能力。为隐式控制车底规模，若该路径为从虚拟起点至虚拟终点的虚拟路径，代表该动车组未被启用，则将该路径设c_p=M。通过奖励闲置车底，驱动算法尽可能减少动车组的使用。

2.3.2　约束条件

（1）动车组路径唯一性约束。式(6)保证每列动车组有且仅有一条被分配的路径。若动车组被分配了空路径，即路径从虚拟起点直接到达虚拟终点，不经过任何动车段所与列车路径，则代表该动车组未被启用。

\sum _{p\in P_k}{f}_p^k=\mathrm{1}\hspace{1em}\hspace{1em}\forall k\in K(6)

（2）列车需求约束。式(7)保证所有被运用的动车组路径均可覆盖需要被担当的所有列车，即任意列车都应该被某个路径所覆盖。

\sum _{k\in K}\sum _{p\in P_k}{\alpha }_p^l{f}_p^k=\mathrm{1}\hspace{1em}\hspace{1em}\forall l\in L(7)

式中：{\alpha }_p^l为0-1变量，表示若路径p包含列车l则为1，否则为0。

（3）动车段所需求约束。式(8)限制了日计划末时，每个动车段所最终回库的动车组数量都应满足次日的运用计划需要。

\sum _{k\in K}\sum _{p\in P_k}{\beta }_p^d{f}_p^k\ge w_d\hspace{1em}\hspace{1em}\forall d\in D(8)

式中：{\beta }_p^d为0-1变量，表示若路径p最终回到动车段所d则为1，否则为0；w_d为动车段所d的次日运用计划需要动车组数，列。

（4）到发线占用约束。该约束限制了在任意时刻内，各车站的动车组占用到发线数量不应高于该车站该时刻的可用到发线数量。

\sum _{k\in K}\sum _{p\in P_k}{o}_{p,s}^t{f}_p^k\le O_s^t\hspace{1em}\hspace{1em}\forall s\in S，\forall t\in T(9)

式中：o_{p,s}^t为0-1变量，表示路径p在s车站的t时刻占据车站某条到发线则为1，否则为0；T为时间集合，将时间按分钟为单位离散化，T=\left\{\mathrm{1,2},\dots ,\right.\mathrm{1}\mathrm{440}\}；O_s^t为s车站的t时刻的空闲到发线数量，个。

3　算法设计

研究构建的动车组运用优化模型目标是在满足接续规则与检修约束的前提下，为每一动车组k从其可行路径集合P_k中选择一条路径，从而实现动车组运用弹性的整体最优。由于可行路径集合规模庞大，导致模型的决策变量数量远超约束数量，直接求解完整模型将面临巨大的计算复杂度。针对上述特征，采用列生成算法^[23]对模型进行求解，列生成算法流程图如图5所示。列即代表动车组路径，子问题表现为一个带资源约束的最短路径问题，其求解结果用于判断是否存在检验数为负的路径。若存在，则将该路径列加入主问题的变量集中继续迭代；若生成的可行列的检验数均不小于零，则表明已无法搜寻到能使解更优的列。由于列生成本质上是在求解原问题的线性松弛模型，所求得的分数解无法直接用于实际运营。因此，在列生成结束后，将主问题的决策变量重新限制为整数变量，基于现有的列池求解整数规划问题^[24]，从而最终确定优化后的动车组运用计划。

3.1　受限主问题构造

在列生成框架下，主问题是对原始动车组运用优化模型的线性松弛形式。设P_k^{\text{'}}为当前迭代中动车组k的可行路径集合，对原模型中的0-1决策变量f_p^k进行线性松弛处理，使其取值范围为f_p^k\in [\mathrm{0,1}]。此时受限主问题(RMP)的数学表达式可表示为

\mathrm{m}\mathrm{a}\mathrm{x}Y=\sum _{k\in K}\sum _{p\in P_k^{\text{'}}}{c}_p{f}_p^k(10)

\sum _{p\in P_k^{\text{'}}}{f}_p^k=\mathrm{1}\hspace{1em}\hspace{1em}\forall k\in K(11)

\sum _{k\in K}\sum _{p\in P_k^{\text{'}}}{\alpha }_p^l{f}_p^k=\mathrm{1}\hspace{1em}\hspace{1em}\forall l\in L(12)

\sum _{k\in K}\sum _{p\in P_k^{\text{'}}}{\beta }_p^d{f}_p^k\ge w_d\hspace{1em}\hspace{1em}\forall d\in D(13)

\sum _{k\in K}\sum _{p\in P_k^{\text{'}}}{o}_{p,s}^t{f}_p^k\le O_s^t\hspace{1em}\hspace{1em}\forall s\in S，\forall t\in T(14)

f_p^k\in \left[\mathrm{0,1}\right]\hspace{1em}\hspace{1em}\forall k\in K，\forall p\in P_k^{\text{'}}(15)

设约束的对偶值分别为动车组k的路径唯一性约束对偶值{\pi }_k，列车l的需求约束对偶值{\mu }_l，动车组d的库存需求约束对偶值{\sigma }_d，车站s在t时刻的到发线占用约束对偶值{\theta }_{s,t}。约束对偶值可用于代入定价子问题，指导新列的生成，并将生成的新列加入P_k^{\text{'}}进行下一步的迭代。

3.2　定价子问题求解

定价子问题本质上是一个带资源约束的最短路径问题^[25]，其中资源约束为动车组的检修周期，即对路径的总运行里程与时间限制。具体而言，即从接续网络的虚拟起点出发，寻找一条到虚拟终点的路径代价最小的可行路径，使得运行总里程和总时间均不超过一级修修程。对于动车组k，其定价子问题满足路径可行性约束的前提下，寻找使检验数最小的路径，即

\mathrm{m}\mathrm{i}\mathrm{n}Z={\mathrm{\pi }}_k+a_p^l{\mu }_l-{\beta }_p^d{\sigma }_d+o_{p,s}^t{\theta }_{s,t}-c_p(16)

为将主问题求解所得的对偶信息有效地融入定价子问题的求解过程中，需要将各约束对应的对偶变量映射至动车组接续网络的弧段结构中。通过该映射，可将对偶值转化为路径生成过程中的成本或收益，从而指导子问题的路径搜索方向^[3]。对偶变量的嵌入方式如下。

（1）动车组路径唯一性约束对偶值{\mathrm{\pi }}_k。该对偶值与动车组k的路径分配直接相关。为此，将{\mathrm{\pi }}_k加入动车组k的虚拟开始弧A_k^{\mathrm{v}\mathrm{b}}中，代表动车组k的启用成本。

（2）列车任务需求约束对偶值{\mu }_l。该对偶值和列车任务l被某动车组执行有关。由于列车任务的执行可通过出段弧A_k^{\mathrm{o}\mathrm{u}\mathrm{t}}和接续弧A_k^{\mathrm{c}\mathrm{o}\mathrm{n}}体现，将{\mu }_l加入到通向列车l对应的节点的出段弧和接续弧中，以体现执行该列车任务的收益。

（3）动车段所d的库存需求约束对偶值{\sigma }_d。该对偶值反映动车组在完成任务后返回动车段所d的收益。因此将{\sigma }_d加入到到达该动车段所节点的入段弧A_k^{\mathrm{i}\mathrm{n}}中，表示动车组返回该动车段所带来的运用效益。

（4）车站到发线占用约束对偶值{\theta }_{s,t}。该对偶值体现动车组执行接续任务时于车站s在t时刻的到发线占用成本。由于到发线资源难以直接映射至接续网络中的静态节点结构，引入到发线惩罚变量B_{i,j}代表其占用资源的影响。设s_{i,j}为i列车与j列车接续发生车站，T_{i,j}为接续过程中占据车站到发线的时刻集合，则惩罚变量B_{i,j}定义为

B_{i,j}=\mathrm{m}\mathrm{a}\mathrm{x}({\theta }_{s,t})\hspace{1em}\hspace{1em}s=s_{i,j}，t\in T_{i,j}(17)

将B_{i,j}加入接续弧\left(i,j\right)\in A_k^{\mathrm{c}\mathrm{o}\mathrm{n}}中，用以体现接续过程对车站到发线资源的占用代价。

结合问题特点设计标签算法^[26]求解子问题。算法中，每个节点可附着多个标签。对于节点k上的第n个标签L_n\left(k\right)=\left(Z_{k,n},R_{k,n}^{\mathrm{m}},R_{k,n}^{\mathrm{t}}\right)，分别记录从起点到达该节点的路径代价、累计运行里程、累计运行时间，算法求解步骤如下。

步骤1：为接续网络的虚拟起点节点创建初始标签L_{\mathrm{0}}\left(s\right)=\left(\mathrm{0,0},\mathrm{0}\right)，并将该标签放入待拓展标签集合V_L中。

步骤2：从集合V_L中选出累计运行里程最少的标签L_a\left(i\right)，对应节点i上的第a个标签。对所有从节点i出发的可行弧\left(i,j\right)，设该弧上的路径代价、列车运行里程、列车运行时间分别为z_{i,j}，r_{i,j}^{\mathrm{m}}，r_{i,j}^{\mathrm{t}}，生成新的标签L_b\left(j\right)=\left(Z_{i,b}+z_{i,j},R_{i,b}^{\mathrm{m}}+r_{i,j}^{\mathrm{m}},R_{i,b}^{\mathrm{t}}+r_{i,j}^{\mathrm{t}}\right)，若该标签满足一级修的里程和时间约束，则保留标签。

步骤3：对于同一节点j上已存在的任意标签L_c\left(j\right)，若新生成的标签L_b\left(j\right)在路径代价和已运行里程与时间均不劣于L_c\left(j\right)，即Z_{j,b}\le Z_{j,c}，R_{j,b}^{\mathrm{m}}\le R_{j,c}^{\mathrm{m}}，R_{j,b}^{\mathrm{t}}\le R_{j,c}^{\mathrm{t}}，则保留新标签L_b\left(j\right)，同时将新生成的标签放入待拓展标签集合V_L中，否则删除该标签，返回步骤2。

步骤4：若V_L=\mathrm{\varnothing }，则算法结束，否则返回步骤2。

3.3　生成初始可行解

列生成算法的求解依赖于初始解以获取对偶变量信息，采用启发式算法构造初始解。设{\epsilon }_{s,t}为车站s在t时刻的到发线占用数，条，{\varphi }_d为日计划末到达d动车段所的动车组数，列。算法流程如下。

步骤1：根据列车始发时间与动车组剩余里程，分别对列车集合L、动车组集合K进行升序排列。

步骤2：取动车组集合中剩余里程最小的动车组k\in K，以列车集合中该动车组可担当且始发时间最小的列车l\in L为路径起点。

步骤3：在满足接续条件及一级修修程的前提下，搜索接续弹性最大的后序列车作为接续。若有多个最优接续对，优先取接续时间最少的接续对。重复此过程延伸路径，直至无法找到可接续的后序列车。

步骤4：将生成的交路加入初始解集，并将路径包含的列车从集合L中移除。

步骤5：计算新路径对车站到发线的占用。若存在接续对在车站s于t时刻的占用到发线，则更新{\epsilon }_{s,t}={\epsilon }_{s,t}+\mathrm{1}。若{\epsilon }_{s,t}=O_s^t，则禁止后续路径生成选择在车站s包含t时刻的接续对。

步骤6：检查现有路径是否满足动车段所需求。对路径终点对应的动车段所d，更新{\varphi }_d={\varphi }_d+\mathrm{1}。若{\varphi }_d=w_d，说明该动车段所已满足需求，则将动车段所节点d从接续网络中暂时移除。直至所有的动车段所均满足运用需求，恢复所有的动车段所节点。

步骤7：若列车集合L为空，则将剩余未分配路径的动车组均分配空路径，输出初始解。否则转到步骤2。

4　实例分析

以京沪高速铁路以及部分相邻线路为算例进行实证研究。选取相关线路上运行的227列列车作为研究对象，涉及21座始发/终到车站，算例涉及始发终到车站路网图如图6所示。算例中已知各列车的时刻表、缓冲时间。基于列车近期一年的历史运行实绩数据拟合晚点分布函数，计算各列车晚点系数。部分列车信息如表1所示，晚点系数信息见最后一列。已知各动车组的初始位置和剩余可运行的里程与时间，以及日计划结束时各动车段所所需的动车组数量等数据。算例设动车组一级检修最大里程为4 400 km，最大运行时间为2 880 min，最小接续时间标准为15 min，后序列车缓冲时间权重系数δ为0.1。基于以上数据，对原有的动车组运用计划进行优化，以验证模型与算法在实际场景中的可行性与有效性。

算例求解信息如表2所示，列生成算法收敛过程如图7所示。结果显示算法的最优性间隙低至1×10^-5%。说明所设计算法能在可接受的时间内生成高质量的运用计划。动车组运用计划优化前后指标对比如表3所示。优化后的动车组运用计划在不增加动车组运用数量的前提下，实现了显著的弹性提升。交路段平均弹性值由0.851提高至0.974，提升幅度为14%。从分布结构来看，弹性值大于0.99的高弹性交路段比例达77%，相比原计划(45个)显著增加至87个；弹性值在(0.90~0.99]区间的较高弹性交路段由20个收缩至15个，反映出弹性分布重心实现了向极高值区的偏移。弹性值在[0.50~0.90]区间的中低弹性交路段，由40个缩减至11个，且无任何交路段的弹性值低于0.5，有效消除了高风险交路段的存在。

以上分析表明，通过对列车接续关系的全局寻优，改变了传统模式下对最小接续时间的单一追求模式，实现了接续冗余时间在时空维度上的合理重分配与适度增加。这种削峰填谷式的资源重构，在不增加额外运力投入的情况下，结合接续冗余时间的边际递减效应，将有限的冗余时间精准配置到了最需要的部分，这不仅显著增强了交路计划的宏观稳定性(提升交路段平均弹性)，更有效补强了系统的微观短板(消除低弹性交路段)，实现了整体运用弹性的均衡提升。此外，在编制实际运用计划时，应重点识别并优化那些接续时间紧张、前序列车晚点风险较高且后序列车缓冲时间匮乏的关键接续对，以通过局部精准调整提升整体计划的抗干扰能力。

为进一步分析动车组资源配置对交路段弹性提升的边际贡献影响，进行动车组运用数量的灵敏度分析。在保持其他条件不变的情况下，逐步增加可投入运用的动车组数量，比较不同运用动车组数量的弹性优化结果如图8所示。结果表明，随着运用动车组数量的增加，交路段平均弹性值持续上升，但增幅呈现边际递减趋势。然而，增加动车组运用对于消除系统的短板具有决定性作用。实验显示，最低弹性交路段的弹性得到显著改善，当额外增加2列动车组后，所有交路段的弹性值均可超过0.9。

由此可见，增加动车组运用数量对整体弹性的提升作用有限，但对改善低弹性交路段具有明显效果。换言之，对于难以通过接续关系调整实现优化的交路段，可通过引入额外动车组，对接续关系紧张的交路对进行结构性拆解，从而显著提升其局部弹性。然而，从经济性视角出发，鉴于动车组启用成本较高，其在计划阶段的应用不具经济性，无法作为提升弹性的常规手段。因此，建议采取分级优化策略，即在计划编制层面，优先挖掘接续关系调整的潜力。而在实际运营层面，则可将额外动车组作为应急响应资源(如设置热备车)，专门用于化解关键接续对的临时扰动，实现经济成本与运行可靠性的最优平衡。

为探究最大接续时间对运用计划弹性的影响，在30 min至120 min的约束范围条件下进行灵敏度分析。不同最大接续时间约束下的优化结果如图9所示，动车组最大接续时间的设定与运用计划的弹性水平呈正线性相关，体现出一定的边际效益递减规律。如图9所示，随着最大允许接续时间由45 min放宽至无约束状态，平均弹性值从0.868 6逐渐提升收敛至0.974 5。这一结果表明，适当延长允许的接续时间能够为列车晚点提供更大的缓冲，显著降低连带延误风险。但需注意弹性的提升是以牺牲车辆周转效率与占用车站到发线资源为代价的，总接续时间由5 231 min增长至10 470 min，且越放松对最大接续时间的约束，对弹性的提升越不明显。因此，在实际编制计划时，应根据运营线路的实际情况与需求，选择边际效益最优的接续时间阈值(如90 min)，以在弹性与效率之间取得最佳平衡。

5　结束语

针对面向弹性提升的动车组运用计划优化问题，通过分析动车组接续冗余时间对列车晚点吸收的机理，提出了基于前序列车的晚点系数与后序列车运行线缓冲时间的接续弹性收益函数。以动车组接续网络为基础，考虑了接续规则、一级修周期、动车段所库存需求以及车站到发线容量限制等要素，转化为带资源约束车辆路径问题的动车组运用优化模型，采用列生成算法实现了模型求解。通过以京沪高速铁路为背景的算例分析，揭示了动车组运用弹性的边际效益递减规律以及弹性提升与车辆周转效率、动车组运用数之间的关系，提示相关部门可通过优化接续结构、根据边际效益选取最优最大接续时间阈值、适度增加动车组运用规模以及在运营中配置热备车等手段高效提高动车组运用的弹性。研究引入了车站到发线容量约束以反映接续过程对车站资源的占用，但现有的约束刻画方式显著增加了模型的计算复杂度，影响了大规模问题下的求解性能。同时，本研究目前主要针对动车组日班计划进行优化，未来可进一步探索多日交路的面向弹性的动车组运用优化问题。

参考文献

[1] 刘　睿，徐传玲，文　超. 基于马尔科夫链的高铁列车连带晚点横向传播[J]. 铁道科学与工程学报，2022，19(10)：2804-2812.

[2] LIU Rui， XU Chuanling， WEN Chao. Lateral Propagation of High Speed Railway Trains’ Knock-on Delays Based on Markov Chain[J]. Journal of Railway Science and Engineering，2022，19(10)：2804-2812.

[3] 赵　鹏，富井规雄. 动车组运用计划及其编制算法[J]. 铁道学报，2003，25(3)：1-7.

[4] ZHAO Peng， TOMII Norio. Train-Set Scheduling and an Algorithm[J]. Journal of the China Railway Society，2003，25(3)：1-7.

[5] 李沁洋，彭其渊，张永祥，等. 基于列生成算法的高速铁路动车组运用调整优化[J]. 交通运输工程与信息学报，2025，23(2)：136-149.

[6] LI Qinyang， PENG Qiyuan， ZHANG Yongxiang，et al. A Column Generation Approach for High Speed Railway Rolling Stock Rescheduling[J]. Journal of Transportation Engineering and Information，2025，23(2)：136-149.

[7] 苗建瑞，王　莹，杨肇夏. 基于最优接续网络的动车组交路计划优化模型与算法研究[J]. 铁道学报，2010，32(2)：2.

[8] MIAO Jianrui， WANG Ying， YANG Zhaoxia. Research on the Optimization of EMU Circulation Based on Optimized Connecting Network[J]. Journal of the China Railway Society，2010，32(2)：2.

[9] 林柏梁，沈姚铭，钟文健，等. 车底数最小化的动车组交路计划优化[J]. 中国铁道科学，2023，44(5)：210-221.

[10] LIN Boliang， SHEN Yaoming， ZHONG Wenjian，et al. Optimization of the Electric Multiple Units Circulation Plan with the Minimum Number of Train-Set[J]. China Railway Science，2023，44(5)：210-221.

[11] CANCA D， SABIDO M， BARRENA E. A Rolling Stock Circulation Model for Railway Rapid Transit Systems[J]. Transportation Research Procedia，2014，3：680-689.

[12] 户佐安，张文豪，周甲明，等. 考虑可变编组和均衡检修的动车组运用计划编制优化研究[J]. 北京交通大学学报，2025，49(2)：14-24.

[13] HU Zuoan， ZHANG Wenhao， ZHOU Jiaming，et al. Research on Optimization of EMU Operation Planning Considering Variable Grouping and Balanced Maintenance[J]. Journal of Beijing Jiaotong University，2025，49(2)：14-24.

[14] 李　健，王　莹，李海鹰，等. 城际铁路动车组交路计划优化模型[J]. 铁道科学与工程学报，2018，15(7)：1664-1670.

[15] LI Jian， WANG Ying， LI Haiying，et al. Optimization Model of Rolling Stock Circulation of Intercity Railway[J]. Journal of Railway Science and Engineering，2018，15(7)：1664-1670.

[16] 王　莹，刘　军，苗建瑞. 基于列生成算法的动车组检修计划优化[J]. 中国铁道科学，2010，31(2)：115-120.

[17] WANG Ying， LIU Jun， MIAO Jianrui. Column Generation Algorithms Based Optimization Method for Maintenance Scheduling of Multiple Units[J]. China Railway Science，2010，31(2)：115-120.

[18] 何筱雍，王　莹，李　涵，等. 客流波动场景下的动车组运用计划调整研究[J]. 铁道科学与工程学报，2024，21(8)：3072-3081.

[19] HE Xiaoyong， WANG Ying， LI Han，et al. Study on Rolling Stock Rescheduling under Passenger Demand Fluctuation[J]. Journal of Railway Science and Engineering，2024，21(8)：3072-3081.

[20] 陈　旭，李海鹰，王　莹，等. 放射状路网条件下动车组运用优化研究[J]. 铁道学报，2017，39(11)：23-29.

[21] CHEN Xu， LI Haiying， WANG Ying，et al. Research on Optimization of EMU Scheduling for Radial HSR Network[J]. Journal of the China Railway Society，2017，39(11)：23-29.

[22] 郭倩倩，王振宇，林柏梁. 离所时间限制下动车组交路计划优化研究[J]. 铁道学报，2023，45(11)：11-19.

[23] GUO Qianqian， WANG Zhenyu， LIN Boliang. Research on Optimization of EMU Routing Plan under Time Limit of Departure from Station[J]. Journal of the China Railway Society，2023，45(11)：11-19.

[24] LI J， LIN B L， WANG Z K，et al. A Pragmatic Optimization Method for Motor Train Set Assignment and Maintenance Scheduling Problem[J]. Discrete Dynamics in Nature and Society，2016，2016：4540503.

[25] 王　昕，聂　磊，李文俊. 基于动车运用的高速铁路列车运行图鲁棒性研究[J]. 铁道运输与经济，2014，36(11)：50-55.

[26] WANG Xin， NIE Lei， LI Wenjun. Study on Robustness of High Speed Train Working Diagram Based on EMU Utilization[J]. Railway Transport and Economy，2014，36(11)：50-55.

[27] 仝　硕，陈绍宽，刘葛辉，等. 考虑接续可靠性的动车组运用计划优化方法[J]. 铁道学报，2020，42(4)：27-34.

[28] TONG Shuo， CHEN Shaokuan， LIU Gehui，et al. Optimum Circulation Model for Electrical Multiple Units Considering Reliability of Their Operational Connections[J]. Journal of the China Railway Society，2020，42(4)：27-34.

[29] TRÉFOND S， BILLIONNET A， ELLOUMI S，et al. Optimization and Simulation for Robust Railway Rolling-Stock Planning[J]. Journal of Rail Transport Planning & Management，2017，7(1-2)：33-49.

[30] 朱昌锋，李引珍. 考虑车底接续延误概率的普速旅客列车车底套用方案鲁棒优化[J]. 中国铁道科学，2016，37(5)：122-131.

[31] ZHU Changfeng， LI Yinzhen. Robust Optimization on Operation Assignment of Common-Speed Passenger Train Stock Considering Delay Probability of Stock Connection[J]. China Railway Science，2016，37(5)：122-131.

[32] 周晓昭，张　琦，许　伟，等. 考虑动车组接续的列车运行图智能调整方法[J]. 铁道学报，2018，40(8)：19-27.

[33] ZHOU Xiaozhao， ZHANG Qi， XU Wei，et al. Intelligent Adjustment Method for Train Operation Diagram with Consideration of Motor Train Set Connection[J]. Journal of the China Railway Society，2018，40(8)：19-27.

[34] 聂　磊，赵　鹏，杨　浩，等. 高速铁路动车组运用的研究[J]. 铁道学报，2001，23(3)：1-7.

[35] NIE Lei， ZHAO Peng， YANG Hao，et al. Study on Motor Trainset Operation in High Speed Railway[J]. Journal of the China Railway Society，2001，23(3)：1-7.

[36] 钟庆伟，庾映雪，田金玉，等. 严重干扰下考虑空车调拨的动车组运用计划实时调整方法[J]. 铁道运输与经济，2025，47(1)：82-91，101.

[37] ZHONG Qingwei， YU Yingxue， TIAN Jinyu，et al. Real-Time Train Set Operation Adjustment Considering Empty Car Scheduling under Severe Disturbances[J]. Railway Transport and Economy，2025，47(1)：82-91，101.

[38] 李　智，张　琦，孙延浩，等. 高速铁路列车运行图鲁棒性协同优化模型研究[J]. 交通运输系统工程与信息，2019(5)：169-176.

[39] LI Zhi， ZHANG Qi， SUN Yanhao，et al. Robustness Collaborative Optimization Model for High Speed Railway Train Timetable[J]. Journal of Transportation Systems Engineering and Information Technology，2019(5)：169-176.

[40] BRANDEJSKY T. The Train Delay Model Developed by the Genetic Programming Algorithm[J]. Journal of Advanced Transportation，2022，2022：8858756.

[41] BARNHART C， JOHNSON E L， NEMHAUSER G L，et al. Branch-and-Price：Column Generation for Solving Huge Integer Programs[J]. Operations Research，1998，46(3)：316-329.

[42] 李沁洋，彭其渊，张永祥，等. 基于列生成算法的高速铁路动车组司机乘务计划调整优化[J]. 铁道运输与经济，2025，47(6)：56-66.

[43] LI Qinyang， PENG Qiyuan， ZHANG Yongxiang，et al. Crew Schedule Optimization for Rolling Stock Drivers of High Speed Railway via Column Generation Algorithm[J]. Railway Transport and Economy，2025，47(6)：56-66.

[44] HIMMICH I， HALLAOUI I EL， SOUMIS F. A Multiphase Dynamic Programming Algorithm for the Shortest Path Problem with Resource Constraints[J]. European Journal of Operational Research，2024，315(2)：470-483.

[45] DUMITRESCU I， BOLAND N. Algorithms for the Weight Constrained Shortest Path Problem[J]. International Transactions in Operational Research，2001，8(1)：15-29.

基金资助

甘肃省科技计划资助-联合科研基金重大项目(24JRRA865)

国家自然科学基金项目(U2368211)

国家自然科学基金铁路基础研究联合基金项目(U2268207)