基于列生成算法的高速铁路动车组司机乘务计划调整优化

Crew Schedule Optimization for Rolling Stock Drivers of High Speed Railway via Column Generation Algorithm

摘要

为解决高速铁路区间完全中断情况下动车组司机乘务计划实时调整优化问题，基于调整后列车运行图，为动车组司机构建接续网络描述其从出乘至退乘的值乘全过程。在满足高速铁路乘务规则的情况下，综合运用乘务片段取消、便乘、改变接续以及使用备用动车组司机等调整措施，以乘务片段取消惩罚、乘务计划偏离惩罚以及动车组司机值乘成本的加权和最小为优化目标，建立基于动车组司机值乘路径的整数线性规划模型，并设计列生成算法求解。最后，选取郑州局集团公司配属动车组服务网络数据构造算例验证所提出方法的有效性。结果表明：所提出模型和算法能在32 s内求解不同区间、不同中断开始时刻下的实际案例，求解时间满足实时调度需要，可为现场调度员提供辅助决策支持。

Abstract

To adjust and optimize the crew schedule of rolling stock drivers in real time in case of complete section blockage for high speed railway, this paper constructed the connection network for drivers to describe the whole process of drive duty based on the rescheduled train timetable. On the premise that high speed railway crew rules were followed, rescheduling strategies such as crew task cancellation, crew deadheading, change of connections, and use of standby rolling stock drivers were adopted in this paper. To minimize the weighted sum of penalties for crew task cancellations, penalties for deviation from the original crew schedule, and costs of drive duty, an integer linear planning model based on the drive path was built, and a column generation algorithm was designed to solve the model. A set of real-life instances was designed based on the rolling stock service network data from China Railway Zhengzhou Group to verify the effectiveness of the proposed method. Results show that the proposed model and algorithm can solve real-life instances under different sections and start moments of disruptions within 32 seconds, where the computational time satisfies the demand for real-time scheduling. The obtained solution can provide decision support for on-site dispatchers.

Graphical abstract

关键词

高速铁路 / 区间完全中断 / 乘务计划 / 实时调整 / 列生成算法

Key words

High Speed Railway / Complete Section Blockage / Crew Schedule / Real-Time Adjustment / Column Generation Algorithm

0　引言

动车组司机(以下简称“司机”)是高速铁路(以下简称“高铁”)系统重要的运力资源之一，随着时间的推移，人力成本在高铁运营中的占比逐渐增大，司机成本占比显著上升，这使得其工作计划的优化变得至关重要。司机乘务计划是确定各司机从出乘至退乘过程中执行乘务任务顺序的计划^[1]。在日常运营过程中，由于突发事件(如设施设备故障、恶劣天气)影响^[2-3]，需要调整列车运行图和动车组运用计划，可能导致原有的司机乘务计划不可行。为确保高铁运营计划的正常执行，在给定调整运行图和动车组运用计划的情况下，调度员需凭借经验对司机乘务计划进行调整。然而这种人工调整方式无法保障司机乘务计划的调整质量和效率，可能导致部分列车无法安排司机，不利于列车运行秩序的快速恢复。因此，研究聚焦于区间完全中断(即区间上下行正线同时中断)这一典型场景，对干扰情况下的司机乘务计划调整优化问题展开研究，以提出科学有效的调整方法，辅助调度员决策。

乘务计划调整问题广泛存在于航空、铁路、城市交通等多个领域。为解决该问题，国内外学者在模型建立和算法设计方面开展了大量研究工作。在模型构建方面，一般将乘务问题构建为集合覆盖模型和集合划分模型^[4-5]，通过构建接续网络^[6-7]或时空状态网络^[1，8]描述乘务组工作过程，且考虑乘务片段取消、乘务组间休以及乘务组工作时间等基本要素^[9]。随着研究工作的不断深入，部分学者进一步考虑了乘务组便乘^[10]、改变列车始发时刻^[5]、细分干扰场景^[11]、提前预知干扰事件^[12]以及列车编组可变^[13]等其他实际因素，为解决干扰情况下乘务计划实时调整提供了新的思路。

在求解算法方面，部分学者设计了蚁群算法^[14]、禁忌搜索算法^[12]以及深度优先搜索^[15]等启发式算法求解乘务计划调整问题。虽然启发式算法求解效率高，但求解质量难以保证。因此，还有一部分学者尝试采用列生成^[6，16]、分支定价^[11]等精确算法求解乘务计划实时调整问题，在测试案例中表现出较好性能^[6]。

目前国内学者主要研究乘务计划编制问题，关于高铁司机乘务计划调整问题的研究较少，既有部分研究侧重于确定事件下的地铁乘务轮转计划调整(乘务请假、临时加开列车等)^[11]，未涉及高铁司机固定区段轮乘模式以及不同动车组车型对司机的技术条件和工作能力要求。国外学者关于高铁司机乘务计划调整问题的研究，由于其司机乘务规则与国内不同，因此其方法不可直接用于我国高铁司机运用实际。

鉴于此，基于文献[5]和文献[6]的方法，综合考虑乘务片段取消、司机便乘、接续变更和使用备用司机等调整措施，考虑固定区段轮乘、司机工作时间和动车组车型技术条件等多种实际因素，在给定调整运行图和动车组运用计划的情况下，研究区间完全中断下的高铁司机乘务计划实时调整问题。具体而言，为各司机构建接续网络，区分司机的便乘和值乘，将司机乘务计划调整问题构建为基于司机值乘路径的整数线性规划模型，并设计列生成算法，将其分解为主问题与各司机路径子问题迭代求解。其中，子问题为考虑司机接续、固定区段轮乘和司机工作时间等约束的资源限制最短路问题。

