考虑新旧计划交替的高铁乘务排班计划优化策略

Optimization Strategy of High-Speed Railway Crew Rostering Plan Considering the Alternation between Old and New Plans

摘要

乘务排班计划是为司乘人员制定的工作计划，其编制质量关乎高速铁路运营安全以及成本效益。为合理接续乘务交路，并使得新旧计划良好过渡，采用2阶段优化策略对高铁司机乘务排班计划进行优化。在第1阶段以总接续时间最小和冗余接续时间均衡为目标构建模型，确定新计划中乘务交路的接续顺序以及大休安排；在第2阶段以便乘次数最少和新旧计划交替费用最小为目标构建模型，为司机合理分配新计划第1天担当的具体任务。以南昌铁路局集团有限公司某动车车队真实数据为背景设计案例，并利用商业求解器Gurobi求解。结果表明：相较传统方法，第1阶段模型能进一步压缩接续时间，计划周期缩短1 d，完成计划所需的司机相应减少1名；第2阶段模型能有效控制计划交替产生的影响，计划交替期间共产生2次便乘，仅有1名司机连续担当多日交路，且无司机错过大休。

Abstract

Crew rostering plan is a work schedule designed for crews, the quality of which directly affects the operational safety and cost-efficiency of high-speed railway. To ensure a reasonable connection of crew routes and a smooth transition between old and new plans, a two-stage optimization strategy is adopted to optimize the rostering plan of high-speed train crews. In the first stage, a model is formulated with the objectives of minimizing total connecting time and balancing the redundancy connection time, aiming to determine the sequence of crew routes and long time-off arrangements in the new plan. In the second stage, a model is developed with the goals of minimizing the number of crew deadheading and plan alternation costs, aiming to reasonably allocate specific tasks undertaken by drivers on the first day of the new plan. Utilizing real data from a EMU fleet of China Railway Nanchang Group Co., Ltd. as background to design the case, the commercial solver Gurobi is employed for solution. The results show that, compared with traditional methods, the first-stage model further reduces connecting time, shortens the plan cycle by 1 day and reduces the plan required number of drivers by 1. The second-stage model effectively controls the impacts of plan alternation, during which only 2 instances of crew deadheading occur, only 1 driver consecutively undertakes multi-day routes, and no driver misses long time-off.

Graphical abstract

关键词

高速铁路 / 乘务排班计划 / 接续时间 / 大休安排 / 2阶段优化策略

Key words

High-speed railway / Crew rostering plan / Connecting time / Time-off arrangement / Two-stage optimization strategy

司乘人员在保障动车组运行安全中发挥着重要作用，科学组织高铁乘务工作对于提升运行效率与服务质量具有重要意义。作为乘务组织的核心内容，乘务计划在编制过程中通常分为乘务交路计划与乘务排班计划。其中，乘务排班计划是在乘务交路计划编制完成的基础上，为司乘人员制定的工作计划，明确其在一个排班周期内所担当的乘务交路及休息情况。在制定排班计划时，不仅需要遵循乘务规则、控制运营成本，还需兼顾人性化需求等复杂因素，因而编制难度较高。近年来，铁路部门为适应客流波动，对列车运行图的调整日益频繁，导致乘务排班计划的编制需求相应增加，这对计划编制的质量及效率提出了更高的要求。然而，目前铁路现场沿用的人工排班方式效率较低，难以满足运输组织需要，尤其在乘务交路数量较大的情况下，寻找最优解十分困难。

随着世界高速铁路运输组织的发展，国内外学者对乘务排班计划进行了广泛且深入的研究。赵鹏^［1］综合分析了国内外各种交通方式的乘务计划编制方法，并根据我国高速铁路情况，利用模拟进化算法实现乘务计划的自动编制。褚飞跃等^［2］针对高速铁路单一循环模式下的乘务排班计划编制问题，建立以乘务交路总接续时间最小和冗余接续时间分布均衡为目标的优化模型。由于高铁司机和一般列车乘务员在工作内容、乘务规则上存在差异，在编制排班计划时需采取不同的方式。王东先等^［3-4］针对高铁司机的乘务排班问题，将其抽象为单基地、考虑中途休息的多旅行商问题，并提出一种改进的蚁群算法进行求解。杨国元等^［5］针对一般乘务员的排班需求，以乘务交路和工时为主要约束条件，以减少乘务班组数量、降低乘务成本为优化目标建立模型，并设计遗传算法进行求解。随着问题规模的扩大，Sato等^［6］提出一种基于网络流模型的0-1整数规划方法，以应对复杂的乘务计划调整问题。乘务排班计划需根据已确定的乘务交路进行编制，为优化乘务交路计划，符卓等^［7-8］针对不同类型的乘务交路展开分析，为获得乘务计划整体最优打下基础。考虑到乘务排班计划还受列车运行图的影响，Walker等^［9］将乘务排班计划和列车运行图进行协同优化，构建了能够在实时条件下同时调整乘务排班计划与列车运行图的优化模型，以应对突发事件对计划的干扰。

