侯彦娥，孔云峰，朱艳芳，马 瑞

(河南大学a.计算机与信息工程学院；b.黄河中下游数字地理技术教育部重点实验室，河南开封475004)

0 引言

公共交通在城市交通体系中占据重要的地位.大力发展公共交通不仅能够减少交通拥堵，而且还能提倡人们绿色出行减少大气污染.公交车辆调度与司机排班是公交企业编制生产作业计划的基础，也是公交企业运营管理中的一个重要环节.良好的生产作业计划不仅能够减少公交线路所需公交车的数量，还能在满足国家相关政策法规的条件下达到企业和司机各方面的需求，为安全和高效的公交运营提供保障.因此，研究公交车辆调度和司机排班问题具有现实意义.

针对公交车调度和司机排班问题，国内外学者展开了深入的研究.国外学者针对此类问题的研究相对比较成熟[1-4].针对此类问题，有些文献[5-7]将问题分成车辆调度和司机排班2个子问题分阶段求解，先基于线路时刻表完成车辆调度，再进行司机任务分配，最后编制司机轮班计划作业.文献[8-9]同时考虑车辆调度和司机排班，力求获得更优的公交作业方案.然而，国外现有的解决方案和算法难以适应于我国的车辆调度和司机排班问题.其原因在于：国外公交企业中司机和车辆关系不固定，1个司机在1天内可以驾驶多个车辆；而国内的公交企业通常采用“人车绑定”模式，即1位司机在同一个工作日内驾驶同一辆车.

国内学者也展开多样化的研究[10-16].王鹏飞[10]和陈程[11]设计遗传算法求解车辆调度和司机排班问题.陈明明等[12]设计了一种禁忌算法求解多车场公交乘务排班问题；魏金丽[13]、王森磊[14]等均采用生成与选择方法优选司机排班方案，刘涛[15]研究司机调度和轮班问题的元启发算法；陈明明[16]针对多种公交管理模式系统地讨论了相关的问题模型和算法.这些研究均表明使用优化算法比人工排班具有一定的优势，但也存在一些不足：测试案例单一并且规模较小，难以验证算法的优化性能和通用性；多数研究并未兼顾车辆和司机的成本，不能反映实际应用的需求.

本文针对国内“人车绑定”模式下的公交司机排班问题进行研究，同时考虑车辆和司机的成本，设计1个迭代局部搜索算法(Iterated Local Search,ILS)和集合覆盖模型(Set Cover Problem,SCP)混合的元启发算法寻找最小车辆数和最少司机数量的排班方案，并验证算法的有效性.

1 问题描述

本文研究“人车绑定”管理模式下的单条公交线路的司机排班问题，其实质是同时兼顾车辆调度和司机排班2个问题.假设公交车可以停靠在某个车场(具有出发的起始车站或终点车站)且在起点或终点可以为司机提供就餐或车辆充电等服务.1条公交线路上有若干个班次任务的集合，每个班次任务具有起始站点、终点站点、发车时间、结束时间、运行时间等属性.1辆公交车从车场出发，依次执行若干个班次任务，然后再回到车场.车场与若干个班次任务构成的集合称为1个班次链，所有班次链的集合构成1条公交线路的作业方案.每个班次链表示车辆从车场出发，依次完成若干班次任务，再回到车场；每个班次链需要1辆公交车，1位或2位司机.每个班次链的成本由固定成本和日常成本2部分组成，其中车辆和司机数量属于固定成本，车辆行驶里程和停留等待成本等属于日常成本.目标即通过安排合理的班次链组合，使公交作业方案的成本最低.每个班次链要满足以下约束条件：1个班次任务完成后，车辆需停运若干时间保证司机的休息时间；在司机上班时间内需要在合适的时间和地点就餐；同时根据司机的工作班制要求，司机工作时间不能超过规定的最长时间.

2 算法设计

2.1 算法总体设计

迭代局部搜索算法是一种基于邻域搜索的元启发算法，具有简单有效、易于与其他算法混合等优点.本文设计的混合元启发算法在多启动的ILS算法框架内，从初始解出发，迭代地应用局部搜索算子、破坏重建扰动进行解的改进，并记录发现的可行班次链的集合；然后，根据记录的班次链集合构造SCP模型进行全局寻优.算法的基本流程如图1所示.