1　问题描述

高铁司机乘务计划调整问题是在干扰发生后，根据乘务任务、调整后运行图和动车组运用计划，合理地调整各司机从干扰时刻开始至退乘过程中执行乘务任务的顺序。乘务任务即司机的最小工作单元，一般为乘务片段，是根据分界点(乘务基地或换乘站)将列车运行线分割而成^[4]。司机除在乘务片段上值乘外，还可作为乘客通过乘务片段调拨(便乘)。在司机乘务计划调整时，因干扰影响可能导致无法为部分乘务片段指派司机值乘(乘务片段取消)。乘务片段取消会对运营秩序产生较大影响，可通过改变原有乘务片段间的接续关系(接续变更)或安排在乘务基地待命的司机出发值乘(使用备用司机)等措施，保障列车运行秩序。

在高铁司机乘务计划调整过程中主要考虑以下乘务规则^[4，17]。

（1）司机连续值乘2个非同一动车组担当的乘务片段时，2个乘务片段的时间间隔\tau需满足\tau \ge {\tau }_{\mathrm{m}\mathrm{i}\mathrm{n}}，{\tau }_{\mathrm{m}\mathrm{i}\mathrm{n}}为最小乘务换乘时间，min。

（2）在连续工作一段时间后，必须有一段间休时间\epsilon用于司机休息、用餐等，间休时间\epsilon需满足\epsilon \ge {\epsilon }_{\mathrm{m}\mathrm{i}\mathrm{n}}，{\epsilon }_{\mathrm{m}\mathrm{i}\mathrm{n}}为最小乘务间休时间，min。

（3）司机连续工作一段时间\lambda(含换乘时间)后，必须经过间休才能继续工作，连续工作时间\lambda需满足\lambda \le {\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}，{\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}为最大乘务连续工作时间，min。

（4）司机每天总工作时间\mu(包含间休时间、换乘时间、值乘时间、出乘和退乘时间)，需满足\mu \le {\mu }_{\mathrm{m}\mathrm{a}\mathrm{x}}，{\mu }_{\mathrm{m}\mathrm{a}\mathrm{x}}为最大乘务总工作时间，min。

（5）高铁司机采用“固定区段轮乘”模式，通常只值乘固定区段且担当动车组型号为其准驾车型的动车组列车。

假设有车站A与B，列车运行图和乘务片段如图1所示，包含8列列车，其中列车Ⅳ和Ⅴ所需动车组车型为AL，其余列车所需动车组车型为A，c站为乘务基地。准驾AL车型动车组的司机也准驾A车型，反之不行。由于干扰导致区段A—c在9：00至10：30内中断，调整后列车运行图如图1b所示。以乘务基地c为分界点，按照区段A—c和c—B将运行线划分为乘务片段并编号，乘务片段划分如图1c所示。

司机路径调整过程如图2所示。路径(r1)和(r2)为原司机乘务计划中区段A—c路径，车型为A和AL；路径(r3)和(r4)为原司机乘务计划中区段c—B路径，车型为AL和A。由于区段A—c在9：00至10：30内中断，乘务片段3和5始发时间延后，使得路径(r4)司机值乘完乘务片段5后由于接续时间不足无法继续值乘乘务片段8，若按照原计划执行，乘务片段8将因没有司机值乘而额外取消。因此，为更好利用乘务资源，减少乘务片段取消数量，需从9：00开始调整司机值乘路径。

新的司机值乘路径如图2中(r5)、(r6)、(r7)和(r8)所示，其中区段A—c的路径(r5)和(r6)接续关系和车型不变。区段c—B的路径(r7)中司机在值乘完乘务片段1、片段4和5后，到达车站B，在车站B间休后值乘乘务片段12；路径(r8)中司机通过乘务片段1便乘前往车站B，在车站B间休后值乘乘务片段8和9，最后通过乘务片段12便乘返回乘务基地。新路径(r7)相较于原路径(r3)接续关系减少2个，新增2个，偏离为4；新路径(r8)相较于原路径(r4)接续关系减少1个，新增1个，偏离为2，车型由A变为AL。虽然新路径组合计划偏离量增加，改变了部分路径车型，但没有乘务片段额外取消，保障了运输服务质量。

综上，研究问题可描述为：给定高铁网络及乘务基地、区段划分、待值乘的乘务片段、乘务片段所需车型、原乘务计划、司机所在位置、干扰发生后调整运行图以及动车组运用计划，研究确定乘务片段的司机需求满足情况、调整后乘务交路以及司机便乘，使得司机满足乘务规则，且乘务片段取消数量、乘务计划偏离以及司机工作成本之和最小。

2　模型构建

2.1　模型假设及符号定义

（1）在调整乘务计划时，不允许改变列车在车站的到发时刻。

（2）在干扰发生前司机按照原计划值乘，为灵活利用乘务资源，司机可在其他乘务基地退乘。

（3）允许司机通过便乘的方式前往车站，以灵活值乘后续乘务片段。

（4）备用司机随时准备执行乘务任务，在模型中与值乘司机不作区分。

（5）在调整乘务计划时，允许司机的总工作时间延长30 min。

模型符号定义如表1所示。

2.2　乘务接续网络构建

