A model for solving vehicle scheduling problems: a case of study
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.
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.
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.
Authors can archive the pre-print version (i.e., the version prior to peer review) and post-print version (that is, the final version after peer review and layout process) on their personal website, institutional repository and / or thematic repository
- Upon acceptance of an article, it will be published online through the page https://revistas.udea.edu.co/index.php/ingenieria/issue/archive in PDF version with its correspondent DOI identifier
The Revista Facultad de Ingeniería -redin- encourages the Political Constitution of Colombia, chapter IV
Chapter IV Sanctions 51
The following shall be liable to imprisonment for two to five years and a fine of five to 20 times the legal minimum monthly wage: (1) any person who publishes an unpublished literary or artistic work, or part thereof, by any means, without the express prior authorization of the owner of rights; (2) any person who enters in the National Register of Copyright a literary, scientific or artistic work in the name of a person other than the true author, or with its title altered or deleted, or with its text altered, deformed, amended or distorted, or with a false mention of the name of the publisher or phonogram, film, videogram or software producer; (3) any person who in any way or by any means reproduces, disposes of, condenses, mutilates or otherwise transforms a literary, scientific or artistic work without the express prior authorization of the owners thereof; (4) any person who reproduces phonograms, videograms, software or cinematographic works without the express prior authorization of the owner, or transports, stores, stocks, distributes, imports, sells, offers for sale, acquires for sale or distribution or in any way deals in such reproductions. Paragraph. If either the material embodiment or title page of or the introduction to the literary work, phonogram, videogram, software or cinematographic work uses the name, business style, logotype or distinctive mark of the lawful owner of rights, the foregoing sanctions shall be increased by up to half.