基于工作强度均衡的地铁乘务轮班计划优化模型

陈绍宽，马卓然，彭小波，金 华，王志美

(1.北京交通大学城市交通复杂系统理论与技术教育部重点实验室，北京100044；2.中国铁路设计集团有限公司，天津300251)

0 引言

乘务轮班计划是指在乘务排班计划编制完成后，按照一定的规则，建立班次与乘务人员对应关系的过程.乘务轮班计划的质量不仅关系到运行图所制定的运输任务能否顺利完成，而且和运输人工成本密切关联，对运输企业的运营管理具有重要意义[1].

乘务轮班计划广泛应用于航空、铁路、地铁、公交等不同的运输行业部门.国内外学者针对其建模及求解算法开展了一系列的研究，例如，Dohn等将乘务轮班计划定义为一个广义的集合分割模型并使用分枝定价算法求解[2].Nishi等将乘务轮班计划分解为上层主问题与下层子问题，主问题的求解采用分枝定界算法[3].Lučic等构建了乘务轮班计划的多目标优化模型，求解时首先应用“飞行员连接飞行员”的启发式算法生成初始解，再采用模拟退火算法对初始解进行优化[4].Maenhout等采用禁忌搜索方法求解乘务计划问题[5].刘涛将乘务轮班计划构建为多层次均衡指派问题并设计了基于遗传算法的求解方法[6].Xie等将乘务计划问题转化为多商品流问题并采用商业软件CPLEX进行求解[7].彭小波[8]将乘务轮班计划问题的求解分为轮班划分和轮班分配两个阶段顺序求解，在轮班划分阶段不区分同类型的班次，轮班分配阶段将具体班次分配到划分阶段的结果中，可有效优化大规模乘务轮班计划.Sodhi等[9]曾在研究两阶段方法求解伦敦地铁乘务轮班问题时，证明了分阶段求解与一体化求解相比最优解的差距在2%之内，但可大幅度减少求解时间.因此，两阶段方法受到了较为广泛的应用[7-10].

基于上述研究，本文考虑实际生产工作中对乘务轮班计划的一般性约束，以工作强度均衡为目标构建乘务轮班问题的两阶段模型，并设计混合智能算法求解所构建的模型，为乘务轮班计划的编制与优化提供依据.

1 乘务轮班计划及其编制

地铁乘务轮班计划通常基于排班计划的结果，寻找覆盖所有班次的可行轮班模式来安排司机某天具体值乘的班次，其编制目标之一是实现司机工作量的均衡.单一循环模式是目前地铁运营实践中经常采用的一种手工编制方法，其核心思想是将所有班次按一定顺序由所有乘务员依次循环执行，乘务员在该类型的轮班计划中工作内容完全相同.循环周期长度等于所有班次和休息次数之和，当工作班数较多时，轮班计划的循环周期较长.

地铁运营组织中乘务工作班制复杂、乘务人员规模较大，导致单一轮班循环周期较长，因而在一定时间段内实现乘务员工作量均衡较为困难.本文提出基于周期循环的乘务轮班计划编制方法，采用基于循环“轮班单元”而非单个班次的形式获得轮班计划，如表1所示，其中M、D、N、R分别表示早班、白班、夜班、休息.表1中列表示1周7天，行表示轮班单元，即周数，每一周对应1位乘务员.同组的乘务人员采用相同的轮班单元计划，从不同的行(周数)开始执行.例如，表1中共有5个轮班单元，对应5位乘务人员.若轮班周期为30天，则第1位乘务员值乘的班次序列以轮班单元和班次表示为001-002-003-004-D-D，第2位乘务员为002-003-004-005-N-M，以此类推，第5位乘务员对应005-001-002-003-M-R.

表1 轮班单元计划Table 1 Unit rostering

采用引入“轮班单元”的周期循环模式时，大周期内乘务人员的工作安排是相同的，因此以“轮班单元”为单位考虑均衡度优化.通常从两个角度考虑均衡：一是从班次角度，对“轮班单元”的不同类型班次数和总班次数的均衡；二是从具体工作指标角度，对工作时间和驾驶时间的均衡.本文针对平日及双休乘务计划展开研究，轮班单元的长度选为7天，主要考虑以下的计划制定要素.

(R1)班次覆盖性.每一个班次均有乘务员值乘且每位乘务员每天最多值乘1个班次.

(R2)连续工作与休息时间限制.乘务人员连续工作与休息不能超过规定天数.考虑到夜班特殊性，连续值乘的夜班数量也不能超过规定值.

(R3)值乘模式约束.依据工作规章制度避免某种值乘序列出现，常见的为避免连续休息日中单独1天工作的班次连接，即避免“休息—工作—休息”的组合形式.