对于司机k，根据乘务接续规则，构建司机接续网络G_k=(V_k,A_k)，其中V_k和A_k分别为G_k的节点集和弧集。为区分司机在乘务片段上的值乘和便乘状态，将集合U_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}中待值乘乘务片段u复制，得到便乘乘务片段u^{\text{'}}，u^{\text{'}}与u有相同始发时刻、终到时刻、始发车站和终到车站，将u^{\text{'}}加入便乘乘务片段集合U_{\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{d}}中，乘务片段集合U=U_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}\bigcup U_{\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{d}}。构建司机k接续网络如图3所示。

对于司机k，其接续网络G_k中的节点集合V_k包括乘务基地出勤节点v_k^{\mathrm{o}\mathrm{u}\mathrm{t}}、乘务基地退勤节点集合V_k^{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}}、乘务片段节点集合V_k^u以及虚拟终点v_k^{\mathrm{e}\mathrm{n}\mathrm{d}}。为便于描述，为所有非虚拟节点i\in V_k\backslash v_k^{\mathrm{e}\mathrm{n}\mathrm{d}}引入属性：m_i^{\mathrm{d}}，m_i^{\mathrm{a}}，q_i^{\mathrm{d}}，q_i^{\mathrm{a}}，{\varphi }_i，v_i^u，{\tau }_i和v_i^s，分别表示节点i的始发车站、终到车站、始发时刻、终到时刻、对应动车组车底、对应乘务片段、值乘时间和图定车型。对于乘务基地出勤节点，m_i^{\mathrm{d}}和m_i^{\mathrm{a}}为其对应乘务基地，q_i^{\mathrm{d}}和q_i^{\mathrm{a}}为干扰发生时刻，剩余属性取值均为0；对于乘务基地退勤节点，m_i^{\mathrm{d}}和m_i^{\mathrm{a}}为其对应乘务基地，剩余属性取值均为0；对于乘务片段节点，全部属性均取实际值。其中：①虚拟终到节点v_k^{\mathrm{e}\mathrm{n}\mathrm{d}}用以构造单源单汇接续网络；②乘务基地出勤节点v_k^{\mathrm{o}\mathrm{u}\mathrm{t}}和乘务基地退勤节点集合V_k^{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}}中的节点表示司机的出发乘务基地和可能的终到乘务基地，司机k\in K需途经乘务基地出勤节点和乘务基地退勤节点表示出勤和退勤；③乘务片段节点集V_k^u中的节点i\in V_k^u表示在司机k值乘区段中且车型为司机准驾车型v_i^s\in S_k的乘务片段。

弧集A_k分为虚拟弧A_k^{\mathrm{v}\mathrm{i}\mathrm{r}}、接续弧A_k^{\mathrm{c}\mathrm{o}\mathrm{n}}、虚拟值乘弧A_k^{\mathrm{v}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{o}\mathrm{n}}、出勤弧A_k^{\mathrm{o}\mathrm{u}\mathrm{t}}以及退勤弧A_k^{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}}。其中：①虚拟弧(i,j)\in A_k^{\mathrm{v}\mathrm{i}\mathrm{r}}连接乘务基地退勤节点i\in V_k^{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}}和虚拟终到节点j(j=v_k^{\mathrm{e}\mathrm{n}\mathrm{d}})，以创建单源单汇接续网络；②接续弧(i,j)\in A_k^{\mathrm{c}\mathrm{o}\mathrm{n}}连接满足司机接续要求的乘务片段节点i和j，表示司机依次值乘乘务片段v_i^u和v_j^u；当m_i^{\mathrm{a}}=m_j^{\mathrm{d}}时，若乘务片段v_i^u和v_j^u所属动车组车底相同，即{\varphi }_i={\varphi }_j，则接续时间需满足q_j^{\mathrm{d}}-q_i^{\mathrm{a}}\ge \mathrm{0}；反之，则接续时间需满足q_j^{\mathrm{d}}-q_i^{\mathrm{a}}\ge {\tau }_{\mathrm{m}\mathrm{i}\mathrm{n}}；③虚拟工作弧(i,j)\in A_k^{\mathrm{v}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{o}\mathrm{n}}连接司机k乘务基地出勤节点i(i=v_k^{\mathrm{o}\mathrm{u}\mathrm{t}})和对应相同乘务基地的乘务基地退勤节点j\in V_k^{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}}，即m_i^{\mathrm{a}}=m_j^{\mathrm{d}}，表示该司机未工作；④出勤弧(i,j)\in A_k^{\mathrm{o}\mathrm{u}\mathrm{t}}连接乘务基地出勤节点i(i=v_k^{\mathrm{o}\mathrm{u}\mathrm{t}})和始发车站为乘务基地m_i^{\mathrm{a}}的乘务片段节点j\in V_k^u，即m_i^{\mathrm{a}}=m_j^{\mathrm{d}}，表示司机k从乘务基地m_i^{\mathrm{a}}开始值乘乘务片段v_j^u；⑤退勤弧(i,j)\in A_k^{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}}连接乘务片段节点i\in V_k^u和乘务基地退勤节点j\in V_k^{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}}，表示司机k在值乘完乘务片段v_i^u后在乘务基地m_j^{\mathrm{d}}退勤。

为所有弧(i,j)\in A_k引入属性{\tau }_{i,j}，表示节点i和j之间的接续时间，若(i,j)\in A_k^{\mathrm{v}\mathrm{i}\mathrm{r}}，则{\tau }_{i,j}=\mathrm{0}。此外，为出勤弧(i,j)\in A_k^{\mathrm{o}\mathrm{u}\mathrm{t}}引入属性c_k^{\mathrm{1}}，表示司机k开始工作成本；为退勤弧(i,j)\in A_k^{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}}引入属性c_k^{\mathrm{2}}，表示司机k的退勤成本，若司机返回原乘务基地，则c_k^{\mathrm{2}}=\mathrm{0}；为弧(i,j)\in A_k^{\mathrm{o}\mathrm{u}\mathrm{t}}\bigcup A_k^{\mathrm{c}\mathrm{o}\mathrm{n}}引入非负属性d_{i,j}，表示计划偏离。

