Crew Rostering Schedule Optimization for Urban Rail Transit Through Resource Sharing
-
摘要:
在城市轨道交通网络化运营条件下，实现乘务资源共享对优化资源配置、降低运营成本、提高网络运输效率具有重要意义. 首先，针对城市轨道交通系统既有固定班制轮班模式，将多线乘务资源共享引入乘务轮班计划编制，在传统单一线路轮班基础上考虑乘务员的跨线值乘和出退勤偏好需求，建立面向线网乘务轮班优化模型以实现区域线网乘务计划的协同优化；其次，根据乘务员对出退勤地点的偏好进行分组，在各组内进行独立的轮班优化，均衡所有乘务员轮班计划工作量；然后，基于班次工作时间、班次间衔接时间和早晚时段工作时间，提出定量化的“辛苦”指标衡量不同班次的工作负荷；最后，根据固定班制和乘务资源共享的特点设计改进的蜂群算法，通过改进初始解生成和迭代搜索机制以完成模型的高效求解。研究表明：引入乘务资源共享可促进乘务员工作量的均衡性，同时满足乘务员对出退勤地点的偏好需求，在既有城市轨道交通乘务轮班模式下提高乘务计划效率和乘务员满意度.
Abstract:Given the context of network-level operation conditions of urban rail transit, crew resource sharing is significant for resource allocation optimization, operation cost reduction, and transport efficiency improvement. Firstly, targeted at existing fixed rostering patterns in urban rail transit systems, crew resource sharing among various lines was applied to crew rostering schedules. By considering cross-line duty and attendance and departure preferences of the crew based on traditional single line rostering, a crew rostering optimization model was proposed to achieve coordinated optimization of crew schedules for regional line networks. Secondly, the crew was grouped according to preferences for attendance and departure locations, and crew rostering in the groups was optimized separately, so as to balance the workload for crew rostering schedules. A quantified index was brought up to evaluate the workload of different crew shifts according to the shift working time, connecting time between shifts, and working time in morning and evening hours. Finally, through an improved swarm algorithm based on the characteristics of fixed crew rostering patterns and crew resource sharing, the model was solved efficiently by improving initial solution generation and iterative search methods. The results show that crew resource sharing can improve the balance of the crew workload, accommodate the crew preferences for attendance and departure locations, and enhance crew schedule efficiency and crew satisfaction under the existing crew rostering patterns of urban rail transit.
-
Key words:
- urban rail transit /
- crew rostering schedule /
- fixed rostering pattern /
- resource sharing /
- balance
-
乘务计划是城市轨道交通系统运营计划的重要组成，决定了乘务人员的工作内容、强度与负荷[1]. 高质量的乘务计划可在提高轨道交通系统运转效率的同时满足乘务人员合理的偏好要求，特别在线网规模较大时，应考虑乘务员在轨道交通线网中的通勤过程和关于出退勤地点的差异性需求[2]. 城市轨道交通的快速发展以及逐步形成的规模化线网使得基于资源共享的运营组织技术与方法得到关注[3]. 已有部分研究在排班中考虑资源共享，可实现不同线路间的乘务员工作量均衡[4]或缩减乘务员规模[1,5-6]，然而，在轮班优化中考虑资源共享的研究尚不多见. 轮班优化是乘务计划的关键环节，决定了乘务员、班次以及时间的匹配关系. 在轮班计划中考虑乘务资源共享不仅有利于在更大时空范围内实现乘务人员和班次的精确匹配，也有利于满足乘务员更多的值乘偏好需求. 轮班模式是编制轮班计划的基础因素，主要包括循环轮班和非循环轮班[7]. 非循环轮班模式的约束条件较少，乘务员拥有不同的班次序列；在循环轮班模式下，所有乘务员按照一定循环机制共享所有的班次序列. 循环轮班模式可形成长期的轮班计划，保证了乘务员之间的工作量均衡，因其便于管理得到了广泛的实际应用.
大部分既有研究主要针对循环轮班模式展开，褚飞跃等[8]基于指派问题思路构建了适用于铁路周期循环轮班的优化模型. Xie等[9]构建了特殊的多商品流网络图模型，在仅进行小范围调整的条件下，可同时生成循环和非循环的轮班计划. 实现工作量均衡和满足乘务员偏好是乘务轮班既有研究的2个主要优化目标，但一般需要乘务排班的支持和协同[10]. Maenhout等[11]采用多种资源相较于标准值的偏离程度来衡量轮班计划的均衡性，同时，设定量化参数表示乘务员对不同班次的满意程度. Xie等[12]考虑了乘务员对不同时间班次或班次组合的偏好. 王骁[13]分析了乘务员对班次类型的偏好，并提出基于权重分配的偏好表示方法. 相较于循环轮班，非循环轮班具有更好的灵活性，可实现多种类型的乘务员偏好需求，如周末休息、连续双休等[14].
此外，还有部分研究对固定班制轮班模式展开建模与优化. 固定轮班具有严格的循环轮班属性，要求每个轮班单位执行的班次类型顺序一致，即应满足相同的轮班模式. 固定轮班便于对乘务员进行班组化和统一管理. 张增勇[15]分别考虑了固定班制轮班模式和一般周期循环轮班的城市轨道交通乘务员轮班优化方法，研究表明，固定班制轮班可实现较好的均衡性. 罗红双[16]构建了网络化下的固定班制轮班模型，以提高均衡性为目标展开轮班优化. 金华等[17]将固定班制下排班和轮班问题进行一体化建模，通过加入班次比例和备班限制，实现满足固定班制需求的乘务员规模最小化.
目前，仅有少部分研究考虑乘务资源共享下的轮班优化问题[4,16-17]，且主要针对非循环的轮班模式[18]. 由于固定班制轮班模式在城市轨道交通系统中广泛应用，本文将乘务资源共享引入固定班制下的轮班计划优化问题，以实现乘务员工作的均衡性和差异性偏好. 其中，固定班制可保证优化结果在实际中的可应用性，乘务资源共享可均衡不同线路间值乘任务工作量的差异，提高乘务资源利用效率. 相比于单线独立轮班优化，乘务资源共享允许乘务员跨线值乘，为乘务员提供更多的出退勤地点选择，满足乘务员就近出退勤的个性化需求，显著节省乘务员出退勤的通勤时间.
1. 固定班制下乘务资源共享对轮班计划的影响
1.1 固定班制轮班
乘务计划包括乘务排班和乘务轮班2个紧密相连的环节，乘务排班生成班次和值乘内容，决定了班次和乘务员的值乘关系. 在固定班制下，乘务员值乘的班次类型顺序是确定的，如图1所示的四班三运转班次为例，乘务员值乘的班次类型顺序为白班—晚班—早班—休息（休班）. 所有班次按照白（D）—晚（E）—早（M）—休（R）的顺序连接成一个班次循环并形成内环，相同数量的乘务员组成一个乘务员循环并作为外环，内外环的对应关系决定了每个乘务员值乘的班次. 除此之外，常见的固定班制类型还有六班五运转、三班两运转等.
图 1 基于四班三运转的轮班计划Figure 1. Crew rostering schedule based on four-team and three-shift pattern由图1可知，在四班三运转模式中，可将所有乘务员划分为4个乘务组，各乘务组值乘的班次顺序如表1所示. 同一乘务组在同一天值乘相同类型的班次，如乘务组1 （含乘务员1、5、9、13）在第1天均值乘白班（含D2、D3、D4、D1）. 为匹配固定班制的轮班需要，早班、白班和晚班的数量需保持一致，各乘务组的乘务员数量相同. 类似地，六班五运转模式下早班、白班和晚班的比例为2∶1∶2，更适用于具有早晚工作高峰特征的系统.
表 1 四班三运转下4个乘务组的轮班计划Table 1. Crew rostering schedule for four crew groups regarding four-team and three-shift pattern乘务组 第 1 天 第 2 天 第 3 天 第 4 天 第 5 天 第 6 天 … 1 E M R D E M … 2 M R D E M R 3 R D E M R D 4 D E M R D E 固定班制具有长期的循环特征，在完整的班次循环中所有乘务员工作量一致，可实现长期工作量的均衡. 但在班次规模庞大的情况下，较长的循环周期使得在分配班次时不仅要满足班次类型顺序要求，还需重点考虑短期的均衡性.
1.2 乘务资源共享对轮班计划的影响
受限于固定班制对班次类型顺序的限制，通常难以通过班次调整改善乘务员对班次类型的偏好需求，如希望周末双休等. 但乘务资源共享可实现跨线值乘，为满足乘务员对出退勤地点的偏好提供了改进空间. 如图2中绿线所示，分属于2条线路的乘务员可通过具有换乘功能的轮乘站C实现跨线值乘，配属于线路2的乘务员可在线路1的轮乘站A出退勤. 此时，配属于线路2的乘务员可根据个人偏好选择轮乘站A或B作为出退勤地点，以节省乘务员的通勤时间并提高乘务员的工作效率.
图 2 乘务资源共享下排班和轮班的关系Figure 2. Relationships between crew scheduling and rostering through resource sharing在乘务资源共享的条件下，除满足乘务员的出退勤地点个性化需求外，可将对单条线路的工作负荷均衡优化推广至多条线路，从而实现同一运营主体的若干线路间乘务员短期工作负荷均衡.
1.3 乘务资源共享下轮班和排班的关系
排班和轮班是乘务计划编制中2个相互关联的阶段，乘务资源共享对排班和轮班具有不同影响. 如图2中实线所示的排班阶段可实现不同线路工作需求的直接衔接，从而协同乘务员应对不同线路的工作高峰. 跨线值乘也提高了出退勤的灵活性，其作为乘务员选择不同出退勤地点的基础条件. 如虚线所示的轮班过程中需额外考虑出退勤地点的衔接，同时可将单线乘务员的工作负荷均衡应用到多条线路.
因此，各班次的工作负荷和出退勤地点在排班阶段生成，且应根据乘务员的偏好尽可能实现满足需求的班次集合[5]. 在轮班阶段，需要根据各班次的类型、工作负荷和出退勤地点进行合理安排，一方面，应提高不同线路乘务员的工作负荷均衡性；另一方面，应尽可能满足乘务员的偏好需求.
需要说明的是，虽然在排班阶段可考虑乘务员的出退勤偏好，但该个性化需求无法保证被全部满足. 因为在班次中构建虚拟跨线值乘任务会增大班次的工作量，对轮班优化产生不利影响[5]. 因此，在轮班阶段应根据班次与乘务员需求的匹配关系，最大程度地满足乘务员出退勤需求，并关注乘务员需求被满足的公平性.
2. 模型构建
2.1 建模分析
固定班制下，乘务员值乘固定班次类型序列，因此，班次类型对应的具体班次活动需要安排和优化，在班次均被覆盖基础上优化全部乘务员的轮班均衡性[19].
乘务资源共享能够满足乘务员对出退勤地点的个性化选择，根据排班阶段生成的班次集合，按照不同出勤地点需求对乘务员进行分组，每组中的乘务员展开单独轮班. 班次活动根据出退勤地点类型分配给相应乘务员组，但当乘务员的出退勤地点需求难以全部满足时，应将无法满足需求的乘务员归为本线路的乘务员组，以保证全部班次均被覆盖.
以多线排班的班次集合为输入，根据乘务员出退勤偏好划分相应乘务员组和班次子集，不同乘务员组的轮班过程相对独立，以下将以一个乘务员组为例说明轮班优化数学模型.
2.2 符号定义
为便于模型构建，符号及含义如表2所示.
表 2 符号定义Table 2. Symbol definition符号 含义 xj,i 决策变量，当且仅当班次 j 位于班次循环中第 i 个位置时，取值为 1 H 优化目标，所有轮班单位“辛苦”程度的均衡性 i 班次循环中的位置序号，i∈I，I 为班次位置集合 j 班次序号，j∈J，J 为班次集合 ts, j、te, j 班次 j 的开始和结束时间 td, j、tde, j、ti, j 班次 j 的驾驶时间、特殊时段附加值、非驾驶工作时间 JM, JE 早、晚班的班次集合 IE 班次循环中应分配晚班的位置集合 Tmins 晚班和早班的最小夜间休息（接续）时间 pi,k 0-1 变量，第 i 个位置的班次类型为 k 时，取值为 1 lk, j 0-1变量，班次 j 属于班次类型 k 时，取值为1 t∗ 轮班单位长度，d r 轮班单位序号，r∈R，R 为轮班单位集合 Hr 轮班单位 r 的“辛苦”程度 h1,r、h2,r 轮班单位 r 由班次直接产生和接续产生的“辛苦”程度 qi,r 0-1变量，轮班单位 r 包含位置 i 时，取值为 1 ir,m 轮班单位 r 的第 m 个班次（m=1,2,⋯,t）在班次循环中的位置 Tt,i,i* 班次循环中第 i 和第 i* 个位置对应班次类型之间的接续时间阈值 v1、v2、v3、v4 驾驶时间、特殊时段附加值、非驾驶工作时间、班次接续时间转化为“辛苦”程度的折算比例 2.3 约束条件
根据建模分析，考虑资源共享的乘务轮班计划优化问题需要确定一个覆盖所有班次的最优序列，所得结果形成一个轮班循环. 固定班制要求轮班循环中实际安排的班次活动应符合相应的班次类型，约束如式（1）所示.
∑j∈Jlk,jxj,i=pi,k. (1) 此外，模型需限制晚班和早班之间的夜间休息时间满足最小时间的要求，约束如式（2）所示. 即位置i的班次j （晚班）后接续位置i+1的班次j* （早班）时，晚班结束时间和早班开始时间的差值应不小于夜间休息最小时间，其中
1440 为一天的时间长度.ts,j∗−te,j+1440⩾(xj,i+xj∗,i+1−1)Tmins,∀j∗∈JM,j∈JE,i∈IE. (2) 2.4 优化目标
模型主要考虑短期工作负荷的均衡性优化，通过如图3所示的轮班单位进行计算. 一个轮班单位包括多个不同类型的班次活动，其长度取决于固定班制对应的班次序列周期t，如四班三运转下任意相邻4d的班次集合为一个轮班单位.
短期均衡性优化目标为每个轮班单位“辛苦”程度的差异性最小，“辛苦”程度是对轮班单位中工作量的综合计算，涵盖工作时间、驾驶时间和非驾驶时间、特殊工作时间等要素，避免了按照单一指标产生的同质评价，如相同时间的白班与晚班工作负荷不相同.
一个轮班单位r的“辛苦”程度Hr由班次直接产生的“辛苦”程度h1,r和轮班单位内班次接续产生的“辛苦”程度h2,r组成，如式（3）.
Hr=h1,r+h2,r,∀r∈R. (3) h1,r由班次的驾驶时间、特殊时段的附加值和班次内非驾驶时间3部分构成. 轮班单位r的“辛苦”程度应包含其中所有的班次，具体计算如式（4）. 其中，特殊时段的附加值为一天中过早（早于6：00）或过晚（晚于23：00）的工作时间.
h1,r=∑i∈I∑j∈Jxj,iqi,r(v1td,j+v2tde,j+v3ti,j). (4) 班次接续产生的“辛苦”程度主要来源于连续班次接续时间低于一定阈值的情况，具体计算如式（5）所示. 若连续的班次中存在休息，则不计入“辛苦”程度. 若轮班单位r中第m和m+1位次的2个连续班次j和j* 的间隔时间小于接续时间阈值，则不足的部分折算入轮班单位的“辛苦”程度，超出阈值的部分不计入.
h2,r=t∗−1∑m=1∑j∈J∑j∗∈Jv4xj,ir,mxj∗,ir,m+1max{Tt,ir,m,ir,m+1−ts,j∗+te,j,0}. (5) 根据现场调研得知，乘务人员对不同时段内工作的状态描述和实际意愿，设定折算比例取值为v1=1.0，v2=0.3，v3=0.5，v4=0.2.
乘务轮班计划优化模型的目标函数如式（6）所示，其中，Std(·)为标准差函数. 优化目标的计算范围涵盖了所有轮班单位，即包含所有乘务员组下的各个轮班循环，通过尽可能降低所有轮班单位之间“辛苦”程度Hr的差异以优化短期均衡性.
H=minStd(Hr). (6) 式（6）中的指标通过式（3）～（5）计算，模型的约束条件为式（1）和式（2）.
3. 求解算法
基于固定班制的轮班优化模型属于非线性整数规划模型，同类型班次的可对调决定了问题规模，随着乘务员和班次数量的增加而快速增大[20-21]，因此，通过设计改进的离散蜂群算法（ABC）实现模型的高效求解. ABC算法通过模仿蜜蜂的采蜜行为搜索问题的满意解，其核心思想是将解视作蜜源，通过多个蜂群并行搜索一系列的蜜源实现解的改进. 蜂群包括观察蜂、雇佣蜂和侦察蜂3种，其中：观察蜂根据当前代对蜜源的评估生成下一轮的蜜源搜索方向；雇佣蜂按照观察蜂给定的方向搜索下一个蜜源以期获得更好的蜜源；侦察蜂在蜜源长期未优化时搜索新的蜜源.
本文考虑固定班制轮班特征，基于经典ABC算法的线性搜索方法，设计了基于特征轮班单位的观察蜂搜索策略、基于班次类型交换的雇佣蜂搜索策略和基于班次类型组合的侦察蜂搜索策略.
1） 编码与初始解
算法的编码方式如图4所示，首先，根据出退勤地点进行班次分组，分为h1和h2共2组. 对于给定出退勤地点h的班次，定义Fk,h表示类型为k(k∈{M,D,E})的班次排序序列，将早班、白班和晚班班次按Fk,h的顺序进行组合，即可得到各组不同出退勤地点的班次循环. 根据上述对应关系，可将班次循环编码为2条对应不同出退勤地点的一维数据，每条数据由各类型班次的顺序FM,h、FD,h和FE,h连接构成.
固定轮班模式下，若不考虑长夜班的夜间休息时间约束，则具有相同出退勤地点和相同班次类型的班次允许随意相互调换，因此，初始解可通过分别对不同出退勤地点和不同班次类型的班次随机排序生成，且可满足除夜间休息时间约束外的全部约束. 针对不满足夜间休息时间的约束冲突，在适应度计算中加上一个较大的惩罚值，通过算法迭代排除约束冲突的情况.
2） 基于特征轮班单位的观察蜂搜索策略
在生成算法搜索方向时，选择具有不同特征的若干个轮班单位，以提高均衡“辛苦”程度的能力. 搜索策略的具体步骤如下：
步骤1 在既有班次循环R中依次生成随机选择、“辛苦”程度最大和最小的轮班单位，分别对应r1、r2和r3. 每选出一个轮班单位时，需对所选轮班单位外的所有班次进行遍历判断. 若班次与所选轮班单位中任一班次同属于任一轮班单位，则将该班次剔除，以保证3个轮班单位之间没有班次重叠.
步骤2 随机选择一种班次类型k，交换r1、r2和r3中类型为k的班次，共包含6种交换方式.
步骤3 计算6种交换方式得到的新蜜源适应度，保留最优的蜜源.
3） 基于班次类型交换的雇佣蜂搜索策略
雇佣蜂搜索策略为交换随机一种类型的班次序列，遍历该班次序列的交换位置以生成若干用于搜索的邻域，具体步骤如下：
步骤1 在当前蜜源Xa外随机选择另一蜜源Xb.
步骤2 随机选择一种班次类型k和出退勤地点h，取Xb中对应的班次序列Fk,h.
步骤3 考虑Fk,h进行位置移动的所有情况，移动m个单位后得到F(m)k,h，记n为Fk,h的总长度. 移动后F(m)k,h的第m + 1位至第n位为Fk,h的第1位至第n−m位，F(m)k,h的第1位至第m位为Fk,h的第n−m + 1位至第n位.
步骤4 用Xb中Fk,h的所有可能位置结果依次替换当前蜜源Xa中的Fk,h，计算各种可能替换结果得到新蜜源的适应度，保留最优的蜜源.
4） 基于班次类型组合的侦察蜂搜索策略
在连续多次迭代均无法搜索到更优解的情况下，应用侦察蜂搜索策略以跳出局部最优. 在当前蜜源Xa之外随机选择2个其他的蜜源，将3个蜜源的早、白和晚班序列进行组合以保证新蜜源的质量.
4. 案例分析
4.1 案例背景
以北京市可实现换乘的3条地铁线路为例进行案例分析，如图5所示. 3条线路间设有A、B、C 3座换乘站. 轮乘站一般设置在换乘站，以便乘务员通过换乘站实现跨线值乘. 其中换乘站A、B被设为轮乘站，所有乘务员均在轮乘站A、B出退勤.
列车经过轮乘站A、B时会产生换班机会，通过换班机会分割运行图可得乘务区段. 其中，连续值乘区段为满足连续值乘时间小于2.5 h的所有可行连续乘务区段数量. 3条线路共有
1915 个乘务区段和超过7144 个连续值乘区段.基于上述3条线路和轮乘站位置，构建如表3所示的3个场景，以验证乘务资源共享在不同规模线网上的应用效果，后续案例均基于这3个场景展开分析.
表 3 3个案例场景的参数Table 3. Parameters of three scenarios in case studies场景 涉及线路 乘务区段数/个 连续值乘区段数/个 场景 1 线路 1、3 1332 > 4567 场景 2 线路 1、2 1689 > 6563 场景 3 线路 1、2、3 1915 > 7144 针对各场景中的2个出退勤地点，设hA、hB分别为出退勤地点位于轮乘站A、B的班次，记为A类和B类班次；hAB为出退勤地点位于不同轮乘站的班次. 需要说明的是，从车辆段出发或返回车辆段的班次，出退勤地点调整为就近的轮乘站，计算班次的开始或结束时间需考虑车辆段到轮乘站办理出退勤手续的时间.
4.2 乘务轮班优化分析
设偏好A类和B类班次的乘务员各占50%，将A类和B类班次分别配给具有对应偏好差异的2组乘务员，并各自进行乘务组织和优化. 在四班三运转和六班五运转模式下首先由排班优化方法[5]生成班次，备班比例取10%，结果如表4所示.
表 4 考虑乘务员出退勤偏好的轮班输入构成Table 4. Composition of crew rostering considering crew attendance and departure preferences人 班次
类型班次数量 四班三运转 六班五运转 场景 1 场景 2 场景 3 场景 1 场景 2 场景 3 早班 排班数 41 43 54 56 68 78 备班数 5 5 6 6 8 8 白班 排班数 41 43 54 28 34 39 备班数 5 5 6 3 4 4 晚班 排班数 41 43 54 56 68 78 备班数 5 5 6 6 8 8 总乘务员数 368 384 480 372 456 516 固定班制下轮班计划的优化结果如表5所示，其中，总“辛苦”程度是覆盖轮乘站A和B 2组乘务员的整体统计. A组（A类班次）“辛苦”程度的变异系数为4.43%～5.39%，B组（B类班次）“辛苦”程度的变异系数为4.05%～5.78%. 变异系数为标准差和均值的比值，可直观对比均值存在差异的2组数据离散水平，以此说明优化模型可提高有效乘务员“辛苦”程度的均衡性. 由总“辛苦”程度可知，虽然A组和B组进行独立轮班，但总体“辛苦”程度差异不大，变异系数控制在4.42%～5.87%. 此外，由于六班五运转的轮班单位长于四班三运转，所以六班五运转的“辛苦”程度均值相对较高. 求解算法的收敛过程如图6所示，说明ABC算法在后期具有较好的搜索能力，从而生成适应度较高的满意解. 从求解时间上看，最复杂场景下的求解时间为4.64 h，模型的求解时间均在可接受范围内.
表 5 不同场景和班制下乘务轮班计划优化结果Table 5. Optimization results of crew rostering schedules in different scenarios and rostering patterns场景 班制 A 组“辛苦”程度 B 组“辛苦”程度 总“辛苦”程度 计算时间/s 均值 标准差 均值 标准差 均值 标准差 场景 1 四班三运转 883.6 42.2 854.3 46.2 869.0 46.5 8763 六班五运转 1311.6 58.1 1279.6 51.8 1295.6 57.3 11821 场景 2 四班三运转 902.6 44.0 883.2 44.9 892.9 45.5 9138 六班五运转 1327.9 62.8 1269.1 61.0 1298.5 68.5 15033 场景 3 四班三运转 902.1 48.6 869.8 46.5 886.0 50.2 11410 六班五运转 1310.6 69.7 1261.1 72.9 1285.8 75.4 16693 
图 6 场景1四班三运转下不同算法的收敛过程Figure 6. Convergence process of different algorithms regarding four-team and three-shift pattern in scenario 1模型的复杂性导致难以获得模型的准确解，所以将本文改进的蜂群算法（ABC）和基于精英保留策略[16]的改进遗传算法（GA）进行求解效果对比，以说明所得结果的质量. 按照相同的算法设计思路，GA算法的交叉算子与ABC算法的搜索策略基本一致，2个算法的搜索过程和结果对比如图6和表6所示. 在不同场景下2个算法所得“辛苦”程度的均值基本一致，但ABC算法可降低5.60%～17.01%的标准差，对应图6的场景1中可提升2.39%～2.44%的适应度；同时可节省1.97%～3.21%的求解时间，说明本文提出的算法具有较好的求解效率和求解质量.
表 6 四班三运转下ABC与GA算法求解结果对比Table 6. Comparison of ABC and GA results regarding four-team and three-shift pattern场景 总“辛苦”程度 计算时间/s ABC GA ABC GA 场景 1 868.95 ± 46.53 868.96 ± 49.76 8763 9053 场景 2 892.91 ± 45.45 892.90 ± 52.82 9138 9385 场景 3 885.97 ± 50.20 885.98 ± 53.18 11410 11639 注：u ± v中u为各个乘务组对应统计指标的均值，v为标准差. 4.3 乘务资源共享的影响分析
基于包含线路最多的场景3分析固定轮班模式下应用乘务资源共享的效果，设置如下3种情景，包括2种资源共享和1种非资源共享情形. 具体的，共享情形1中A类和B类乘务员各占50%，情形2不考虑出退勤地点偏好约束，即A类和B类乘务员比例均为0.
各情形下的优化结果如表7所示. 乘务资源共享情形2需要的乘务员规模最小，说明进行线路间维修资源共享有助于降低乘务员规模需求；相比不考虑资源共享的情形，在四班三运转和六班五运转下分别减少了4.10%和4.55%的乘务员数量. 而考虑乘务员出退勤偏好的共享情形1所需乘务员数较共享方案2有所增大. 此外，2种乘务资源共享情形的工作效率均优于分线优化情形，因为相同工作量下，减少的乘务员数量可提高工作效率.
表 7 场景3轮班计划对比Table 7. Comparison of crew rostering schedules for scenario 3班制 优化情形 乘务员数/人 日均额外通勤时间/h 工作效率/% 人均日工作时间/min “辛苦”程度均值/min “辛苦”程度标准差/min 四班三运转 分线优化 488 225.7 73.7 244.5 885.2 54.9 乘务共享1 480↓ 0 73.9↑ 241.4↓ 886.0↑ 50.2↓ 乘务共享2 468↓ 216.5↓ 74.9↑ 244.5↓ 890.3↑ 52.6↓ 六班五运转 分线优化 528 236.2 69.5 242.9 1287.3 89.0 乘务共享1 504↓ 0 70.0↑ 246.6↑ 1285.8 ↓75.4↓ 乘务共享2 504↓ 248.4↑ 70.7↑ 244.3↑ 1291.9 ↑70.9↓ 注：“↑”表示相较分线优化情形数值上增加；“↓”表示相较分线优化情形数值上减少. 对于日均额外通勤时间，考虑出退勤地点比例约束的情形1可实现所有乘务员按需选择轮乘站，日均额外通勤时间均为0，相较于分线优化方案，平均每人每日可节省约0.5 h的通勤时间. 在不考虑出退勤地点偏好需求时，情形2的结果与分线优化较为接近. 此外，进行乘务资源共享对轮班“辛苦”程度的平均值影响较小，变化范围不超过1%，但可有效降低“辛苦”程度的标准差，提高乘务计划的均衡性.
4.4 轮班班制的影响分析
为分析不同轮班班制对轮班计划的影响，基于表3中的3个场景，从“辛苦”程度和值乘偏好满足2个方面展开分析. 设A类和B类乘务员各占50%，非循环轮班计划的编制周期为30 d，固定班制的编制周期为班次完成一次循环的时间. 非循环轮班的乘务员数量设为与四班三运转相同，以保证非循环轮班和固定班制循环轮班之间的可比性.
不同轮班班制下各指标对比如图7所示. 各班制下的日均“辛苦”程度呈现规律性的差异，四班三运转最高，六班五运转次之，非循环轮班模式最低. 相较于四班三运转，六班五运转的日均“辛苦”程度更小，因为六班五运转所需的乘务员规模更大. 非循环轮班模式可不考虑班次类型比例约束，具有更好的灵活性，生成的乘务计划可更贴合值乘任务的时空分布，通过降低非工作时间来降低工作负荷并提高乘务员的工作效率.
图 7 不同轮班模式下轮班计划“辛苦”程度对比Figure 7. Comparison of workload degrees of rostering schedules regarding different rostering patterns3种轮班班制在周和月“辛苦”程度标准差上呈现相同的规律，由大至小依次为非循环轮班、四班三运转、六班五运转，说明固定班制轮班具有更好的均衡性；而非循环轮班模式对乘务值乘需求的满足限制了均衡性的提升. 2种固定班制中，六班五运转因班次序列的固有均衡特征获得了更好的乘务工作量均衡效果.
5. 结 论
1） 乘务资源共享可提高乘务计划的均衡程度和工作效率，同时可有效满足乘务员就近选择出退勤地点的个性化需求.
2） 相较于非循环轮班，固定班制轮班模式虽然满足乘务员个性化需求的范围减小，但更容易实现较高的乘务工作量均衡性，且具有更优的实际应用能力.
3） 本文提出的改进离散人工蜂群算法具有较高的寻优和收敛能力，可有效优化乘务员“辛苦”程度的短期均衡性，有利于实现在大规模班次情况下的轮班计划工作量均衡.
本文考虑了资源共享下固定班制轮班计划优化，一定程度上受到排班结果的影响，后续可考虑乘务资源共享下排班和轮班的交互关系并开展一体化研究. 此外，本文提出了“辛苦”程度这一涵盖4个层面的工作量指标，针对乘务员工作负荷的评估与量化方法有待引入更多要素并展开全面分析.
-
图 1 基于四班三运转的轮班计划
Figure 1. Crew rostering schedule based on four-team and three-shift pattern
图 2 乘务资源共享下排班和轮班的关系
Figure 2. Relationships between crew scheduling and rostering through resource sharing
图 6 场景1四班三运转下不同算法的收敛过程
Figure 6. Convergence process of different algorithms regarding four-team and three-shift pattern in scenario 1
图 7 不同轮班模式下轮班计划“辛苦”程度对比
Figure 7. Comparison of workload degrees of rostering schedules regarding different rostering patterns
表 1 四班三运转下4个乘务组的轮班计划
Table 1. Crew rostering schedule for four crew groups regarding four-team and three-shift pattern
乘务组 第 1 天 第 2 天 第 3 天 第 4 天 第 5 天 第 6 天 … 1 E M R D E M … 2 M R D E M R 3 R D E M R D 4 D E M R D E 
下载: 导出CSV
表 2 符号定义
Table 2. Symbol definition
符号 含义 xj,i 决策变量，当且仅当班次 j 位于班次循环中第 i 个位置时，取值为 1 H 优化目标，所有轮班单位“辛苦”程度的均衡性 i 班次循环中的位置序号，i∈I，I 为班次位置集合 j 班次序号，j∈J，J 为班次集合 ts, j、te, j 班次 j 的开始和结束时间 td, j、tde, j、ti, j 班次 j 的驾驶时间、特殊时段附加值、非驾驶工作时间 JM, JE 早、晚班的班次集合 IE 班次循环中应分配晚班的位置集合 Tmins 晚班和早班的最小夜间休息（接续）时间 pi,k 0-1 变量，第 i 个位置的班次类型为 k 时，取值为 1 lk, j 0-1变量，班次 j 属于班次类型 k 时，取值为1 t∗ 轮班单位长度，d r 轮班单位序号，r∈R，R 为轮班单位集合 Hr 轮班单位 r 的“辛苦”程度 h1,r、h2,r 轮班单位 r 由班次直接产生和接续产生的“辛苦”程度 qi,r 0-1变量，轮班单位 r 包含位置 i 时，取值为 1 ir,m 轮班单位 r 的第 m 个班次（m=1,2,⋯,t）在班次循环中的位置 Tt,i,i* 班次循环中第 i 和第 i* 个位置对应班次类型之间的接续时间阈值 v1、v2、v3、v4 驾驶时间、特殊时段附加值、非驾驶工作时间、班次接续时间转化为“辛苦”程度的折算比例
下载: 导出CSV
表 3 3个案例场景的参数
Table 3. Parameters of three scenarios in case studies
场景 涉及线路 乘务区段数/个 连续值乘区段数/个 场景 1 线路 1、3 1332 > 4567 场景 2 线路 1、2 1689 > 6563 场景 3 线路 1、2、3 1915 > 7144
下载: 导出CSV
表 4 考虑乘务员出退勤偏好的轮班输入构成
Table 4. Composition of crew rostering considering crew attendance and departure preferences
人 班次
类型班次数量 四班三运转 六班五运转 场景 1 场景 2 场景 3 场景 1 场景 2 场景 3 早班 排班数 41 43 54 56 68 78 备班数 5 5 6 6 8 8 白班 排班数 41 43 54 28 34 39 备班数 5 5 6 3 4 4 晚班 排班数 41 43 54 56 68 78 备班数 5 5 6 6 8 8 总乘务员数 368 384 480 372 456 516
下载: 导出CSV
表 5 不同场景和班制下乘务轮班计划优化结果
Table 5. Optimization results of crew rostering schedules in different scenarios and rostering patterns
场景 班制 A 组“辛苦”程度 B 组“辛苦”程度 总“辛苦”程度 计算时间/s 均值 标准差 均值 标准差 均值 标准差 场景 1 四班三运转 883.6 42.2 854.3 46.2 869.0 46.5 8763 六班五运转 1311.6 58.1 1279.6 51.8 1295.6 57.3 11821 场景 2 四班三运转 902.6 44.0 883.2 44.9 892.9 45.5 9138 六班五运转 1327.9 62.8 1269.1 61.0 1298.5 68.5 15033 场景 3 四班三运转 902.1 48.6 869.8 46.5 886.0 50.2 11410 六班五运转 1310.6 69.7 1261.1 72.9 1285.8 75.4 16693
下载: 导出CSV
表 6 四班三运转下ABC与GA算法求解结果对比
Table 6. Comparison of ABC and GA results regarding four-team and three-shift pattern
场景 总“辛苦”程度 计算时间/s ABC GA ABC GA 场景 1 868.95 ± 46.53 868.96 ± 49.76 8763 9053 场景 2 892.91 ± 45.45 892.90 ± 52.82 9138 9385 场景 3 885.97 ± 50.20 885.98 ± 53.18 11410 11639 注：u ± v中u为各个乘务组对应统计指标的均值，v为标准差.
下载: 导出CSV
表 7 场景3轮班计划对比
Table 7. Comparison of crew rostering schedules for scenario 3
班制 优化情形 乘务员数/人 日均额外通勤时间/h 工作效率/% 人均日工作时间/min “辛苦”程度均值/min “辛苦”程度标准差/min 四班三运转 分线优化 488 225.7 73.7 244.5 885.2 54.9 乘务共享1 480↓ 0 73.9↑ 241.4↓ 886.0↑ 50.2↓ 乘务共享2 468↓ 216.5↓ 74.9↑ 244.5↓ 890.3↑ 52.6↓ 六班五运转 分线优化 528 236.2 69.5 242.9 1287.3 89.0 乘务共享1 504↓ 0 70.0↑ 246.6↑ 1285.8 ↓75.4↓ 乘务共享2 504↓ 248.4↑ 70.7↑ 244.3↑ 1291.9 ↑70.9↓ 注：“↑”表示相较分线优化情形数值上增加；“↓”表示相较分线优化情形数值上减少.
下载: 导出CSV
-
[1] 薛锋,梁鹏,李海,等. 地铁乘务排班计划优化的最短路快速算法[J]. 铁道科学与工程学报,2022,19(9): 2532-2540.XUE Feng, LIANG Peng, LI Hai, et al. Optimization of subway crew scheduling based on shortest path faster algorithm[J]. Journal of Railway Science and Engineering, 2022, 19(9): 2532-2540. [2] 潘寒川, 戚博洋, 胡华, 等. 考虑司机偏好的城市轨道交通混合乘务轮转模型[J]. 交通运输系统工程与信息,2023,23(1):258-267.PAN Hanchuan, QI Boyang, HU Hua, et al. Preference-oriented task-type-mixed crew rostering optimization model for urban railway transit[J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(1):258-267. [3] 杨子涵,刘葛辉,李明,等. 考虑资源共享的城市轨道交通架修基地选址优化模型[J]. 铁道科学与工程学报,2023,20(1): 74-83.YANG Zihan, LIU Gehui, LI Ming, et al. Optimum location selection of heavy repair depots for urban rail transit considering resource sharing[J]. Journal of Railway Science and Engineering, 2023, 20(1): 74-83. [4] 石俊刚,杨静,王凤丽. 多线乘务员共享条件下城市轨道交通乘务计划均衡编制探讨[J]. 铁道运输与经济,2016,38(3): 84-87.SHI Jungang, YANG Jing, WANG Fengli. Discussing on balanced crew scheduling of urban rail transit based on multi-line crews sharing[J]. Railway Transport and Economy, 2016, 38(3): 84-87. [5] 金华,陈绍宽,王志美,等. 基于地铁乘务资源共享的排班计划优化方法[J]. 交通运输系统工程与信息,2021,21(2): 126-132.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. [6] JIN H, CHEN S K, RAN X C, et al. Column generation-based optimum crew scheduling incorporating network representation for urban rail transit systems[J]. Computers & Industrial Engineering, 2022, 169: 108155.1-108155.12. [7] IBARRA-ROJAS O J, DELGADO F, GIESEN R, et al. Planning, operation, and control of bus transport systems: a literature review[J]. Transportation Research Part B: Methodological, 2015, 77: 38-75. [8] 褚飞跃,田志强,倪少权. 高速铁路单循环乘务排班计划编制模型与算法[J]. 铁道学报,2012,34(7): 1-9. doi: 10.3969/j.issn.1001-8360.2012.07.001CHU 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. doi: 10.3969/j.issn.1001-8360.2012.07.001 [9] XIE L, SUHL L. Cyclic and non-cyclic crew rostering problems in public bus transit[J]. OR Spectrum, 2015, 37(1): 99-136. doi: 10.1007/s00291-014-0364-9 [10] QUESNEL F, DESAULNIERS G, SOUMIS F. Improving air crew rostering by considering crew preferences in the crew pairing problem[J]. Transportation Science, 2020, 54(1): 97-114. [11] MAENHOUT B, VANHOUCKE M. A hybrid scatter search heuristic for personalized crew rostering in the airline industry[J]. European Journal of Operational Research, 2010, 206(1): 155-167. [12] XIE L, MERSCHFORMANN M, KLIEWER N, et al. Metaheuristics approach for solving personalized crew rostering problem in public bus transit[J]. Journal of Heuristics, 2017, 23(5): 321-347. doi: 10.1007/s10732-017-9348-7 [13] 王骁. 高速铁路客运乘务排班优化研究[D]. 兰州:兰州交通大学,2021. [14] 金华,陈绍宽,冯旭杰,等. 考虑乘务员值乘需求的地铁乘务轮班优化方法[J]. 铁道学报,2023,45(7): 29-37. doi: 10.3969/j.issn.1001-8360.2023.07.004JIN Hua, CHEN Shaokuan, FENG Xujie, et al. A crew rostering optimization method for urban rail transit considering crew preference[J]. Journal of the China Railway Society, 2023, 45(7): 29-37. doi: 10.3969/j.issn.1001-8360.2023.07.004 [15] 张增勇. 城市轨道交通乘务计划编制方法研究[D]. 北京:北京交通大学,2014. [16] 罗红双. 网络化条件下城市轨道交通乘务计划编制方法研究[D]. 成都:西南交通大学,2019. [17] 金华,陈绍宽,刘爽,等. 基于固定班制的地铁乘务计划一体化优化方法[J]. 西南交通大学学报,2020,55(5): 955-962. doi: 10.3969/j.issn.0258-2724.20190952JIN Hua, CHEN Shaokuan, LIU Shuang, et al. Integrated optimum crew planning in fixed shift system for subways[J]. Journal of Southwest Jiaotong University, 2020, 55(5): 955-962. doi: 10.3969/j.issn.0258-2724.20190952 [18] LAI D S W, LEUNG J M Y, DULLAERT W, et al. A graph-based formulation for the shift rostering problem[J]. European Journal of Operational Research, 2020, 284(1): 285-300. doi: 10.1016/j.ejor.2019.12.019 [19] 石俊刚,杨静,周峰,等. 基于任务均衡的城市轨道交通乘务任务轮转模型及算法[J]. 铁道学报,2017,39(9): 17-24. doi: 10.3969/j.issn.1001-8360.2017.09.003SHI Jungang, YANG Jing, ZHOU Feng, et al. Crew rostering model and algorithm based on balanced workload in urban rail transit[J]. Journal of the China Railway Society, 2017, 39(9): 17-24. doi: 10.3969/j.issn.1001-8360.2017.09.003 [20] 汤希峰,何杰,张浩. 考虑碳排放的两阶段选址-路径问题及其算法[J]. 西南交通大学学报,2023,58(5): 1110-1116,1125. doi: 10.3969/j.issn.0258-2724.20210773TANG Xifeng, HE Jie, ZHANG Hao. Two-echelon location routing problem considering carbon emissions and its algorithm[J]. Journal of the Southwest Jiaotong University, 2023, 58(5): 1110-1116,1125. doi: 10.3969/j.issn.0258-2724.20210773 [21] 李冰,任泽强,轩华. 考虑多编组站专场作业的铁路枢纽车流组织优化[J]. 西南交通大学学报,2023,58(3): 489-498,545. doi: 10.3969/j.issn.0258-2724.20210796LI Bing, REN Zeqiang, XUAN Hua. Optimization of wagon flow assignment with transship work for multiple marshaling stations at railroad terminals[J]. Journal of the Southwest Jiaotong University, 2023, 58(3): 489-498,545. doi: 10.3969/j.issn.0258-2724.20210796 -
下载:
下载:
点击查看大图
计量
- 文章访问数: 79
- HTML全文浏览量: 25
- PDF下载量: 17
- 被引次数: 0