Modelo para resolver problemas de programación de vehículos: un estudio de caso
DOI:
https://doi.org/10.17533/udea.redin.n88a03Palabras clave:
programación de vehículos, programación matemática, transporte públicoResumen
En este trabajo se formula un modelo para resolver un tipo de problema de programación de vehículos, derivado de la operación del sistema de transporte masivo (MIO) en la ciudad de Cali, Colombia. Cuatro compañías operan el sistema con 3 tipos de buses y cuatro patios. Dos tipos de tareas deben asignarse a los buses de los operadores. Una tarea es una secuencia de viajes consecutivos de una ruta entre dos estaciones: inicial y final. Cada tarea debe comenzar y debe terminar en un patio, no necesariamente el mismo. Hay dos objetivos principales definidos por los operadores. Un objetivo es minimizar el total de kilómetros en vacío entre patios y estaciones donde las tareas deben comenzar o terminar. El otro objetivo es minimizar la desviación máxima de kilómetros (comercial y en vacío) asignada a los operadores con respecto a la cantidad ideal de kilómetros que deberían tener, según el número de sus buses en la flota. El modelo propuesto se implementa con el software Gurobi, utilizando nueve instancias representativas generadas con datos reales obtenidos de la operación del sistema. Todos los resultados obtenidos mejoran las soluciones propuestas por la empresa. Se proponen variaciones del modelo para considerar nuevas restricciones deseables para la empresa.
Descargas
Citas
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.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2018 Revista Facultad de Ingeniería Universidad de Antioquia
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Los artículos disponibles en la Revista Facultad de Ingeniería, Universidad de Antioquia están bajo la licencia Creative Commons Attribution BY-NC-SA 4.0.
Eres libre de:
Compartir — copiar y redistribuir el material en cualquier medio o formato
Adaptar : remezclar, transformar y construir sobre el material.
Bajo los siguientes términos:
Reconocimiento : debe otorgar el crédito correspondiente , proporcionar un enlace a la licencia e indicar si se realizaron cambios . Puede hacerlo de cualquier manera razonable, pero no de ninguna manera que sugiera que el licenciante lo respalda a usted o su uso.
No comercial : no puede utilizar el material con fines comerciales .
Compartir igual : si remezcla, transforma o construye a partir del material, debe distribuir sus contribuciones bajo la misma licencia que el original.
El material publicado por la revista puede ser distribuido, copiado y exhibido por terceros si se dan los respectivos créditos a la revista, sin ningún costo. No se puede obtener ningún beneficio comercial y las obras derivadas tienen que estar bajo los mismos términos de licencia que el trabajo original.
Twitter