公共交通驾驶员调度研究综述

doi:10.15960/j.cnki.issn.1007-6093.2021.01.001

摘要/Abstract

摘要：

公共交通驾驶员调度是公共交通运营企业必不可少的核心业务之一，自20世纪60年代起就受到企业界和学术界的广泛重视，并且一直是公共交通研究领域的热点课题之一。首先阐述驾驶员调度问题与数学模型；然后对现有的驾驶员调度研究成果进行归纳分析，总结出主要求解模式，并且根据驾驶员调度问题研究的历史发展，对驾驶员调度方法进行综述；最后展望未来的趋势和研究方向。

关键词: 驾驶员调度, 公共交通, 整数规划, 智能优化, 综述

Abstract:

Driver scheduling is one of the indispensable core businesses in public transportation system. The driver scheduling problem has attracted much research interests and a large amount of scheduling approaches have been developed since the 1960s. This paper first introduces the driver scheduling problem and its common mathematical model; then, two kinds of solution modes are summarized whilst an overview of driver scheduling approaches are reported; finally, future research trends and directions are suggested.

Key words: driver scheduling, public transportation, integer linear programming, intelligent optimization, review

中图分类号:

U491.17

沈吟东, 钱壮, 李媛媛. 公共交通驾驶员调度研究综述[J]. 运筹学学报, 2021, 25(1): 1-16.

Yindong SHEN, Zhuang QIAN, Yuanyuan LI. A survey on driver scheduling in public transportation[J]. Operations Research Transactions, 2021, 25(1): 1-16.

图/表 7

图1

图2

图3

图4

表1

图5

图6

参考文献 73

