严重干扰下考虑空车调拨的动车组运用计划实时调整方法

Real-Time Train Set Operation Adjustment Considering Empty Car Scheduling under Severe Disturbances

摘要

研究严重干扰场景下高速铁路网络动车组运用计划实时调整问题，根据调整后列车运行图，以偏离原动车组运用计划程度最小、取消车次数量最少、动车段(所)日常库存偏离最少及空车调拨次数最少为目标，在考虑车组改编及日常检修限制等安全约束条件下，基于车次接续建立两阶段整数线性规划模型。第一阶段模型旨在生成多种与原动车组运用计划方案相似的可行路径集合；第二阶段模型则保证具体执行各路径动车组的一致性，以及各备选动车组与其可能执行路径之间的检修可行性。最后以郑州局集团公司所辖部分高速铁路网络为例，对提出模型及算法的有效性进行验证，计算结果表明该方法能够快速实现多个场景问题的求解，为严重干扰下考虑空车调拨的动车组运用计划调整提供参考。

Abstract

This paper studied the real-time train set operation adjustment problem under severe disturbances of the high speed railway network. According to the adjusted train working diagram, a train connection-based two-stage integer linear programming model was established to minimize the deviation from the original train set operation, the number of canceled trains, the deviation of daily inventory at train depots, and the frequency of empty car scheduling, with safety constraints such as train rearrangement and daily maintenance considered. In this model, the first stage aimed to generate a variety of feasible paths similar to the original train set operation. The second stage guaranteed the consistency of the train set serving their paths, as well as the maintenance feasibility of each candidate train set and their possible paths. Finally, the effectiveness of the proposed model and algorithm was verified by the high speed railway network managed by China Railway Zhengzhou Group. The calculation results show that the proposed method can quickly solve multiple scenario problems, providing a reference for adjusting train set operation considering empty car scheduling under severe disturbances.

Graphical abstract

关键词

高速铁路 / 动车组运用计划实时调整 / 整数线性规划模型 / 改编 / 空车调拨

Key words

High Speed Railway / Real-Time Train Set Operation Adjustment / Integer Linear Programming Model / Train Remarshalling / Empty Car Scheduling

0　引言

2020年底，我国动车组保有量超3 600多组，占世界高速列车总保有量的1/2以上，每年通过动车组完成的旅客发送量占全国50%以上^[1-2]。高速铁路系统是一个复杂的综合系统，其高速列车在运行过程中易受到来自内部及外部因素的影响。根据受影响程度可对干扰进行等级划分：微干扰、严重干扰及非常严重干扰^[3]。相比于微干扰，严重干扰是出现在较长时间内某铁路区间通过能力部分或全部失效的情况，这种情况下通常会导致列车严重偏离原计划。当严重干扰发生时，调度员通常遵循“人工调整为主，系统调整为辅”的策略，重点对列车运行图进行调整。而仅对运行图调整，可能会出现某些车次无动车组担当的情况。此时，调度员需要凭借自身经验调整动车组运用计划，不仅效率低，而且压力大。因此，有必要借助数学优化方法设计一个计算机辅助程序。本研究考虑严重干扰场景条件(干扰发生的铁路区间完全中断、能力失效)下，借鉴“人工经验”提出一个基于车次接续的动车组运用计划调整方法，在调整过程中考虑空车调拨、动车组类型及日常检修条件等多个实际约束条件。

在动车组运用计划调整研究中，受动车组运用计划编制的建模方法及求解思路影响较大。首先对动车组运用计划编制的既有研究进行总结。国外早期研究论证了运筹学优化方法是解决该问题的有效手段^[4]，并提出基于多商品网络流的数学模型^[5]，随后又演变为路径模型^[6]。在国内，赵鹏等^[7]探讨动车组运用模式、编制模型及算法，后又引入空车调拨^[8]，并研究成网条件下该问题的分解、求解算法^[9-10]。随后，借助列生成算法对考虑检修约束的计划编制问题进行探讨^[11-12]。从动车组运用计划编制的既有成果可以看到，虽然成果较为丰富，但环境设定简单，如部分研究未对车组精确分类、不能精确描述车组初始状态，不适用于实时运营层面的计划调整问题。

相较动车组运用计划编制问题而言，动车组运用计划调整问题的既有研究较少。国外早期研究对动车组运用计划调整问题进行定义^[13-14]。Nielsen等^[15]考虑列车取消数量、调车计划偏差量最小等目标对Fioole等^[5]的研究进行拓展，并设计滚动时域算法。随后，Kroon等^[16]考虑干扰发生后乘客出行行为的变化，提出两阶段启发式迭代方法。Wagenaar等^[17]考虑固定的动车组检修时段，建立3种调整模型。Wagenaar等^[18]综合考虑空车调拨、回送及客流需求进行建模。Haahr等^[6]选用2种方式建模并使用商业优化软件及列成生算法进行求解。Lusby等^[19]建立以路径为基础的优化模型，并设计分支定价算法求解。国外既有研究中，部分文献未考虑动车组检修条件限制及空车调拨与回送作业需求^[6，15-16]，且Wagenaar等^[17]与Lusby等^[19]未考虑空车调拨与回送。Wagenaar等^[18]未考虑动车组检修限制，不能给出具体的空车运行线。在国内，仅在部分运行图调整文献中有所涉及^[20]，尚未对动车组运用计划调整问题开展系统研究。

