Operations Research Transactions >
2021 , Vol. 25 >Issue 1: 1 - 16
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2021.01.001
A survey on driver scheduling in public transportation
Received date: 2020-06-16
Online published: 2021-03-05
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.
Yindong SHEN, Zhuang QIAN, Yuanyuan LI . A survey on driver scheduling in public transportation[J]. Operations Research Transactions, 2021 , 25(1) : 1 -16 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.001
| 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, |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 28 | Desrochers M , Soumis F . A column generation approach to the urban transit crew scheduling problem[J]. Transportation Science, 1989, 23 (1): 1- 13. |
| 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. |
| 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. |
| 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. |
| 34 | Lübbecke M E , Desrosiers J . Selected topics in column generation[J]. Operations research, 2005, 53 (6): 1007- 1023. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
/
| 〈 |
|
〉 |
