A hybrid algorithm for the multi-depot vehicle scheduling problem arising in public transportation

Abstract: In this article, a hybrid algorithm is proposed to solve the Vehicle Scheduling Problem with Multiple Depots. The proposed methodology uses a genetic algorithm, initialized with three specialized constructive procedures. The solution generated by this first approach is then refined by means of a Set Partitioning (SP) model, whose variables (columns) correspond to the current itineraries of the final population. The SP approach possibly improves the incumbent solution which is then provided as an initial point to a well-known MDVSP model. Both the SP and MDVSP models are solved with the help of a mixed integer programming (MIP) solver. The algorithm is tested in benchmark instances consisting of 2, 3 and 5 depots, and a service load ranging from 100 to 500. The results obtained showed that the proposed algorithm was capable of finding the optimal solution in most cases when considering a time limit of 500 seconds. The methodology is also applied to solve a real-life instance that arises in the transportation system in Colombia (2 depots and 719 services), resulting in a decrease of the required fleet size and a balanced allocation of services, thus reducing deadhead trips.

How to cite this paper

 Moreno, C., Falcón, L., Bolaños, R., Subramanian, A., Zuluaga, A & Echeverri, M. (2019). A hybrid algorithm for the multi-depot vehicle scheduling problem arising in public transportation.International Journal of Industrial Engineering Computations , 10(3), 361-374.

Refrences

Ceder, A. (2007). Public transit planning and operation: Modeling, practice and behavior. CRC press.
Chu, P. C., & Beasley, J. E. (1998). A genetic algorithm for the multidimensional knapsack problem. Journal of heuristics, 4(1), 63-86.
Dell'Amico, M., Fischetti, M., & Toth, P. (1993). Heuristic algorithms for the multiple depot vehicle scheduling problem. Management Science, 39(1), 115-125.
Fischetti, M., Lodi, A., & Toth, P. (1999). A branch-and-cut algorithm for the multiple depot vehicle scheduling problem. Dipartimento di Elittronica e Informatica, Università di Padova, Italy.
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.
Guedes, P. C., & Borenstein, D. (2015). Column generation based heuristic framework for the multiple-depot vehicle type scheduling problem. Computers & Industrial Engineering, 90, 361-370.
Hadjar, A., Marcotte, O., & Soumis, F. (2006). A branch-and-cut algorithm for the multiple depot vehicle scheduling problem. Operations Research, 54(1), 130-149.
Hassold, S., & Ceder, A. A. (2014). Public transport vehicle scheduling featuring multiple vehicle types. Transportation Research Part B: Methodological, 67, 129-143.
Huisman, D., Freling, R., & Wagelmans, A. P. (2004). A robust solution approach to the dynamic vehicle scheduling problem. Transportation Science, 38(4), 447-458.
Ibarra-Rojas, O. J., Delgado, F., Giesen, R., & Muñoz, J. C. (2015). Planning, operation, and control of bus transport systems: A literature review. Transportation Research Part B: Methodological, 77, 38-75.
Jungnickel, D. (2007). Graphs, networks and algorithms (Vol. 5). Springer Science & Business Media.
Laurent, B., & Hao, J. K. (2009). Iterated local search for the multiple depot vehicle scheduling problem. Computers & Industrial Engineering, 57(1), 277-286.
Leung, T. W., Yung, C. H., & Troutt, M. D. (2001). Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem. Computers & industrial engineering, 40(3), 201-214.
Liu, S., Huang, W., & Ma, H. (2009). An effective genetic algorithm for the fleet size and mix vehicle routing problems. Transportation Research Part E: Logistics and Transportation Review, 45(3), 434-445.
Mesquita, M., & Paixão, J. (1992). Multiple depot vehicle scheduling problem: A new heuristic based on quasi-assignment algorithms. In Computer-Aided Transit Scheduling (pp. 167-180). Springer, Berlin, Heidelberg.
Munoz, J. C., & Paget-Seekins, L. (Eds.). (2016). Restructuring public transport through Bus Rapid Transit: An international and interdisciplinary perspective. Policy Press.
Park, Y. B. (2001). A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines. International Journal of Production Economics, 73(2), 175-188.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31(12), 1985-2002.
Schöbel, A. (2017). An eigenmodel for iterative line planning, timetabling and vehicle scheduling in public transportation. Transportation Research Part C: Emerging Technologies, 74, 348-365.
Shui, X., Zuo, X., Chen, C., & Smith, A. E. (2015). A clonal selection algorithm for urban bus vehicle scheduling. Applied Soft Computing, 36, 36-44.
Subramanian, A., Uchoa, E., & Ochi, L. S. (2013). A hybrid algorithm for a class of vehicle routing problems. Computers & Operations Research, 40(10), 2519-2531.
Wang, H., & Shen, J. (2007). Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints. Applied Mathematics and Computation, 190(2), 1237-1249.
Wen, M., Linde, E., Ropke, S., Mirchandani, P., & Larsen, A. (2016). An adaptive large neighborhood search heuristic for the electric vehicle scheduling problem. Computers & Operations Research, 76, 73-83.