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

交通运输系统工程与信息 ›› 2018, Vol. 18 ›› Issue (1): 133-138.

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

侯彦娥^{a, b}，孔云峰^{* b}，朱艳芳^b，马瑞^b

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

收稿日期:2017-11-09 修回日期:2017-12-25 出版日期:2018-02-25 发布日期:2018-02-26
作者简介:侯彦娥(1980-)，女，河南漯河人，副教授，博士.
基金资助:
国家自然科学基金/National Natural Science Foundation of China(41401461).

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

HOU Yan-e^a, b，KONG Yun-feng^b，ZHU Yan-fang ^b, MA Rui ^b

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, China

Received:2017-11-09 Revised:2017-12-25 Online:2018-02-25 Published:2018-02-26

摘要/Abstract

摘要：

针对我国公交企业中司机在1 个工作日内驾驶同一辆车的“人车绑定”管理模式，提出混合元启发算法求解司机排班问题.首先建立以车辆数为目标的车辆调度模型，获得仅满足司机休息时间的非可行解；接着迭代地使用局部搜索算子、破坏重建扰动等方法对解进行调整，使其满足司机工作时间和吃饭时间等约束，并尽可能地降低排班成本；在迭代搜索过程中记录发现的可行排班链集合，迭代结束后构建集合覆盖问题(SCP)模型对其进行改进，以获得最佳的司机排班方案.在13 条公交线路案例上进行测试，实验结果验证了本文算法的有效性.

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

Abstract:

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.

Key words: urban traffic, transit bus and driver scheduling problem, hybrid metaheuristic, set covering problem, iterated local search heuristic

中图分类号:

U121
TP301.6

侯彦娥，孔云峰，朱艳芳，马瑞. 公交司机排班问题的混合元启发算法研究[J]. 交通运输系统工程与信息, 2018, 18(1): 133-138.

HOU Yan-e，KONG Yun-feng，ZHU Yan-fang, MA Rui. A Hybrid Metaheuristic Algorithm for the Transit Bus and Driver Scheduling Problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(1): 133-138.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract19566.shtml

http://www.tseit.org.cn/CN/Y2018/V18/I1/133

参考文献

[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, MOZ M, PAIA A, et al． A decomposition approach for the integrated vehiclecrew- 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.]