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

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

doi:10.19053/01211129.v26.n45.2017.6052

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).

How to Cite

Ospina-Toro, D., Toro-Ocampo, E. M., & Gallego-Rendón, R. A. (2017). A methodology for creating feeding routes in mass transit systems. Revista Facultad de Ingeniería, 26(45), 9–21. https://doi.org/10.19053/01211129.v26.n45.2017.6052

Download Citation

Metrics

Views/Downloads

Abstract
1844
PDF
450
XML
12

All articles included in the Revista Facultad de Ingeniería are published under the Creative Commons (BY) license.

Authors must complete, sign, and submit the Review and Publication Authorization Form of the manuscript provided by the Journal; this form should contain all the originality and copyright information of the manuscript.

The authors who publish in this Journal accept the following conditions:

a. The authors retain the copyright and transfer the right of the first publication to the journal, with the work registered under the Creative Commons attribution license, which allows third parties to use what is published as long as they mention the authorship of the work and the first publication in this Journal.

b. Authors can make other independent and additional contractual agreements for the non-exclusive distribution of the version of the article published in this journal (eg, include it in an institutional repository or publish it in a book) provided they clearly indicate that the work It was first published in this Journal.

c. Authors are allowed and recommended to publish their work on the Internet (for example on institutional or personal pages) before and during the process.
review and publication, as it can lead to productive exchanges and a greater and faster dissemination of published work.

d. The Journal authorizes the total or partial reproduction of the content of the publication, as long as the source is cited, that is, the name of the Journal, name of the author (s), year, volume, publication number and pages of the article.

e. The ideas and statements issued by the authors are their responsibility and in no case bind the Journal.

Metrics

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

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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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. DOI: https://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.

Downloads

Download data is not yet available.


Fuente Academica Premier

(Categoría B)

Abstract

Keywords

References

Downloads

Similar Articles