1	Sui Y , Shao F , Yu X , et al. Public transport network model based on layer operations[J]. Physica A: Statistical Mechanics and its Applications, 2019, doi: 10.1016/j.physa.2019.04.269
2	Ibarra-Rojas O J , Delgado F , Giesen R , et al. Planning, operation, and control of bus transport systems: A literature review[J]. Transportation Research, 2015, 77B (jul.): 38- 75.
3	Wren A. A review of computer scheduling of buses and crews[C]//Proceedings of a PTRC seminar Birkbeck College London, 1968: 42-47.
4	Hickman M , Mirchandani P , Voß S . Computer-Aided Systems in Public Transport[M]. Berlin: Springer, 2008.
5	王森磊. 基于生成与选择模式的公交驾驶员排班问题研究[D]. 北京: 北京交通大学, 2016.
6	Kwan RSK . Case studies of successful train crew scheduling optimization[J]. Journal of Scheduling, 2011, 14 (5): 423- 434. doi: 10.1007/s10951-010-0212-y
7	Jütte S , Thonemann UW . Divide-and-price: A decomposition algorithm for solving large railway crew scheduling problems[J]. European Journal of Operational Research, 2012, 219 (2): 214- 223. doi: 10.1016/j.ejor.2011.12.038
8	Cavique I , Rego C , Themido I . Subgraph ejection chains and tabu search for the crew scheduling problem[J]. Journal of the Operational Research Society, 1999, 50 (6): 608- 616. doi: 10.1057/palgrave.jors.2600728
9	Silva GP , Reis AFDS . A study of different metaheuristics to solve the urban transit crew scheduling problem[J]. Journal of Transport Literature, 2014, 8 (4): 227- 251. doi: 10.1590/2238-1031.jtl.v8n4a9
10	Peng K , Shen Y . A variable iterated greedy algorithm based on grey relation analysis for crew scheduling[J]. Scientia Iranica, 2018, 25 (2): 831- 840.
11	Kwan R S K , Kwan A . Effective search space control for large and/or complex driver scheduling problems[J]. Annals of Operations Research, 2007, 155 (1): 417- 435. doi: 10.1007/s10479-007-0203-3
12	Kang L , Chen S , Meng Q . Bus and driver scheduling with mealtime windows for a single public bus route[J]. Transportation Research, 2019, 101, 145- 160.
13	Desrochers M, Gilbert J, Michel Sauvé, et al. CREW-OPT: subproblem modeling in a column generation approach to urban crew scheduling[M]//Computer-Aided Transit Scheduling, Heidelberg: Springer, 1992.
14	Shen Y , Peng K , Chen K , et al. Evolutionary crew scheduling with adaptive chromosomes[J]. Transportation Research Part B, 2013, 56 (56): 174- 185.
15	Shen Y , Li J , Peng K . An estimation of distribution algorithm for public transport driver scheduling[J]. International Journal of Operational Research, 2017, 28 (2): 245- 262. doi: 10.1504/IJOR.2017.081483
16	Peng K , Shen Y . An evolutionary algorithm based on grey relational analysis for crew scheduling[J]. Journal of Grey System, 2016, 28 (3): 75- 88.
17	Elias S E G. The use of digital computers in the economic scheduling for both man and machine in public transportation[R]. Manhattan: Kansas State University Bulletin, 1964.
18	Parker M E, Smith B M. Two approaches to computer crew scheduling[M]//Computer Scheduling of Public Transport, North-Holland, 1981: 193-221.
19	Elias S E G. A mathematical model for optimising the assignment of man and machine in public transit "run-cutting"[R]. West Virginia University Engineering Experiment Station, 1966.
20	Smith B M . IMPACS-a bus crew scheduling system using linear programming[J]. Mathematical Programming, 1988, 42, 181- 187. doi: 10.1007/BF01589402
21	Rousseau J M, Desrochers M. Results obtained with CREW-Opt: a column generation method for transit crew scheduling[C]// Computer-Aided Transit Scheduling, New York: Springer Verlag, 1995, 349-358.
22	Kwan R S K. Bus and train driver scheduling[M]//Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Florida: CRC Press, 2004, 51.1-51.5.
23	Ernst A T , Jiang H , Krishnamoorthy M , et al. An integrated optimization model for train crew management[J]. Annals of Operations Research, 2001, 108 (1-4): 211- 224.
24	Zhao L , Wren A , Kwan R S K . Development of a driver duty estimator[J]. The Journal of the Operational Research Society, 1995, 46 (9): 1102- 1110. doi: 10.1057/jors.1995.154
25	Layfield C J. A constraint programming pre-processor for duty scheduling[D]. Leeds: University of Leeds, 2002.
26	Caprara A , Toth P , Fischetti M . Algorithms for the set covering problem[J]. Annals of Operations Research, 2000, 98 (1-4): 353- 371.
27	Willers W P , Proll L G , Wren A . A dual strategy for solving the linear programming relaxation of a driver scheduling system[J]. Annals of Operations Research, 1995, 58, 519- 531. doi: 10.1007/BF02057161
28	Desrochers M , Soumis F . A column generation approach to the urban transit crew scheduling problem[J]. Transportation Science, 1989, 23 (1): 1- 13. doi: 10.1287/trsc.23.1.1
29	Shen Y , Chen S . A column generation algorithm for crew scheduling with multiple additional constraints[J]. Pacific Journal of Optimization, 2014, 10 (1): 113- 136.
30	Saddoune M , Desaulniers G , Elhallaoui I , et al. Integrated airline crew pairing and crew assignment by dynamic constraint aggregation[J]. Transportation Science, 2012, 46 (1): 39- 55. doi: 10.1287/trsc.1110.0379
31	沈吟东, 倪郁东. 列生成法及其在大规模驾驶员调度中的应用[C]//Proceedings of the 27th Chinese Control Conference, 2008: 468-472.
32	Kim J , Jung S , Lee S . Revisiting on the problems of crew scheduling[J]. International Journal of Transportation, 2017, 5 (2): 55- 64. doi: 10.14257/ijt.2017.5.2.05
33	Barnhart C , Johnson E L , Nemhauser G L , et al. Branch-and-price: A column generation for solving huge integer programs[J]. Operations Research, 1998, 46 (3): 316. doi: 10.1287/opre.46.3.316
34	Lübbecke M E , Desrosiers J . Selected topics in column generation[J]. Operations research, 2005, 53 (6): 1007- 1023. doi: 10.1287/opre.1050.0234
35	Fores S. Column generation approaches to bus driver scheduling[D]. Leeds: University of Leeds, 1996.
36	Chen S , Shen Y . An improved column generation algorithm for crew scheduling problems[J]. Journal of Information and Computational Science, 2013, 10 (1): 175- 183.
37	陈仕军, 沈吟东. 加速列生成法求解乘务调度问题[J]. 交通运输系统工程与信息, 2014, 14 (1): 144- 149, 179. doi: 10.3969/j.issn.1009-6744.2014.01.023
38	Gondzio J , González-Brevis P , Munari P . New developments in the primal-dual column generation technique[J]. European journal of operational research, 2013, 224 (1): 41- 51. doi: 10.1016/j.ejor.2012.07.024
39	Briant O , Lemaréchal C , Meurdesoif P , et al. Comparison of bundle and classical column generation[J]. Mathematical Programming, 2008, 113 (2): 299- 344. doi: 10.1007/s10107-006-0079-z
40	Amor H B , Desrosiers J , Frangioni A . On the choice of explicit stabilizing terms in column generation[J]. Discrete Applied Mathematics, 2009, 157 (6): 1167- 1184. doi: 10.1016/j.dam.2008.06.021
41	Tahir A , Desaulniers G , Hallaoui I E . Integral column generation for the set partitioning problem[J]. EURO Journal on Transportation and Logs, 2019, 8.
42	许仲豪, 杜鹏. 基于列生成的城市轨道交通乘务计划优化编制方法研究[J]. 铁道学报, 2019, 41 (3): 25- 32. doi: 10.3969/j.issn.1001-8360.2019.03.004
43	Fores S , Proll L , Wren A . TRACS Ⅱ: a hybrid IP/heuristic driver scheduling system for public transport[J]. Journal of the Operational Research Society, 2002, 53 (10): 1093- 1100. doi: 10.1057/palgrave.jors.2601271
44	Steinzen I , Suhl L , Kliewer N . Branching strategies to improve regularity of crew schedules in ex-urban public transit[J]. OR Spectrum, 2009, 31 (4): 727- 743. doi: 10.1007/s00291-008-0136-5
45	Berthold T , Salvagnin D . Cloud branching[J]. Lecture Notes in Computer Science, 2013, 7874, 28- 43.
46	王凌. 智能优化算法及其应用[M]. 北京: 清华大学出版社, 2001.
47	汪定伟, 王俊伟, 王洪峰, 等. 智能优化方法[M]. 北京: 高等教育出版社, 2007.
48	Boussaïd I , Lepagnot J , Siarry P . A survey on optimization metaheuristics[J]. Information Sciences, 2013, 237, 82- 117. doi: 10.1016/j.ins.2013.02.041
49	Shen Y, Kwan R S K. A constructive approach to bus and train driver scheduling[C]//Proceedings of the ⅡE Annual Conference, May 20-23, 2001.
50	Shen Y. Tabu search for bus and train driver scheduling with time windows[D]. Leeds: University of Leeds, 2001.
51	Shen Y, Ni Y. Modeling and solving the public transport driver scheduling problem with time windows[C]//Proceedings of the 24th Chinese Control Conference (International), 2005: 451-456.
52	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. doi: 10.1111/j.1475-3995.2009.00673.x
53	Yaghini M , Karimi M , Rahbar M . A set covering approach for multi-depot train driver scheduling[J]. Journal of Combinatorial Optimization, 2015, 29 (3): 636- 654. doi: 10.1007/s10878-013-9612-1
54	Kokubo T, Fukuyama Y. Practical train crew scheduling problems using parallel tabu search[C]//2018 57th Annual Conference of the Society of Instrument and Control Engineers of Japan (SICE), 2018.
55	Kokubo T, Fukuyama Y. Generation methods of neighborhood schedules for practical train crew scheduling problems using tabu search[C]//2017 IEEE 10th International Workshop on Computational Intelligence and Applications (IWCIA), 2017.
56	Forsyth P, Wren A. An ant system for driver scheduling[R] Leeds: School of Computing, University of Leeds, 1997.
57	Azadeh A , Farahani M H , Eivazy H , et al. A hybrid meta-heuristic algorithm for optimization of crew scheduling[J]. Applied Soft Computing, 2013, 13 (1): 158- 164. doi: 10.1016/j.asoc.2012.08.012
58	Ma J H , Song C Y , Ceder A , et al. Fairness in optimizing bus-crew scheduling process[J]. PLoS One, 2017, 12 (11): e0187623. doi: 10.1371/journal.pone.0187623
59	García J , Altimiras F , Penna A , et al. A binary Cuckoo search big data algorithm applied to large-scale crew scheduling problems[J]. Complexity, 2018, 2018, 1- 15.
60	Mladenovic N , Hansen P . Variable neighborhood search[J]. Computers & Operations Research, 1997, 24 (11): 1097- 1100.
61	Hansen P , Mladenovic N Moreno P , et al. Variable neighborhood search: methods and applications[J]. Annals of Operations Research, 2010, 175 (1): 367- 407. doi: 10.1007/s10479-009-0657-6
62	Peng K K , Shen Y D . Variable neighbourhood search for public transport crew scheduling[J]. Journal of Transportation Systems Engineering & Information Technology, 2017, 17 (1): 164- 170.
63	Wren A , Wren DO . A genetic algorithm for public transport driver scheduling[J]. Computers & Operations Research, 1995, 22 (1): 101- 110.
64	Luis F. González Hernández, Corne D W. Evolutionary divide and conquer for the set-covering problem[C]//Evolutionary Computing, AISB Workshop, Heidelberg: Springer, 1996.
65	Dias T G , De Sousa J P , Cunha J F . Genetic algorithms for the bus driver scheduling problem: a case study[J]. Journal of the Operational Research Society, 2002, 53 (3): 324- 335. doi: 10.1057/palgrave.jors.2601312
66	Khmeleva E , Hopgood A A , Tipi L , et al. Fuzzy-logic controlled genetic algorithm for the rail-freight crew-scheduling problem[J]. Technical Contribution, 2018, 32, 61- 75.
67	Lourenço HR , Paixao JP , Portugal R . Multiobjective metaheuristics for the bus-driver scheduling problem[J]. Transportation Science, 2001, 35 (3): 331- 343. doi: 10.1287/trsc.35.3.331.10147
68	Kwan RSK, Wren A, Kwan ASK. Hybrid genetic algorithms for scheduling bus and train drivers[C]//Proceedings of the 2000 congress on evolutionary computation, 2000: 285-292.
69	Li J , Kwan R S K . A fuzzy genetic algorithm for driver scheduling[J]. European Journal of Operational Research, 2003, 147 (2): 334- 344. doi: 10.1016/S0377-2217(02)00564-7
70	Pelikan M, Goldberg D E. BOA: the Bayesian optimization algorithm[C]//Conference on Genetic and Evolutionary Computation, San Francisco: Morgan Kaufmann Publishers Inc, 1999: 525-532.
71	Mauri G R , Lorena L A N . A new hybrid heuristic for driver scheduling[J]. International Journal of Hybrid Intelligent Systems, 2007, 4 (1): 39- 47. doi: 10.3233/HIS-2007-4105
72	Elizondo R , Parada V , Pradenas L , et al. An evolutionary and constructive approach to a crew scheduling problem in underground passenger transport[J]. Journal of Heuristics, 2010, 16 (4): 575- 591. doi: 10.1007/s10732-009-9102-x
73	Aickelin U , Burke EK , Li J . An evolutionary squeaky wheel optimization approach to personnel scheduling[J]. IEEE Transactions on Evolutionary Computation, 2009, 13 (2): 433- 443. doi: 10.1109/TEVC.2008.2004262