由图1可知，本文算法包含以下3部分：

(1)初始解构造.

根据任务班次、司机班制及约束条件，建立以车辆数为目标的车辆调度模型，得到仅满足司机休息时间的非可行解.

(2)解的改进.

迭代地应用单班次移动、双班次移动、班次链交叉及合并等局部搜索算子对当前解进行调整，尝试将非可行解调整为可行解，并降低排班成本.同时，记录搜索过程中发现的所有可行的班次链集合.局部搜索完成后，使用破坏重建的方法进行扰动.

(3)SCP模型全局寻优.

根据记录的可行班次链集合，建立SCP模型并求解，选择更优的班次链组合.

图1 算法流程图Fig.1 Algorithm work flow diagram

2.2 初始解构造

由于同时考虑车辆调度和司机排班2个问题，因此直接获得问题的初始解非常困难.为此，本文先建立1个以车辆数最少为主要优化目标的车辆调度模型(Bus Scheduling Problem,BSP)，通过模型求解获得1个仅满足司机休息时间且车辆数最少的初始非可行解.该初始解可以在后续的局部搜索过程中逐渐调整为满足司机排班要求的可行解.

令D={d1,d2,…,dl}、V={v1,v2,…,vn}分别表示停车场和所有班次的集合；ti为班次i的运行时间；tij为班次i与j的时间间隔；tmin为班次间的最小休息时间；Ni为班次i执行完毕后可继续执行的班次任务集合，即Ni={j|j∈V,tij≥tmin}.由此，建立的车辆调度模型(BSP)为

式中：xki，xik和xij为决策变量，xki表示某辆车是否从停车场k出发去执行班次i；xik表示某辆车完成班次i后是否回到停车场k；xij表示某辆车执行班次i后是否接着执行班次j.

目标函数式(1)是最小化所需车辆数和司机休息时间，前者表示车辆数目，参数M是一个足够大的正整数，M取值较大，能够保证模型求解时车辆数最少；后者是车辆执行班次任务间的休息时间，参数ε是一个很小的随机扰动量，使模型多次求解结果有一定的差异.约束条件：式(2)要求每个班次j仅被某车辆访问1次；式(3)要求某车辆完成班次j后必须去执行下一个任务或回到停车场.

2.3 局部搜索

基于初始解提供的班次链集合，迭代地使用邻域算子对其进行改进.改进过程中，将满足司机的最少休息时间、最少就餐时间和班制的最长工作时间等约束的班次链集合认为是可行解，同时尽可能地降低排班的总成本.

本文设计了4种邻域搜索算子在班次链间进行调整，定义如下：

(1)单班次移动.将1个班次链中的某个班次删除，插入到另一个班次链中.

(2)双班次移动.将1个班次链中2个相邻的班次删除，插入到另外一个班次链中.

(3)班次链交叉.将2个班次链分别从某个位置截断，然后再将断开的班次链进行交叉组合.

(4)班次链合并.将2个班次链合并生成1个新的班次链.

假设班次链b1和b2的表示形式为0-a-b-c-d-s和0-u-v-w-s，其中0和s表示出发和停止车场；这4种邻域搜索算子的操作示意如表1所示.

表1 邻域算子操作示意Table 1 Example of neighborhood operators

在局部搜索过程中，迭代地依次调用单班次移动、双班次移动、班次链交叉和班次链合并这4种局部搜索算子.每个算子执行过程中，优先将不可行的班次链调整为可行的班次链，其次再调整班次链降低其成本.同时，记录局部搜索过程中发现的所有可行班次链.

2.4 破坏重建扰动

为了避免局部搜索算法陷入局部最优，通常在局部搜索算法中引入扰动机制.本文采用破坏重建的扰动方法，即对当前局部最优的班次链集合进行破坏而后再重建的方式，扩大搜索空间，尝试发现更优的班次链集合.本文设计2种破坏重建方法：①随机选择班次链集合中1个不可行的班次链，将其截断为2个班次链，并保证这2个班次链都是可行的.这种方法需要增加1辆车生成1条新的班次链.②随机选择2个班次链的2个随机位置将其截断，而后再将截断的班次链片段交叉重组得到2个新的班次链.这2种方法在扰动阶段随机选择其中1种执行.

