A methodology for creating feeding routes in mass transit systems
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 di...
| Main Authors: | , , |
|---|---|
| Format: | Online |
| Language: | eng |
| Published: |
Universidad Pedagógica y Tecnológica de Colombia
2017
|
| Subjects: | |
| Online Access: | https://revistas.uptc.edu.co/index.php/ingenieria/article/view/6052 |
| _version_ | 1801706077703634944 |
|---|---|
| author | Ospina-Toro, Daniela Toro-Ocampo, Eliana Mirledy Gallego-Rendón, Ramón Alfonso |
| author_facet | Ospina-Toro, Daniela Toro-Ocampo, Eliana Mirledy Gallego-Rendón, Ramón Alfonso |
| author_sort | Ospina-Toro, Daniela |
| collection | OJS |
| description | 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. |
| format | Online |
| id | oai:oai.revistas.uptc.edu.co:article-6052 |
| institution | Revista Facultad de Ingeniería |
| language | eng |
| publishDate | 2017 |
| publisher | Universidad Pedagógica y Tecnológica de Colombia |
| record_format | ojs |
| spelling | oai:oai.revistas.uptc.edu.co:article-60522022-06-15T16:17:48Z A methodology for creating feeding routes in mass transit systems Metodología para crear rutas alimentadoras en sistemas de transporte masivo Ospina-Toro, Daniela Toro-Ocampo, Eliana Mirledy Gallego-Rendón, Ramón Alfonso Feeding Routes LKH algorithm Location Routing Problem Math-Heuristic Savings Algorithm Set-Partitioning model Heurística de ahorros Heurística LKH Math-heurística Modelo de partición de conjuntos Problema de localización y ruteo Rutas alimentadoras 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. 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. Universidad Pedagógica y Tecnológica de Colombia 2017-05-02 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion investigation investigación application/pdf application/xml https://revistas.uptc.edu.co/index.php/ingenieria/article/view/6052 10.19053/01211129.v26.n45.2017.6052 Revista Facultad de Ingeniería; Vol. 26 No. 45 (2017); 9-21 Revista Facultad de Ingeniería; Vol. 26 Núm. 45 (2017); 9-21 2357-5328 0121-1129 eng https://revistas.uptc.edu.co/index.php/ingenieria/article/view/6052/5582 https://revistas.uptc.edu.co/index.php/ingenieria/article/view/6052/6403 |
| spellingShingle | Feeding Routes LKH algorithm Location Routing Problem Math-Heuristic Savings Algorithm Set-Partitioning model Heurística de ahorros Heurística LKH Math-heurística Modelo de partición de conjuntos Problema de localización y ruteo Rutas alimentadoras Ospina-Toro, Daniela Toro-Ocampo, Eliana Mirledy Gallego-Rendón, Ramón Alfonso A methodology for creating feeding routes in mass transit systems |
| title | A methodology for creating feeding routes in mass transit systems |
| title_alt | Metodología para crear rutas alimentadoras en sistemas de transporte masivo |
| title_full | A methodology for creating feeding routes in mass transit systems |
| title_fullStr | A methodology for creating feeding routes in mass transit systems |
| title_full_unstemmed | A methodology for creating feeding routes in mass transit systems |
| title_short | A methodology for creating feeding routes in mass transit systems |
| title_sort | methodology for creating feeding routes in mass transit systems |
| topic | Feeding Routes LKH algorithm Location Routing Problem Math-Heuristic Savings Algorithm Set-Partitioning model Heurística de ahorros Heurística LKH Math-heurística Modelo de partición de conjuntos Problema de localización y ruteo Rutas alimentadoras |
| topic_facet | Feeding Routes LKH algorithm Location Routing Problem Math-Heuristic Savings Algorithm Set-Partitioning model Heurística de ahorros Heurística LKH Math-heurística Modelo de partición de conjuntos Problema de localización y ruteo Rutas alimentadoras |
| url | https://revistas.uptc.edu.co/index.php/ingenieria/article/view/6052 |
| work_keys_str_mv | AT ospinatorodaniela amethodologyforcreatingfeedingroutesinmasstransitsystems AT toroocampoelianamirledy amethodologyforcreatingfeedingroutesinmasstransitsystems AT gallegorendonramonalfonso amethodologyforcreatingfeedingroutesinmasstransitsystems AT ospinatorodaniela metodologiaparacrearrutasalimentadorasensistemasdetransportemasivo AT toroocampoelianamirledy metodologiaparacrearrutasalimentadorasensistemasdetransportemasivo AT gallegorendonramonalfonso metodologiaparacrearrutasalimentadorasensistemasdetransportemasivo AT ospinatorodaniela methodologyforcreatingfeedingroutesinmasstransitsystems AT toroocampoelianamirledy methodologyforcreatingfeedingroutesinmasstransitsystems AT gallegorendonramonalfonso methodologyforcreatingfeedingroutesinmasstransitsystems |
