Antonio| Mauttone| mauttone@fing.edu.uy| Instituto de Computación - Facultad de Ingeniería - Universidad de la República| Transit Network Design Problem: formulación matemática y solución heurística| optimización de recorridos en transporte público, programación matemática bi-nivel, heurísticas| DOCTORADO| | El problema de encontrar un conjunto óptimo de recorridos y sus frecuencias asociadas para un sistema de transporte público urbano, tiene en cuenta información de la red vial, demanda origen-destino, intereses de los usuarios y operadores, el comportamiento de los usuarios y un conjunto dado de restricciones físicas, políticas y de presupuesto. Se trata de un problema de compleja formulación y resolución exacta. La principal dificultad de formular el problema es la representación del comportamiento de los usuarios. Los métodos de solución deben enfrentar la alta complejidad combinatoria del problema. La literatura presenta varias soluciones basadas en heurísticas, donde no existe una formulación matemática explícita. Los enfoques basados en programación matemática presentan simplificaciones en la representación del comportamiento de los usuarios. En este trabajo proponemos una formulación de programación matemática que incluye: (i) un modelo del comportamiento de los usuarios que toma en cuenta el “problema de las líneas comunes”, usando un enfoque de estrategias óptimas, (ii) la capacidad de los buses, (iii) restricciones sobre el mínimo porcentaje de demanda satisfecha con un número dado de transbordos. La función objetivo minimiza el tiempo total de viaje (espera y a bordo) de los usuarios. Los intereses de los operadores son formulados mediante una restricción en el tamaño máximo de la flota. Utilizamos una representación de red que combina los modelos clásicos de redes urbanas con el modelo de red de transporte público de Spiess y Florian, que son extendidos para representar los transbordos. La formulación propuesta es bi-nivel, no lineal, con una cantidad exponencial de variables discretas, por lo tanto es muy difícil de ser resuelta de forma exacta, incluso para instancias del problema de tamaño mediano y chico. Proponemos una linealización de la formulación, que habilita a calcular cotas inferiores para instancias pequeñas, utilizando técnicas de programación lineal entera mixta. Implementamos una heurística simple basada en el algoritmo de construcción de recorridos de Mauttone y Urquhart y una búsqueda local en el dominio de las frecuencias; las soluciones obtenidas no son necesariamente factibles con respecto a todas las restricciones de la formulación. Se obtuvieron resultados de la heurística y cotas inferiores utilizando una relajación de la formulación linealizada, para instancias pequeñas de problema. Co autores: Ricardo Giesen y María Urquhart |