基于接续网络G_k，司机k每日值乘任务等价于从乘务基地出勤节点v_k^{\mathrm{o}\mathrm{u}\mathrm{t}}到虚拟终点v_k^{\mathrm{e}\mathrm{n}\mathrm{d}}的一条可行路径，因此研究的问题可视为一类多商品网络流问题，即在满足乘务规则的情况下，为每个司机k确定一条从乘务基地出勤节点到虚拟终点的可行路径，使得乘务片段取消数量、乘务计划偏离以及司机工作成本的加权和最小。各司机值乘路径生成问题本质上为一类受资源限制的最短路问题，在3.2节中将具体描述。

2.3　目标函数

根据问题描述，目标函数可表达为式⑴。

\mathrm{m}\mathrm{i}\mathrm{n}{c}_{\mathrm{1}}\sum _{u\in U_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}}{y}_u+\sum _{k\in K}\sum _{p\in P_k}{d}_p{x}_{p,k}+\sum _{k\in K}\sum _{p\in P_k}{c}_p{x}_{p,k}⑴

公式⑴中，第1项为乘务片段取消总惩罚，第2项为路径偏离总惩罚，第3项为路径值乘总成本。在求解时，对于路径p而言，其途经乘务片段已知，参数d_p和c_p可直接计算得到。在路径生成时考虑司机固定区段轮乘模式、工作时间要求、司机便乘以及动车组车型技术条件。

2.4　约束条件

2.4.1　司机路径选择约束

公式⑵保证每个司机都选择一条路径，若选择不包含任何乘务片段路径，则该司机不需执行值乘乘务任务。

\sum _{p\in P_k}{x}_{p,k}=\mathrm{1}\forall k\in K⑵

2.4.2　乘务片段取消约束

公式⑶表示若乘务片段无司机值乘，则取消。

\sum _{k\in K}\sum _{p\in P_k}{\alpha }_{p,u}{x}_{p,k}=\mathrm{1}-y_u\forall u\in U_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}⑶

2.4.3　变量取值

公式⑷和公式⑸为变量取值范围。

x_{p,k}\in \{\mathrm{0,1}\}\forall k\in K,\forall p\in P_k⑷

y_u\in \{\mathrm{0,1}\}\forall u\in U_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}⑸

3　列生成算法求解

模型⑴至⑸可视为一类指派问题，即为每个司机k选择其可行路径集合P_k中一条值乘路径，因此每个司机可行路径集合P_k的生成至关重要。对于模型⑴至⑸而言，尽管乘务规则约束比较复杂，但可行乘务交路的数目仍然很多，变量(乘务可行路径)数量远大于约束数量，若一次生成所有可行路径耗时大且导致模型⑴至⑸难以求解。考虑到最终司机乘务计划调整方案为所有可行路径的子集，为使问题易于求解，从小部分路径开始逐步生成路径添加到模型⑴至⑸可行路径集合P_k中。为保障各司机可行路径的生成质量，根据模型⑴至⑸当前的求解结果，生成可能改进司机乘务计划调整方案的各司机可行值乘路径并添加到集合P_k。针对模型变量数量远大于约束数量以及通过当前求解结果生成可能的改进变量的特点，列生成算法是一个很好的选择。列生成算法将模型分解为主问题和子问题，可以从一小部分变量开始，根据主问题求解结果生成可能改进主问题的“列”添加到主问题中，直至满足主问题最优性检验。列生成算法需解决3个关键问题：①主问题构造；②子问题构造；③子问题求解。

列生成算法符号定义如表2所示。

3.1　主问题构造

将第2节构建的主问题模型(Master Problem，MP)中的整数变量松弛为连续变量，集合P_k替换为其限制集合{\overline{P}}_k，便可得到如下限制主问题(Relaxed Restricted Master Problem，RRMP)。注意，限制集合{\overline{P}}_k中所含元素数量远小于集合P_k，在迭代时动态更新。

(\mathrm{R}\mathrm{M}\mathrm{P})\mathrm{m}\mathrm{i}\mathrm{n}{c}_{\mathrm{1}}\sum _{u\in U_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}}{y}_u+\sum _{k\in K}\sum _{p\in {\overline{P}}_k}{d}_p{x}_{p,k}+\sum _{k\in K}\sum _{p\in {\overline{P}}_k}{c}_p{x}_{p,k}⑹

\sum _{p\in {\overline{P}}_k}{x}_{p,k}=\mathrm{1}\forall k\in K⑺

\sum _{k\in K}\sum _{p\in {\overline{P}}_k}{\alpha }_{p,u}{x}_{p,k}=\mathrm{1}-y_u\forall u\in U_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}⑻

x_{p,k}\in [\mathrm{0,1}]\forall k\in K,\forall p\in {\overline{P}}_k⑼

y_u\in [\mathrm{0,1}]\forall u\in U_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}⑽

为得到约束对偶值，需要一组初始的值乘路径启动算法，研究首先为各司机可行值乘路径集合添加不包含任何乘务片段的空路径；其次采用结合3.3节标签算法的启发式方法生成初始可行的乘务调整计划，每次迭代将生成路径包含的乘务片段从乘务片段集合中移除，并为剩余乘务片段节点附加惩罚，直至乘务片段集合为空，得到初始解。迭代中的RRMP为线性规划问题，可借助商业优化软件求解。