综上，既有的动车组运用计划调整研究中对以多车种、多动车段(所)构成高速铁路网络背景下的研究较少，且未将空车调拨与回送、动车组改编作业及动车组检修等因素进行综合考虑，对实际问题刻画不够全面，难以满足现场各类应急管理需求。

1　问题描述

当高速铁路运营过程中遇到严重干扰时，首先需要对运行图进行调整，还需要基于调整后的运行图对动车组运用计划进行调整。以某高速铁路网络为例：包含5个车站，1个动车运用所，14个车次任务。严重干扰下运行图调整示例如图1所示，运行图纵轴为车站，动车段(所)与s₂衔接；运行图横轴为时间，原则上所有动车组都需要每天返回动车运用所整备，根据实际情况允许其在特定车站过夜；对车次进行编号1—14，明确其所需的动车组数量：Ⅰ为8编组，Ⅱ为重联的16编组。

若严重干扰位于s₃与s₄间导致该区间完全中断，起始时间为12：00且预计持续1 h，如图1a。调度员随即进行运行图调整，调整时遵循偏离最小原则，如图1b。假设各动车组均符合担当要求及检修限制，得到动车组运用计划示意如图2所示。图2a的动车组运用计划方案包含4条动车组路径，共计使用7个单元的标准组(即8编组的动车组)。当干扰发生后，此时图2a中车次5无法由车次4接续。需重新调整动车组运用计划，如图2b。现实中，调度员难以凭借经验在短时间内编制一个高质量的动车组运用调整计划。因此，本研究以调整后运行图及保有动车组基本信息为输入，在建立包含空车调拨的车次接续网络基础上，构建数学优化模型输出动车组运用计划调整方案，旨在为调度员提供一个计算机辅助决策程序。

2　数学模型

2.1　问题假设

（1）严重干扰下运行图均采用“先到先服务”原则调整，调整后运行图信息已知。

（2）允许动车组在配属动车段(所)外的车站过夜，时间为6 h。

（3）动车组为不固定区段运用模式，允许空车调拨。

（4）动车段(所)具备改编作业能力，出入动车段(所)时需要改编作业。

（5）日常检修时段为夜间，地点为动车段(所)，不考虑检修细节。

2.2　空车调拨接续网络生成

借鉴钟庆伟^[21]提出的方法，构建以车次为基础的动车组接续网络，并引入空车调拨。既有研究通常固定空车调拨区间，能够在一定程度上减少空驶车次的数量。但若构建的接续网络中边数量较多，则导致问题规模大、求解速度慢。本研究提出一种集成空驶车次方法，能在保留空驶可能性的前提下减少空驶车次数量。空驶车次集成及冲突示例如图3所示。如图3a，车站s_{\mathrm{3}}与s_{\mathrm{4}}间存在空车调拨。满足行车安全间隔，将车次1与7间插入的3个空驶车次(红色虚线)进行集成(紫色实线)。

