陈仕军,沈吟东,苏 璇,陈贺命

(华中科技大学控制科学与工程系,武汉430074)

带中式用餐约束的乘务调度问题

陈仕军,沈吟东*,苏 璇,陈贺命

(华中科技大学控制科学与工程系,武汉430074)

有效的乘务调度能够为公交企业带来巨大的成本节约,但是,公交乘务调度问题因受制于一系列劳动法规的约束变得十分复杂.我国公交普遍存在“中式用餐”约束,进一步加大了问题的复杂性,使西方主流调度系统在国内实施面临困难.本文基于“生成与选择”方法解决乘务调度问题,关键在于“生成”阶段处理“中式用餐”难题;利用“中式用餐”约束和乘务问题特点,设计一种基于启发式规则的换班机会筛选方法;在所选换班机会集合的基础上构造能满足“中式用餐”约束的潜在乘务班次集合.对实际公交乘务调度问题中的12组实例进行测试,表明本文方法不仅能处理 “中式用餐”约束,而且能极大减少所求问题的规模,因此适用于解决大规模的带有“中式用餐”约束的乘务调度问题.

城市交通;乘务调度;中式用餐;启发式;班次生成

1 引 言

乘务调度问题是公共交通领域中研究的重要难题之一,属于世界公认的NP难题[1].编制优化的乘务调度方案,可以帮助公交企业节约成本、提高乘务资源效益.因此,自上世纪六十年代起,西方发达国家就开始利用计算机进行公共交通乘务调度问题的研究,至今已有许多解决方法和技术问世[2],并取得成功应用.其中,基于整数线性规划(ILP)的方法仍占主导地位,其应用也最为广泛[3].

经典的ILP方法包括一个“生成班次”和一个“选择班次”的过程,因此,又被归为“生成与选择”方法[4].该类方法首先要根据劳动法规等约束生成一个大的乘务班次(简称“候选班次”)集合;然后基于ILP方法从中选择一个最优的班次子集覆盖全部车辆工作.尽管该方法已有许多成功应用[4],但面对一些特殊问题时有如下困难:一方面,当乘务调度问题具有复杂的劳动法规和约束(如本文的“中式用餐”)时,生成满足劳动法规和约束的全部候选班次会很耗时;另一方面,当乘务调度问题规模较大(现实问题基本都属于大规模问题)时,全部候选班次的数量通常很大(可能是天文数字),使得“选择”阶段超出ILP的求解能力.目前,大多数研究侧重于解决后一问题,即扩大ILP的求解能力,例如典型的方法有列生成法[5]、元启发式方法[6]等.然而,对于如何生成潜在班次集合,一般描述比较简单或假定其已经存在.实际上,潜在班次的构造过程依赖于具体的劳动法规和约束,特别是在求解具有复杂法规和约束的乘务调度问题时,生成全部潜在班次往往非常费时,有时甚至占据总求解时间的85%以上[7].因此,研究有效构造潜在班次集合的方法,使其满足各种劳动法规和约束(尤其是复杂约束),是应用ILP方法解决乘务调度问题的首要工作和基础.

我国的乘务调度问题除了具有一般乘务调度问题的常见劳动法规和约束外(例如总工时、连续工时等的限制),还有一些具有普遍性的特色约束.其中,要求有“中国式”的固定时间段用餐(简称“中式用餐”)这一特色约束[8],使其比已有的乘务调度问题更加复杂,进而,使得在西方国家得到成功应用的各种乘务调度方法在国内实施面临求解困难.本文将采取“生成与选择”的方法解决我国的具有“中式用餐”约束的乘务调度问题,主要是在“生成班次”阶段来处理复杂的“中式用餐”约束.先通过分析“中式用餐”的特点,结合相关的劳动法规等约束和乘务问题特征,设计出基于启发式规则的换班机会筛选方法;再利用筛选出的换班机会集合生成所有潜在班次.本文方法不仅能满足“中式用餐”的约束要求,而且能极大减小所求问题的规模,有利于解决大规模的“中式用餐”乘务调度问题.

2 乘务调度问题

公共交通乘务调度问题就是合理安排一组乘务班次来完成一日内的全部车辆运营任务.单个车辆的运营任务通常是从车场出发,历经若干趟在线路上的运营,最终返回车场,称为一个车辆运营任务块(Block).在每辆车的运营线路上一般会有一个或多个指定的可供乘务员换班的地点,称为“换班点”;换班点与车辆到达该地点的时间结合起来就构成一个“换班机会(RO)”;在任意一个换班机会,乘务员都可以(但不一定)换班;在两个连续的“换班机会”之间,乘务员通常是不允许换班的,这段连续的工作被称为“最小值乘段(Piece)”;一个或几个连续的“最小值乘段”可以构成“连续值乘段(Spell)”.一个或者多个“连续值乘段”进行合理组合,可构成一个乘务班次,简称“班次(Shift)”,也就是乘务员一天的工作安排,通常从场站签到开始到场站签退结束[4,9].根据“班次”的特点,一般可以将其划分成整班、大单班、单班3种类型.整班(又称连续班),期间有一个短暂的时间供乘务员用餐和休息;大单班的乘务员上班时间跨度(从签到至签退)比较长,两个连续值乘段间有一段较长休息时间;单班只包含一个连续乘务段的班次.图1描述了部分与乘务调度相关的概念.