3.2　子问题构造

令{\mathrm{\pi }}_k和{\omega }_u分别为表示限制主问题中约束⑺至⑻的对偶值，其值可在RRMP求解完毕后获得，则子问题的目标函数可表示为公式⑾。

\left(\mathrm{S}\mathrm{P}\right)\mathrm{m}\mathrm{a}\mathrm{x}\sum _{k\in K}{\mathrm{\pi }}_k+\sum _{u\in U_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}}{\alpha }_{p,u}{\omega }_u-\sum _{k\in K}{d}_p-\sum _{k\in K}{c}_p⑾

公式⑾中c_p，d_p为子问题相关变量，其余为已知参数。由公式⑾可进一步分解为\left|K\right|个司机值乘路径生成子问题。司机k值乘路径生成子问题的目标函数如下。

\left(\mathrm{S}{\mathrm{P}}_k\right)\mathrm{m}\mathrm{i}\mathrm{n}{d}_p+c_p-{\mathrm{\pi }}_k-\sum _{u\in U_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}}{\alpha }_{p,u}{\omega }_u⑿

对\forall u\in U_{\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{d}}有{\omega }_u=\mathrm{0}，此时\sum _{u\in U_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}}{\alpha }_{p,u}{\omega }_u=\sum _{u\in U}{\alpha }_{p,u}{\omega }_u。基于接续网络，以弧形式对子问题\mathrm{S}{\mathrm{P}}_k的目标函数进行重构，表示为公式⒀。

\begin{array}{c}\left(\mathrm{R}\mathrm{S}{\mathrm{P}}_k\right)\mathrm{m}\mathrm{i}\mathrm{n}{c}_{\mathrm{2}}\sum _{i\in V_k}\sum _{j\in V_k}{d}_{i,j}{g}_{i,j}+\left(\sum _{i\in V_k}\sum _{j\in V_k}{\tau }_{i,j}{g}_{i,j}+\sum _{i\in V_k}{r}_i\right.\\ \left.\sum _{j\in V_k}{g}_{i,j}+c_k^{\mathrm{1}}+c_k^{\mathrm{2}}\right)-{\mathrm{\pi }}_k-\sum _{i\in V_k^u}{\omega }_i\sum _{j\in V_k}{g}_{i,j}=\sum _{i\in V_k}\sum _{j\in V_k}\left(c_{\mathrm{2}}{d}_{i,j}+\right.\\ \left.{\tau }_{i,j}\right)g_{i,j}+\sum _{i\in V_k}\left(r_i-{\omega }_i\right)\sum _{j\in V_k}{g}_{i,j}+c_k^{\mathrm{1}}+c_k^{\mathrm{2}}-{\mathrm{\pi }}_k\end{array}⒀

综上，对于司机k，其路径子问题可表示如下。

\begin{array}{c}\left(\mathrm{R}\mathrm{S}{\mathrm{P}}_k\right)\mathrm{m}\mathrm{i}\mathrm{n}\sum _{(i,j)\in A_k}(c_{\mathrm{2}}{d}_{i,j}+{\tau }_{i,j}+r_i-{\omega }_i)g_{i,j}+c_k^{\mathrm{1}}+\\ c_k^{\mathrm{2}}-{\mathrm{\pi }}_k\end{array}⒁

