Skip to main navigation menu Skip to main content Skip to site footer

Vol. 26 No. 45 (2017)

Papers

A methodology for creating feeding routes in mass transit systems

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

Published 2017-05-02

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

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

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

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

Abstract

This paper proposes a methodology to identify feeding routes for areas disconnected to the Mass Transit System (MTS), in order to propose an alternative solution to the deficit in the number of carried passengers. The proposed methodology consists of two steps: (1) structuring scenarios for areas disconnected from the transport system, and (2) combining heuristic and exact techniques to solve the feeding routes problem. The methodology considers among its restrictions the path length and the passenger vehicle capacity. To model the problem, a comparison with the Location Routing Problem (LRP), which is usually applied to freight transport problems, was established. The proposed methodology is a math-heuristic that combines the Lin-Kernighan-Helsgaun algorithm (LKH), and the Clark and Wright’s Savings heuristic with the Branch-and-Cut exact algorithm, which is applied into a Mixed Integer Linear Programming model (MILP), also known as a Set Partitioning model (SP) for LRP. This methodological approach is validated with real instances in the massive transport system of Pereira (Megabús), considering some areas disconnected from the Central-Occidental Metropolitan Area System (AMCO) of Pereira, located in the Colombia's Coffee Axis.

Keywords

Feeding Routes, LKH algorithm, Location Routing Problem, Math-Heuristic, Savings Algorithm, Set-Partitioning model

PDF XML

References

  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.

Downloads

Download data is not yet available.