Deadhead Minimization Problem in Multi-Depot Public Transport System

Robert Szczyrbak

doi:10.7494/dmms.2021.15.7138

Authors

Robert Szczyrbak Independent scholar, Skawina, Poland https://orcid.org/0009-0007-4877-4880

DOI:

https://doi.org/10.7494/dmms.2021.15.7138

Keywords:

Vehicle Scheduling Problem, Public Transport System, Crew Rostering, Deadhead Minimization, Deadhead Kilometers, optimization, operations research

Abstract

This paper addresses a vehicle scheduling problem in the public transport system of Krakow, Poland. The primary objective is to develop and evaluate a mathematical model for assigning bus schedules to depots in a way that minimizes non-revenue (deadhead) kilometers. The proposed model, referred to as the Deadhead Minimization Problem in Multi-Depot Public Transport System (DMPMDPTS), seeks to reduce the total distance that is traveled by vehicles from their home depots to the starting points of their first scheduled routes and from the final terminals back to their depots. The model assumes fixed-route structures and known deadhead distances between terminals. Real-world data that was based on the Krakow Municipal Transport (KKM) was used to validate and verify the model. The optimization model was implemented in AMPL and solved using the GLPK Integer Optimizer (v4.43). Computational experiments were conducted across multiple cases that differed in their constraints and parameters in order to assess the model’s flexibility and performance. In all of the cases, optimal solutions were obtained in brief computation times. Compared to the existing operational schedules, the model consistently reduced deadhead kilometers. Case 1 achieved improvements without altering the numbers of vehicles per depot, while Case 2 led to further reductions of the costs of redistributing vehicles among depots, resulting in a less-balanced load structure. These findings demonstrated the model’s potential for supporting decision-making in depot allocation within public transport operations.

References

Agnetis A., Bianciardi C. & Iasparra N. (2019). Integrating lean thinking and mathematical optimization: A case study in appointment scheduling of hematological treatments. Operations Research Perspectives, 6, 100110. DOI: https://doi.org/10.1016/j.orp.2019.100110.

Borndörfer R., Hoppmann H. & Karbstein M. (2017). Passenger routing for periodic timetable optimization. Public Transport, 9, pp. 115–135. DOI: https://doi.org/10.1007/s12469-016-0132-0.

Csalódi R., Süle Z., Jaskó S., Holczinger T. & Abonyi J. (2021). Industry 4.0 driven development of optimization algorithms: A systematic overview. Complexity, 1, 6621235. DOI: https://doi.org/10.1155/2021/6621235.

Friman M. & Fellesson M. (2009). Service supply and customer satisfaction in public transportation: The quality paradox. Journal of Public Transportation, 12(4), pp. 57–69. DOI: https://doi.org/10.5038/2375-0901.12.4.4.

Gdowska K. (2018). How to assess balancing public transportation. In: 14th International Conference on Industrial Logistics, ICIL 2018 - Conference Proceedings, Ben-Gurion University of the Negev, Beer-Sheva, pp. 79–86. URL: https://in.bgu.ac.il/en/engn/iem/ICIL2018/Pages/ICIL%20conference%20proceedings%20book%202018.pdf [10.10.2021].

Gdowska K., Viana A. & Pedroso J.P. (2018). Stochastic last-mile delivery with crowdshipping. Transportation Research Procedia, 30, pp. 90–100. DOI: https://doi.org/10.1016/j.trpro.2018.09.011.

Hassannayebi E., Zegordi S.H., Yaghini M. & Amin-Naseri M.R. (2017). Timetable optimization models and methods for minimizing passenger waiting time at public transit terminals. Transportation Planning and Technology, 40(3), pp. 278–304. DOI: https://doi.org/10.1080/03081060.2017.1283156.

Iliopoulou C. & Kepaptsoglou, K. (2019). Combining ITS and optimization in public transportation planning: state of the art and future research paths. European Transport Research Review, 11, 27. DOI: https://doi.org/10.1186/s12544-019-0365-5.

Korcyl A., Ksiazek R. & Gdowska K. (2016). A milp model for route optimization problem in a municipal multi-landfill waste collection system. In: 13th International Conference on Industrial Logistics, ICIL 2016 - Conference Proceedings, AGH University of Science and Technology, Krakow, pp. 109–118. URL: http://www.icil.zarz.agh.edu.pl/images/ICIL2016/ICIL2016_conference_proceedings_final.pdf [10.10.2021].

Książek R., Gdowska K. & Korcyl A. (2021). Recyclables collection route balancing problem with heterogeneous fleet. Energies, 14(21), 7406. DOI: https://doi.org/10.3390/en14217406.

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. DOI: https://doi.org/10.1002/atr.1312.

Nasibov E., Eliiyi U., Ertaç M.Ö. & Kuvvetli Ü. (2013). Deadhead trip minimization in city bus transportation: A real life application. Promet-Traffic & Transportation, 25(2), pp. 137–145. DOI: https://doi.org/10.7307/ptt.v25i2.1289.

Shang P., Li R., Liu Z., Xian K. & Guo J. (2018). Timetable synchronization and optimization considering time-dependent passenger demand in an urban subway network. Transportation Research Record, 2672(8), pp. 243–254. DOI: https://doi.org/10.1177/0361198118772958.

Szczyrbak R. (2016). Organizacja pracy brygad autobusowych obsługujących wybrane linie w Gminie Skawina [Bachelor’s Thesis]. AGH University of Science and Technology, Kraków.

Szczyrbak R. & Gdowska K. (2017). Tworzenie brygad autobusowych jako problem harmonogramowania zadań. Logistyka, 6, pp. 58–60. URL: https://www.logistyka.net.pl/bank-wiedzy/item/91069-tworzenie-brygad-autobusowych-jako-problem-harmonogramowania-zadan [10.10.2021].

Szczyrbak R. (2018). Problem planowania brygad w sieci komunikacji aglomeracyjnej z wieloma zajezdniami na przykładzie Krakowskiej Komunikacji Miejskiej [Master’s Thesis]. AGH University of Science and Technology, Kraków.

Villarreal B., Garza-Reyes J.A. & Kumar V. (2016). A lean thinking and simulation-based approach for the improvement of routing operations. Industrial Management & Data Systems, 116(5), pp. 903–925. DOI: https://doi.org/10.1108/IMDS-09-2015-0385.