(R4)班次接续关系.连续两天规定班次间必须或避免存在的接续关系，例如考虑“夜—早同员”的制度.

(R5)间隔时间限制.乘务员连续两天值乘的班次间必须满足一定的时间间隔.

(R6)休息频率限制.总的休息天数占轮班周期长度的比例在限定范围内.

2 模型构建

在前述分析基础上以工作强度均衡为目标构建乘务轮班计划的两阶段优化模型.

2.1 轮班划分模型

轮班划分阶段获得确定班次类型的轮班单元计划，以乘务员值乘每类班次和休息的个数与均值的偏差表示工作强度的均衡程度，表示为乘务员值乘每类班次数量的标准差与总值乘班次数标准差的加权和.目标函数为

模型约束条件如式(2)～式(10)所示.

式中：L表示将全部轮班单元首尾相衔接形成的长链；Xjl,k表示若长链L特定位置jl为第k类班次则取1，否则取 0；Kn表示夜班班次的集合；Cd、Cr和Cn分别表示最长连续工作天数、最长连续休息天数和最长连续值乘夜班天数；ka和kb表示必须相连的两类班次，kc和kd表示避免相连的两类班次，ka,kb,kc,kd∈K；Rmin和Rmax分别表示轮班单元内休息日数量上、下限.

式(2)为由规则(R1)规定的覆盖约束，周期循环轮班计划需将轮班单元的首尾相连形成循环闭环，因此构造部分约束时需同时兼顾轮班单元内部和相互之间的衔接.式(3)表示变量间的对应关系.式(4)～式(6)对应规则(R2)，确保长链内部及首尾衔接处满足连续工作与休息时间约束.式(7)对应规则(R3)，避免班次序列中出现“休息—工作—休息”的接续方式.式(8)与(R4)对应式(9)与规则(R6)相关，确保轮班单元内的休息日数量在规定范围内.

2.2 轮班分配模型

轮班分配阶段分配具体的乘务班次.不同班次工作时间和驾驶时间之间存在差异且两者均为反映工作强度的重要指标.其中，工作时间指司机从出勤到退勤的时间，驾驶时间则指司机的在车时间.工作时间和驾驶时间的均衡程度分别用乘务员值乘各类班次的总工作时间标准差之和与总驾驶时间标准差之和表示，目标函数为

式中：λd和λt表示权重系数；q表示1天中的第q个班次；Qj为第j天的班次集合；Qj,k表示第j天第k类班次的集合；dj,q、tj,q、sj,q和ej,q分别表示第j天班次q的工作时间、驾驶时间、出勤时刻与退勤时刻；Averdk、Avertk分别对应轮班单元长度内第k类班次的人均工作时间和人均驾驶时间；yi,j,q为决策变量，若第i位乘务员在第j天值乘第q个班次则取1，否则为0.

模型约束条件如式(12)～式(15)所示.

式中：C表示连续值乘的两个班次间最小间隔时间；T表示1天的时间，即24 h.

式(12)是划分模型求解产生的匹配约束，在确定值乘班次类型后，该位置仅分配对应类型的具体班次；式(13)含义同式(3)；式(14)对应规则(R5)，连续值乘的两个班次间不小于最小间隔时间C.

3 求解算法

本文设计基于粒子群和模拟进化算法的混合算法对所建两阶段模型进行求解，该算法中粒子群算法可快速缩小解空间范围而模拟进化算法具有较强的局部搜索能力.

3.1 轮班划分模型求解算法

轮班划分模型求解算法的种群中每个粒子表示乘务计划的1个解，每个解可表示为一个Imax×Jmax的二维矩阵，矩阵内k表示班次类型，0表示休息.算法的适应度函数为，S表示粒子.

粒子群优化算法由初始化、粒子适应度评价、粒子状态更新、终止条件判断4个步骤组成，其中初始化和粒子状态更新2个步骤根据模型的特征进行相应改进.

(1)初始化.

初始种群构建时，依据覆盖性约束将每天各类班次随机分配给所有乘务员，未分配位置用0表示，此时二维矩阵的每一列均满足覆盖约束；再根据其他约束调整初始解时为保证覆盖约束不被破坏，仅允许在列上进行重排，禁止列与列之间的交换.

(2)更新粒子状态.

编码时粒子表示班次的序列，采用遗传算法交叉算子、变异算子及设计接续诱导算子来完成该步骤.

