Diseño topológico de redes : un caso : 2-node-connected star problem

Abstract

En este trabajo se propone un nuevo problema de optimización combinatoria que denominamos Two-Node-Connected Star Problem (2NCSP), el cual, dado un grafo simple con costos de ruteo y costos de asignación, tiene como objetivo encontrar un subgrafo de costo mínimo conformado por una componente 2-nodo conexa mientras que el resto de los nodos están asignadas a la misma mediante un enlace directo. El 2NCSP es una generalización del conocido Ring Star Problem [1] el cual difiere en que la componente 2-nodo conexa tiene que tener necesariamente topología de anillo. El objetivo de este trabajo es definir formalmente el problema Two-Node-Connected Star Problem y su resolución mediante una metaheurística GRASP de buen desempeño. Se diseñaron e implementaron búsquedas locales basadas en modelos de programación lineal entera y búsquedas locales que generan movimientos tradicionales para este tipo de problemas. Los resultados obtenidos muestran una buena performance del algoritmo en relación a instancias de prueba diseñadas y publicadas por otros autores. Dichas instancias de prueba consideran grafos de entre 50 y 200 nodos de la TSPLIB, donde los costos de asignación y conexión se obtienen con un factor de ponderación de la distancia euclidiana entre los nodos. Dicho factor permite determinar que la componente 2-nodo conexa de la solución deba contener la mayoría de los nodos, o solo unos pocos.