s.t\sum _{j\in V_k}{g}_{i,j}-\sum _{j\in V_k}{g}_{j,i}=\left\{\begin{array}{l}\mathrm{1}i=v_k^{\mathrm{o}\mathrm{u}\mathrm{t}}\\ \mathrm{0}i\in V_k\backslash \{v_k^{\mathrm{o}\mathrm{u}\mathrm{t}},v_k^{\mathrm{e}\mathrm{n}\mathrm{d}}\}\\ -\mathrm{1}i=v_k^{\mathrm{e}\mathrm{n}\mathrm{d}}\end{array}\right.⒂

\begin{array}{c}\sum _{(i^{\text{'}},j)\in A_k;\underline{i}\le i^{\text{'}},j\le i}{\tau }_{i^{\text{'}}}{g}_{i^{\text{'}},j}+\sum _{(i^{\text{'}},j)\in A_k;\underline{i}\le i^{\text{'}},j\le i}{\tau }_{i^{\text{'}},j}{g}_{i^{\text{'}},j}\le {\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}\\ \forall i\in V_k^u,\underline{i}=\mathrm{m}\mathrm{a}\mathrm{x}\{j|{\rho }_{i^{\text{'}},j}{g}_{i^{\text{'}},j}=\mathrm{1},i^{\text{'}},j\le i\}\end{array}⒃

\sum _{(i,j)\in A_k}{\tau }_i{g}_{i,j}+\sum _{(i,j)\in A_k}{\tau }_{i,j}{g}_{i,j}+T_{\mathrm{1}}+T_{\mathrm{2}}\le {\mu }_{\mathrm{m}\mathrm{a}\mathrm{x}}⒄

g_{i,j}\in \{\mathrm{0,1}\}\forall (i,j)\in A_k⒅

式中：d_{i,j}表示司机接续偏差量，其值为d_{i,j}^{\mathrm{1}}+d_{i,j}^{\mathrm{2}}，其中，d_{i,j}^{\mathrm{1}}为弧(i,j)接续新增参数，若原计划中存在接续(i,j)则为0，否则为1，以统计新增接续关系数；d_{i,j}^{\mathrm{2}}为弧(i,j)接续减少参数，若原计划中存在接续关系(i,j)则为-1，否则为原计划中乘务片段节点j后续乘务片段接续关系总数，以统计减少接续关系数。

公式⒂为流平衡约束，保证司机值乘路径的连续性。公式⒃为司机连续工作时间约束，通过统计上一次间休到当前乘务片段节点的工作时间，保证路径不会违反最大乘务连续工作时间约束。为满足公式⒃需按照乘务片段开始时间对乘务片段进行非减排序。公式⒄为司机最大工作时间约束，表示司机从出勤到退勤的总工作时间不超过预定阈值。公式⒅为变量取值范围。

由上可知，每个司机k的路径生成子问题⒁至⒅可视为受资源限制的最短路问题，可用标签算法快速求解，具体见3.3节。需注意的是，由于接续网络各节点均有时间属性，因而其不存在子回路，模型不需纳入破圈约束。

3.3　子问题求解

子问题\mathrm{S}\mathrm{P}每次求解时需根据当前主问题对偶值更新各司机接续网络中节点和弧线成本，所有司机路径子问题\mathrm{R}\mathrm{S}{\mathrm{P}}_k求解结束后即完成一次子问题\mathrm{S}\mathrm{P}求解。本节详细介绍标签算法求解司机k的路径子问题\mathrm{R}\mathrm{S}{\mathrm{P}}_k的实施细节。

（1）支配规则。令L_i，l为节点i标签集合及其索引。对\forall l\in L_i定义属性c，t_{\mu }，t_{\lambda }，t_b，f，分别表示从节点v_k^{\mathrm{o}\mathrm{u}\mathrm{t}}到节点i\in V_k\backslash v_k^{\mathrm{o}\mathrm{u}\mathrm{t}}的部分路径对应的目标函数值、总工作时间、连续工作时间、累计空闲时间以及节点访问顺序。对于\forall l_{\mathrm{1}}，l_{\mathrm{2}}(l_{\mathrm{1}}，l_{\mathrm{2}}\in L_i)，标签支配规则如式⒆所示。

⒆

若节点i\in V_k的2个标签l_{\mathrm{1}}和l_{\mathrm{2}}满足支配规则，且符号不全相等，则称l_{\mathrm{1}}支配l_{\mathrm{2}}，此时l_{\mathrm{2}}可以被舍弃。

（2）算法步骤。在司机k接续网络中，只包含司机可值乘乘务片段，满足了不同车型动车组技术条件需要以及司机固定区段轮乘规则。

对于司机k，标签算法生成值乘路径的具体流程如下。

步骤 0：根据主问题对偶值更新接续网络G_k中点和弧线成本，为每个节点i初始化标签集合q(i)和e(i)；生成所有属性皆为0的标签l_{\mathrm{0}}，添加到q(v_k^{\mathrm{o}\mathrm{u}\mathrm{t}})。

步骤 1：根据干扰开始时间、原乘务计划和车型，确定在干扰发生时司机正在或刚好完成值乘的乘务片段集合U_{\mathrm{n}\mathrm{o}\mathrm{w}}。按照原乘务计划值乘顺序生成节点i(v_i^u\in U_{\mathrm{n}\mathrm{o}\mathrm{w}})标签l，添加到q(i)。

步骤 2：找到所有节点q(i)中成本最小的标签l。

步骤 2.1：遍历节点i(l\in q(i))能连接的节点j，更新标签值c，t_{\mu }，t_{\lambda }，t_b，f，得到新标签\overline{l}。若满足间休要求t_b\ge {\epsilon }_{\mathrm{m}\mathrm{i}\mathrm{n}}，则t_{\lambda }=\mathrm{0}。若v_j^u\in U_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}，则t_b=\mathrm{0}。

步骤 2.2：判断是否满足乘务规则，即t_{\mu }\le {\mu }_{\mathrm{m}\mathrm{a}\mathrm{x}}，t_{\lambda }\le {\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}，不满足则返回步骤2.1。

步骤 2.3：将\overline{l}与q(j)和e(j)中所有标签判断支配规则，删除被支配标签，若\overline{l}未被支配则将\overline{l}添加到q(j)。

步骤 2.4：将标签l从q(i)中删除，添加到e(i)。

步骤 3：重复步骤2，直至所有节点q(i)为空，此时e(v_k^{\mathrm{e}\mathrm{n}\mathrm{d}})中成本最小的标签对应路径为最短路。

3.4　列生成算法流程

综合上述3个关键问题的处理方法，求解司机乘务计划调整问题的列生成算法流程如图4所示。根据分界点将调整后列车运行图划分为乘务片段，并构建接续网络，在此基础上通过启发式方法生成初始可行解，从而开始算法。基于当前可行解集，调用商业求解器求解限制主问题得到乘务约束对偶值，通过求解子问题生成检验数为负的“列”(需满足固定区段值乘限制)，并将得到的“列”添加进可行解集合中，迭代执行以上过程，直至无法找到检验数为负值的“列”。此时已经找到所有可能使得原问题有改进的“列”，将主问题变量恢复为整数变量后重新求解，得到可行或最优的司机乘务计划调整方案。若MP无可行解，将求解过程中保存的非最优路径也一并添加到MP中重新求解，以得到可行解。为减少算法求解时间，在算法初期采用松弛主问题约束和子问题支配规则的加速策略，并在算法快结束时取消加速策略，使得算法至少最后一次迭代严格满足主问题约束和子问题支配规则。

4　案例分析

4.1　案例设计

以中国铁路郑州局集团有限公司(以下简称“郑州局集团公司”)某日运行图数据为例，应用本研究方法对高铁区间中断情况下司机乘务计划调整问题进行求解，验证所提出方法的有效性。在Intel(R) Core(TM) i9-13900HX 2.20 GHz，16.0 GB的个人电脑上实现算法，采用C#语言编程调用求解器 Gurobi 10.0.2求解主问题，求解器参数为默认设置。

郑州局集团公司配属动车组服务网络如图5所示。该网络共有212个车次，包含4种车型(CRH6A、CRH380A、CRH380B和CRH380AL)，司机共210个。结合既有文献选择如图5所示的分界点划分区段，得到576个乘务片段。

为评估所提出方法在不同干扰场景下对司机乘务计划实时调整的优化效果，共设置12个不同的干扰场景，分别为安阳东—鹤壁东区间(1，2)，许昌东—漯河西区间(3，4)，渑池南—洛阳龙门区间(5，6)，商丘—砀山南区间(7，8)，于当日8：00、11：00、14：00因突发事故导致上下行区间中断行车，预计中断时间为2 h。为方便描述，使用二元组(a,b)表示每个干扰场景，其中a表示中断发生区间；b表示中断发生时刻，各案例调整图按照“先到先服务”原则生成。

案例参数设置如下：c_{\mathrm{1}}=\mathrm{1}\mathrm{000}\mathrm{000}，c_{\mathrm{2}}=\mathrm{10}\mathrm{000}，{\epsilon }_{\mathrm{m}\mathrm{i}\mathrm{n}}=\mathrm{60}，{\mu }_{\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{510}，{\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{240}，{\tau }_{\mathrm{m}\mathrm{i}\mathrm{n}}=\mathrm{15}\mathrm{m}\mathrm{i}\mathrm{n}，T_{\mathrm{1}}=T_{\mathrm{2}}=\mathrm{30}\mathrm{m}\mathrm{i}\mathrm{n}，司机启用成本c_k^{\mathrm{1}}=\left|S_k\right|\times \mathrm{100}，S_k为司机k准驾车型集合，若司机返回原乘务基地，则司机退勤成本c_k^{\mathrm{2}}=\mathrm{0}，否则c_k^{\mathrm{2}}=\mathrm{720}。由于篇幅限制，区段长度等参数信息不再列出。

4.2　计算结果

对于24个测试案例，列生成算法均求解得到最优解，具体计算结果如表3所示。其中，第1列为干扰场景，第2列为乘务片段取消数量O_{\mathrm{1}}，第3列为乘务计划总偏离O_{\mathrm{2}}，第4至5列为司机值乘成本O_{\mathrm{3}}中的司机开始工作总成本和司机值乘时间总成本。第6列为RRMP最后得到目标函数值与整数化后目标函数值误差gap。第7列为司机便乘次数de，第8列为使用备用司机数量al，第9列为模型求解时间T。

由表3可知不同干扰场景计算结果有如下特点。

（1）干扰发生时间越晚，算法求解时间越短，这是因为对于干扰发生时间较晚的干扰场景，由于大部分乘务片段已经被值乘，算法只需较少时间计算即可得到最优解。

（2）中断发生时刻越晚，干扰后的乘务片段数量越少，可调整空间越有限^[18]。例如，平均而言第3个时间段的干扰场景相较于第2个时间段的干扰场景无法满足的乘务片段数量更多。

（3）相较于司机便乘，使用备用司机策略的次数更多，且有司机便乘的场景也有备用司机使用。说明在大部分干扰场景中是安排备用司机便乘前往车站值乘，这是因为改变现有司机值乘路径带来的计划偏离惩罚大于使用备用司机成本。

4.3　备用司机使用策略分析

以各区间第1个干扰时段为例，分别在不同c_{\mathrm{2}}取值情况下对模型进行求解，保持其他参数取值不变，以分析不同偏离惩罚对备用司机策略的影响，备用司机使用情况如图6所示。

如图6所示，随着c_{\mathrm{2}}的减小，备用司机使用数量也减少，其中-1代表相较于原计划节省了1名司机。各干扰场景中，随着c_{\mathrm{2}}的减小，乘务片段取消数量不变，但备用司机使用数量减少了2次。这是因为最初c_{\mathrm{2}}取值较大，原本路径不可行的乘务片段之间接续改变成本，大于使用更多备用司机分别值乘的成本；当c_{\mathrm{2}}减少时，原本路径不可行的乘务片段之间的计划偏离成本小于使用备用司机成本，此时非必要的备用司机被节省；当c_{\mathrm{2}}减少到与司机启用成本相近时，此时算法会尽量节省司机的使用，使得备用司机使用数量进一步减少。

5　结论

研究针对高速铁路动车组司机乘务计划在区间完全中断情况下的实时调整问题，考虑动车组司机固定区段轮乘、司机工作时间、便乘、动车组车型不同技术条件以及备用动车组司机等因素，构建接续网络区分动车组司机便乘和值乘，并建立了基于动车组司机路径的整数线性规划模型。以郑州局集团公司配属动车组服务网络为背景构造不同干扰场景验证所提出的方法。结果表明：根据模型特点设计的列生成算法，采用加速策略后能在32 s内获得所有案例的最优动车组司机乘务计划调整方案，满足现场调度员对调整实时性的要求。通过对备用动车组司机使用策略分析发现，适当地减小计划偏离惩罚可以避免使用非必要的备用动车组司机，但可能导致计划偏离程度增加，增大调度指挥难度，在实际生产中，调度员应综合实际情况采用合适的计划偏离惩罚。

参考文献

[1] 张哲铭，王　莹，廖正文，等. 基于时空状态网络的高速铁路乘务交路计划优化研究[J]. 铁道学报，2019，41(9)：1-11.

[2] ZHANG Zheming， WANG Ying， LIAO Zhengwen，et al. Research on Optimization of Crew Scheduling of High Speed Railway Based on Time Space State Network[J]. Journal of the China Railway Society，2019，41(9)：1-11.

[3] 郭凯生. 铁路防洪防汛对运输的影响及对策研究[J]. 铁道货运，2023，41(6)：37-42.

[4] GUO Kaisheng. Impact of Railway Flood Control on Transportation and Its Countermeasures[J]. Railway Freight Transport，2023，41(6)：37-42.

[5] 李小波，晏兴奎，郑平标，等. 山区铁路汛期运输组织应急调整对策探讨[J]. 铁道货运，2017，35(1)：5-9.

[6] LI Xiaobo， YAN Xingkui， ZHENG Pingbiao，et al. Discussion on Countermeasures of Transport Organization Emergency Adjustment of Mountain Railway in Flood Season[J]. Railway Freight Transport，2017，35(1)：5-9.

[7] 王　莹，刘　军，苗建瑞. 客运专线乘务交路计划编制的优化模型与算法[J]. 铁道学报，2009，31(1)：15-19.

[8] WANG Ying， LIU Jun， MIAO Jianrui. Modeling and Solving the Crew Scheduling Problem of Passenger Dedicated Line[J]. Journal of the China Railway Society，2009，31(1)：15-19.

[9] VEELENTURF L P， POTTHOFF D， HUISMAN D，et al. Railway Crew Rescheduling with Retiming[J]. Transportation Research Part C：Emerging Technologies，2012，20(1)：95-110.

[10] BREUGEM T， VAN ROSSUM B T C， DOLLEVOET T，et al. A Column Generation Approach for the Integrated Crew re-Planning Problem[J]. Omega，2022，107：102555.

[11] CAROSI S， GUALANDI S， MALUCELLI F，et al. Delay Management in Public Transportation：Service Regularity Issues and Crew re-Scheduling[J]. Transportation Research Procedia，2015，10：483-492.

[12] FENG T， LUSBY R M， ZHANG Y X，et al. An ADMM-Based Dual Decomposition Mechanism for Integrating Crew Scheduling and Rostering in an Urban Rail Transit Line[J]. Transportation Research Part C：Emerging Technologies，2023，149：104081.

[13] POTTHOFF D， HUISMAN D， DESAULNIERS G. Column Generation with Dynamic Duty Selection for Railway Crew Rescheduling[J]. Transportation Science，2010，44(4)：493-505.

[14] VEELENTURF L P， POTTHOFF D， HUISMAN D，et al. A Quasi-Robust Optimization Approach for Crew Rescheduling[J]. Transportation Science，2016，50(1)：204-215.

[15] 杨　岳. 高速铁路乘务调整问题研究[D]. 北京：北京交通大学，2020.

[16] 黄志远，周　峰，张在龙. 基于可预知事件的城市轨道交通乘务轮转计划优化调整[J]. 交通运输系统工程与信息，2017，17(4)：111-117.

[17] HUANG Zhiyuan， ZHOU Feng， ZHANG Zailong. Optimizing Adjustment of Urban Rail Transit Crew Rostering Plan Based on Predictable Events[J]. Journal of Transportation Systems Engineering and Information Technology，2017，17(4)：111-117.

[18] 杨　帆，陈绍宽，刘泽远，等. 面向列车可变编组的地铁乘务排班计划优化研究[J]. 铁道运输与经济，2024，46(7)：159-167.

[19] YANG Fan， CHEN Shaokuan， LIU Zeyuan，et al. Optimization of Metro Crew Scheduling Plan Based on Variable Train Formation[J]. Railway Transport and Economy，2024，46(7)：159-167.

[20] ZENG Z L， MENG L Y， HONG X. Integrated Optimization of Rolling Stock and Crew Rescheduling for High Speed Railway[C]//2018 International Conference on Intelligent Rail Transportation (ICIRT). Singapore：IEEE，2018：1-5.

[21] VERHAEGH T， HUISMAN D， FIOOLE P J，et al. A Heuristic for Real-Time Crew Rescheduling during Small Disruptions[J]. Public Transport，2017，9(1)：325-342.

[22] HUISMAN D. A Column Generation Approach for the Rail Crew re-Scheduling Problem[J]. European Journal of Operational Research，2007，180(1)：163-173.

[23] 林　枫. 固定区段轮乘制乘务交路计划编制模型及算法[J]. 铁道学报，2019，41(12)：10-18.

[24] LIN Feng. Bilevel Scale Model and Multi-Objective Multi-Stage Heuristic Algorithm for Crew Scheduling Based on Fixed-Section Pooling Mode[J]. Journal of the China Railway Society，2019，41(12)：10-18.

[25] 周凌霜，彭其渊，张志博，等. 高速铁路动车组运用计划与乘务计划协同调整研究[J]. 铁道运输与经济，2021，43(5)：1-7.

[26] ZHOU Lingshuang， PENG Qiyuan， ZHANG Zhibo，et al. Research on Collaborative Rescheduling for Rolling Stock and Crew on High Speed Railways[J]. Railway Transport and Economy，2021，43(5)：1-7.

基金资助

国家重点研发计划项目(2022YFB4300502)

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

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

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