作者(出版年)	求解模式	方法	数据来源
Kang L等(2019)	生成与选择	传统整数规划方法	实例
Tahir A等(2019)	生成与选择	基于列生成的方法	测试数据集
许仲豪和杜鹏(2019)	生成与选择	基于列生成的方法	实例
Ma JH等(2018)	生成与选择	混合蚁群算法	实例
Kokubo T 和Fukuyama Y (2018)	构造型	并行禁忌搜索	实例
Khmeleva E等(2018)	生成与选择	遗传算法	实例
彭琨琨和沈吟东(2018)	生成与选择	基于灰关联分析的贪婪迭代算法	实例
José García等(2018)	生成与选择	二进制布谷鸟算法	测试数据集
Kokubo T 和Fukuyama Y(2017)	构造型	禁忌搜索	实例
沈吟东等(2017)	生成与选择	分布估计算法	实例
彭琨琨和沈吟东(2017)	生成与选择	变邻域搜索	实例
彭琨琨和沈吟东(2016)	生成与选择	基于灰色关联分析的进化算法	实例
Yaghini M等(2015)	生成与选择	禁忌搜索	测试数据集

[1]	赵丹, 高岳林. 非线性整数规划问题的无参数填充函数算法[J]. 运筹学学报, 2020, 24(4): 63-73.
[2]	郑宇军, 吴晨昕, 陈恩富, 卢雪琴, 张敏霞. 新冠肺炎疫情条件下的企业复工复产优化规划方法[J]. 运筹学学报, 2020, 24(3): 43-56.
[3]	杨沐明, 黄亚魁, 戴彧虹. 一类多商品设施选址问题的基于线性松弛解的启发式方法[J]. 运筹学学报, 2019, 23(3): 15-26.
[4]	陈薪蓓, 朱明康, 陈建利. 基于迭代投影的梯度硬阈值追踪算法[J]. 运筹学学报, 2019, 23(1): 1-14.
[5]	朱征露, 鲁习文. 带学习效应的两台平行机时间表长问题[J]. 运筹学学报, 2018, 22(1): 55-66.
[6]	吴佩佩, 高岳林. 一个新的非线性整数规划问题的单参数填充函数算法[J]. 运筹学学报, 2017, 21(3): 111-118.
[7]	董振宇, 冯恩民, 尹洪超, 张誉铎. 国际原油价格预测的双层随机整数规划模型、算法及应用[J]. 运筹学学报, 2015, 19(3): 18-25.
[8]	井彩霞, 赵聪俐, 袁二明. 重入排序问题综述[J]. 运筹学学报, 2015, 19(2): 37-44.
[9]	何胜学. 无预警紧急疏散中公交车辆路径的确定方法[J]. 运筹学学报, 2014, 18(3): 47-59.
[10]	孙小玲，李端. 整数规划新进展[J]. 运筹学学报, 2014, 18(1): 39-68.
[11]	孙小玲, 白晓迪, 郑小金. 概率约束最优化问题[J]. 运筹学学报, 2012, 16(3): 65-74.
[12]	田静, 吴至友, J. Ugon. 一类特殊多项式整数规划问题的最优化算法[J]. 运筹学学报, 2011, 15(4): 23-35.