Optimization of urban transport vehicle tasks for large, mixed fleet of vehicles and real-world constraints

Piotr Kisielewski; Jerzy Duda; Marek Karkula; Iwona Skalna; Adam Redmer; Szymon Fierek

doi:10.61089/aot2024.qnwb3h25

Authors

Piotr Kisielewski Cracow University of Technology, Faculty of Mechanical Engineering, Kraków, Poland Author https://orcid.org/0000-0003-0013-5477
Jerzy Duda AGH University of Krakow, Faculty of Management, Kraków, Poland Author https://orcid.org/0000-0002-9225-7123
Marek Karkula AGH University of Krakow, Faculty of Management, Kraków, Poland Author https://orcid.org/0000-0001-9468-1529
Iwona Skalna AGH University of Krakow, Faculty of Management, Kraków, Poland Author https://orcid.org/0000-0001-5707-7525
Adam Redmer Poznan University of Technology, Faculty of Civil and Transport Engineering, Poznań, Poland Author https://orcid.org/0000-0003-2154-232X
Szymon Fierek Poznan University of Technology, Faculty of Civil and Transport Engineering, Poznań, Poland Author https://orcid.org/0000-0003-1076-2722

DOI:

https://doi.org/10.61089/aot2024.qnwb3h25

Keywords:

urban public transport, optimization of vehicle tasks, fast heuristics

Abstract

Planning the operation of urban public transport vehicles is the first stage of operational planning and consists in combining timetable tips, which are input data, into blocks that constitute the daily tasks of vehicles. For a large mixed fleet of vehicles of various types, especially those with battery power that requires recharging, operating from many depots, with numerous requirements and rolling stock constraints, the problem is a major engineering challenge, even for an experienced team of planners. IT solutions based on realistic, mathematical decision-making models and fast optimization algorithms can be of great assistance. For the problem formulated this way, a mathematical decision model with a multi-criteria objective function was built, taking into account technical, economic, and ecological criteria, natural, and binary decision variables. The model takes into account the real requirements and constraints, a mixed fleet of different types vehicles, including electric buses, multiple depots, technical trips (dead heads), and battery charging. The considered problem is an NP-hard combinatorial optimization problem. The use of classical, exact algorithms to solve this problem is not possible for schedules with many thousands of line trips and fleets of hundreds or thousands of vehicles. This research proposes an original, dedicated heuristic, enabling to obtain an acceptable, but still suboptimal solution, in a very short time. The tests of the proposed heuristic algorithm were carried out on real databases of public transport systems of the two selected medium and large Polish cities. In particular, multiple depots, a mixed fleet of different types of vehicles, and real-world constraints were taken into account. The results of computer experiments carried out using the developed heuristic were compared with the results obtained manually by a team of experienced and expert planners. For the developed multi-criteria decision-making model results comparable to and better than those prepared manually by experts were obtained in a very short time using the proposed heuristics. It is the basis for further development works on expanding the model and improving the optimization algorithm.

References

Árgilán, V., Balogh, J., Békési, J., Dávid, B., Krész, M. & Tóth, A. (2012). Driver scheduling based on “driver-friendly” vehicle schedules. In: Klatte, D., Lüthi, H.J., Schmedders, K. (eds) Operations Research Proceedings 2011. Operations Research Proceedings, 323–328, Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29210-1_52.

Bunte, S. & Kliewer, N. (2009). An overview on vehicle scheduling models. Public Transport, 1, 299–317. https://doi.org/10.1007/s12469-010-0018-5.

Chung, Y.-S. & Chiou, Y.-C. (2023). Economic characteristics of city bus operation with a mixed fleet: the influence of electric buses. Transportmetrica A: Transport Science. https://doi.org/10.1080/23249935.2023.2192308.

Ceder, A. (2007). Public Transit Planning and Operation: Theory, Modeling, and Practice. Elsevier, Butterworth-Heinemann, 1st ed.

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.

Gintner, V., Kliewer, N. & Suhl, L. (2005). Solving large multiple-depot multiple-vehicle-type bus scheduling problems in practice. OR Spectrum, 27 (4), 507–523. https://doi.org/10.1007/s00291-005-0207-9.

Hassold, S. & Ceder, A. (2014). Public transport vehicle scheduling featuring multiple vehicle types, Transportation Research Part B: Methodological, 67, 129–143. https://doi.org/10.1016/j.trb.2014.04.009.

Kisielewski, P. (2019). Computer-Aided Planning of City Public Transport. Warsaw: Publishing House of Warsaw University of Technology. (in Polish).

Mahadikar, J., Mulangi, R.H. & Sitharam, T.G. (2015). Optimization of bus allocation to depots by minimizing dead kilometers. Journal of Advanced Transportation, 49 (8), 901–912. https://doi.org/10.1002/atr.1312.

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.

Rinaldi, M., Picarelli, E., D'Ariano, A. & Viti, F. (2020). Mixed-fleet single-terminal bus scheduling problem: Modelling, solution scheme and potential applications, Omega, 96, p. 102070. https://doi.org/10.1016/j.omega.2019.05.006.

Sassi, O. & Oulamara, A. (2017). Electric vehicle scheduling and optimal charging problem: complexity, exact and heuristic approaches, International Journal of Production Research, 55 (2), 519–535. https://doi.org/10.1080/00207543.2016.1192695.

Sung, Y.-W., Chu, J.C., Chang, Y.-J., Yeh, J.-C. & Chou, Y.-H. (2022). Optimizing mix of heterogeneous buses and chargers in electric bus scheduling problems. Simulation Modelling Practice and Theory, 119, p. 102584. https://doi.org/10.1016/j.simpat.2022.102584.

Tang, C., Xue, H., Ceder, A. & Ge, Y.-E. (2023). Optimal variable vehicle scheduling strategy for a network of electric buses with fast opportunity charging, Transportmetrica A: Transport Science. https://doi.org/10.1080/23249935.2023.2182611.

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.

Vigren, A. (2020). The Distance Factor in Swedish Bus Contracts How far are operators willing to go? Transportation Research Part A: Policy and Practice, 132, 188–204. https://doi.org/10.1016/j.tra.2019.11.010.

Wang, J.-Y. & Lin, C.-K. (2010). A new model and heuristic algorithms for the multiple‐depot vehicle scheduling problem, Journal of the Chinese Institute of Engineers, 33 (2), 287–299. https://doi.org/10.1080/02533839.2010.9671618.

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.

Wen, M., Linde, E., Ropke, S., Mirchandani, P. & Larsen, A. (2016). An adaptive large neighbourhood search heuristic for the Electric Vehicle Scheduling Problem, Computers & Operations Research, 76, 73–83. https://doi.org/10.1016/j.cor.2016.06.013.

Zhang, A., Li, T., Zheng, Y., Li, X., Abdullah, M.G. & Dong, C. (2022). Mixed electric bus fleet scheduling problem with partial mixed-route and partial recharging. International Journal of Sustainable Transportation, 16 (1), 73–83. https://doi.org/10.1080/15568318.2021.1914791.