UN FRAMEWORK PARA LA CREACIÓN DE INSTANCIAS DEL PROBLEMA DE RUTAS DE TRÁNSITO URBANO

Abstract

Los sistemas de transporte son componentes críticos para las ciudades, impactando inmensamente la calidad de vida de sus ciudadanos, proveyendo alternativas de transporte, reduciendo drásticamente el tráfico vehicular y la contaminación atmosférica. Se requiere de una cuidadosa planificación para evitar usuarios descontentos y un sistema insostenible, siendo fundamental el correcto diseño de la red de rutas de buses. En consecuencia, el Urban Transit Routing Problem (UTRP) se enfoca en encontrar un conjunto de rutas de buses que minimiza el tiempo de viaje de los pasajeros y los costos al operador del sistema. Varios algoritmos han sido desarrollados para resolver el UTRP, pero la mayoría de las instancias del problema carecen de datos de demanda de la vida real, con las instancias más conocidas siendo muy pequeñas para los estándares actuales y/o generadas aleatoriamente. Las técnicas de relajación del estado del arte se basan en características inherentes de los sistemas de transporte urbano y no pueden reducir de manera significativa el orden de magnitud de instancias complejas. En este trabajo, se propone un framework para generar instancias de UTRP usando datos de demanda zonal de la vida real, que incluyen miles de ubicaciones de paraderos. Los algoritmos de clustering permiten al framework reducir la complejidad del problema generando una aproximación que mantiene el comportamiento de la demanda y la estructura de caminos manteniendo conectadas y representadas tanto ubicaciones centrales como periféricas. El framework se aplica al complejo sistema de transporte público de la ciudad de Santiago de Chile. Se generan instancias con un comportamiento similar de demanda al usar una cantidad suficiente de clústeres. Además, los diversos algoritmos de clustering probados muestran una alta similitud en su salida y rendimiento. Este framework es fácilmente aplicable a diferentes realidades y debería ayudar a futuros investigadores en el diseño de algoritmos de resolución, así como mejorar los modelos de aproximación de otras ciudades.Transportation systems are critical components of urban cities, by hugely impacting the quality of life of their citizens, providing alternative means of transportation and drastically reducing street traffic and atmospheric pollution. Careful planning is required to avoid disgruntled users and an unsustainable system, where the correct design of the bus routes network is a fundamental task. Thus, Urban Transit Routing Problem (UTRP) aims to find a set of bus routes that minimises users travelling time and system operator costs. Several algorithms have been developed to solve the UTRP, but most problem instances lack real-life demand data information, where well-known benchmark instances are very small w.r.t. current standards and/or they have been randomly generated. State-of-the-art relaxation techniques are based on inherent features of urban transport systems and they cannot significantly reduce the order of magnitude of complex instances. In this work, we propose a framework to generate UTRP instances using real-life zone-based demand data, including thousand of bus stops locations. Clustering algorithms allow the framework to reduce the problem complexity by generating an approximation that preserves demand behaviour and road structure by keeping central and periphery locations represented and connected. Our study case is the complex public transport system of Santiago, Chile. We generate instances that have similar demand behaviour when using enough amount of clusters. Also, the use of several cluster algorithms shows similar performance and output. This framework is easily applicable to different realities and it should help future researchers to test network design algorithms as well as to improve the approximation models of other cities.