Modelo para resolver problemas de programación de vehículos: un estudio de caso

Autores/as

  • María Gulnara Baldoquin Universidad EAFIT
  • Alvaro José Rengifo-Campo Metro Cali S.A.

DOI:

https://doi.org/10.17533/udea.redin.n88a03

Palabras clave:

programación de vehículos, programación matemática, transporte público

Resumen

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.

|Resumen
= 372 veces | PDF (ENGLISH)
= 303 veces|

Descargas

Los datos de descargas todavía no están disponibles.

Biografía del autor/a

María Gulnara Baldoquin , Universidad EAFIT

Departamento de Ciencias Matemáticas.

Alvaro José Rengifo-Campo, Metro Cali S.A.

Metro Cali S.A., Operaciones e Infraestructura.

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

2018-09-18

Cómo citar

Baldoquin , M. G., & Rengifo-Campo, A. J. (2018). Modelo para resolver problemas de programación de vehículos: un estudio de caso. Revista Facultad De Ingeniería Universidad De Antioquia, (88), 16–25. https://doi.org/10.17533/udea.redin.n88a03