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

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

Abstract

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

CLC Number:

U491.17

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

Figures/Tables 7

References 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]	HUANG Yakui, LI Bo, KANG Yang, DAI Yuhong, LIU Jianjun. A mixed integer model and an algorithm for steady-state gas network optimization [J]. Operations Research Transactions, 2017, 21(2): 13-23.
[2]	JING Caixia, ZHAO Congli, YUAN Erming. A review of re-entrant scheduling problems [J]. Operations Research Transactions, 2015, 19(2): 37-44.

A survey on driver scheduling in public transportation

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 73

Related Articles 2

Recommended Articles

Metrics

Comments