Optimal driver scheduling with evolutionary approach in urban public transport

Adam Redmer; Piotr Kisielewski; Jacek Obłaza

doi:10.61089/aot2025.919ryp91

Authors

Adam Redmer Faculty of Civil and Transport Engineering, Poznan University of Technology, Poznan, Poland Author https://orcid.org/0000-0003-2154-232X
Piotr Kisielewski Faculty of Mechanical Engineering, Cracow University of Technology, Cracow, Poland Author https://orcid.org/0000-0003-0013-5477
Jacek Obłaza DPK System Co. Ltd, Wieliczka, Poland Author https://orcid.org/0009-0009-0896-035X

DOI:

https://doi.org/10.61089/aot2025.919ryp91

Keywords:

bus public transport, crew scheduling problem, heuristics

Abstract

The optimal vehicle (VSP) and crew (CSP) scheduling problems solving in urban public transportation involves assigning timetabled trips to daily vehicle tasks, called blocks, and next to daily driver tasks, called duties. The aim is to minimize the number of vehicles and drivers. This maximizes usage of the both assets, makes the schedules more convenient for vehicle operations and drivers, and as a result mitigates possible delays, and fits into the legal requirements for the drivers' working time. The scheduling can be done either sequentially or simultaneously. In the former, vehicles are scheduled first, then drivers based on an already constructed vehicle blocks. Whereas in the latter, vehicles and drivers are scheduled at the same time, thus integrated (VCSP). As for the solution methods for the VCSP the Evolutionary Algorithms (EA) play a crucial role in addressing this complex challenge. Moreover, recent publications point out that metaheuristics, in particular the EA, are widely and successfully used in both the sequential and simultaneous solution approaches. The integrated scheduling of vehicles and rivers requires much longer computational time, which often cannot be accepted in practice for the VSP and CSP are usually solved separately by different institutions, i.e., the public transport authority (PTA) and the public transport operator (PTO), respectively. Alternatively, in the sequential approach, that is less computationally demanding, the influence of a solution of the VSP on a solution of the CSP can also be included. To solve sequentially the CSP taking into account an already solved the VSP and its characteristics (e.g., multiple depots, electric vehicles (EVs)), a specific and original EA is proposed in this paper. The algorithm divides vehicle blocks into pieces of work to be assigned to drivers’ duties. The pieces of work can be composed of the entire vehicle blocks as well as their parts, for the algorithm can divide them according to a set of proposed rules. The algorithm was tested on a real-world databases of public transport systems of the three large Polish cities. The results were compared with those obtained manually by a team of experienced transport planners. The crew schedules obtained using the algorithm were comparable or even better than those prepared manually and reached within significantly shorter time.

References

1. Amberg, B. & Amberg, B. (2023). Robust and cost-efficient integrated multiple depot vehicle and crew scheduling with controlled trip shifting. Transportation Science. 57(1), 82-105. https://doi.org/10.1287/trsc.2022.1154.

2. Andrade-Michel, A., Ríos-Solís, Y.A. & Boyer, V. (2021). Vehicle and reliable driver scheduling for public bus transportation systems. Transportation Research Part B. 145, 290-301. https://doi.org/10.1016/j.trb.2021.01.011.

3. Beasley, J.E. & Cao, B. (1996). A tree search algorithm for the crew scheduling problem. European Journal of Operational Research, 94(3), 517-526.

4. Boyer, V., Ibarra-Rojas, O.J. & Ríos-Solís, Y.Á. (2018). Vehicle and crew scheduling for flexible bus transportation systems. Transportation Research Part B. 112, 216-229. https://doi.org/10.1016/j.trb.2018.04.008.

5. Duda, J., Fierek, S., Karkula, M., Kisielewski, P., Puka, R., Redmer, A. & Skalna, I. (2022). Multi-objective optimization model for multi-depot mixed fleet electric vehicle scheduling problem with real world constraints. Transport Problems. 17(4), 137-149. https://doi.org/10.20858/tp.2022.17.4.12.

6. Esquivel-González, G., Sedeño-Noda, A. & León, G. (2023). The problem of assigning bus drivers to trips in a Spanish public transport company. Engineering Optimization. 55(9), 1597-1615. https://doi.org/10.1080/0305215X.2022.2102165.

7. Freling, R., Huisman, D. & Wagelmans, A.P.M. (2003). Models and algorithms for integration of vehicle and crew scheduling. Journal of Scheduling. 6, 63-85. https://doi.org/10.1023/A:1022287504028.

8. Ge, L., Kliewer, N., Nourmohammadzadeh, A., Voß, S. & Xie, L. (2024). Revisiting the richness of integrated vehicle and crew scheduling. Public Transport. 16, 775-801. https://doi.org/10.1007/s12469-022-00292-6.

