Ir al menú de navegación principal Ir al contenido principal Ir al pie de página del sitio

Vol. 26 Núm. 45 (2017)

Articulos

Metodología para crear rutas alimentadoras en sistemas de transporte masivo

https://doi.org/10.19053/01211129.v26.n45.2017.6052

Publicado 2017-05-02

  • Daniela Ospina-Toro
    • ,
  • Eliana Mirledy Toro-Ocampo
    • ,
  • Ramón Alfonso Gallego-Rendón

Daniela Ospina-Toro
Universidad Tecnológica de Pereira (Pereira-Risaralda, Colombia).

Eliana Mirledy Toro-Ocampo
Universidad Tecnológica de Pereira (Pereira-Risaralda, Colombia).

Ramón Alfonso Gallego-Rendón
Universidad Tecnológica de Pereira (Pereira-Risaralda, Colombia).

Resumen

Se propone una metodología para identificar rutas alimentadoras en zonas no conectadas para un sistema de transporte masivo, con el fin de aumentar la cobertura del servicio y mejorar el nivel de ocupación del sistema. La metodología propuesta consta de dos etapas: 1) estructurar escenarios de áreas no conectadas al sistema de transporte y 2) combinar técnicas heurísticas y exactas para resolver el problema de rutas alimentadoras. La metodología considera dentro de sus restricciones la duración de la ruta y la capacidad del vehículo alimentador. Para su modelamiento se establece una analogía entre los problemas del transporte de pasajeros y el problema de localización y ruteo, Location Routing Problem (LRP), que usualmente es aplicado a problemas de transporte de mercancías. La metodología de solución propuesta es una matheurística que combina las heurísticas Lin-Kernighan-Helsgaun (LKH) y ahorros con el algoritmo de ramificación y corte, Branch-and-Cut, aplicado sobre un modelo lineal entero mixto de partición de conjuntos (Set Partitioning) para LRP. Esta propuesta metodológica es validada con casos de prueba reales del sistema de transporte masivo de la ciudad de Pereira (Megabús), donde se consideran algunas zonas no conectadas del Área Metropolitana Centro Occidente, localizada en el eje cafetero colombiano.

Palabras clave

Heurística de ahorros, Heurística LKH, Math-heurística, Modelo de partición de conjuntos, Problema de localización y ruteo, Rutas alimentadoras

PDF (English) XML (English)

