Determining lower bound on number of vehicle blocks in multi-depot vehicle scheduling problem with mixed fleet covering electric buses

Jerzy Duda; Szymon Fierek; Marek Karkula; Piotr Kisielewski; Radosław Puka; Adam Redmer; Iwona Skalna

doi:10.5604/01.3001.0016.2475

Authors

Jerzy Duda AGH University of Science and Technology, Kraków Author https://orcid.org/0000-0002-9225-7123
Szymon Fierek Poznan University of Technology, Poznań Author https://orcid.org/0000-0003-1076-2722
Marek Karkula AGH University of Science and Technology, Kraków Author https://orcid.org/0000-0001-9468-1529
Piotr Kisielewski Cracow University of Technology, Kraków Author https://orcid.org/0000-0003-0013-5477
Radosław Puka AGH University of Science and Technology, Kraków Author https://orcid.org/0000-0002-3201-0735
Adam Redmer Poznan University of Technology, Poznań Author https://orcid.org/0000-0003-2154-232X
Iwona Skalna AGH University of Science and Technology, Kraków Author https://orcid.org/0000-0001-5707-7525

DOI:

https://doi.org/10.5604/01.3001.0016.2475

Keywords:

public transport, organization of public transport, vehicle scheduling, electric buses, mixed fleet

Abstract

Scheduling buses in public transport systems consists in assigning trips to vehicle blocks. To minimize the cost of fuel and environmental impact of public transport, the number of vehicle blocks used should be as small as possible, but sufficient to cover all trips in a timetable. However, when solving real life transportation problems, it is difficult to decide whether the number of vehicle blocks obtained from an algorithm is minimal, unless the actual minimal number is already known, which is rare, or the theoretical lower bound on the number of vehicles has been determined. The lower bound on the number of vehicle blocks is even more important and useful since it can be used both as a parameter that controls the optimization process and as the minimum expected value of the respective optimization criterion. Therefore, methods for determining the lower bound in transportation optimization problems have been studied for decades. However, the existing methods for determining the lower bound on the number of vehicle blocks are very limited and do not take multiple depots or heterogeneous fleet of vehicles into account. In this research, we propose a new practical and effective method to assess the lower bound on the number of vehicle blocks in the Multi-Depot Vehicle Scheduling Problem (MDVSP) with a mixed fleet covering electric vehicles (MDVSP-EV). The considered MDVSP-EV reflects a problem of public transport planning encountered in medium-sized cities. The experimental results obtained for a real public transport system show the great potential of the proposed method in determining the fairly strong lower bound on the number of vehicle blocks. The method can generate an estimated distribution of the number of blocks during the day, which may be helpful, for example, in planning duties and crew scheduling. An important advantage of the proposed method is its low calculation time, which is very important when solving real life transportation problems.

References

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

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

Caprara, A., Fischetti, M., Toth, P., (1999). A Heuristic Method for the Set Covering Problem. Operations Research, 47(5), 730-743. DOI: 10.1287/opre.47.5.730.

Lübbecke, M.E., Cochran, J.J., Cox L.A., Keskinocak, P., Kharoufeh, J.P., Smith, J.C., (2010). Column generation. John Wiley & Sons, Inc.

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

Olsen, N., Kliewer, N., Wolbeck, L., (2022). A study on flow decomposition methods for scheduling of electric buses in public transport based on aggregated time-space network models. Central European Journal of Operations Research, 30, 883-919. DOI: 10.1007/s10100- 020-00705-6. [7] 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. DOI: 10.1016/j.ejor.2021.10.058.

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. DOI: 10.1080/15568318.2021.1914791.

Fisher, M.L., (2004). The Lagrangian relaxation method for solving integer programming problems. Management Science, 50(12), 1861-1871. DOI: 10.1287/mnsc.1040.0263.