2.5 SCP模型改进

局部搜索算法具有天生的“短视”局限，且搜索过程中仅记录当前最优解.为充分利用算法所探索过的解空间，可采用集合覆盖问题(SCP)模型从全局的角度选择全局最优解.基本思路是：根据局部搜索过程中所发现的可行班次链集合，从历史班次链中寻找最优的班次链组合.令集合Ω={b1,b2,…,bn}为局部搜索过程中发现的所有可行班次链集合，班次链bi满足车辆调度和司机排班的约束条件，其成本为ci.定义决策变量xi，当xi=1，表示班次链bi包含在问题的解中；否则，xi=0.由此，建立的SCP模型为

目标函数式(5)用于选择成本最低的班次链组合；约束条件式(6)保证班次集合中每一个班次均被所选择的某个班次链覆盖；约束式(7)限定了决策变量xi的取值.

根据建立的SCP模型，然后使用优化工具求解该模型，并将模型求解的结果作为算法最终的全局最优解.

3 实验与分析

本文算法使用Python 2.7实现，测试环境为PC机，配置为core i7-6 700 3.40GHz，8G内存、Windows 10、64位操作系统.BSP模型和SCP模型采用PuLP模型工具创建，并使用CBC 2.9进行求解.BSP模型中，M=106,|ε|≤0.001；限定SCP模型求解时间不超过200 s.算法的参数设置如下：Mstart=10、Niter=1 500.算法使用排班参数判断班次链是否可行，排班参数及其取值为：司机最短休息时间为4 min(tmin=4)；司机最短就餐时间为30 min，且仅在上行出发站就餐；正常班制最长工作时间为8.5 h(510 min)；长班班制最长工作时间为11 h(tlong=660min).考虑到算法的随机性，约定每个案例运行10次.

3.1 测试案例

测试案例选择国内某城市的13条公交线路的运行时刻表，均为双向发车线路.案例的基本描述如表2所示.

3.2 实验结果

针对每个案例，分别使用本文设计的算法(记做ILS-SCP)和去掉SCP模型改进的迭代局部搜索算法(ILS)进行求解.统计结果如表3所示，黑体部分表示ILS-SCP相对于ILS算法有所改进.

表2 测试案例基本描述Table 2 Description of benchmarks

表3 2种算法的运算结果比较Table 3 Comparison of the best solution obtained by two algorithms

由表3可知：应用了SCP模型的ILS-SCP算法比ILS算法具有更好的寻优能力.ILS-SCP算法的总车辆数和总司机数为219辆和327人，比ILS算法分别少了2辆车和2位司机；而在司机总的工作时间上，比ILS算法减少了1 890 min.由于车辆数和司机数量是排班方案中的主要优化目标，因此ILS-SCP算法能够更好地降低司机排班的总成本.从执行时间上来看，ILS-SCP算法因为增加了SCP模型，使得整体算法的运算时间有所增加.

为了验证本文算法的有效性，将算法的排班结果和某公交企业的实际排班结果进行比较.由于实际排班方案中，大部分司机工作时间通常在12 h以上，因此将本文算法在最长工作时间为12 h时的排班方案与实际排班方案进行比较.统计结果如表4所示，其中NR、DR为实际车辆数和司机数，NA、DA为本算法规划的结果.

由表4的结果可知，当司机最长工作时间限定为12 h时，本文算法在13个案例上所需的总车辆数和总司机人数为219辆和319人，比实际方案的总车辆数和总司机数减少了0.9%和10.1%.当司机最长工作时间降低到11 h时，本文算法排班的车辆数和司机数量为219辆和327人(表2)，仍然优于实际的排班方案.与实际排班方案相比，本文所提算法在严格满足司机休息时间和工作时长的约束下，能够减少公交线路所需的车辆数和司机数，进而减轻司机的工作负担.

