Methodology for creating feeder routes in mass transit systems

This paper proposes a methodology to identify feeder routes for areas disconnected to the Mass Transit System (MTS), in order to propose an alternative solution to the deficit in the number of passengers carried. The proposed methodology consists of two steps: (1) structuring scenarios for areas not connected to the transport system and (2) combining heuristic and exact techniques to solve the feeding routes problem considering in the restrictions the path length and passengers vehicle capacity. To model the problem, a comparison with the Location Routing problem is established, which is usually applied to freight transport problems. The methodology proposed is a math-heuristic combining 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 considering locations in Pereira (Megabús), where some areas disconnected to the Central-Occidental Metropolitan Area System (AMCO) of Pereira, located in Colombia's Coffee Axis are considered.
En este artículo se propone una metodología para identificar rutas alimentadoras en zonas no conectadas para un sistema de transporte masivo, esto 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 de transporte de pasajeros y el 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.