Diseño topológico de redes. Caso de estudio: Capacitated m Two-Node Survivable Star Problem

Abstract

Hoy en día prácticamente todas las actividades inherentes al ser humano tienen un soporte de hardware y software que las gestiona o las controla. Los elementos de comunicaciones cumplen un papel vital en este entramado. El diseño de topologías de redes tolerantes a fallos ha pasado a tener una importancia fundamental en la infraestructura de estas redes y constituye un elemento crítico a la hora de mantener la comunicación ante la falla de un enlace o alguno de sus nodos. El problema tratado en esta tesis intenta resolver eficientemente el diseño de una red con conexiones redundantes utilizada a menudo por los operadores telefónicos y servicios de internet. Dicha red conecta un nodo principal con clientes y establece algunas normas que modelan su construcción, tales como cantidad de clientes, número de componentes y tipos de enlaces, con el fin de satisfacer restricciones técnicas y necesidades operativas. Se considera en este trabajo un problema de optimización combinatoria denominado CmTNSSP (Capacitated m Two-Node-Survivable Star Problem), una relajación del problema CmRSP (Capacitated m Ring Star Problem). La variante relajada consiste en que los anillos (rings) del problema CmRSP pueden ser componentes 2-nodo-conexas, las cuales no necesariamente deben ser ciclos. El objetivo de esta tesis consta de la especificación de un modelo de programación matemática del problema a tratar, la resolución exacta mediante un lenguaje algebraico y un solver, y la resolución aproximada del mismo a través de una metaheurística que alterna búsquedas locales que obtienen soluciones incrementalmente mejores y búsquedas locales de resolución exacta basadas en modelos de programación matemática, en particular Programación Lineal Entera. Los resultados computacionales obtenidos por los algoritmos desarrollados muestran la robustez y competitividad de los mismos, comparados con las instancias benchmark publicadas en la literatura. Así mismo los experimentos muestran la relevancia de considerar la variante concreta del problema estudiado en esta tesis.