表4 算法排班与实际排班的结果比较Table 4 Comparison of two bus and drivers scheduling plans

4 结论

本文研究了人车绑定管理模式下的司机排班问题，同时考虑了车辆调度和司机排班的总成本，并设计迭代局部搜索和SCP模型混合的元启发算法进行求解.实验结果表明，混合SCP算法能够在严格满足司机休息时间、工作时间等约束下，在增加少量运算时间的基础上提高算法的求解质量；并且算法排班方案优于实际排班方案.该算法将排班参数作为判定可行解的主要条件，通过设置合适的排班参数就能够适应实际企业灵活多样的排班管理需求.由于本文算法仅考虑单条线路的司机排班问题，因此如何将本文算法扩展到求解跨线运营的公交司机排班问题将是下一步的研究方向.

[1]PINE NIEMEYER J,CHISHOLM R.Transit scheduling:basic and advanced manuals[M].Washington:Transportation Research Board,1998.

[2]CEDER A.Transit scheduling[J].Journal of Advanced Transportation,1991,25(2):137-160.

[3]GUIHAIRE V,HAO J.Transit network design and scheduling:A global review[J].Transportation Research Part A-Policy and Practice,2008,42(10):1251-1273.

[4]IBARRAROJAS 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(2015):38-75.

[5]LOURENCO H R,PAIXAO J M,PORTUGAL R,et al.Multiobjective metaheuristics for the bus driver scheduling problem[J].Transportation Science,2001,35(3):331-343.

[6]DE LEONE R,FESTA P,MARCHITTO E,et al.A bus driver scheduling problem:A new mathematical model and a GRASP approximate solution[J].Journal of Heuristics,2011,17(4):441-466.

[7]LIN D,HSU C.A column generation algorithm for the bus driver scheduling problem[J].Journal of Advanced Transportation,2016,50(8):1598-1615.

[8]MESQUITA M,MOZM,PAIAA,etal.A decomposition approach for the integrated vehicle-crew-roster problem with days-off pattern[J].European Journal of Operational Research,2013,229(2):318-331.

[9]VALOUXIS C,HOUSOS E.Combined bus and driver scheduling[J].Computers&Operations Research,2002,29(3):243-259.

[10]王鹏飞.智能公交车辆人员排班算法的研究与应用[D].济南:山东大学,2006.[WANG P F.Research on intelligent bus driver scheduling problem optimization algorithm[D].Jinan:Shandong University,2006.]

[11]陈程.基于多目标优化算法的公交车辆调度研究[D].北京：北京邮电大学,2014.[CHEN C.The research on vehicle scheduling problem based on multi-objective optimization algorithms[D].Beijing:Beijing University of Posts and Telecommunications,2014.]

[12]陈明明,牛惠民.多车场公交乘务排班问题优化[J].交通运输系统工程与信息,2013,13(5):159-166.[CHEN M M,NIU H M.An optimization model for bus crew scheduling with multiple depots[C].Journal of Transportation Systems Engineering and Information Technology,2013,13(5):159-166.]

[13]魏金丽,郭亚娟,张萌萌.基于集合覆盖理论的公交线路驾驶员排班优化方法[J].公路交通科技,2016,33(1):125-129.[WEI J L,GUO Y J,ZHANG M M.A method of optimizing work schedule of bus drivers based on set covering theory[J].Journal of Highway and Transportation Research and Development,2016,33(1):125-129.]

[14]王森磊.基于生成与选择模式的公交驾驶员排班问题研究[D].北京：北京交通大学,2016.[WANG S L.The research on bus driver scheduling problem based on the pattern of generation and selection[D].Beijing:Beijing Jiaotong University,2016.]

[15]刘涛.公交驾驶员排班与轮班问题的模型与算法研究[D].北京:北京交通大学,2013.[LIU T.Models and algorithms for bus driver run cutting and rostering[D].Beijing:Beijing Jiaotong University,2013.]

[16]陈明明.城市公共交通乘务调度优化理论和方法[D].兰州：兰州交通大学,2016.[CHEN M M.Theory and method for crew scheduling problem of urban public transport[D].Lanzhou:Lanzhou Jiaotong University,2016.]