Citas

  1. I. Thomson, Impacto de las tendencias sociales, económicas y tecnológicas sobre el transporte público: investigación preliminar en ciudades de América Latina; United Nations Publications, 2002.
  2. Ministerio de Transporte de Colombia, Política para mejorar el servicio de transporte Público urbano de pasajeros; Consejo Nacional de Política Económica y Social, CONPES 3167, Departamento Nacional de Planeación, 2002.
  3. Ministerio de Transporte de Colombia, Política Nacional de Transporte Urbano y Masivo; Consejo Nacional de Política Económica y Social, CONPES 3260," Deparamento Nacional de Planeación, 2003.
  4. El Tiempo. Redacción Barranquilla, Medellín, Bucaramanga y Pereira, "Ninguno de los 'Transmilenios' del país se salva de líos financieros," El Tiempo, 2013.
  5. M. J. Anson, F. J. Fabozzi, and F. J. Jones, The handbook of traditional and alternative investment vehicles: investment characteristics and strategies, vol. 194: John Wiley & Sons, 2010. DOI: http://doi.org/10.1002/9781118258248. DOI: https://doi.org/10.1002/9781118258248
  6. A. Blumstein, and A. J. Beck, "Population growth in US prisons, 1980-1996," Crime. & Just., vol. 26, pp. 17-61, Jan. 1999. DOI: http://doi.org/10.1086/449294. DOI: https://doi.org/10.1086/449294
  7. J. W. Grossman, "Patterns of collaboration in mathematical research," SIAM News, vol. 35, pp. 8-9, 2002.
  8. G. Laporte, Y. Nobert, and D. Arpin, "An exact algorithm for solving a capacitated location-routing problem," Annals of Operations Research, vol. 6 (9), pp. 291-310, Sep. 1986. DOI: http://doi.org/10.1007/BF02023807. DOI: https://doi.org/10.1007/BF02023807
  9. C. Prodhon, and C. Prins, "A memetic algorithm with population management (MA| PM) for the periodic location-routing problem," Lecture Notes in Computer Science, vol. 5296, pp. 43-57, 2008. DOI: http://doi.org/10.1007/978-3-540-88439-2_4. DOI: https://doi.org/10.1007/978-3-540-88439-2_4
  10. G. Nagy, and S. Salhi, "Location-routing: Issues, models and methods," European Journal of Operational Research, vol. 177 (2), pp. 649-672, Mar. 2007. DOI: http://doi.org/10.1016/j.ejor.2006.04.004. DOI: https://doi.org/10.1016/j.ejor.2006.04.004
  11. S. Salhi, and G. K. Rand, "The effect of ignoring routes when locating depots," European Journal of Operational Research, vol. 39 (2), pp. 150-156, Mar. 1989. DOI: http://doi.org/10.1016/0377-2217(89)90188-4. DOI: https://doi.org/10.1016/0377-2217(89)90188-4
  12. D. Tuzun, and L. I. Burke, "A two-phase tabu search approach to the location routing problem," European Journal of Operational Research, vol. 116 (1), pp. 87-99, Jul. 1999. DOI: http://doi.org/10.1016/S0377-2217(98)00107-6. DOI: https://doi.org/10.1016/S0377-2217(98)00107-6
  13. M. Albareda-Sambola, J. A. Dı́az, and E. Fernández, "A compact model and tight bounds for a combined location-routing problem," Computers & Operations Research, vol. 32 (3), pp. 407-428, Mar. 2005. DOI: http://doi.org/10.1016/S0305-0548(03)00245-4. DOI: https://doi.org/10.1016/S0305-0548(03)00245-4
  14. J. Melechovský, C. Prins, and R. W. Calvo, "A metaheuristic to solve a location-routing problem with non-linear costs," Journal of Heuristics, vol. 11 (5-6), pp. 375-391, Dec. 2005. DOI: http://doi.org/10.1007/s10732-005-3601-1. DOI: https://doi.org/10.1007/s10732-005-3601-1
  15. S. Barreto, C. Ferreira, J. Paixao, and B. S. Santos, "Using clustering analysis in a capacitated location-routing problem," European Journal of Operational Research, vol. 179 (3), pp. 968-977, Jun. 2007. DOI: http://doi.org/10.1016/j.ejor.2005.06.074. DOI: https://doi.org/10.1016/j.ejor.2005.06.074
  16. C. Prins, C. Prodhon, A. Ruiz, P. Soriano, and R. Wolfler Calvo, "Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation-granular tabu search heuristic," Transportation Science, vol. 41 (4), pp. 470-483, Nov. 2007. DOI: http://doi.org/10.1287/trsc.1060.0187. DOI: https://doi.org/10.1287/trsc.1060.0187
  17. C. Prodhon, "An elsxpath relinking hybrid for the periodic location-routing problem," Lecture Notes in Computer Science, vol. 5818, pp. 15-29, 2009. DOI: http://doi.org/10.1007/978-3-642-04918-7_2. DOI: https://doi.org/10.1007/978-3-642-04918-7_2
  18. C. Prodhon, "A hybrid evolutionary algorithm for the periodic location-routing problem," European Journal of Operational Research, vol. 210 (2), pp. 204-212, Apr. 2011. DOI: http://doi.org/10.1016/j.ejor.2010.09.021. DOI: https://doi.org/10.1016/j.ejor.2010.09.021
  19. C. Duhamel, P. Lacomme, C. Prins, and C. Prodhon, "A GRASP× ELS approach for the capacitated location-routing problem," Computers & Operations Research, vol. 37 (11), pp. 1912-1923, Nov. 2010. DOI: http://doi.org/10.1016/j.cor.2009.07.004. DOI: https://doi.org/10.1016/j.cor.2009.07.004
  20. J. W. Escobar, R. Linfati, and P. Toth, "A two-phase hybrid heuristic algorithm for the capacitated location-routing problem," Computers & Operations Research, vol. 40 (1), pp. 70-79, Jan. 2013. DOI: http://doi.org/10.1016/j.cor.2012.05.008. DOI: https://doi.org/10.1016/j.cor.2012.05.008
  21. S. Pirkwieser, and G. R. Raidl, Variable neighborhood search coupled with ILP-based very large neighborhood searches for the (periodic) location-routing problem: Springer, 2010. DOI: < a href="http://doi.org/10.1007/978-3-642-16054-7_13">http://doi.org/10.1007/978-3-642-16054-7_13. DOI: https://doi.org/10.1007/978-3-642-16054-7_13
  22. B. Yu, Z.-Z. Yang, and B. Yao, "An improved ant colony optimization for vehicle routing problem," European Journal of Operational Research, vol. 196 (1), pp. 171-176, Jul. 2009. DOI: http://doi.org/10.1016/j.ejor.2008.02.028. DOI: https://doi.org/10.1016/j.ejor.2008.02.028
  23. V. C. Hemmelmayr, J.-F. Cordeau, and T. G. Crainic, "An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics," Computers & Operations Research, vol. 39 (12), pp. 3215-3228, Dec. 2012. DOI: http://doi.org/10.1016/j.cor.2012.04.007. DOI: https://doi.org/10.1016/j.cor.2012.04.007
  24. R. T. Berger, C. R. Coullard, and M. S. Daskin, "Location-routing problems with distance constraints," Transportation Science, vol. 41 (1), pp. 29-43, Feb. 2007. DOI: http://doi.org/10.1287/trsc.1060.0156. DOI: https://doi.org/10.1287/trsc.1060.0156
  25. Z. Akca, R. Berger, and T. Ralphs, "A branch-and-price algorithm for combined location and routing problems under capacity restrictions," in Operations Research and Cyber-Infrastructure, ed: Springer, pp. 309-330, 2009. DOI: http://doi.org/10.1007/978-0-387-88843-9_16. DOI: https://doi.org/10.1007/978-0-387-88843-9_16
  26. J.-M. Belenguer, E. Benavent, C. Prins, C. Prodhon, and R. W. Calvo, "A branch-and-cut method for the capacitated location-routing problem," Computers & Operations Research, vol. 38 (6), pp. 931-941, Jun. 2011. DOI: http://doi.org/10.1016/j.cor.2010.09.019. DOI: https://doi.org/10.1016/j.cor.2010.09.019
  27. C. Prodhon and C. Prins, "A survey of recent research on location-routing problems," European Journal of Operational Research, vol. 238 (1), pp. 1-17, Oct. 2014. DOI: http://doi.org/10.1016/j.ejor.2014.01.005. DOI: https://doi.org/10.1016/j.ejor.2014.01.005
  28. G. U. Clarke and J. W. Wright, "Scheduling of vehicles from a central depot to a number of delivery points," Operations Research, vol. 12, pp. 568-581, 1964. DOI: http://doi.org/10.1287/opre.12.4.568. DOI: https://doi.org/10.1287/opre.12.4.568
  29. K. Helsgaun, "An effective implementation of the Lin–Kernighan traveling salesman heuristic," European Journal of Operational Research, vol. 126, pp. 106-130, 2000. DOI: http://doi.org/10.1016/S0377-2217(99)00284-2. DOI: https://doi.org/10.1016/S0377-2217(99)00284-2
  30. S. Liu, W. Huang, and H. Ma, "An effective genetic algorithm for the fleet size and mix vehicle routing problems," Transportation Research Part E: Logistics and Transportation Review, vol. 45 (3), pp. 434-445, May. 2009. DOI: http://doi.org/10.1016/j.tre.2008.10.003. DOI: https://doi.org/10.1016/j.tre.2008.10.003
  31. A. Giraldo and J. Caicedo, Construcción de matriz origen destino de transporte para amco (2008-2012), Facultad de Ingeniería Industrial. Universidad Tecnológica de Pereira, Pereira, 2010.
  32. F. Carmona, E. Guillen, Estudio de factibilidad para la creación de rutas exclusivas de transporte en los municipios de Pereira y Dosquebradas para la comunidad estudiantil de jornada diurna de la Universidad Tecnológica de Pereira, Ingeniería Industrial, Universidad Tecnológica de Pereira, Pereira, 2014.

Descargas

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