Título: Optimización de recorridos y frecuencias en sistemas de transporte público

Marco de Trabajo: Doctorado

Área de desarrollo: Investigació Operativa

Autor: Antonio Mauttone

Contacto: mauttone@fing.edu.uy

Día: MARTES

Hora: 9:00

Palabras Claves: TNDP, heurísticas, optimización multi-objetivo, caso de estudio real

Resumen:
El TNDP (Transit Network Design Problem) consiste en determinar los trazados de los recorridos de un sistema de transporte público y sus frecuencias, minimizando los tiempos de viaje y de espera de los usuarios y los costos de los operadores. Los principales datos del problema son la red de calles sobre la que se definen los recorridos y una matriz origen-destino que indica la demanda de viajes entre distintos puntos de la ciudad en un determinado horizonte horario. Desde el punto de vista del modelado matemático y su resolución algorítmica, el problema plantea varias dificultades [1]: complejidad combinatoria, sub-modelo de asignación y naturaleza multi-objetivo. Los métodos de optimización existentes en la literatura para el TNDP pueden clasificarse en exactos (formulaciones de programación matemática, en algunos casos con un algoritmo asociado de resolución) y aproximados (heurísticas y metaheurísticas). Los avances de esta tesis de Doctorado en Informática se presentan en torno a los siguientes cuatro aspectos del TNDP:

- El Pair Insertion Algorithm [4] es un algoritmo ávido, que construye un conjunto de recorridos que cubre la demanda, tratando de minimizar las funciones objetivo de los usuarios y los operadores. Este algoritmo puede utilizarse como subrutina de un método aproximado para el TNDP.
- El algoritmo GRASP TNDP [2] obtiene en una sola ejecución un conjunto de soluciones no-dominadas, que representan diferentes grados de compromiso entre los objetivos en conflicto de los usuarios y de los operadores.
- Formulación de programación lineal entera que modela los tiempos de espera y los transbordos, elementos del TNDP no incluidos en formulaciones existentes en la literatura [5].
- Se aplica el algoritmo GRASP TNDP a la instancia de la ciudad de Rivera, Uruguay, cuyos datos fueron relevados específicamente con este fin. Se formulan conclusiones acerca del algoritmo y de la solución de recorridos y frecuencias que opera en la ciudad al momento de realizar el estudio [3]
[1] Baaj, M; Mahmassani, H. An AI-based approach for transit route system planning and design. Journal of Advanced Transportation 25(2):187–210, 1991.
[2] Mauttone, A.; Urquhart, M. A Multi-Objective Metaheuristic approach for the Transit Network Design Problem. En: 10th International Conference on Computer Aided Scheduling of Public Transport, Leeds, United Kingdom, 2006.
[3] Mauttone, A.; Urquhart, M. Optimización multi-objetivo de recorridos y frecuencias en transporte público aplicado a un caso de estudio real. En: XIII Congreso Chileno de Ingeniería de Transporte, Santiago, Chile, 2007.
[4] Mauttone, A.; Urquhart, M. A route set construction algorithm for the Transit Network Design Problem. Computers and Operations Research, en prensa, 2008.
[5] Mauttone, A.; Urquhart, M. Modelo de programación lineal entera para el diseño de redes de transporte público. In: XIV Congreso Latino Ibero Americano de Investigación de Operaciones, Cartagena de Indias, Colombia, 2008.