乘务调度是一个极为复杂的组合优化问题,其目标是采用最少数量和最小运营成本的乘务班次集合去执行完所有车辆任务,且所有乘务班次需要同时满足运营企业和国家规定的相关劳动法规和约束.对于一般的乘务调度问题,其乘务班次需要满足如下约束[9-11]:

(1)乘务员连续值乘时长不可超过规定的最长时长Tmax和最短时长Tmin;

(2)班次的总工时不可超过相应班型所规定的最长总工时TSmax与最短总工时TSmin;

(3)班次的有效工时不可超过相应班型所规定的最长有效工时TWmax与最短有效工时TWmin;

(4)整班型班次的用餐时间不得超出规定的用餐最长时间TBmax与最短时间TBmin;

(5)大单班型班次中两个连续值乘段间的休息时间不得少于规定的最短休息时间TBSmin.

图1 车辆任务和乘务班次Fig.1 Vehicle work and crew shift

式中 xj为决策变量,cj是班次j的成本;式(1)是目标函数;式(2)表示任意最小值乘段至少被一个被选择班次所覆盖.

由模型可以看出,乘务调度问题的规模与n(即候选班次的数量)的大小直接相关,而生成候选班次的数量直接由RO数量决定.假设有p辆车的运营计划,平均每辆车的运营计划中含有r个RO(含有r-1个最小值乘段).若暂不考虑班次的合法性约束,则所有车辆运行计划可以生成p×r× ( r-1 )/2个连续值乘段.当考虑生成最多包含k个连续值乘段的班次时,理论上我们可以算出可能的候选班次数量

当k较大时,候选班次的数量n以RO的数量r呈高次多项式级增长,给ILP模型求解带来极大困难.因此,在不损失最优解前提下尽可能减小候选RO数量r是解决该问题的关键.下文将基于“中式用餐”约束和乘务问题特点设计一些启发式策略,筛选出一些“好”的RO作为候选换班机会集合,从而缩小候选乘务班次集J的规模.

3 “中式用餐”约束下的乘务班次集生成

3.1 换班机会的选择

由于“中式用餐”约束要求用餐时间在规定时间段[tstart,tend]内进行,故规定[tstart,tend]内的任何RO都可能被用作换班,所以应保留这些RO;另一方面,因为用餐必须要换班,且在[tstart,tend]内进行,故用[tstart,tend]外的大部分换班机会可能不会被使用,因此可以剔除其中一些“不好”或“不合理”的RO,以缩小问题的规模.本文在用餐规定的时间段[tstart,tend]外,根据乘务调度问题的本身特点选择出一些“好”或“合理”的RO,剔除剩余的RO,使得生成的班次既能满足“中式用餐”约束,且不会损失关键的RO.选择一些“好”的RO时,主要基于乘务问题的如下特点:乘务人员在执行车辆运营任务时,一般应尽可能持续较长的工作,以免造成多次换班,从而影响值乘效率;特别,车辆出车场后的工作,一般由同一乘务员执行尽可能长的任务后,才考虑换班;同理,返回车场的最后一段值乘任务也尽可能长,以提高工作效率.

首先,对给定时间区间[t1,t2]内的车辆任务,给出一个简单启发式RO选择方法(SHA),使所生成连续值乘段尽可能长.记[t1,t2]内最早的换班机会为rc(对应时间tc),SHA如下:

Step 1 若t2-tc≤Tmax,则停止;

Step 2 从rc开始,向前寻找新的换班机会rf(对应时间tr),使得rc与rf连接构成的连续值乘段尽可能长,且满足tr-tc≤Tmax;

Step 3 选择rf,记当前换班机会(rf)为rc,返回Step1.

现对各个车辆任务分别选择出一些RO,以用作生成潜在班次集J.记车辆从车场出发时间ts,返回车场的时间t,中餐时间段[t1,t1],晚餐时

estartend间段[t2start,t2end],具体的筛选RO策略如下.

(1)选择车辆从车场出发和返回车场的RO (必用换班机会,即班次开始和结束RO),如图2所示.图2中,黑色圆点,表示选择的RO;白色圆点表示没有被选择的RO;虚线表示未画出的车辆运营任务段.