9. Kisielewski, P. (2019). Computer-aided planning of city public transport. Publishing House of Warsaw University of Technology, Warsaw, Poland (in Polish).

10. Kletzander, L. & Musliu, N. (2020). Solving large real-life bus driver scheduling problems with complex break constraints. Proceedings of the International Conference on Automated Planning and Scheduling. 30(1), 421-429. https://ojs.aaai.org/index.php/ICAPS/article/view/6688.

11. Liu, T., Ji, W., Gkiotsalitis, K. & Cats, O. (2023). Optimizing public transport transfers by integrating timetable coordination and vehicle scheduling. Computers & Industrial Engineering. 184, 109577. https://doi.org/10.1016/j.cie.2023.109577.

12. Mertens, L., Amberg, B. & Kliewer, N. (2024). Integrated bus timetabling and scheduling with a mutation-based evolutionary scheme maximizing headway quality and connections. Operational Research Forum. 5, 25. https://doi.org/10.1007/s43069-024-00296-x.

13. Mertens, L., Wolbeck, L.-A., Rößler, D., Xie, L., & Kliewer, N. (2023). An overview of optimization approaches for scheduling and rostering resources in public transportation. Industrial Engineering & Business Information Systems. arXiv e-prints: 2310.13425. https://doi.org/10.48550/arXiv.2310.13425.

14. Öztop, H., Eliiyi, U., Eliiy, D. & Kandiller, L. (2017). A bus crew scheduling problem with eligibility constraints and time limitations. Transportation Research Procedia. 22, 222-231. https://doi.org/10.1016/j.trpro.2017.03.029.

15. Pan, H., Liu, Z., Yang, L., Liang, Z., Wu, Q. & Li, S. (2021). A column generation-based approach for integrated vehicle and crew scheduling on a single metro line with the fully automatic operation system by partial supervision. Transportation Research Part E. 152, 102406. https://doi.org/10.1016/j.tre.2021.102406.

16. Peña, D., Tchernykh, A., Dorronsoro, B. & Ruiz, P. (2022). A novel multi-objective optimization approach to guarantee quality of service and energy efficiency in a heterogeneous bus fleet system. Engineering Optimization. 55(6), 981-997. https://doi.org/10.1080/0305215X.2022.2055007.

17. Perumal, S.S.G., Dollevoet, T., Huisman, D., Lusby, R.M., Larsen, J. & Riis, M. (2021). Solution approaches for integrated vehicle and crew scheduling with electric buses. Computers & Operations Research. 132, 105268. https://doi.org/10.1016/j.cor.2021.105268.

18. Perumal, S.S.G., Lusby, R.M. & Larsen, J. (2022). Electric bus planning & scheduling: A review of related problems and methodologies. European Journal of Operational Research. 301(2), 395-413. https://doi.org/10.1016/j.ejor.2021.10.058.

19. Shen, Y. & Li, Y. (2023). Minimum cost flow-based integrated model for electric vehicle and crew scheduling. Journal of Advanced Transportation. 2023, 6658030. https://doi.org/10.1155/2023/6658030.

20. Simões, E.M.L., Batista, L.D.S. & Souza, M.J.F. (2021). A matheuristic algorithm for the multiple-depot vehicle and crew scheduling problem. IEEE Access. 9, 155897-155923. https://doi.org/10.1109/ACCESS.2021.3128871.

21. Sistig, H.M. & Sauer, D.U. (2023). Metaheuristic for the integrated electric vehicle and crew scheduling problem. Applied Energy. 339, 120915. https://doi.org/10.1016/j.apenergy.2023.120915.

22. Steinzen, I., Gintner, V., Suhl, L. & Kliewer, N. (2010). A time-space network approach for the integrated vehicle- and crew-scheduling problem with multiple depots. Transportation Science. 44(3), 367-382. https://doi.org/10.1287/trsc.1090.0304.

23. Tang, X., Lin, X. & He, F. (2019). Robust scheduling strategies of electric buses under stochastic traffic conditions. Transportation Research Part C. 105, 163-182. https://doi.org/10.1016/j.trc.2019.05.032.

24. Valouxis, C. & Housos, W. (2002). Combined bus and driver scheduling. Computers & Operations Research. 29(2), 243-259. https://doi.org/10.1016/S0305-0548(00)00067-8.

25. Wang, J., Wang, H., Chang, A. & Song, C. (2022). Collaborative optimization of vehicle and crew scheduling for a mixed fleet with electric and conventional buses. Sustainability. 14(6), 3627. https://doi.org/10.3390/su14063627.