A methodology for creating Feeding routes in mass transit systems Translated title: Metodologia para criar rotas alimentadoras em sistemas de transporte masivo Translated title: Metodología poro croar rutas alimentadoras en sistemas de transporte masivo

Abstract

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.

Translated abstract

Resumo Propõe-se uma metodologia para identificar rotas alimentadoras em áreas não conectadas para um sistema de transporte massivo, com o fim de aumentar a cobertura do serviço e melhorar o nível de ocupação do sistema. A metodologia proposta consta de duas etapas: 1) estruturar cenários de áreas não conectadas ao sistema de transporte e 2) combinar técnicas heurísticas e exatas para resolver o problema de rotas alimentadoras. A metodologia considera, dentro de suas restrições, a duração da rota e a capacidade do veículo alimentador. Para seu modelamento estabelece-se uma analogia entre os problemas do transporte de passageiros e o problema de localização e roteamento, Location Routing Problem (LRP), que usualmente é aplicado a problemas de transporte de mercadorias. A metodologia de solução proposta é uma matheurística que combina as heurísticas Lin-Kernighan-Helsgaun (LKH) e economias com o algoritmo de ramificação e corte Branch-and-Cut, aplicado sobre um modelo lineal inteiro misto de partição de conjuntos (Set Partitioning) para LRP. Esta proposta metodológica é validada com casos de prova reais do sistema de transporte massivo da cidade de Pereira (Megabús), onde se consideram algumas regiões não conectadas da Área Metropolitana Centro Ocidente, localizada no Eje Cafetero colombiano.

Translated abstract

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.