Exact and metaheuristic approaches por Network Design Problems

Abstract

El Diseño de Redes juega un papel importante para entender y optimizar los flujos de información, recursos y servicios. En esta tesis, realizada en cotutela junto con la Universidad Libre de Bruselas, estudiamos problemas de Diseño de Redes desde el punto de vista de la Optimización combinatoria, buscando encontrar propiedades y métodos efectivos que mejoren el proceso de obtención de soluciones óptimas o al menos buenas. Los problemas tratados diseñan una red que sirve a cierta parte de un conjunto de pares de demanda origen/destino. Además se ha considerado la existencia de una red alternativa que puede ser utilizada por este conjunto de demanda, de manera que coopere con la red que se va a diseñar o que compita con la misma. Abordamos la resolución de todos los problemas propuestos a partir de la teoría de la Descomposición de Benders, diseñando e implementando lo que actualmente se conoce como Branch-and-Benders-cut. Además, se han considerado enfoques metaheur´ısticos para algunos de los problemas en cuestión.