Modelo de optimización robusto para el diseño de redes bajo condiciones de equilibrio

Abstract

Los problemas de diseño de red se utilizan en muchos contextos, como por ejemplo, para modelar el transporte de pasajeros que se mueven desde y hacia distintos lugares dentro de una ciudad como también para la transmisión de mensajes en una red de comunicación o transmisión de energía en una red eléctrica. En este trabajo de tesis, se busca enfocar el problema de diseño de red para modelar el tránsito de personas de un punto a otro dentro de un área urbana incorporando su comportamiento en este tipo de situaciones. Para ello, se considera el problema de diseño de redes modelado a través de una programación binivel, donde un nivel de decisión determina el comportamiento egoísta de los usuarios de la red que buscan escoger el camino más corto entre sus orígenes y destinos, mientras que en el otro nivel, un planificador central decide reducir los costos de la red completa. Además de esto, se considera que la demanda del problema es incierta y se incorpora al modelo utilizando una metodología de optimización robusta. Se presentan dos formulaciones de modelos que se diferencian principalmente por el tipo de función de latencia que se considera. En una se utiliza una función de latencia lineal y se incorporan restricciones de capacidad, mientras que en la otra se ingresa la capacidad en una función de latencia estrictamente convexa, pudiendo remover las restricciones de capacidad. Con el fin de aproximar el problema robusto para que pueda ser computacionalmente tratable, se demuestra que si el conjunto de incertidumbre es un poliedro y, además, la función de costos es convexa, entonces resolver el problema de diseño de redes con demandas que sean vértices del conjunto de incertidumbre permite determinar cotas superiores e inferiores al valor óptimo del problema de diseño de redes robusto. Por lo que en definitiva, se encuentra una solución robusta que es una aproximación a la solución óptima del problema robusto original. Los resultados computacionales muestran que en instancias pequeñas el modelo funciona eficientemente con bajos tiempos de ejecución, sin embargo, si el tamaño del problema crece, la resolución en forma exacta incurre en altos costos computacionales. No obstante, en las instancias pequeñas se observa que la solución robusta aproximada tiene una modesta sub-optimalidad en escenarios deterministas cerca del promedio mientras que reduce significativamente el costo del peor caso. En particular, a medida que la incertidumbre crece, la protección del modelo robusto en el peor caso es mayor. En síntesis, en esta tesis se plantea, resuelve e implementa un modelo de optimización de diseño de redes que es robusto respecto a demandas inciertas y que minimiza costos de tiempos de viaje sujeto a restricciones de presupuesto, donde los usuarios se comportan satisfaciendo condiciones de equilibrio.