María| Urquhart| urquhart@fing.edu.uy| Instituto de Computación - Facultad de Ingeniería - Universidad de la República| Modelos y algoritmos para el Transit Network Design Problem| optimización de recorridos en transporte público, metaheurísticas para optimización multi-objetivo, caso de estudio real| INVESTIGACION| | El Transit Network Design Problem (TNDP) consiste en encontrar un conjunto de recorridos con sus correspondientes frecuencias para un sistema de transporte público urbano. Se busca optimizar los objetivos de los usuarios y de los operadores bajo un conjunto dado de restricciones, tomando como información de entrada la red vial y una matriz origen-destino. Presentamos los principales resultados en el contexto de un proyecto en marcha de largo alcance, abocado al desarrollo de modelos y algoritmos para el TNDP y la construcción de una herramienta de software que asista al investigador en la aplicación de los mismos. El Algoritmo de Inserción de Pares es un algoritmo constructivo goloso, que produce un conjunto de recorridos que son convenientes para los usuarios y los operadores; las frecuencias no son consideradas. Es inspirado en el Algoritmo de Generación de Recorridos de Baaj y Mahmassani. Ambos algoritmos producen soluciones de similar calidad desde el punto de vista de los usuarios (en términos de tiempo de viaje a bordo), mientras el primero produce mejores soluciones desde el punto de vista del operador (en términos de la cantidad de recorridos y la duración total de los mismos), requiriendo un mayor tiempo de ejecución. La característica multi-objetivo del TNDP es atacada en el algoritmo GRASP TNDP, que produce un conjunto de soluciones (recorridos con sus frecuencias) no dominadas que representan diferentes niveles de compromiso entre los objetivos conflictivos de usuarios y operadores. El algoritmo es heurístico en dos sentidos: (i) no necesariamente cubre el rango completo de niveles de compromiso entre los objetivos conflictivos, (ii) no garantiza la Pareto optimalidad de las soluciones obtenidas. El algoritmo usa ideas de Greedy Randomized Adaptive Search Procedures y produce el resultado en una sola ejecución, es decir, no resuelve el problema multi-objetivo resolviendo repetidamente un problema de objetivo único El algoritmo GRASP TNDP es aplicado a la ciudad de Rivera, Uruguay. La ciudad tiene 65000 habitantes y su sistema de transporte público tiene 13 líneas. La matriz origen-destino fue obtenida realizando una encuesta a bordo de las líneas del sistema existente; de esta forma se obtuvo una aproximación a la matriz real de viajes deseados. El algoritmo produjo 238 soluciones no dominadas que cubren un amplio rango de niveles de compromiso entre los objetivos en conflicto. El sistema existente en la ciudad (recorridos y frecuencias) fue evaluado usando el mismo modelo de asignación y fue comparado con las soluciones de GRASP TNDP. igoR-tp es una herramienta de software desarrollada en el proyecto, que soporta el procesamiento de datos geográficos y de demanda, y la experimentación con nuevos algoritmos. Al momento, la herramienta tiene propósitos de investigación, sin embargo puede ser extendida con funcionalidades orientadas al planificador del sistema de transporte público. Co autores: Héctor Cancela, Antonio Mauttone y Omar Viera |