公交司机排班问题的混合元启发算法研究  

A Hybrid Metaheuristic Algorithm for the Transit Bus and Driver Scheduling Problem

作　　者：侯彦娥[1,2] 孔云峰[2] 朱艳芳[2] 马瑞[2] HOU Yan-e;KONG Yun-feng;ZHU Yan-fang;MA Rui;(a. College of Computer and Information Engineering; b. Key Laboratory of Geospatial Technology for the Middle and Lower Yellow River Regions, Ministry of Education, Henan University, Kaifeng 475004, Henan, Chin)

机构地区：[1]河南大学计算机与信息工程学院,河南开封475004 [2]河南大学黄河中下游数字地理技术教育部重点实验室,河南开封475004

出　　处：《交通运输系统工程与信息》2018年第1期133-138,共6页Journal of Transportation Systems Engineering and Information Technology

基　　金：国家自然科学基金(41401461)~~

摘　　要：针对我国公交企业中司机在1个工作日内驾驶同一辆车的"人车绑定"管理模式,提出混合元启发算法求解司机排班问题.首先建立以车辆数为目标的车辆调度模型,获得仅满足司机休息时间的非可行解;接着迭代地使用局部搜索算子、破坏重建扰动等方法对解进行调整,使其满足司机工作时间和吃饭时间等约束,并尽可能地降低排班成本;在迭代搜索过程中记录发现的可行排班链集合,迭代结束后构建集合覆盖问题(SCP)模型对其进行改进,以获得最佳的司机排班方案.在13条公交线路案例上进行测试,实验结果验证了本文算法的有效性.This paper deals with the bus and driver scheduling problem that arises from most transit companies in China where a driver should drive the same bus in the same day. A hybrid metaheuristic algorithm is proposed for the problem. Firstly, a bus schedule model with minimum number of buses is built and solved as the initial solution, which is an invalid solution just satisfying with the constraint of driver break time. Secondly, the local search operators are literately used to adjust the invalid solution to a feasible solution as well as reducing the solution cost. And then, a ruin and recreate method is introduced to expand the search space to avoid trapping into the local optimum. All the blocks of the feasible solution in the local search are also collected. Finally, a set covering problem（SCP） model tries to select global best solution from the collected historic blocks. The algorithm was tested on 13 real world instances and the results show that the proposed method is effective.

关 键 词：城市交通 公交司机排班 混合元启发算法 集合覆盖模型 迭代局部搜索算法 

分 类 号：U121[交通运输工程] TP301.6[自动化与计算机技术—计算机系统结构]