A methodology for creating feeding routes in mass transit systems

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


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.


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


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.

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.

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.

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.

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.

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.

J. W. Grossman, "Patterns of collaboration in mathematical research," SIAM News, vol. 35, pp. 8-9, 2002.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

Article Metrics

Abstract Views

Metrics Loading ...


  • There are currently no refbacks.

Copyright (c) 2017 Revista Facultad de Ingeniería

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.


Revista Facultad de Ingeniería (Rev. Fac. Ing.) - ISSN: 0121-1129 - ISSN: 2357-5328 (Online)

Indexed by: Publindex(Categoría A2)Emerging Sources Citation Index, Latindex, SciELO, Redalyc, REDIB, DOAJDialnetSHERPA/RoMEO.



Licencia de Creative Commons

This work is licensed under a Creative Commons Attribution 4.0 International

Sede Central Tunja–Boyacá–Colombia
Avenida Central del Norte 39-115
PBX: (57+8) 7405626
portalweb@uptc.edu.co Comentarios de este sitio
Horario de atención y servicio telefónico
8:00 a.m. a 12:00 m y 2:00 p.m a 6:00 p.m.

Atención al Ciudadano
Línea Gratuita: 01 8000 942024
Tel: (57+8) 7428263
Notificaciones Judiciales
Notificaciones de aviso

Institución de Educación Superior sujeta a inspección y vigilancia por el Ministerio de Educación Nacional
Sistema OJS - Metabiblioteca |