Inteligencia computacional para la generación de matrices origen-destino y la relocalización de paradas de autobuses

Abstract

Conocer la movilidad de los habitantes resulta fundamental para la planificación y diseño del sistema de transporte urbano con el fin de brindar un servicio de calidad cada vez más exigente. En este proyecto se estudia el problema de generación de matrices origen-destino y el problema de relocalización de paradas de autobuses. Ambos problemas están relacionados y tienen aspectos en común. Para el primer problema se implementan dos algoritmos para procesar grandes volúmenes de información del transporte público específico para la ciudad de Montevideo, Uruguay. Estos algoritmos permiten generar la matriz origen-destino mediante la estimación de los destinos analizando la información de los boletos vendidos y la localización de los autobuses. El escenario utilizado corresponde a los datos del año 2015, alcanzando un volumen de 200 GB de datos. Se propone una implementación distribuida, obteniendo mejoras en speedup de hasta 17.10. Para el segundo problema se implementa un algoritmo evolutivo multiobjetivo (más específicamente NSGA-II) para relocalizar las paradas de los autobuses, buscando mejorar la calidad de servicio, optimizando el tiempo de recorrido minimizando el costo. El algoritmo es evaluado con instancias realistas del problema, generadas a partir de la matriz origen-destino obtenida y las líneas y paradas de autobuses correspondientes al año 2015. Los resultados experimentales muestran que el algoritmo es eficiente en la búsqueda de soluciones de calidad, obteniendo mejoras de hasta 16.7% y 33.9% en tiempo y costo respectivamente frente a la situación correspondiente al año 2015.

Knowing the mobility of habitants is essential for planning and design of the urban transport system in order to provide an even more demanding quality service. This project studies the generation of origin-destination matrices problem and the bus stop relocation problem. Both problemas are related and have aspects in common. For the rst problem two algorithms are implemented for processing large volumes of public transport information speci c for the city of Montevideo, Uruguay. These algorithms allow generating the origin-destination matrix by estimating the destinations analyzing the information of the tickets sales and the location of the buses. The scenario used corresponds to the data for the year 2015, reaching a volume of 200 GB of data. A distributed implementation is proposed, obtaining improvements in speedup of up to 17.10. For the second problem, a multiobjective evolutionary algorithm (more specifi cally NSGA-II) is implemented to relocate bus stops, in order to improve quality of service, by optimizing travel time while minimizing cost. The algorithm is evaluated with realistic instances of the problem, generated from the origin-destination matrix obtained and the lines and bus stops for the year 2015. The experimental analysis show that the algorithm is effcient in searching for quality solutions, obtaining improvements of up to 16.7% and 33.9% in time and cost respectively compare to the current situation for the year 2015.