其他交通运输领域的乘务排班计划相关研究与铁路系统的有一定相通之处，能够为铁路相关问题的研究提供有益参考。在航空领域，孙宏等^［10］根据国内航空公司普遍采用的单枢纽线性航线结构，构造了飞机排班问题的数学模型。Suraweera等^［11］设计了一个智能系统，通过机器学习算法提取历史排班中人工调整的经验规则，并将其转化为可用于计划自动编排的数学约束。在公交系统中，Mesquita等^［12］运用多商品流模型优化驾驶员排班计划，从提高运营效率和降低运营成本的角度，提出了多种混合整数线性规划模型。Ciancio等^［13］研究了公交时刻表和司机排班的综合优化问题，并针对车辆调度和人员排班2个环节设计了一种集成算法。陈明明等^［14-15］引入禁忌搜索算法，进一步提升公交系统乘务排班的优化质量。在城市轨道领域，金华等^［16］构建了乘务排班计划的集合覆盖模型，相较于传统模型，该模型不仅考虑了乘务员跨线值乘，还为乘务员提供了更多的出退勤地点选择，显著减少了通勤时间与班组数量。许仲豪等^［17］提出一种列生成算法，用于求解城市轨道交通系统的乘务排班计划。马亮等^［18］研究了便乘情况下的地铁乘务任务配对问题，综合考虑乘务员工作量、出退勤地点、轮换休息时间和地点等因素，建立了以乘务任务数最少为目标的约束优化模型，并采用约束传播与启发式回溯结合的算法进行求解。

尽管上述研究在乘务排班计划优化方面取得了显著成果，但普遍忽略了新旧计划交替产生的影响。而在实际工作中，新旧计划的平稳过渡是计划编制人员关注的重点之一。良好的计划交替不仅有助于提升运输组织的连续性和稳定性，还为运输系统的顺畅运行提供重要保障^［19］。本文采取2阶段优化策略，对乘务排班计划编制的全过程进行系统研究。在第1阶段，以总接续时间最小和冗余接续时间均衡为目标构建模型，确定新计划中乘务交路的接续顺序，并结合现场实际，提出一种能够减少接续时间的大休安排方式。在第2阶段，以便乘次数最少和计划交替费用最小为目标构建模型，确定司机在新计划第1天担当的具体任务，旨在减少新旧计划交替对司机的影响，实现计划间的良好衔接。

1 问题描述

目前，高铁司机乘务排班计划在编制时普遍采用单一循环模式，即将所有乘务交路纳入1个大循环，司机按照顺序依次担当各项任务。在此模式下，1个完整排班周期内，每个司机的工作内容完全相同，消除了乘务交路差异导致的工作量不均衡问题。由于计划中每日任务由1名司机执行，排班周期的天数即对应完成计划所需的司机数量。合理安排乘务交路的接续顺序和休息时间，以减少计划总接续时间，进而压缩所需司机人数，就成为乘务排班计划编制过程中的关键目标。

理想情况下，倘若计划开始时所有司机均处于相同状态，则安排哪名司机从循环中的哪项任务开始执行并无实质差异。但在实际情况中，司机的初始状态往往受到旧计划的影响，在新计划开始时通常是不同的。因此，司机与任务之间的匹配情况会直接影响计划的交替质量。图1展示了新旧计划交替的简单示例，其中R1—R3表示不同乘务交路；为了更清晰地描述司机每日担当的具体任务内容，将图1中的多日交路以“d”为单位进行拆分，例如，将2日交路R3分为R3-1（第1天）和R3-2（第2天），即2个单日任务。

在图示方案中，司机在旧计划与新计划中均按照单一循环模式轮流执行任务，在1个完整周期（5 d）担当任务完全相同；然而该方案并未考虑司机在计划交替时所处位置以及担当任务情况上的差异，导致在计划过渡阶段存在诸多问题。如，司机1在计划交替前后连续担当2日交路，频繁在外段过夜，从人性化角度应尽量减少此类情况发生；司机2在旧计划最后1天完成R3-1任务后位于C站，在新计划第1天需要担当由A站出发的交路任务R2'，造成便乘；类似地，司机5在计划交替阶段也需进行便乘。上述情况都会对计划的连贯性和司机的工作状态产生负面影响，因此在编制乘务排班计划时，应充分考虑新旧计划交替情况，合理安排哪名司机从新计划循环中的哪项任务开始执行。

2 优化策略

新旧计划交替本质上是确定司机与任务之间的匹配关系，在新计划的乘务交路循环确定之后才能进行优化；而乘务交路循环侧重于乘务交路之间的接续关系。两者的制定、优化主体并不相同。同时，新计划制定的首要目标是获得总接续时间最小的乘务交路循环，不能因追求新旧计划交替质量而反向影响乘务交路循环的结果。基于以上原因，考虑采取2阶段优化策略，先求解出新计划中的乘务交路循环，再制定任务指派方案，从而实现对高铁司机乘务排班计划的优化。

第1阶段优化目标是获得总接续时间最小并且冗余接续时间相对均衡的乘务交路循环。一般来说，接续时间越少，计划排班周期、所需司机数量就越少；冗余接续时间越均衡，司机每日的休息时间就越均衡，有助于进一步提升计划质量。第1阶段的输入数据为乘务交路信息。

第2阶段旨在减少新旧计划交替对司机运用造成的影响，合理指派司机从循环中哪项任务开始执行。便乘会对乘务资源利用效率产生巨大影响，在计划中应尽量避免，因此将便乘次数最少作为该阶段的主要优化目标；为获得更优的计划方案，进一步将便乘时间以及其他人性化因素量化为计划交替费用，作为次要优化目标。第2阶段的输入数据包括新计划的乘务交路循环方案即第1阶段的优化结果，以及在旧计划结束时的司机信息。

针对上述2个阶段的需求构造整数规划模型，并利用商业求解器求解。

2.1　第1阶段模型

2.1.1　符号定义

