Diseño de redes 2-nodo-conexas de mínimo costo con nodos de Steiner y caminos acotados (2NCON-BP-SN)

Abstract

El objeto de estudio es un problema de optimización de aplicabilidad en telecomunicaciones. Se dispone de una red con costos en sus aristas, la cual cuenta con nodos de Steiner opcionales con costos de construcción y una matriz de requerimientos de distancias entre cada par de nodos terminales. Se desea diseñar una subred 2-nodo conexa de costo mínimo, satisfaciendo las restricciones requeridas de largo de caminos entre todo par de nodos terminales. Este problema se denomina Diseño de Redes 2-Nodo-Conexas de Costo Mínimo con Nodos de Steiner y Caminos Acotados (2NCON-BP-SN, por sus siglas inglesas "2-Node CONnected Bounded Problem with Steiner Nodes"). El problema es intr nsecamente intratable del punto de vista computacional, por ser una generalizaci on del Problema de Steiner 2-Nodo Conexo (STNSNP). Como consecuencia, se desarrolla una metaheurística GRASP, que ha mostrado gran aplicabilidad en problemas de telecomunicaciones. En una primera etapa, la cual se denomina fase de construcción, se crean caminos iterativamente, con inspiración en el algoritmo CADILAC ("CAminos DIsjuntos de Largo Acotado"). A efectos comparativos, se ha definido una noción ávida o Greedy de resolución. Los resultados numéricos sobre instancias basadas en la librería TSPLIB indican un ahorro significativo con respecto a la solución Greedy.