交叉算子采用当前粒子及其到目前为止的最优个体、该群体到目前为止的最优个体三者交叉，新生成的粒子随机包含这三者中某一片段，为维持覆盖约束，交叉时只允许相同位置列交叉互换；变异算子值按概率随机选取并打乱1天中班次顺序，当种群平均适应度值接近种群中最大适应度值时，突增变异概率以增加种群的多样性；接续诱导算子通过导向变异相关基因诱导种群中个体向更优的方向进化，具体为轮班单元内部在每次变异后，对任意相邻两天的班次进行调整，通过在列上交换位置满足班次接续关系约束；轮班单元衔接处通过深度优先算法调整轮班单元的顺序，使其首尾相连后满足班次的接续关系.

粒子群算法达到设定迭代次数后，将其最优解引入模拟进化算法中.评价个体与种群适应度时以每天轮班顺序的惩罚函数值作为个体适应度函数值.当满足所有约束时，惩罚函数值为0，个体的适应度为正无穷.个体重组从轮班的角度，为随机打乱1天或几天的班次，使其重新排列，同时加入诱导算子将重组的个体调整到可行.具体算法流程如图1所示.

3.2 轮班分配模型算法设计

轮班分配模型的求解算法步骤与轮班划分模型相似.编码时Imax×Jmax的二维矩阵内q表示具体班次，0表示休息.所有轮班单元中的每一个位置班次类型均固定，在加入动态变异算子与重组个体的过程中如需将1天内班次顺序打乱(即在列上进行重排)，则仅允许相同类型班次的顺序重新排列而禁止不同类型班次间的交换.算法流程如图2所示.

图1 轮班划分阶段算法流程图Fig.1 Algorithm flow chart of partition stage

4 案例研究

本文以北京地铁某线路平日及双休日运行计划为例，开展乘务轮班计划优化研究.该线路全长19.0 km，设13座车站.既有乘务计划班次类型共6种，各类班次数量如表2所示.

表2 平日及周末各类班次数量Table 2 Number of shifts on weekdays and weekends

该轮班计划是基于六班五运转的单一班制，按照“白—夜—早—休—夜—早”的单一循环模式编制而成.每日100个值乘班次(其中含8个休息补足班次)，20个休息班次.

(1)参数设置.

案例中共有120名乘务员，轮班单元长度为7，包含6种类型的班次，因此，Imax=120、Jmax=7、Kmax=6，aj,k取值根据表2获得，其余各参数如表3所示.考虑夜早同员，两者衔接即为最小间隔时间.

(2)模型求解.

种群规模设为100.轮班划分模型采用粒子群算法迭代1 500代，搜索到接近可行解后将结果引入模拟进化算法中，继续优化2×105代.最终适应度值收敛为0.23，目标函数值为4.31.轮班分配模型算法迭代次数与划分模型相同，适应度值收敛为2.91×10-3，目标函数为344.5 min.

图2 轮班分配阶段算法流程图Fig.2 Algorithm flow chart of allocation stage

表3 案例参数取值Table 3 Value of parameters

(3)工作强度均衡度分析.

案例中轮班单元长度为7天，取7天的既有轮班方案与模型优化结果进行对比分析.

①班次类型均衡程度.

既有轮班方案的班次类型均衡度与模型优化后结果如表4所示.

表4 班次类型均衡程度对比Table 4 Comparisons on the balance of shift types

由表4可知，各班次和休息的均衡度较既有方案分别优化了25.7%，32.4%、32.4%和21.3%，预备班次的均衡程度相同.优化模型的目标函数值较既有方案的5.35优化了19.4%，表明乘务员值乘各类班次数量差别更小，乘务员之间工作强度更加均衡.

②工作时间与驾驶时间均衡程度.

对比既有方案乘务员值乘各类班次工作时间、驾驶时间的标准差和模型优化结果，如图3所示.模型优化结果的各标准差均小于或等于既有方案，除预备班外，均有大幅度的优化.驾驶时间均衡程度的优化率均超过50%，轮班分配模型的目标函数值为344.5 min，较既有方案的650.3 min优化了47%.

图3 模型求解与既有方案对比Fig.3 Comparison between model solution and existing method

5 结论

在分析地铁乘务轮班计划实际需求基础上，提出基于“轮班单元”的周期循环乘务轮班计划优化方法.以乘务员工作强度均衡为目标构建轮班计划两阶段模型，设计了嵌套粒子群和模拟进化算法的混合智能算法对模型进行求解.通过案例研究，优化结果与既有轮班方案相比，两阶段优化模型的目标函数值分别改善了19.4%和47%，有效提高了乘务员间工作量均衡程度.本文研究成果适用于具有周期性规律的乘务轮班计划，主要考虑工作强度的均衡程度，未来研究还应进一步考虑线路运营组织(多交路、跨线运营等)、乘务员个性需求(如周末休息等)等影响因素及求解算法效率以满足大规模乘务计划优化的需要.