设T为调整后运行图车次集合，S为车站集合。任意车次t\in T包含4个属性({\alpha }_t^d，{\alpha }_t^a，s_t^d，s_t^a)。s_t^d，s_t^a分别为t的始发、终到车站；{\alpha }_t^d，{\alpha }_t^a为t的最早始发、终到时间，s；区间内不存在列车越行。{\gamma }_{s，s\mathrm{\text{'}}}为从s空驶至s\mathrm{\text{'}}的时间，s。T^e为所有空驶车次集合。T^{e\mathrm{*}}为集成空驶车次集合，由算法生成，集成空驶车次生成算法如图4所示。

\varphi，\phi分别为s_t^a，s_{t^{\mathrm{1}}}^d的到发间隔时间，s。{\theta }_{t^{e\mathrm{*}}}为冗余时间，s，如公式⑴所示。

{\theta }_{t^{e\mathrm{*}}}={\alpha }_{t^{e\mathrm{*}}}^a-{\alpha }_{t^{e\mathrm{*}}}^d-{\gamma }_{s，s\mathrm{\text{'}}}⑴

假设t\in T在同一区间的紧邻前序车次为\lambda (t)，定义\mathrm{\Delta }(t)为一个时间差，s，\mathrm{\Delta }(t)的大小为t\in T与\lambda (t)二者始发或终到时间差的最小值，如公式⑵所示。

\mathrm{\Delta }(t)=\mathrm{m}\mathrm{i}\mathrm{n}({\alpha }_t^a-{\alpha }_{\lambda (t)}^a，{\alpha }_t^d-{\alpha }_{\lambda (t)}^d)⑵

定位空车调拨区间，对任意固有t\in T，若其对应的\mathrm{\Delta }(t)大于2倍的最小间隔时间H，则t\in T与其对应\lambda (t)之间至少可以插入1个集成空驶车次t^{e\mathrm{*}}。

当插入t^{e\mathrm{*}}时，t^{e\mathrm{*}}会与同区间原图定车次冲突。假设{\partial }_{t^{e\mathrm{*}}}为可能与t^{e\mathrm{*}}冲突的原运行图固有车次集合，如图3b绿色阴影包含的车次。此时，可通过以下步骤获取{\partial }_{t^{e\mathrm{*}}}：①检查是否位于同一区间；②检查固有车次的始发时间；③检查该固有车次的终到时间。上述3个步骤可用公式⑶表示。

{\partial }_{t^{e\mathrm{*}}}=\{t\in T|s_{t^{e\mathrm{*}}}^d=s_t^d\bigcap s_{t^{e\mathrm{*}}}^a=s_t^a\bigcap {\alpha }_{t^{e\mathrm{*}}}^d+H\le {\alpha }_t^d\le {\alpha }_{t^{e\mathrm{*}}}^d+H+{\theta }_{t^{e\mathrm{*}}}\bigcap {\alpha }_{t^{e\mathrm{*}}}^a+H-{\theta }_{t^{e\mathrm{*}}}\le {\alpha }_t^a\le {\alpha }_{t^{e\mathrm{*}}}^a+H\}⑶

综上，当{\partial }_{t^{e\mathrm{*}}}为空集时，则表示t\in T与其对应\lambda (t)间至少能够插入1个t^{e\mathrm{*}}。上述公式⑴，⑵，⑶可简化表述为公式⑷。

\begin{array}{cc}\underset{t\in {\partial }_{{}_{t^{e\mathrm{*}}}}}{\mathrm{m}\mathrm{a}\mathrm{x}}\mathrm{\Delta }(t)\ge \mathrm{2}H& {\partial }_{t^{e\mathrm{*}}}\ne \mathrm{\varnothing }\end{array}⑷

在建立包含空车调拨的动车组接续网络基础上，构建两阶段整数线性规划模型，2个模型间以特定的方式进行迭代(见算法设计)，最终获得高质量满意解。

2.3　阶段一：可行调整路径实时生成模型

2.3.1　目标函数

目标函数包含4部分：最小化取消车次惩罚；最小化偏离原计划惩罚；最小化额外空驶车次使用惩罚；最小化库存不平衡惩罚。

\mathrm{m}\mathrm{i}\mathrm{n}{z}_{(\mathrm{M}-\mathrm{P})}=\sum _{\begin{array}{l}t\in T^{\mathrm{*}}\\ m=m_e\end{array}}\xi ·y_m^t+\sum _{\begin{array}{l}c\in C,c\mathrm{*}\in C\mathrm{*}\\ c=c\mathrm{*}\\ d{e}_{f_c}\ge Di{s}_s\\ \bigcup d{e}_{s_c}\ge Di{s}_s\end{array}}\sum _{m\in M}\sum _{m\mathrm{\text{'}}\in M}\zeta ·|F_{m，m\mathrm{\text{'}}}^c-F_{m，m\mathrm{\text{'}}}^{c\mathrm{*}}|+\sum _{\begin{array}{l}t\in T^a\\ m\ne m_e\end{array}}\lambda ·y_m^t+\sum _{u\in U}\sum _{b\in B}\epsilon ·J_b^u⑸

式中：T，T^{\mathrm{*}}与T^a分别为所有车次、图定车次与额外备选空驶车次(严重干扰后)集合；C，C\mathrm{*}分别为可行车次接续组合与原图定车次接续组合集合，C\mathrm{*}\subset C；M为动车组编组方式集合；U为动车组型号集合；B为动车段(所)集合；f_c，s_c分别为c中的第一个与第二个车次；d{e}_{f_c}，d{e}_{s_c}分别f_c与s_c的始发时间，s；Di{s}_s为严重干扰发生的开始时刻，s；F_{m，m\mathrm{\text{'}}}^{c\mathrm{*}}为0-1参数，保持原接续及编组取1，否则取0；\xi，\zeta，\lambda，\epsilon分别为取消车次、偏离原动车组计划、使用额外空驶车次及动车段(所)存车数偏离期望的惩罚；y_m^t为0-1决策变量，若t的编组为m则取1，否则取0；F_{m，m\mathrm{\text{'}}}^c为0-1决策变量，若m，m\mathrm{\text{'}}分别为c中f_c，s_c的编组，则取1，否则取0；J_b^u为整数变量，辆，代表动车段(所)b在运营时间段结束后，u型动车组偏离期望的数量；m_e为“空”编组，表示该车次取消。

对公式⑸线性化，线性化前先引入约束公式⑹。

\begin{array}{cc}{\mathrm{\Omega }}_{m,m\mathrm{\text{'}}}^c\ge F_{m,m\mathrm{\text{'}}}^c-F_{m,m\mathrm{\text{'}}}^{c\mathrm{*}}\bigcap {\mathrm{\Omega }}_{m,m\mathrm{\text{'}}}^c\ge F_{m,m\mathrm{\text{'}}}^{c\mathrm{*}}-F_{m,m\mathrm{\text{'}}}^c& \forall c\in C,c\mathrm{*}\in C\mathrm{*}:c\end{array}=c\mathrm{*}；m，m\mathrm{\text{'}}\in M⑹

式中：{\mathrm{\Omega }}_{m，m\mathrm{\text{'}}}^c为0-1中间变量，当{\mathrm{\Omega }}_{m，m\mathrm{\text{'}}}^c=\mathrm{1}时表示偏离原动车组计划，否则为0。

另引入0-1中间变量{\gamma }^c，如公式⑺所示。

\begin{array}{cc}\sigma ·{\gamma }^c\ge \sum _{m\in M}\sum _{m^{,}\in M}{\mathrm{\Omega }}_{m,m^{,}}^c& \forall c\in C,c\mathrm{*}\in C\mathrm{*}:c\end{array}=c\mathrm{*}⑺

式中：\sigma为足够大的正整数。

通过公式⑹至⑺，将公式⑸线性化表示为公式⑻。

\mathrm{m}\mathrm{i}\mathrm{n}{z}_{(M-P)}=\sum _{\begin{array}{l}t\in T^{\mathrm{*}}:\\ m=m_e\end{array}}\xi ·y_m^t+\sum _{\begin{array}{l}c\in C:\\ d{e}_{f_c}\ge Di{s}_s\\ \bigcup d{e}_{s_c}\ge Di{s}_s\end{array}}\zeta ·\sigma ·{\gamma }^c+\sum _{\begin{array}{l}t\in T^a:\\ m\ne m_e\end{array}}\lambda ·y_m^t+\sum _{u\in U}\sum _{b\in B}\epsilon ·J_b^u⑻

2.3.2　约束条件

（1）车次担当唯一性约束如下。

\begin{array}{cc}\sum _{m\in M}{y}_m^t+\sum _{m\in M}{y}_m^{t\mathrm{\text{'}}}=\mathrm{1}& \forall t\in T^{\mathrm{1}},t\mathrm{\text{'}}\end{array}\in T^{\mathrm{2}}⑼

\begin{array}{cc}\sum _{m\in M}{y}_m^t\le \mathrm{1}& \forall t\in T^e\bigcup T^s\end{array}:A_t，D_t\notin B⑽

式中：T^{\mathrm{1}}，T^{\mathrm{2}}分别为第一天与第二天的车次集合；T^e，T^s分别为可用空驶车次集合与可用过夜车次集合；A_t，D_t分别为t的终到与始发车站。

（2）动车组接续网络流平衡约束如下。

\begin{array}{cc}\left\{\begin{array}{c}\sum _{\begin{array}{l}c\in C:\\ f_c=t\end{array}}\sum _{m\mathrm{\text{'}}:(m,m\mathrm{\text{'}})\in Z_{m,m\mathrm{\text{'}}}^c}{F}_{m,m\mathrm{\text{'}}}^c=y_m^t\\ \sum _{\begin{array}{l}c\in C:\\ s_c=t\end{array}}\sum _{m\mathrm{\text{'}}:(m\mathrm{\text{'}},m)\in Z_{m\mathrm{\text{'}},m}^c}{F}_{m\mathrm{\text{'}},m}^c=y_m^t\end{array}\right.& \begin{array}{l}\forall t\in T:A_t,D_t\notin B\\ m\in M\end{array}\end{array}⑾

式中：z_{m，m\mathrm{\text{'}}}^c为c的可行编组方式，即f_c的编组为m，s_c的编组为m\mathrm{\text{'}}。

（3）动车段(所)库存能力限制约束如下。

\begin{array}{cc}\left\{\begin{array}{c}{v}_{u,\mathrm{c}}^{+}=\sum _{m\in M}\sum _{m\mathrm{\text{'}}:(m,m\mathrm{\text{'}})\in Z_{m,m\mathrm{\text{'}}}^c}{F}_{m,m\mathrm{\text{'}}}^c·{\varphi }_{m,m\mathrm{\text{'}}}^u\\ v_{u,\mathrm{c}}^{-}=\sum _{m\in M}\sum _{m\mathrm{\text{'}}:(m,m\mathrm{\text{'}})\in Z_{m,m\mathrm{\text{'}}}^c}{F}_{m,m\mathrm{\text{'}}}^c·{\phi }_{m,m\mathrm{\text{'}}}^u\end{array}\right.& \forall c\in C,u\in U\end{array}⑿

{\omega }_{u，b}^{time}=so{d}_b^u-\sum _{\begin{array}{l}c\in C:\\ D_{f_c}=b,\\ {\eta }_c\le time\end{array}}{v}_{u，c}^{+}+\sum _{\begin{array}{l}c\in C:\\ A_{s_c}=b,\\ {\mu }_c\le time\end{array}}{v}_{u，c}^{-}+\sum _{\begin{array}{l}c\in C:\\ f_c,s_c\in T^{\mathrm{*}},\\ {\mu }_c\le time\end{array}}{g}_{c，u}^b-\sum _{\begin{array}{l}c\in C:\\ f_c,s_c\in T^{\mathrm{*}},\\ {\eta }_c\le time\end{array}}{q}_{c，u}^b\forall time\in Time，u\in U，b\in B⒀

\begin{array}{cc}{\omega }_{u,b}^{time}\le Ma{x}_b^u& \forall time\in Time,u\in U,b\in B\end{array}⒁

式中：{\varphi }_{m，m\mathrm{\text{'}}}^u，{\phi }_{m，m\mathrm{\text{'}}}^u分别为从m改编为m\mathrm{\text{'}}时重联/摘解的u型动车组数量，辆；so{d}_b^u为运营开始前b中u型动车组的数量，辆；Time为时间范围，s；time为时刻，s；{\eta }_c，{\mu }_{\mathrm{c}}分别为c中摘解/重联完毕时刻，s；Ma{x}_b^u为b中u型动车组的数量上限，辆；v_{u，\mathrm{c}}^{+}，v_{u，\mathrm{c}}^{-}为非负整数变量，分别为c中u类动车组重联/摘解数量，辆；{\omega }_{u，b}^{time}为非负整数变量，为在时刻time动车段(所)b内u类动车组的数量，辆；q_{c，u}^b，g_{c，u}^b为0-1决策变量，分别表示c中重联/摘解的u类动车组是否来自动车段(所)b，是则为1，否则取0。

（4）动车段(所)库存平衡约束如下。

\begin{array}{cc}{J}_b^u\ge (so{d}_b^u-eo{d}_b^u)-{\omega }_{u,b}^{etime}+{\omega }_{u,b}^{btime}& \forall b\in B,u\in U\end{array}⒂

式中：eo{d}_b^u为运营结束后b中u类动车组的数量，辆。

（5）实时优化调整约束如下。严重干扰发生时，原运行图中的部分车次已经执行，其对应的车次接续关系及其编组方式已固定，如公式⒃所示。结合公式⒄，确定该车次与其他车次间的接续关系。

\begin{array}{cc}{y}_m^t=y_m^{t\mathrm{*}}& \forall t\in T^{\mathrm{*}}:a{r}_t\le Di{s}_s\end{array}，m\in M⒃

式中：a{r}_t为t的终到时间，s；y_m^{t\mathrm{*}}为0-1参数，若保持原编组取1，否则取0。

\begin{array}{cc}{F}_{m,m\mathrm{\text{'}}}^c=F_{m,m\mathrm{\text{'}}}^{c^{\mathrm{*}}}& \forall c\in C:a{r}_{f_c}\end{array}\le Di{s}_s，m\in M，m\mathrm{\text{'}}\in M⒄

2.4　阶段二：包含日常检修的动车组指派模型

2.4.1　目标函数

目标函数为最小化动车组虚拟启动费\mathrm{m}\mathrm{i}\mathrm{n}{z}_{(\mathrm{S}-\mathrm{P})}^[22]。

\mathrm{m}\mathrm{i}\mathrm{n}{z}_{(\mathrm{S}-\mathrm{P})}=\sum _{p\in P_r}\sum _{r\in R}{x}_r^p·a{c}_r⒅

式中：R为标准组集合；P_r为r的所有路径集合；a{c}_r为r的启动费用，元；x_r^p为0-1变量，若r担当路径p\in P_r取1，否则取0。

2.4.2　约束条件

列车运行线覆盖约束如公式⒆所示；路径唯一性约束如公式⒇所示；日常检修的时间与距离限制约束如公式 所示。

{\begin{array}{cc}\sum _{r\in R}\sum _{p\in P_r}{\partial }_p^t·x_r^p=N_t& \forall t\in T\end{array}}^{\mathrm{*}}⒆

\begin{array}{cc}\sum _{p\in P_r}{x}_r^p\le \mathrm{1}& \forall r\in R\end{array}⒇

\begin{array}{cc}\left\{\begin{array}{c}\sum _t{\partial }_p^t·l_t·x_r^p+E_r^{length}\le \mathrm{5}\mathrm{500}\\ p_{time}·x_r^p+E_r^{time}\le \mathrm{2}\mathrm{880}\end{array}\right.& \begin{array}{l}\forall r\in R,p\in P_r:\\ u_r=p_u\bigcap p_b=b_r\end{array}\end{array}(21)

式中：{\partial }_p^t为0-1参数，当t是p\in P的一部分时取1，否则取0；N_t为t所需要的标准组数量，辆；l_t为t的运行距离，km；E_r^{length}为r的初始累积运行里程，km；E_r^{time}为r的初始累积运行时间，s；u_r为r的类型；b_r为r的初始停放动车段(所)；p_u，p_b分别为p的动车组类型、始发动车段(所)；p_{time}为p的运行时间，s。

此外，还需满足实时优化调整约束，如公式 所示。该式能固定严重干扰发生前已经执行列车车次的担当动车组，即当新的路径属于原动车组计划采用的路径集合且该路径中包含已经被执行的列车车次，其归属关系判定见算法设计。

\begin{array}{cc}\sum _{r\in R\mathrm{*}}{x}_r^p=\mathrm{1}& \forall p:p\in P\mathrm{*}\end{array}(22)

式中：P\mathrm{*}为原动车组计划采用的路径集合；R\mathrm{*}为P\mathrm{*}中任意一个路径p对应的标准组集合。

3　算法设计

迭代优化算法流程图如图5所示，包含2个阶段。一是预处理阶段。根据调整后的运行图，构建包含空车调拨的动车组接续网络，并生成额外的空驶列车车次集合。二是求解阶段。求解阶段包含3个步骤。①通过阶段一模型获得多种可行的路径实时调整方案，将所有的可行路径方案储存在解池中。②设置抽取规则，从解池中依次抽取固定数量的路径调整方案。经过路径搜索算法将该可行解转换为单个标准动车组的可行路径集合^[11]。③以获得的单个标准动车组的可行路径集合作为输入，求解阶段二模型。求解时存在单个或多个可行解，按目标函数排序输出最优解。如在求解时限内没有可行解，则返回步骤②；若解池中没有更多解，则返回步骤①。

此外，考虑严重干扰事故发生前已经执行列车车次的担当动车组，需要判定路径间的归属关系：①原动车组运用计划中的任意一个路径p，若其第一个车次t^{\mathrm{1}}的a{r}_{t^{\mathrm{1}}}小于Di{s}_s，则该路径已经执行，将t^{\mathrm{1}}放入集合T^{Special}中。②任意一个新路径p\mathrm{\text{'}}，若其第一个车次t^{\mathrm{1}\mathrm{\text{'}}}的a{r}_{t^{\mathrm{1}\mathrm{\text{'}}}}小于Di{s}_s，则该路径已经执行，将p\mathrm{\text{'}}放入P\mathrm{*}中。此时路径p\mathrm{\text{'}}\in p。③在T^{Special}，若t^{\mathrm{1}\mathrm{\text{'}}}=t^{\mathrm{1}}，则将t^{\mathrm{1}}的标准组r_{t^{\mathrm{1}}}添加到集合R_{t^{\mathrm{1}\mathrm{\text{'}}}}中。通过以上步骤，能够获得公式 中的P\mathrm{*}及R\mathrm{*}(即R_{t^{\mathrm{1}\mathrm{\text{'}}}})。

4　案例分析

4.1　参数设定

以中国铁路郑州局集团有限公司(以下简称“郑州局集团公司”)所辖部分高速铁路网络为例，其拓扑结构如图6所示，主要考虑郑焦城际(郑州—焦作)、郑开城际(郑州东—宋城路)及郑机城际(郑州东—郑州航空港)3条线路，包括15个车站及2个动车运用所，在图中用不同颜色的实线进行区分。路网中其他相衔接的高速铁路线路及车站均用灰色虚线表示，在本案例中不考虑其他相衔接的高速铁路线路影响。

以2018—2019年运行图实际数据为输入^[21]，在该运行图中包含117个图定列车车次。这里的图定列车车次为集成车次，如将郑州—宋城路的途经列车车次集成为1个列车车次。根据列车运行计划及动车组运用数据，车站最小动车组接续作业时间为15 min。考虑3种类型车组：CRH380A，CRH380B及CRH6A。各动车所不同类型的标准组保有量信息如表1所示，对应的可行动车组编组方式如表2所示，各动车组的初始累积运行时间及初始累积运行里程参考文献[21]。动车组重联作业耗时12 min，摘解作业耗时8 min。

在表1、表2中，“CRHen”“CRHen-空长”“CRHen-空短”即“空编组”。在实际运营过程中，取消车次会对乘客带来较大的影响，因此求解时需要添加较大的惩罚。案例构造了多个场景，严重干扰场景设定如表3所示。各案例的运行图调整均采用“先到先服务”的原则。

案例其他主要参数的设定如表4所示，包括取消车次的惩罚参数、动车组计划偏离的惩罚参数、使用额外空驶车次的惩罚参数及库存不平衡参数的设定，各参数取值参考既有文献及前期研究实验确定^[11，17-18]。

上述模型及算法使用编程语言进行编译，其中两阶段整数规划模型调用商业优化软件进行求解。根据既有研究的测试及验证^[11]，在求解过程中，将商业求解器解池的求解强度参数(Intensity)设置为2，第一阶段模型在每次调用商业优化软件求解时向解池中填充的可行解数量N为100，从中选取的前F个可行解数量为10。

4.2　计算结果分析

案例1与案例2：允许郑州东—郑州，郑州东—南曹，以及郑州—南曹3个区段在事故发生后4 h内进行空车调拨，允许郑州—焦作区段在事故发生后1 h内进行空车调拨；案例3与案例4：允许郑州东—郑州，郑州东—南曹，以及郑州—南曹3个区段在事故发生后4 h内进行空车调拨，允许南曹—新郑机场区段在事故结束后1 h内进行空车调拨；案例5：允许郑州东—南曹，郑州—南曹2个区段在事故发生后4 h内进行空车调拨；案例6：允许郑州—南曹，郑州东—郑州2个区段在事故发生后4 h内进行空车调拨；案例7：允许郑州—南曹，郑州东—郑州2个区段在事故发生后4 h内进行空车调拨；案例8与案例9：允许郑州东—郑州，郑州东—南曹，以及郑州—南曹3个区段在事故发生后4 h内进行空车调拨，允许郑州东—宋城路区段在事故结束后1 h内进行空车调拨。

各案例的计算时间如表5所示。需要注意的是调整后的运行图需要满足“可行”条件，即该运行图至少能找到一种可行的动车组运用计划。从表5可以看到，所有案例均能在15 s以内求解完成，时间较短。根据文献[22]，阶段一模型的最优解即为整个问题的下界解，根据计算结果，上述9个案例均能求得最优解，各案例的其他关键指标统计如表6所示。

表6中，“标准组”为最后求解结果中所使用的标准组数量；“取消车次”为最后求解结果中由“CRHen”类型标准组担当的车次数；“偏离原计划”为以原动车组运用计划为基准，车次接续组合或编组方式改变的数量；“库存偏离”为所有动车段(所)内各型号标准组偏离的数量；“额外空驶车次”为最后求解结果中，新增加的空车调拨车次的数量。从表6可以看出，案例3与案例4需取消部分车次，其他案例均未取消车次。分析发现，案例3中被取消的车次为12：00从新郑机场前往郑州东的车次，此时无法安排任何标准组前往接续。案例4同理。除案例5外，其他案例均有不同程度的偏离原计划。这是因为案例5中发生严重干扰的区段为郑州东—郑州，从拓扑结构来看，该区段发生严重干扰时仅会影响宋城路—焦作区段往返的动车组。由于原运行图中往返宋城路—焦作区段的列车较少，案例5能够利用原运行图的冗余时间。所有的案例均能保持库存平衡。此外，当严重干扰发生在南曹—孟庄区段及宋城路—运粮河区段时，执行调整后的运行图需要使用额外的空驶车次。仅有案例5、案例6与原动车组运用计划使用了相同数量的标准组。这说明如果标准组的数量受到限制，将会有更多的车次被取消。分析被取消车次的案例，发现当位于网络中心位置的动车段(所)服务于放射状高速铁路网络时，若部分区间发生严重干扰，则位于网络尽端区域的始发车次具有较大被取消的可能性。

若不考虑空车调拨，重新对9个案例进行求解，不考虑空车调拨时各案例的关键指标统计如表7所示。从表7可以看出，在路网中无法进行空车调拨时，将额外增加动车组单元的使用，同时也有更多的车次因无法接续而被取消。

5　结束语

当高速铁路在运营过程中受到来自内部或外部因素的干扰，导致某铁路区间在较长时间内完全中断时，通常会使运营中的列车严重偏离原计划，即发生严重干扰^[23]。针对严重干扰场景，提出考虑日常检修限制的动车组运用计划实时调整方法：基于调整后的运行图，引入包含空车调拨的动车组接续网络，并设计空驶车次集成算法以减小调整模型的复杂度；将考虑改编且带维修限制的动车组运用计划调整问题描述为一个两阶段模型，并根据模型特征设计迭代优化算法实现问题的快速求解；以郑州局集团公司城际高速铁路网络为背景，构造多个案例对所提出的模型及方法的可行性、有效性进行验证。结果表明，在所设置的干扰背景下，3条城际线路中受严重干扰影响最大的是郑机城际铁路，其次是郑开城际铁路。研究在假设中，忽略了其他高速铁路线路的影响。在实际运营过程中，其他高速铁路线路上的列车可能也会对研究范围内的高速铁路网络造成影响，如时间或空间上的重叠。因此，未来研究中还可以探讨其他衔接高速铁路线路的影响。

参考文献

[1] 搜狐网. 中国动车在速度和数量上引领世界[EB/OL].(2020-08-18)[2023-08-10].

[2] 人民网. 2019年国家铁路完成旅客发送量35.7亿人[EB/OL].(2020-01-02)[2023-08-10].

[3] 占曙光. 区间通过能力临时失效下高速铁路列车运行实时调整模型与算法研究[D]. 成都：西南交通大学，2016.

[4] CORDEAU J F， SOUMIS F， DESROSIERS J. Simultaneous Assignment of Locomotives and Cars to Passenger Trains[J]. Operations Research，2001，49(4)：531-548.

[5] FIOOLE P J， KROON L， MARÓTI G，et al. A Rolling Stock Circulation Model for Combining and Splitting of Passenger Trains[J]. European Journal of Operational Research，2006，174(2)：1281-1297.

[6] HAAHR J T， WAGENAAR J C， VEELENTURF L P，et al. A Comparison of Two Exact Methods for Passenger Railway Rolling Stock (Re)Scheduling[J]. Transportation Research Part E：Logistics and Transportation Review，2016(91)：15-32.

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

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

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

[10] 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.

[11] 佟　璐，聂　磊，赵　鹏. 蚁群算法在动车组运用问题中的应用[J]. 交通运输系统工程与信息，2009，9(6)：161-167.

[12] TONG Lu， NIE Lei， ZHAO Peng. Application of Ant Colony Algorithm in Train-Set Scheduling Problem[J]. Journal of Transportation Systems Engineering and Information Technology，2009，9(6)：161-167.

[13] 李　华，韩宝明，张　琦，等. 动车组交路计划优化模型与算法研究[J]. 铁道学报，2013，35(3)：1-8.

[14] LI Hua， HAN Baoming， ZHANG Qi，et al. Research on Optimization Model and Algorithm of EMU Circulation Plan[J]. Journal of the China Railway Society，2013，35(3)：1-8.

[15] ZHONG Q W， LUSBY R M， LARSEN J，et al. Rolling Stock Scheduling with Maintenance Requirements at the Chinese High Speed Railway[J]. Transportation Research Part B：Methodological，2019(126)：24-44.

[16] GAO Y， SCHMIDT M， YANG L X，et al. A Branch-and-Price Approach for Trip Sequence Planning of High Speed Train Units[J]. Omega，2020(92)：102150.

[17] BUDAI G， MARÓTI G， DEKKER R，et al. Rescheduling in Passenger Railways：The Rolling Stock Rebalancing Problem[J]. Journal of Scheduling，2010，13(3)：281-297.

[18] CACCHIANI V， CAPRARA A， GALLI L，et al. Railway Rolling Stock Planning：Robustness Against Large Disruptions[J]. Transportation Science，2012，46(2)：217-232.

[19] NIELSEN L K， KROON L， MARÓTI G. A Rolling Horizon Approach for Disruption Management of Railway Rolling Stock[J]. European Journal of Operational Research，2012，220(2)：496-509.

[20] KROON L， MARÓTI G， NIELSEN L. Rescheduling of Railway Rolling Stock with Dynamic Passenger Flows[J]. Transportation Science，2015，49(2)：165-184.

[21] WAGENAAR J C， KROON L G， SCHMIDT M. Maintenance Appointments in Railway Rolling Stock Rescheduling[J].Transportation Science，2017，51(4)：1138-1160.

[22] WAGENAAR J， KROON L， FRAGKOS I. Rolling Stock Rescheduling in Passenger Railway Transportation Using Dead-Heading Trips and Adjusted Passenger Demand[J]. Transportation Research Part B：Methodological，2017(101)：140-161.

[23] LUSBY R M， HAAHR J T， LARSEN J，et al. A Branch-and-Price Algorithm for Railway Rolling Stock Rescheduling[J]. Transportation Research Part B：Methodological，2017(99)：228-250.

[24] 孟令云，杨肇夏，李海鹰. 单线铁路区间能力失效条件下列车运行调整模型[J]. 系统工程理论与实践，2012，32(4)：885-894.

[25] MENG Lingyun， YANG Zhaoxia， LI Haiying. Train Dispatching Models under Field Capacity Breakdowns on Single-Track Railway Lines[J]. Systems Engineering：Theory & Practice，2012，32(4)：885-894.

[26] 钟庆伟. 基于效率提升的高速铁路动车组运用优化与调整研究[D]. 成都：西南交通大学，2020.

[27] 钟庆伟，张永祥，王　典，等. 基于列车车次的动车组运用优化模型与算法[J]. 西南交通大学学报，2021，56(2)：385-394.

[28] ZHONG Qingwei， ZHANG Yongxiang， WANG Dian，et al. Optimization Model and Algorithm for Train-Set Scheduling Based on Trip Sequence[J]. Journal of Southwest Jiaotong University，2021，56(2)：385-394.

[29] 牛红霞，张大勇. 区段强干扰下的列车运行调整研究[J]. 铁道运输与经济，2019，41(2)：37-42.

[30] NIU Hongxia， ZHANG Dayong. A Train Rescheduling Research under Section Strong Interference[J]. Railway Transport and Economy，2019，41(2)：37-42.

基金资助

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

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

四川省自然科学基金资助项目(2022NSFSC1902)

四川省自然科学基金资助项目(2023NSFSC0901)