Morrison, D.R., Jacobson, S.H., Sauppe, J.J., Sewell, E.C., (2016). Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning, Discrete Optimization, 19, 79–102. DOI: 10.1016/j.di sopt.2016.01.005.

Akker van den, M., Hoogeveen, H., Velde de, S., (2002). Combining Column Generation and Lagrangean Relaxation to solve a single-machine common due date problem. INFORMS Journal on Computing, 14(1), 37-51. DOI: 10.1287/ijoc.14.1.37.7706.

Byung-In, K., Seongbae, K., Junhyuk, P., (2012). A school bus scheduling problem, European Journal of Operational Research, 218, 577–585. DOI: 10.1016/j.ejor.2011.11.035.

Bunte S., Kliewer N.: An overview on vehicle scheduling models, Public Transport, 1, 2009, 299-317. DOI: 10.1007/s12469-010-0018-5.

Mesquita M, Paias A, Respicio A (2009) Branching approaches for integrated vehicle and crew scheduling. Public Transp 1:21-37.

Ribeiro, C., Soumis, F., (1994). A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem. Operations Research, 42(1), 41–52. DOI: 10.1287/opre.42.1.41.

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. DOI: 10.1023/A:1022287504028.

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. DOI: 10.1016/j.cor.2016.06.013.

Stern, H.I., Ceder, A., (1983). Technical Note – An improved lower bound to the minimum fleet size problem, Transportation Science, 17(4), 471-477. DOI: 10.1287/trsc.17.4.471.

Ceder, A., (2011). Optimal multi-vehicle type transit timetabling and vehicle scheduling, Procedia Social and Behavioral Sciences, 14th EWGT & 26th MEC & 1st RH, 20, 19-30. DOI: 10.1016/j.sbspro.2011.08.005.

Ceder, A. (2002), "A Step Function for Im proving Transit Operations Planning Using Fixed and Variable Scheduling", Taylor, M.A.P. (Ed.) Transportation and Traffic Theory in the 21st Century, Emerald Group Publishing Limited, Bingley, 1-21. DOI: 10.1108/9780585474601-001. [21] Carpaneto, G., Dell’Amico, M., Fischetti, M., Toth, P., (1989). A branch and bound algorithm for the multiple depot vehicle scheduling problem. Networks, 19, 531-548. DOI: 10.1002/net.3230190505.

Mesquita, M., Paixão, J., (1992). Multiple De pot Vehicle Scheduling Problem: A New Heuristic Based on Quasi-Assignment Algorithms. In: Desrochers, M., Rousseau, JM. (eds) Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 386. Springer, Berlin, Heidelberg, 167-180. DOI: 10.1007/978-3-642-85968-7_12.

Bodin, L., Golden, B., Assad, A., Ball, M., (1983). Routing and scheduling of vehicles and crews: the state of the art. Computers & Operations Research, 10(2), 63-211. DOI: 10.1016/0305-0548(83)90030-8.

Bertossi, A.A., Carraresi, P., Gallo, G., (1987). On some matching problems arising in vehicle scheduling models. Networks, 17, 271-281. DOI: 10.1002/net.3230170303.

Lamatsch, A., (1992). An Approach to Vehicle Scheduling with Depot Capacity Constraints. In: Desrochers, M., Rousseau, J.M., (eds), Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 386. Springer, Berlin, Heidelberg, 181-195. DOI: 10.1007/978-3-642-85968-7_13.

Kliewer, N., Mellouli, T., Suhl, L., (2002). A new solution model for multi-depot multi-vehicle-type vehicle scheduling in (sub)urban public transport. In: Proceedings of the 13th Mini EURO Conference and the 9th meeting of the EURO working group on transportation, 604-609.

Kliewer, N., Mellouli, T., Suhl, L., (2006). A time-space network based exact optimization model for multi-depot bus scheduling. European Journal of Operational Research, 175(3), 1616-1627. DOI: 10.1016/j.ejor.2005.02.030.

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