J为乘务交路集合，i，j为索引，i,j\in J；t_{ij}为乘务交路i与乘务交路j的接续时间，min；t_{ij}^{\mathrm{R}\mathrm{e}\mathrm{d}}为乘务交路i与乘务交路j的冗余接续时间，min；t_{\mathrm{A}\mathrm{v}\mathrm{g}}为平均冗余接续时间，min；n为乘务交路数量；s_i^{\mathrm{A}\mathrm{r}\mathrm{r}}为乘务交路i的终到站；s_j^{\mathrm{D}\mathrm{e}\mathrm{p}}为乘务交路j的始发站；t_{ij}^{\mathrm{B}\mathrm{a}\mathrm{s}}为乘务交路i和乘务交路j之间的基础接续时间，min；T_j^{\mathrm{D}\mathrm{e}\mathrm{p}}为乘务交路j的出发时刻；T_i^{\mathrm{A}\mathrm{r}\mathrm{r}}为乘务交路i的到达时刻；t_{ij}^{\mathrm{N}\mathrm{o}\mathrm{r}}为考虑正常接续时间标准下乘务交路i和乘务交路j之间的接续时间，min；T_{\mathrm{S}\mathrm{t}\mathrm{a}}为乘务交路间的接续时间标准，min；T_{\mathrm{N}\mathrm{o}\mathrm{r}}为正常接续时间标准，表示未安排大休情况下，允许接续的最小时间，min；T_{\mathrm{R}\mathrm{s}\mathrm{t}}为安排大休时乘务交路间的接续时间标准，min；N_{\mathrm{R}\mathrm{s}\mathrm{t}}为计划周期中大休的次数；x_{ij}为表示乘务交路i与乘务交路j接续情况的0-1变量，若两交路接续则取值为1，否则取值为0；y_{ij}为表示乘务交路i与乘务交路j之间大休安排情况的0-1变量，若安排大休则取值为1，否则取值为0。

2.1.2　目标函数

第1阶段优化目标分为2项：以乘务交路总接续时间最小为主要优化目标，以冗余接续时间均衡为次要优化目标。由此得到目标函数Z₁为

Z_{\mathrm{1}}=\mathrm{m}\mathrm{i}\mathrm{n}\left({\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{j=\mathrm{1}}^n}{t}_{ij}{x}_{ij}+\epsilon \sqrt[]{{\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{j=\mathrm{1}}^n}{x}_{ij}(t_{ij}^{\mathrm{R}\mathrm{e}\mathrm{d}}-t_{\mathrm{A}\mathrm{v}\mathrm{g}}{)}^{\mathrm{2}}/n}\right)（1）

其中，

t_{ij}^{\mathrm{R}\mathrm{e}\mathrm{d}}=t_{ij}-T_{\mathrm{S}\mathrm{t}\mathrm{a}}

t_{\mathrm{A}\mathrm{v}\mathrm{g}}={\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{j=\mathrm{1}}^n}{x}_{ij}{t}_{ij}^{\mathrm{R}\mathrm{e}\mathrm{d}}/n

式中：\epsilon为权重系数，保证在总接续时间最小的情况下，对冗余接续时间不同的方案进行择优；\sqrt[]{{\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{j=\mathrm{1}}^n}{x}_{ij}(t_{ij}^{\mathrm{R}\mathrm{e}\mathrm{d}}-t_{\mathrm{A}\mathrm{v}\mathrm{g}}{)}^{\mathrm{2}}/n}为冗余接续时间的标准差，用于衡量其分布的均衡性。

2.1.3　约束条件

为确保乘务交路之间能够合理接续，并满足司机的大休要求，建立以下约束条件。

式（2）和式（3）分别为紧前紧后约束，限制每个乘务交路有且仅有1个紧前交路和1个紧后交路与之接续。

{\displaystyle \sum _{i=\mathrm{1}}^n}{x}_{ij}=\mathrm{1}j=\mathrm{1,2}\dots ,n（2）

{\displaystyle \sum _{j=\mathrm{1}}^n}{x}_{ij}=\mathrm{1}i=\mathrm{1,2}\dots ,n（3）

式（4）为地点接续约束。当乘务交路i的终到站s_i^{\mathrm{A}\mathrm{r}\mathrm{r}}与乘务交路j的始发站s_j^{\mathrm{D}\mathrm{e}\mathrm{p}}相同时，两者才可接续。

x_{ij}\left(s_i^{\mathrm{A}\mathrm{r}\mathrm{r}}-s_j^{\mathrm{D}\mathrm{e}\mathrm{p}}\right)=\mathrm{0}i,j=\mathrm{1,2}\dots ,n（4）

由于乘务交路以“d”为单位，因此只能次日接续。同时，需避免同一交路自我接续。在不考虑接续时间标准以及大休安排的情况下，乘务交路之间的基础接续时间t_{ij}^{\mathrm{B}\mathrm{a}\mathrm{s}}的计算方法如式（5）所示。为了便于计算，以0点为基准将时刻转化为分钟，如8：00可转换为480 min。

