A model for solving vehicle scheduling problems: a case of study
DOI:
https://doi.org/10.17533/udea.redin.n88a03Keywords:
vehicle scheduling, mathematical programming, public transportAbstract
In this work we formulate a model to solve a type of vehicle scheduling problem, derived from the operation of the mass transit system (MIO) in Cali city, Colombia. Four companies operate the system with 3 types of buses and four depots. Two kinds of tasks should be assigned to operators’ buses. A task is a sequence of consecutive travels of a route between two stations: initial and final. Each task should start and should finish in a depot, not necessarily the same. There are two main objectives defined by the operators. One objective is to minimize the total deadhead kilometers between depots and stations where tasks should start or end. The other objective is to minimize the maximum deviation of kilometers (commercial and deadhead) assigned to the operators regarding the ideal quantity of kilometers that they should have, according to the number of their buses in the fleet. We have implemented the proposed model in AMPL using Gurobi solver and we validate it using nine representative instances, generated with real data obtained from the system operation. The results obtained, in all cases, improve the solutions proposed by the company.
Downloads
References
L. Bodin, B. Golden, A. Assad, and M. Ball, “Routing and scheduling of vehicles and crews the state of the art,” in Computers and Opertions Research, 1983, pp. 63–211.
J. R. Daduna and et al., “Vehicle scheduling for public mass transit – an overview,” in Computer-Aided Transit Scheduling, J. R. Daduna, I. Branco, and J. M. P. Paixão, Eds. Berlin: Springer, 1995, pp. 76–90.
S. Bunte and N. Kliewer. (2009, Nov.) An overview on vehicle scheduling models in public transport. [Online]. Available: https: //link.springer.com/article/10.1007%2Fs12469-010-0018-5
A. Ceder, Public Transit Planning and Operation: Theory, Modeling and Practice, 1st ed. Oxford, UK: Elsevier, 2007.
O. J. Ibarra, F. Delgado, R. Giesen, and J. Muñoz, “Planning, operation, and control of bus transport systems: A literature
review,” Transportation Research Part B: Methodological, vol. 77, pp. 38–75, Jul. 2015.
A. A. Bertossi, P. Carraresi, and G. Gallo, “On some matching problems arising in vehicle scheduling models,” Networks, vol. 17, no. 3, pp. 271–281, 1987.
P. Carraresi and G. Gallo, “Network models for vehicle and crew scheduling,” European Journal of Operations Research, vol. 16, no. 2, pp. 139–151, May 1984.
B. Gavish and E. Shifler, “An approach for solving a class of transportation scheduling problems,” European Journal of Operations Research, vol. 3, no. 2, pp. 122–134, Mar. 1979.
A. Haghani and M. Banihashemi, “Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints,” Transportation Research A: Policy and practice, vol. 36, no. 4, pp. 309–333, May 2002.
A. Haghani, M. Banihashemi, and K. H. Chiang, “A comparative analysis of bus transit vehicle scheduling models,” Transportation Research Part B: Methodological, vol. 37, no. 4, pp. 301–322, May 2003.
N. Kliewer, T. Mellouli, and L. Suhl, “A time–space network based exact optimization model for multi-depot bus scheduling,” European Journal of Operational Research, vol. 175, no. 3, pp. 1616–1627, Dec. 2006.
A. Löbel, “Solving large-scale multiple depot vehicle scheduling problems,” in Computer Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, N. H. M. Wilson, Ed. Cambridge, MA, USA: Springer, 1997, pp. 193–220.
M. Mesquita and J. Paixão, “Multiple depot vehicle scheduling problem: a new heuristic based on quasi-assignment algorithm,” in Fifth International Workshop on Computer-Aided Scheduling of Public Transport, Canada, 1990, pp. 167–180.
M. Mesquita and J. Paixão, “Exact algorithms for the multipledepot vehicle scheduling problem based on multicommodity
network flow type formulations,” in Computer-aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, N. H. M. Wilson, Ed. Berlin: Springer, 1999, pp. 221–222.
C. Ribeiro and F. Soumis, “A column generation approach to the multiple-depot vehicle scheduling problem,” Operations Research, vol. 42, no. 1, pp. 41–52, Jan. 1994.
D. Huisman, R. Freling, and A. Wagelmans, “A robust solution approach to the dynamic vehicle scheduling problem,” Transportation Science, vol. 38, no. 4, pp. 447–458, nov 2004.
A. Lamatsch, “An approach to vehicle scheduling with depot capacity constraints,” in Fifth International Workshop on Computer-Aided Scheduling of Public Transport, canada, 1990, pp. 181–195.
I. Sevim, H. Tekiner, M. G. Güler, and Z. P. Mutlu, “Automated vehicle scheduling system: A case study of metrobus system,” Sigma Journal of Engineering and Natural Sciences, vol. 7, no. 1, pp. 1–7, Dec. 2016.
X. Xu, Z. Ye, J. Li, and C. Wang, “An improved model and algorithm for the large-scale multi-depot vehicle scheduling problem with departure-duration restrictions,” in 96th Annual Meeting Transportation Research Board, Washington DC, United States, 2017, p. 18.
M. Sâmara, D. Borenstein, O. C. Bassi, and P. Guedes, “A new implementation to the vehicle type scheduling problem with time windows for scheduled trips,” in Simpósio Brasileiro de Pesquisa Operacional-SBPO, Natal RN, 2013, pp. 1549–1559.
B. Prata, “Using a maximal covering approach for the vehicle and crew scheduling: a case of study,” Sistemas & Gestão, vol. 8, no. 3, pp. 266–275, Sep. 2013.
E. Ucar, S. Birbil, and I. Muter, “Managing disruptions in the multi-depot vehicle scheduling problem,” Transportation Research Part B: Methodological, vol. 105, pp. 249–269, Nov. 2017.
J. F. López, S. F. Henao, and M. M. Morales, “Aplicación de la programación por metas en la distribución de servicios entre empresas operadoras del sistema de transporte masivo,” Scientia et Technica, vol. 1, no. 37, pp. 339–343, Dec. 2007.
A. J. Rengifo, M. G. Baldoquin, and J. Mosquera, “Modelos matemáticos en la solución de un problema de asignación y ruteo para el sistema integrado de transporte masivo SITM-MIO en cali, colombia,” in CLAIO XVII, Joint ALIO/SMIO Conference on Operations Research, Monterrey, Mexico, 2014, p. 56.
Y. Ding and et al., “Normalization and other topics in multi-objective optimization,” in Proceedings to the Fields-MITACS Industrial Problem Solving Workshop, Toronto, Canada, 2006, pp. 89–101.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2018 Revista Facultad de Ingeniería Universidad de Antioquia
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Revista Facultad de Ingeniería, Universidad de Antioquia is licensed under the Creative Commons Attribution BY-NC-SA 4.0 license. https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en
You are free to:
Share — copy and redistribute the material in any medium or format
Adapt — remix, transform, and build upon the material
Under the following terms:
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
NonCommercial — You may not use the material for commercial purposes.
ShareAlike — If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original.
The material published in the journal can be distributed, copied and exhibited by third parties if the respective credits are given to the journal. No commercial benefit can be obtained and derivative works must be under the same license terms as the original work.
Twitter