图2 选择车辆运营任务的始末ROFig.2 Selecting the start RO and the end RO

(2)选择规定用中餐时间段[t1,t1]和晚餐

startend时间段[t2,t2]内的所有RO,如图3所示.图3

startend中的黑圆点表示被选择的RO,白圆点表示未被选择RO.

图3 选择用餐时间段内的所有ROFig.3 Selecting all the ROs in meal-break time

由于只依赖策略(1)、策略(2)所选择的RO集合,无法保证所有车辆任务被分割成合法的连续值乘段,因此还需根据策略(3)选择一些其他RO.

(3)选择用餐时间段[t1,t1]、[t2,t2]以

startendstartend外的其他RO,确保所有车辆任务能形成连续值乘段(根据参数Tmax).

不妨假定车辆运营任务包含中餐和晚餐时间段(只包含1个中餐或晚餐时间段的方法类似),记[t1start,t1

end]内最早和最晚RO的时间分别为t1f, t1

l;[t2start,t2

end]内最早和最晚RO的时间分别为t2f, t2.分以下三种情况,依次选择RO

l

① 当t1f-ts＞Tmax时,则从 t1f向后逐个寻找新RO(对应时间tr),直到tr-ts≤Tmax;选择时间段[tr,t1start]内的所有RO,如图4所示.

图4 向后逐个寻找选择ROFig.4 Selecting the ROs backward

② 当te-t2l＞Tmax时,则从t2l向前逐个寻找新RO(对应时间tr),直到te-tr≤Tmax;选择时间段[t2end,tr]内的所有RO,如图5所示.

③ 当t2f-t1l＞Tmax时,则对[t1l,t2f]内的车辆任务利用SHA选择RO,如图6所示.

图6 利用SHA选择ROFig.6 Selecting the ROs by using SHA

(4)若车辆任务计划不包含用餐时间段,则在[ts,te]时间段内应用SHA选择RO.

通过以上RO的选择过程,形成可能用到的RO集合R.

3.2 候选班次集J的生成

基于3.1节筛选出的RO集合R,根据如下步骤形成候选班次集J0:

Step 1 根据R中的换班机会,对所有车辆任务集进行切割划分,以形成最小值乘段集(Piece集);

Step 2 对多个相邻的最小值乘段进行连接(要求相连的总长度不超过Tmax),形成所有可行连续值乘段集(Spell集);

Step 3 对所有连续值乘段按起始时间排序;

Step 4 对排序后的连续值乘段集,通过完全枚举法进行连接,并判断是否满足第2节中的乘务约束(2)-(5),得到候选班次集J0.

Step 5 对J0剔除不满足中式用餐约束的班次,即删除不满足约束(6)的班次,得到班次集J.

4 案例计算

生成候选班次集J之后,若|J|不大(例如小于2 000),则可以利用著名数学优化软件ILOG Cplex求解式(1)、式(2)对应的ILP模型[12];但当候选班次集规模|J|较大时,还需要利用列生成法[10]、元启发式方法[6]等大规模优化方法求解.主要测试在生成班次满足“中式用餐”约束条件下,筛选换班机会方法对生成乘务班次集规模|J|的影响.

通过测试12组实际数据来说明本文方法的有效性,测试数据主要来自海口市、武汉市和十堰市的部分公交线路行车方案.相关乘务约束所采用的参数设置如下:乘务员的连续值乘时间不得低于2 h且不超过5 h;乘务员的实际值乘时间不得少于6.5 h且不超过8 h,其中单班的值乘时间不低于2 h且不超过5 h;中餐时间段:11:00-13:00,晚餐时间段:18:00-20:00;整班用餐时间不得低于30 min,大单班的休息时间不得低于4 h.

主要考虑和比较两类潜在班次集生成方法:

(1)传统的考虑所有换班机会的方法(一般方法);

(2)本文筛选换班机会的方法(本文方法).

计算和测试两类不同方法下 Piece、Spell及Shift的数量变化.特别是Shift数量直接影响到求解乘务调度集覆盖模型的求解难度.相关的实验结果如表1所示.在表1中,12个测试案例按Block数量从小到大排列;ro、piece、spell和shift,各自表示该方法下ro、piece、spell和最终生成潜在班次的数量.RPD表示利用本文方法后潜在班次数量相对于一般方法班次数量减少的百分比,计算为

表1 潜在班次集生成实验结果Table 1 Experimental results for generation of potential shift set

从表1可知,应用本文所提筛选换班点方法后,很大程度地减少了ro、piece、spell及候选班次的数量.特别是,筛选换班机会后,候选班次数量平均减少了63.9%.因此,有利于求解更大规模的问题.

5 研究结论