\begin{array}{l}{t}_{ij}^{\mathrm{B}\mathrm{a}\mathrm{s}}=\left\{\begin{array}{ll}\mathrm{1}\mathrm{440}+T_j^{\mathrm{D}\mathrm{e}\mathrm{p}}-T_i^{\mathrm{A}\mathrm{r}\mathrm{r}}& i\ne j\\ \mathrm{\infty }& i=j\end{array}\right.\\ i,j=\mathrm{1,2}\dots ,n\end{array}（5）

当基础接续时间不满足正常接续时间标准T_{\mathrm{N}\mathrm{o}\mathrm{r}}（未安排大休情况下允许接续的最小时间）时，需在基础接续时间上增加1 440 min（即增加1 d），将交路接续顺延至下一日进行。考虑正常接续时间标准下的接续时间t_{ij}^{\mathrm{N}\mathrm{o}\mathrm{r}}的计算方法如式（6）所示。

（6）

在现场实际中，高铁司机每月需安排1~2次时长在48~72 h的大休，休息时间自退勤开始计算，至再次出勤结束。式（7）为大休安排约束，限制只能在相互接续的乘务交路间安排大休。

y_{ij}\le x_{ij}i,j=\mathrm{1,2}\dots ,n（7）

式（8）规定了1个计划周期中大休的次数N_{\mathrm{R}\mathrm{s}\mathrm{t}}，该数值可根据现场实际需求设置。

{\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{j=\mathrm{1}}^n}{y}_{ij}=N_{\mathrm{R}\mathrm{s}\mathrm{t}}（8）

为了充分利用司机资源并压缩排班周期，计划编制人员在安排大休时会尽可能贴近大休时间下限48 h。然而，既有研究普遍采取以“d”为单位的大休安排方式，在2个乘务交路之间插入2个自然日（从0点至24点为1个自然日），而忽略司机从上一交路退勤至当日24点以及下一交路值乘当日0点至出勤前的这段休息时间。为了更加贴近实际并进一步压缩接续时间，提出1种优化大休安排方式：计划安排大休时以“min”而非“d”为单位，以便从上一交路的退勤时间开始计算大休时间。图2展示了2种大休安排方式在不同情况下的对比。

图2（a）为前续交路到达时刻T_i^{\mathrm{A}\mathrm{r}\mathrm{r}}不大于后续交路出发时刻T_j^{\mathrm{D}\mathrm{e}\mathrm{p}}的情况示例，此时R1的到达时刻与R2的出发时刻均为14：30，按照优化大休安排方式，乘务交路间的接续时间将少于传统方式，形成的节省时间等于传统方式下产生的冗余接续时间之和，恰好为1 d。因此，计划所需的时间减少1 d，完成计划所需的司机数量也相应减少1名。图2（b）展示了前续交路到达时刻T_i^{\mathrm{A}\mathrm{r}\mathrm{r}}大于后续交路出发时刻T_j^{\mathrm{D}\mathrm{e}\mathrm{p}}的情况，此时R3到达时刻为18：00，R4的出发时刻为10：00，2种方法下的接续时间相等，产生的冗余接续时间也相等。综上，相较于传统大休安排方式，优化大休安排方式具有进一步减少接续时间的潜力。

优化大休安排方式下的乘务交路间接续时间t_{ij}的计算方法，如式（9）所示。

i,j=\mathrm{1,2}\dots ,n（9）

式（10）用于判断接续时间标准T_{\mathrm{S}\mathrm{t}\mathrm{a}}的取值。

T_{\mathrm{S}\mathrm{t}\mathrm{a}}=\left\{\begin{array}{cc}{T}_{\mathrm{N}\mathrm{o}\mathrm{r}}& y_{ij}=\mathrm{0}\\ T_{\mathrm{R}\mathrm{s}\mathrm{t}}& y_{ij}=\mathrm{1}\end{array}\right.i,j=\mathrm{1,2}\dots ,n（10）

为保证乘务交路循环的完整性，引入式（11）和式（12）以消除不覆盖所有交路的局部闭合子循环。

\begin{array}{l}{u}_i-u_j+n{x}_{ij}\le n-\mathrm{1}i=\mathrm{1},\cdots ,n,\\ j=\mathrm{2},\cdots ,n,i\ne j\end{array}（11）

u_i\ge \mathrm{0}i=\mathrm{1}\cdots ,n（12）

式中：u_i为用于构造约束条件而引入的辅助变量，仅在数学推导和约束条件的设定过程中起作用，并不具备实际意义^［20］。

式（13）为变量的取值范围约束。

x_{ij},y_{ij}\in \{\mathrm{0,1}\}i,j=\mathrm{1,2},\cdots ,n（13）

2.2　第2阶段模型

第2阶段模型是在第1阶段模型求得的乘务交路循环基础上，进一步确定司机担当的具体任务，以及进入循环的具体位置。其本质是1个复杂的指派问题，因此构建新旧计划交替模型对问题进行描述。

2.2.1　符号定义

P为司机集合，p为索引，p\in P；Q为任务集合，包括交路任务和大休任务，q和k均为索引，q，k\in Q；R （q）为任务q的交路段集合，r\in R （q）；c_{pq}^{\mathrm{B}}和c_{pq}^{\mathrm{F}}分别为司机p担当任务q时产生的便乘费用和疲劳费用；T_q^{\mathrm{D}\mathrm{e}\mathrm{p}}和T_q^{\mathrm{A}\mathrm{r}\mathrm{r}}分别为任务q的出发时刻和到达时刻；T_{qr}^{\mathrm{D}\mathrm{e}\mathrm{p}}和T_{qr}^{\mathrm{A}\mathrm{r}\mathrm{r}}分别为任务q中交路段r的出发时刻和到达时刻；T_{\mathrm{T}\mathrm{r}\mathrm{a}}为换乘时间标准，min；l_p为司机p所处位置；s_q^{\mathrm{D}\mathrm{e}\mathrm{p}}和s_q^{\mathrm{A}\mathrm{r}\mathrm{r}}分别为任务q的始发站和终到站；s_{qr}^{\mathrm{D}\mathrm{e}\mathrm{p}}和s_{qr}^{\mathrm{A}\mathrm{r}\mathrm{r}}分别为任务q中交路段r的始发站和终到站；T_p^{\mathrm{O}\mathrm{l}\mathrm{d}}为司机p在旧计划中最后1项任务的到达时刻；s_{\mathrm{B}\mathrm{a}\mathrm{s}}为乘务基地位置；T_{\mathrm{R}\mathrm{s}\mathrm{t}}为大休间隔时间标准，d；T_p^{\mathrm{L}\mathrm{r}\mathrm{s}}为司机p上次大休距离新计划开始的时间，d；T_q^{\mathrm{N}\mathrm{r}\mathrm{s}}为以任务q为新计划担当的第1项任务时，下次大休距离新计划开始的时间，d；F_p^{\mathrm{O}\mathrm{l}\mathrm{d}}为司机p在旧计划结束时的疲劳指数，F_q^{\mathrm{N}\mathrm{e}\mathrm{w}}为任务q的疲劳指数，此类指数反映任务的交路类型（单日交路或多日交路）及多日交路的持续时间；b_{pqr}为司机p便乘情况的0-1变量，当其便乘任务q的交路段r时取值为1，否则取值为0；y_{pq}为司机p担当任务情况的0-1变量，若其担当任务q则取值为1，否则取值为0；v_q为判断任务q是否为大休任务的参数，若为大休任务则取值为1，否则取值为0。

2.2.2　目标函数

为提高新旧计划交替的顺畅性，应尽量减少便乘情况的发生。在此基础上，还需考虑人性化需求，尽量避免司机在计划交替前后连续担当多日交路。此阶段模型的优化目标由2项构成，第1项用于保证计划的便乘次数最少，为模型的主要优化目标；第2项为次要优化目标，旨在减少计划交替产生的费用，这里的费用包括便乘费用以及与上述人性化需求相关的疲劳费用。由此得到目标函数Z₂为

Z_{\mathrm{2}}=\mathrm{m}\mathrm{i}\mathrm{n}\left(\sum _{p\in P}\sum _{q\in Q}\sum _{r\in R(q)}{b}_{pqr}+\sigma \sum _{p\in P}\sum _{q\in Q}({\mu }_{\mathrm{1}}{c}_{pq}^{\mathrm{B}}+{\mu }_{\mathrm{2}}{c}_{pq}^{\mathrm{F}})y_{pq}\right)（14）

式中：\sigma为权重系数，用来保证只在便乘次数达到最小值时，选择计划交替费用相对较小的方案；{\mu }_{\mathrm{1}}和{\mu }_{\mathrm{2}}均为量纲转换参数，可以根据现场实际需要进行设置。

2.2.3　约束条件

在计划交替过程中，司机的任务匹配、便乘交路接续及大休安排等需符合乘务规则与实际情况，因此建立如下约束条件。

式（15）和式（16）为司机任务匹配约束，保证了1个司机只能担当1项任务；1项任务也只能由1个司机担当。

\sum _{p\in P}{y}_{pq}=\mathrm{1}q\in Q（15）

\sum _{q\in Q}{y}_{pq}=\mathrm{1}p\in P（16）

式（17）为便乘担当唯一性约束，要求司机不能同时便乘和担当同一任务。

b_{pqr}{y}_{pq}=\mathrm{0}p\in P,q\in Q,r\in R(q)（17）

式（18）为便乘时间接续约束。该式要求司机便乘任务的到达时刻与换乘时间之和不大于实际担当任务的出发时刻。

\begin{array}{l}{b}_{pqr}{y}_{pk}(T_{qr}^{\mathrm{A}\mathrm{r}\mathrm{r}}+T_{\mathrm{T}\mathrm{r}\mathrm{a}}-T_k^{\mathrm{D}\mathrm{e}\mathrm{p}})\le \mathrm{0}p\in P,q,k\in Q,\\ r\in R(q),q\ne k\end{array}（18）

式（19）为便乘地点接续约束。该式要求司机便乘交路段的始发站必须与其初始位置相同。

b_{pqr}(s_p-s_{qr}^{\mathrm{D}\mathrm{e}\mathrm{p}})=\mathrm{0}p\in P,q\in Q,r\in R(q)（19）

式（20）要求司机完成便乘后的地点与实际担当任务的始发站必须相同。

\begin{array}{l}{b}_{pqr}{y}_{pk}(s_{qr}^{\mathrm{A}\mathrm{r}\mathrm{r}}-s_k^{\mathrm{D}\mathrm{e}\mathrm{p}})=\mathrm{0}p\in P,q,k\in Q,\\ r\in R(q),q\ne k\end{array}（20）

式（21）为司机任务匹配时间约束。司机在旧计划中最后1项任务与新计划中第1项任务之间应满足接续时间标准。

\begin{array}{l}{y}_{pq}(\mathrm{1}-v_q)(T_q^{\mathrm{D}\mathrm{e}\mathrm{p}}-T_p^{\mathrm{O}\mathrm{l}\mathrm{d}}+\mathrm{1}\mathrm{440}-T_{\mathrm{N}\mathrm{o}\mathrm{r}})\ge \mathrm{0}\\ p\in P,q\in Q\end{array}（21）

式（22）为司机任务匹配大休约束。对于在新计划第1天进行大休的司机p，所处位置必须为乘务基地。

y_{pq}{v}_q(s_p-s_{\mathrm{B}\mathrm{a}\mathrm{s}})=\mathrm{0}p\in P,q\in Q（22）

在现实情况中，计划的排班周期通常在十至数十天不等，若忽略司机计划交替前后2次大休的时间间隔，将可能违反乘务规则中司机每30 d至少进行1次大休的要求。为保证司机不错过大休，设置以下大休间隔约束如式（23）所示。

y_{pq}[T_{\mathrm{R}\mathrm{s}\mathrm{t}}-(T_p^{\mathrm{L}\mathrm{r}\mathrm{s}}+T_q^{\mathrm{N}\mathrm{r}\mathrm{s}})]\ge \mathrm{0}p\in P,q\in Q（23）

式（24）为便乘费用计算式，将便乘任务出发时刻与担当任务出发时刻之间的时间作为便乘所产生的费用。

\begin{array}{l}{c}_{pq}^{\mathrm{B}}=\sum _{q\in Q}\sum _{r\in R(q)}{b}_{pqr}{x}_{pk}(T_k^{\mathrm{D}\mathrm{e}\mathrm{p}}-T_{qr}^{\mathrm{D}\mathrm{e}\mathrm{p}})p\in P,\\ k\in Q,k\ne q\end{array}（24）

根据现场编制人员工作经验，在新旧计划交替时，应尽量避免司机连续担当多日交路情况发生，以防止司机在计划衔接段过于疲劳。设定疲劳指数以反映司机担当的任务类型（单日交路或多日交路），并体现多日交路的持续时间。疲劳指数越大，表示司机的疲劳程度越高。具体设定如下。

（1）若旧计划中司机执行的最后1项任务为单日交路，则F_p^{\mathrm{O}\mathrm{l}\mathrm{d}}=\mathrm{0}。若为多日交路，F_p^{\mathrm{O}\mathrm{l}\mathrm{d}}则根据该任务在交路中的第几天赋值，以反映司机在旧计划结束时已连续担当该多日交路的时间，即当任务为多日交路的第m天时F_p^{\mathrm{O}\mathrm{l}\mathrm{d}}=m。

（2）若新计划中的任务为单日交路，则F_q^{\mathrm{N}\mathrm{e}\mathrm{w}}=\mathrm{0}。若为多日交路，F_q^{\mathrm{N}\mathrm{e}\mathrm{w}}则按照以下规则取值：当任务为多日交路的最后1天任务时F_q^{\mathrm{N}\mathrm{e}\mathrm{w}}=\mathrm{0}，此时，该任务虽然为多日交路，但司机实际只需担当1 d，疲劳情况等同于完成1个单日交路；若为持续时间为m d的多日交路的第1天任务，则F_q^{\mathrm{N}\mathrm{e}\mathrm{w}}=m；若为多日交路第h天的任务且h\ne\mathrm{1}\ne m，则F_q^{\mathrm{N}\mathrm{e}\mathrm{w}}=m-h+\mathrm{1}。

式（25）为疲劳费用计算式。

c_{pq}^{\mathrm{F}}=F_p^{\mathrm{O}\mathrm{l}\mathrm{d}}{F}_q^{\mathrm{N}\mathrm{e}\mathrm{w}}p\in P,q\in Q（25）

式（26）为变量的取值范围约束。

y_{pq},b_{pqr}\in \{\mathrm{0,1}\}p\in P,q\in Q,r\in R(q)（26）

3 案例研究

为了验证模型的应用效果，以南昌铁路局集团有限公司（以下简称“南昌局”）担当杭长高铁乘务的某动车车队为背景进行案例研究。该车队以南昌西站为乘务基地，以杭州东站、长沙南站为换乘站并设乘务人员公寓。案例中每个乘务交路都将由南昌西站始发，并最终返回该站，图3为杭长高铁示意图。

表1展示了该车队需担当的乘务交路信息，共计16项任务，包括4个2日交路和1个3日交路。最早开始的乘务交路为R04，始发时刻为8：00；最晚结束的乘务交路为R10，终到时刻为22：13。

根据乘务规则，设置以下参数：乘务交路间的正常接续时间标准为960 min，安排大休时的接续时间标准为2 880 min；考虑乘务交路数量，计划期内安排1次大休。将以上参数和表1数据代入第1阶段模型，并在搭载Intel（R）Core（TM）m7-6Y75 CPU @ 1.20 GHz和8 GB内存的笔记本电脑上，运用pycharm2021.1.3调用Gurobi 9.5.2进行求解。耗时580 s得到最优解，最优目标函数值为18 868.49 min。其中，总接续时间为18 819 min，冗余时间标准差为49.49 min。计算得到的乘务交路接续顺序以及大休安排如图4所示。图中：交路按顺时针方向进行接续；灰色、黄色和红色线段分别表示接续时间、大休时间和冗余接续时间；线段长短反映时间在数值上的大小。

对图4进行分析发现，大休时间以及接续时间均满足相应时间标准，同时冗余接续时间占比较少，分布较为均衡，体现了计划的合理性；按照模型中的优化大休安排方式在R01与R13之间安排的大休，有效降低了整个计划的接续时间。

图5展示了2种大休安排方式下的情况对比。由图5可知，相比以“d”为单位插入大休的传统大休安排方式，优化方式下的接续时间减少了1 440 min，整个计划周期缩短1 d，完成计划所需的司机也相应减少1名。

根据第1阶段获得的乘务交路循环，可在第2阶段进一步确定司机与具体任务间的匹配关系，以实现新旧计划的良好过渡。表2展示了乘务交路循环下的新计划任务信息，具体包含22个单日任务和1次大休，计划周期为23 d，相应需要配置23名司机。

为了在乘务排班计划中综合考虑便乘、大休间隔和疲劳费用等众多因素，还需知道司机在新计划开始前的状态。表3提供了旧计划结束时司机信息。具体而言，在旧计划结束时，每个司机所处的位置有所差异，任务的终到时刻、疲劳指数以及距离上1次大休的时间都不相同，这些数据将为司机从新计划乘务交路循环中的哪项任务开始执行提供依据。

结合现场实际情况对参数取值，\sigma =\mathrm{0.000}\mathrm{1}、{\mu }_{\mathrm{1}}=\mathrm{1}、{\mu }_{\mathrm{2}}=\mathrm{100}，换乘时间标准为60 min。在与第1阶段相同配置环境下，利用Gurobi对第2阶段模型进行求解。将表2和表3中的数据及参数代入模型后，共得到37 283个约束条件以及6 809个变量，耗时73 s求得最优解。最优解的目标函数值为2.076 7，其中便乘次数为2，计划交替费用为767。计算得到的乘务排班计划的计划周期为23 d，每1天计划司机均执行不同的任务，直至第24天进入该计划的新1轮任务循环周期；便乘交路只发生在新旧计划交替时，即新计划的第1天，后续计划执行中不再需要便乘。以司机C03和C02为例，第1天C03执行1号任务，包括便乘交路R16-3 （1）以及担当交路R01 （1）和R01 （2）；C02执行2号任务，在乘务基地休息。第2天C03执行2号任务（休息），C02执行3号任务，担当交路R13-1 （1），以此类推。该乘务排班计划第1天的司机任务安排如图6所示。分析图6可知：乘务排班计划第1天共发生2次便乘，分别为司机C03从长沙南便乘R16-3 （1）到达南昌西以及司机C11从南昌西便乘R06 （1）到达杭州东，相应产生的便乘费用为250和317。结合表2中任务的始发站信息和表3中司机位置信息可知：新计划中每天从南昌西、长沙南和杭州东出发的乘务交路任务分别为17，3和3条，而在旧计划结束时，处在南昌西、长沙南和杭州东的司机分别为17，4和2名，因此必然产生司机便乘的情况；在理想情况下，只需令1名位于长沙南的司机便乘前往杭州东即可，然而受限于司机前后担当交路之间、便乘交路与担当交路之间的接续时间要求，这种理想情况并不可行，实际中至少需要2名司机进行便乘。

为了进一步说明上述乘务排班计划的合理性，从人性化角度对计划安排进行分析。表4展现了司机在新旧计划交替前后担当乘务交路所对应的疲劳费用以及大休情况，可以看出计划尽可能避免了司机在计划交替前后连续担当多日交路的情况。例如，对于在旧计划结束时刚担当完2日交路的司机C04，安排其在新计划第1天担当1个单日交路，而将新计划中的3日交路安排给在旧计划最后1日担当单日交路的司机C17；在旧计划最后1天，司机C08担当了1个2日交路第1天的任务并在任务结束时位于杭州东，为了避免发生便乘，在新计划开始时，安排其值乘从杭州东出发的乘务交路R16-2，因此相对于其他司机疲劳费用为0，司机C08的疲劳费用为2。此外，司机在计划交替前后2次大休的时间间隔最大为30 d，不存在因计划交替而在规定时间内未进行大休的情况，并且在后续计划中，每个司机的大休间隔时间都与计划周期相同，为23 d，符合乘务规则中高铁司机每月应有1~2次大休的要求。

4 结语

本文结合现场实际，提出了2阶段优化策略，对高铁司机乘务排班计划进行优化。在第1阶段以总接续时间最小和冗余接续时间均衡为目标构建模型，确定新计划中乘务交路的接续顺序以及大休安排；接着，在第2阶段以便乘次数最少和计划交替费用最小为目标构建模型，确定司机从循环中哪项任务开始执行。以南昌局某动车车队数据为背景，进行案例研究。相较传统方法，第1阶段模型能够进一步减少乘务交路循环的接续时间，计划周期缩短1 d，完成计划所需的司机相应减少1名。第2阶段模型能够有效控制计划交替产生的影响，在计划必然产生便乘的情况下，新旧计划交替期间仅产生2次便乘，仅有1名司机在计划交替前后连续担当多日交路且无司机错过大休。综上，本文所建模型能够为实际生产中的高铁司机乘务排班计划编制提供参考，以提高计划的编制效率和实施质量。

高铁司机乘务排班计划编制是1个复杂的组合优化问题。随着问题中乘务交路数量以及司机数量的增加，商业求解器的计算时间将大幅延长。未来，还需设计更加高效的求解算法以应对更大规模的问题求解。

参考文献

[1] 赵鹏.高速铁路动车组和乘务员运用的研究［D］.北京：北京交通大学，1998.

[2] ZHAO Peng. Research on the Application of High-Speed Railway EMU and Crew ［D］. Beijing： Beijing Jiaotong University， 1998. in Chinese

[3] 褚飞跃，田志强，倪少权.高速铁路单循环乘务排班计划编制模型与算法［J］.铁道学报，2012，34（7）：1-9.

[4] CHU Feiyue， TIAN Zhiqiang， NI Shaoquan. Model and Algorithm for Formulation of the Single Cycle Crew Rostering Plans of High-Speed Railways ［J］. Journal of the China Railway Society， 2012， 34 （7）： 1-9. in Chinese

[5] 王东先，孟学雷，何国强，等.基于改进蚁群算法的铁路乘务排班计划编制［J］.计算机应用，2019，39（12）：3678-3684.

[6] WANG Dongxian， MENG Xuelei， HE Guoqiang， et al. Railway Crew Rostering Plan Based on Improved Ant Colony Optimization Algorithm ［J］. Journal of Computer Applications， 2019， 39 （12）： 3678-3684. in Chinese

[7] 王东先，孟学雷，乔俊，等.基于改进蚁群算法的铁路乘务交路计划的编制［J］.计算机应用，2019，39（9）：2749-2756.

[8] WANG Dongxian， MENG Xuelei， QIAO Jun， et al. Railway Crew Routing Plan Based on Improved Ant Colony Algorithm ［J］. Journal of Computer Applications， 2019， 39 （9）： 2749-2756. in Chinese

[9] 杨国元，史天运，张秋亮.铁路客运乘务排班计划编制模型及算法［J］.交通运输系统工程与信息，2016，16（4）：159-164.

[10] YANG Guoyuan， SHI Tianyun， ZHANG Qiuliang. Model and Algorithm for Railway Passenger Crew Rostering Plan ［J］. Journal of Transportation Systems Engineering and Information Technology， 2016， 16 （4）： 159-164. in Chinese

[11] SATO T， SAKIKAWA S， MORITA T， et al. Crew and Vehicle Rescheduling Based on a Network Flow Model and Its Application to a Railway Train Operation ［J］. IAENG International Journal of Applied Mathematics， 2009， 39 （3）： 142-150.

[12] 符卓，袁雪莹.高速动车组乘务交路辅助编制系统研究［J］.铁道运输与经济，2019，41（8）：18-21，42.

[13] FU Zhuo， YUAN Xueying. A Research on High-Speed EMU Crew Schedule Auxiliary Preparation System ［J］. Railway Transport and Economy， 2019， 41 （8）： 18-21， 42. in Chinese

[14] 符卓，袁雪莹，车瑶.高速动车组司机乘务交路优化编制方法［J］.铁道学报，2020，42（7）：24-33.

[15] FU Zhuo， YUAN Xueying， CHE Yao. Optimization Method for High-Speed Electric Multiple Unit Crew Scheduling ［J］. Journal of the China Railway Society， 2020， 42 （7）： 24-33. in Chinese

[16] WALKER C G， SNOWDON J N， RYAN D M. Simultaneous Disruption Recovery of a Train Timetable and Crew Roster in Real Time ［J］. Computers & Operations Research， 2005， 32 （8）： 2077-2094.

[17] 孙宏，杜文.飞机排班数学规划模型［J］.交通运输工程学报，2004，4（3）：117-120.

[18] SUN Hong， DU Wen. Mathematical Programming Model of Aircraft Assignment ［J］. Journal of Traffic and Transportation Engineering， 2004， 4 （3）： 117-120. in Chinese

[19] SURAWEERA P， WEBB G I， EVANS I， et al. Learning Crew Scheduling Constraints from Historical Schedules ［J］. Transportation Research Part C： Emerging Technologies， 2013， 26： 214-232.

[20] MESQUITA M， MOZ M， PAIAS A， et al. A Decompose-and-Fix Heuristic Based on Multi-Commodity Flow Models for Driver Rostering with Days-off Pattern ［J］. European Journal of Operational Research， 2015， 245 （2）： 423-437.

[21] CIANCIO C， LAGANÀ D， MUSMANNO R， et al. An Integrated Algorithm for Shift Scheduling Problems for Local Public Transport Companies ［J］. Omega， 2018， 75： 139-153.

[22] 陈明明，牛惠民.多车场公交乘务排班问题优化［J］.交通运输系统工程与信息，2013，13（5）：159-166.

[23] CHEN Mingming， NIU Huimin. An Optimization Model for Bus Crew Scheduling with Multiple Depots ［J］. Journal of Transportation Systems Engineering and Information Technology， 2013， 13 （5）： 159-166. in Chinese

[24] 陈明明，牛惠民.带时间窗的多车场公交乘务排班优化［J］.兰州交通大学学报，2015，34（4）：100-106.

[25] CHEN Mingming， NIU Huimin. An Optimization for Bus Crew Scheduling with Multiple Depots under Time Window Condition ［J］. Journal of Lanzhou Jiaotong University， 2015， 34 （4）： 100-106. in Chinese

[26] 金华，陈绍宽，王志美，等.基于地铁乘务资源共享的排班计划优化方法［J］.交通运输系统工程与信息，2021，21（2）：126-132.

[27] JIN Hua， CHEN Shaokuan， WANG Zhimei， et al. Crew Schedule Optimization for Urban Rail Transit with Crew Resources Sharing ［J］. Journal of Transportation Systems Engineering and Information Technology， 2021， 21 （2）： 126-132. in Chinese

[28] 许仲豪，杜鹏.基于列生成的城市轨道交通乘务计划优化编制方法研究［J］.铁道学报，2019，41（3）：25-32.

[29] XU Zhonghao， DU Peng. A Column Generation-Based Crew Scheduling Optimization Method for Urban Rail Transit ［J］. Journal of the China Railway Society， 2019， 41 （3）： 25-32. in Chinese

[30] 马亮，徐晓英.考虑便乘的地铁乘务任务配对的约束优化模型研究［J］.铁道学报，2021，43（3）：25-33.

[31] MA Liang， XU Xiaoying. Research on Constraint Optimization Model for Metro Crew Pairing Problem with Passenger Tasks ［J］. Journal of the China Railway Society， 2021， 43 （3）： 25-33. in Chinese

[32] 吕苗苗，倪少权.新旧列车运行图交替期客车车底运用方案的编制［J］.中国铁道科学，2013，34（4）：99-104.

[33] Miaomiao LÜ， NI Shaoquan. Passenger Train Stock Scheduling in Alternative Periods between the New Train Diagram and the Old One ［J］. China Railway Science， 2013， 34 （4）： 99-104. in Chinese

[34] 王继强.基于LINGO的旅行商问题的建模方法［J］.计算机工程与科学，2014，36（5）：947-950.

[35] WANG Jiqiang. LINGO-Based Modeling Methods for the Traveling Salesman Problem ［J］. Computer Engineering & Science， 2014， 36 （5）： 947-950. in Chinese

基金资助

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