城市轨道交通乘务夜早任务搭配模型研究*
2016-03-15石俊刚徐瑞华
董 皓 石俊刚 周 峰 徐瑞华
(1.北京城建设计发展集团股份有限公司,100037,北京; 2.华东交通大学轨道交通学院，330013，南昌;3.同济大学交通运输工程学院,201804,上海∥第一作者，工程师)
城市轨道交通乘务夜早任务搭配模型研究*
董 皓1石俊刚2周 峰3徐瑞华3
(1.北京城建设计发展集团股份有限公司,100037,北京; 2.华东交通大学轨道交通学院，330013，南昌;3.同济大学交通运输工程学院,201804,上海∥第一作者，工程师)
乘务夜早任务连乘是我国城市轨道交通(以下简为“城轨”)乘务普遍采用的轮转策略。编制良好的乘务夜早任务搭配方案可保证乘务员工作的均衡性和安全性。根据城轨乘务夜早任务连乘需求,建立了相应的最优分配模型(NMC模型),设计了夜早连乘任务综合费用函数,并结合传统的匈牙利算法对NMC模型进行了求解。以某地铁线路为例,进行了算例分析。结果表明,NMC模型所编制的夜早连乘方案能够满足现场需求,可提高乘务夜早任务搭配的效率。
城市轨道交通; 乘务计划编制; 夜早任务搭配; 最优分配
First-author′s address Beijing Urban Engineering Design and Research Institute Co.,Ltd.,100037,Beijing China
1 问题的提出
乘务计划编制是城市轨道交通(以下简为“城轨”)乘务管理的重要工作,良好的乘务计划既能保证乘务员之间工作的均衡性,又能保证乘务员的驾车效率和安全性[1-9]。乘务计划编制包括乘务任务配对和乘务任务轮转[2-3]两部分工作。乘务夜早任务搭配是乘务任务轮转的前期工作,也是乘务计划编制过程中出现的新问题。
我国城轨列车运营时间长,一般一日首班车始发时间在凌晨5∶00—6∶00,末班车收车时间超过24∶00,为降低乘务人员工作负荷和保障列车运行的安全性,乘务管理中,将一日内的列车驾驶任务分为早班、白班、夜班,分三班进行轮转。然而，过早开始运营使得早班乘务员难以按时赶到出勤地点,过晚结束运营使得夜班乘务员无法乘坐公共交通回家,交通补贴费用高。因此,乘务轮转中,一般安排夜班乘务员退勤后留宿在退勤地点,次日继续值乘早班任务(称为夜早班连乘),由此可解决早班出勤难和夜班退勤难的问题。夜早班连乘示意图如图1所示,司机执勤完夜班后留宿在出退勤点2,第二天继续执勤早班任务,最后在出退勤点1退勤,完成夜早班连乘。
夜早班连乘是目前国内大部分城市的城轨乘务管理普遍采用的轮换策略,如北京、上海、苏州等。夜早班连乘过程中需要考虑以下问题:
(1) 乘务员夜间休息时间均衡。一般夜班早退勤的乘务员早班早出勤,反之亦然。
(2) 乘务员夜早连乘总任务量不超劳。夜早连乘要求司机保持良好的值乘状态,因此夜早连乘的总工作量不宜过长,一般采用驾驶里程和总工作时间进行衡量。
图1 夜早连乘示意图
(3) 夜早连乘地点一致。夜班任务退勤地点必须与早班任务出勤地点保持一致。一般要求夜班出勤地点与次日早班退勤地点尽量保持一致,方便乘务员处理一些出退勤事宜(如更换工作服等)。
一个较优的乘务夜早班连乘方案,既能保证乘务员之间任务的均衡性,又能保证乘务员的夜间休息时间和驾车安全性。夜早班连乘方案编制即将夜班任务与早班任务按照特定要求进行一一对应,形成夜早连乘任务集合,称为夜早任务搭配。目前国内乘务计划编制过程中,夜早班搭配基本采用人工手段,工作难度大,出错率高,特别是当夜早任务较多时,手工编制难以将所有因素考虑齐全,因此需要进行计算机优化计算。
夜早任务搭配是城轨乘务计划编制过程中的新问题,目前国内外还没有相关研究。本文以此为研究对象,建立相关数学模型及算法进行求解,希望能够提高乘务计划编制的效率。
2 数学建模及求解
乘务任务夜早班搭配发生在乘务任务配对工作之后。乘务任务配对指将给定的列车运行计划(即列车运行图)配对形成若干乘务任务[2],乘务任务一般分早班、白班、夜班三种。乘务任务夜早班搭配指将夜班与早班按照特定要求进行一一搭配,形成夜早连乘任务集合,即夜早任务搭配方案(见图2,其中虚线框内为一个夜早连乘任务)。
设夜班集合为N,早班集合为M,夜班任务i与早班任务j搭配可形成夜早连乘任务(i,j),cij为连乘任务(i,j)的综合费用,夜早班连乘任务集合为S(即夜早任务搭配方案)。夜早任务搭配问题可归纳为寻找一个最优的夜早任务搭配方案,使得所有的夜早连乘任务总费用最小。
图2 夜早任务搭配示意图
夜早任务搭配需要保证夜班与早班任务数量严格一致,然而在实际乘务任务配对过程中,往往难以完全保证,此时可采用备班任务(作为预备乘务员)填充夜班或早班,使得夜早任务数一致。因此,本文仅需考虑夜早任务数一致的情况,设夜早任务数均为n。
基于以上分析,为乘务夜早任务搭配问题建立如下数学模型(以下简为NMC模型):
目标约束:要求形成的搭配方案S中所有夜早连乘任务的总费用最小。即:
(1)
式中：
xij——夜早连乘任务是否被采用标识,采用为1,反之则为0。
一一搭配约束：要求一个夜班只能搭配一个早班。即：
(2)
(3)
0-1约束:
(4)
上述模型最优解需要保证夜早连乘任务之间的休息时间相对均衡,任务量不超劳,且出退勤的地点保持一致。为此,需要设计特殊的夜早连乘任务综合费用函数cij。
首先将夜班任务依次按照出勤地点(按车站名称)、退勤地点(按车站名称)、退勤时间(由早到晚)排序,存于N中;其次将早班任务依次按照退勤地点(按车站名称)、出勤地点(按车站名称)、出勤时间(由早到晚)排序,存于M中。以N为行,M为列,构建夜早连乘任务费用矩阵,如表1所示。
基于夜早连乘任务费用矩阵,设计夜早连乘任务(i,j)的综合费用cij如下:
表1 夜早连乘任务费用矩阵
(5)
式(5)中：
ctij为夜班任务i搭配早班任务j出退勤次序错乱造成的费用,其具体形式见式(6)。当i=j时,夜班任务i搭配早班任务j为正常出退勤次序,此时将不造成费用;当i
(6)
SEij表示夜班任务i出勤地点与早班任务j退勤地点是否一致,如果不一致,则SEij=1,反之SEij=0,γ为不一致的惩罚值。
ESij表示夜班任务i退勤地点与早班任务j出勤地点是否一致,如果不一致,则ESij=1,反之ESij=0,λ为不一致的惩罚值。此部分可保证夜早班搭配的出退勤地点保持一致。
OTij表示夜早连乘任务(i,j)工作时间是否超劳,如果超劳，则OTij=1,反之OTij=0,σ为不一致的惩罚值。即：
(8)
式中：
tij——夜早连乘任务(i,j)的总工作时间;
Tmax——允许的最大工作时间。
ODij表示夜早连乘任务(i,j)驾驶里数程是否超限，如果超限，则ODij1，反正ODij=0,ω为不一致的惩罚值。即：
(7)
式中：
dij——夜早连乘任务(i,j)的总驾驶里程；
Dmax——允许的最大驾驶里程。
NMC模型为最优分配模型[8-9],可结合匈牙利算法[8]进行求解。其求解步骤如下:
步骤1:构建夜早连乘任务费用矩阵。分别将夜班、早班进行排序,基于式(5)构建表1的夜早连乘任务费用矩阵;
步骤2:基于费用矩阵,采用匈牙利算法求解最优矩阵(独立零的个数为n),并获取最优解X;
步骤3:根据最优解X,将夜早任务搭配形成夜早连乘任务集合,形成最优夜早任务搭配方案。
3 算例分析
某地铁线路基本情况如图3所示,S为普通站,D为车场。其中，AHQB与TGY为终端折返站,XG为中间折返站,XS为中间站,LBC、MJP、NZL均为车场。该线路采用大小交路方式运营,大交路为AHQB→TGY,小交路为AHQB→XG。
图3 线路示意图
夜班出勤地点为XS、TGY,退勤地点为LBC、MJP、NZL三个车场;早班出勤地点为LBC、MJP、NZL三个车场,退勤地点为XS、TGY。夜早任务搭配具体要求如下:
(1) 尽量保证乘务员夜间休息时间均衡,即做到夜班早退勤,则早班早出勤,反之亦然;
(2) 夜班与早班总驾驶公里不得超过246 km,总工作时间不得超过11 h;
(3) 夜班退勤地点与早班出勤地点必须一致,夜班出勤地点与早班退勤地点必须一致。
以该线路某次乘务计划编制过程中的部分夜早任务搭配为例,采用所述方法进行求解。需要进行夜早搭配的任务如表2。
表2中夜班任务依次按照出勤地点、退勤地点、退勤时间进行了排序,早班任务依次按照退勤地点、出勤地点、出勤时间进行了排序。显然,若不考虑工作量约束,表中夜早班对应顺序即为夜早班衔接的最优方案。然而，XL2与LX2衔接,公里数超出了限制;XM2与MX2衔接,工作时间超出了限制，因此需要进行夜早班优化搭配。
表2 夜早班任务信息
具体求解过程如下:
步骤1:设计夜早连乘费用函数,并产生费用矩阵。
现场调研了解到,现场对于出退勤地点一致性要求最高,其次是工作时间和工作量约束,最后是休息时间均衡性。根据此需求,设计夜早连乘任务费用函数如下:
(9)
其中
(10)
根据式(9),产生表3所示费用矩阵。
步骤2:基于夜早连乘任务,采用匈牙利算法[8-9]求解表3的最优约简矩阵。
根据匈牙利算法原理可知,最优约简矩阵中,独立零的个数恰好为n,找出所有独立零对应的变量,这些变量取1,其它变量取0,即为最优解。表3中,加粗黑数字即为独立零对应的位置,该位置对应的变量取1,其它变量取0,即为NMC模型的最优解。
步骤3:基于最优解,获取最优夜早班搭配方案。
将表3中加粗黑数字对应的夜早班搭配起来,形成最优夜早班搭配方案,如表4所示。
由表4可以看出,最优搭配方案具有以下特点:
(1) 夜早班出退勤地点完全一致。
(2) 夜早连乘任务工作量满足限制。所有夜早连乘任务的驾驶公里和工作时间均在约束范围以内,保证了工作量约束,同时尽量减少出退勤顺序的调整幅度，避免了表2中XL2与LX2搭配公里数超出、XM2与MX2搭配工时超出等问题。
表3 夜早连乘任务费用矩阵
表4 夜早班最优衔接方案
(3) 夜早连乘任务休息时间尽量均衡。在满足地点约束和工作量约束的情况下,基本保证了夜班早退勤、早班早出勤的规则,如MT与TM系列任务,XN与NX系列任务。
4 结语
本文以乘务计划编制过程中的夜早班任务搭配为研究对象,充分分析夜早班任务搭配需求,建立了夜早班任务搭配的NMC模型。NMC模型的核心在于设计夜早连乘任务费用函数。本文根据夜早任务搭配需求(出退勤地点一致,夜早连乘工作量约束,乘务员休息时间均衡),设计了满足多需求的夜早连乘任务综合费用函数。通过分析NMC模型的特性,将其归纳为最优分配模型,并结合传统匈牙利算法[9-10]进行求解。
实例验证表明,NMC模型求解的最优夜早连乘方案能够满足所有需求,可提高乘务夜早班搭配工作的效率,为乘务计划编制的下一步工作(乘务任务轮转)打下基础。
[1] 王英,辛继伟等.地铁乘务管理体系标准化探讨[J].都市快轨交通,2013，26(3)：62.
[2] 石俊刚,史宏杰,徐瑞华.城市轨道交通乘务任务划分模型及算法研究[J].铁道学报,2014,36(5):1.
[3] 石俊刚,周峰,徐瑞华.城轨交通乘务任务配对的集合分割模型及算法[J].同济大学学报(自然科学版),2015,43(2):232.
[4] BEASLEY J E.An algorithm for set covering problems[J].European Journal of Operational Research,1987,31(1):85.
[5] KARLA L,HOFFMAN,MANFRED Padberg.Solving airline crew scheduling problems by branch-and-cut[J].Management Science,1993,39(6):657.
[6] MARSTEN R E,SHEPARDSON F.Exact solutionof crew scheduling problems using the set partitioning model:recent successful applications[J].Networks,1981,11(2):165.
[7] WEDELIN Dag.An algorithm for large scale 0-1 integer programming with applicationto airline crew scheduling[J].Annals of Operations Research,1995,57(1):283.
[8] LAN Guanghui,DEPUY Gail W,WHITEHOUSE Gary E.An effective and simple heuristic for the set covering Problem[J].European Journal of Operational Research,2007,176(3):1387.
[9] KOHL Niklas.Airline crew rostering:problem types,modeling and optimization[J].Annals of Operations Research,2004,127(1-4):223.
[10] 傅家良.运筹学方法与模型[M].上海:复旦大学出版社,2006:193.
[11] 裘民民,赵晓波,王建才,等.基于(s,S)库存策略的分销系统最优分配问题[J].清华大学学报(自然科学版),2006,46(5):749.
Early and Late Tasks Pairing Model for Urban Rail Transit Crew
DONG Hao, SHI Jungang, ZHOU Feng, XU Ruihua
The early and late tasks pairing rotation strategy is widely adopted by urban rail transit crew in China. A good composition of the early and late tasks pairing scheme can ensure the balance and security of attendants work. Based on the demands of early and late tasks pairing tasks,an optimal allocation model(NMC) is established and a cost function of early and late tasks pairing rotation is designed combined with the traditional Hungarian algorithm to solve the NMC model.A numerical example of a certain rail transit line is analyzed,and the result indicates that the scheme complied by model could meet the field demands and improve the efficiency of the tasks.
urban rail transit; crew schedule plan; early and late tasks pairing; optimal allocation
*中国博士后科学基金项目(2014M551454)；国家自然科学基金项目(71271153)
F 530.7
10.16037/j.1007-869x.2016.07.007
2015-05-22)