本文提出了一种能够有效处理“中式用餐”约束且能极大缩小问题规模的乘务候选班次集的生成方法.“中式用餐”约束与西方国家的用餐约束存在很大差异,因此,使得现有的基于ILP的方法无法直接求解.本文通过在“生成”阶段预先生成满足“中式用餐”约束的候选班次集合,不仅使得传统的ILP方法可以用以求解具有中国特色的乘务调度问题,而且,还能有效利用“中式用餐”约束,达到降低候选班次集规模的目的.总之,本文所提的乘务班次生成方法不仅有助于解决带有“中式用餐”的乘务调度问题,而且有助于扩大基于ILP的乘务调度方法的求解规模.

虽然本文方法能够有效降低问题的规模,但对于大规模的乘务调度问题(如本文所测试的多数案例),潜在班次数量仍然很大,直接利用整数规划软件(如ILOG Cplex)求解ILP模型仍然存在时间上的困难.因此,需要进一步研究智能优化方法或列生成技术以解决更大规模的乘务调度问题.

[1]Wren A,Fores S,Kwan A S K,et al.A flexible system for scheduling drivers[J].Journal of Scheduling, 2003,6(5):437-55.

[2]Hickman M,Mirchandani P.Computer-aided systems in public transport[C]//Lecture Notes in Economics and Mathematical Systems.Berlin:Springer,2008.

[3]JütteS, Thonemann U W. Divide-and-price: A decomposition algorithm for solving large railway crew scheduling problems[J]. European Journal of Operational Research,2012,219(2):214-223.

[4]Shen Y,Kwan R S K.Tabu search for driver scheduling [C].Lecture Notes in Economics and Mathematical Systems,Berlin:Springer,2001(505):121-135.

[5]Fores S.Column generation approaches to bus driver scheduling[D].University of Leeds,1996.

[6]Li J,Kwan R S K.A fuzzy genetic algorithm for driver scheduling[J]. European JournalofOperational Research,2003,147(2):334-344.

[7]Shen Y.Tabu search for bus and train driver scheduling with time windows[D].University of Leeds,2001.

[8]Shen Y,Xia J.Integrated bus transit scheduling for the Beijing bus group based on a unified mode of operation[J].International Transactions in Operational Research,2009,16(2):227-242.

[9]沈吟东,倪郁东.含时间窗的司售员调度问题建模及多邻域结构设计[J].华中科技大学学报,2008, 36(12):31-34.[SHEN Y D,NI Y D.Model for crew scheduling with time windows and multineighborhood structures[J].Journal of Huazhong University of Science and Technology(Natural Science Edition),2008,36(12):31-34.]

[10]Mesquita M,Paias A.Set partitioning and coveringbased approaches for the integrated vehicle and crew scheduling problem[J].Computers& Operations Research,2008,35(5):1562-1575.

[11]Shen Yindong.Two neighbourhood search approaches: 2-opt heuristics and tabu search for bus and train driver scheduling[M].Beijing:Science Press,2003.

[12]Shen Y,Chen S,Su X.Rail crew scheduling based on a pooling mode for high speed passenger lines[C]// Proceedingsof2010 InternationalConference on Logistics Engineering and Intelligent Transportation Systems,2010.

A Crew Scheduling with Chinese Meal Break Rules

CHEN Shi-jun,SHEN Yin-dong,SU Xuan,CHEN He-ming
(Department of Control Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074,China)

An efficient crew scheduling can significantly reduce the operational cost for transit enterprises. However,the crew scheduling problem,known to be NP-hard,is complicated by the fact that there are many restrictions on the shift generation.Moreover,there are some special requirements in China,for example, meal break is normally required to be taken during the conventional time ranges for lunch or dinner,which is called a Chinese meal break rule to distinguish from the western ones.It also makes the existing crew scheduling approaches encountering difficulties.On the basis of the“generate and select”approach to solve the crew scheduling problem,this paper proposes an approach to handling the Chinese meal break rule in the phase of“generate”.Taking advantages of the characteristics of Chinese meal break rule and problem domain knowledge,a heuristic-based approach is proposed to select some promising relief opportunities (ROs).A shift generation approach is then devised to generate a large set of potential shifts that satisfy the Chinese meal break rule.Experimental results from 12 groups of real-world problem instances demonstrate the success of the proposed approach,which can greatly reduce the number of potential shifts generated. Therefore,it is suggested that the proposed approach be used to solve the large scale crew scheduling problems with Chinese meal break rule.

U268.6

A

U268.6

A

1009-6744(2013)02-0090-06

2012-10-11

2012-11-20录用日期:2012-12-07

国家自然科学基金(70971044,71171087).

陈仕军(1980-),男,湖北襄阳人,博士生.

*通讯作者:yindong@hust.edu.cn.

Key words:urban transportation;crew scheduling;Chinese meal break;heuristics;shift generation