Diseño heurístico de redes con requerimientos de conectividad

Abstract

Proponemos una heurística para el problema generalizado de Steiner (Generalized Network Steiner Problem), un problema de importancia en el diseño de redes de comunicaciones. Una instancia de este problema consiste en una red con costos asociados a las líneas y con requerimientos de arista-conectividad asociados a cada par (i,j) de nodos terminales. El objetivo es encontrar una red de mínimo costo utilizando las líneas disponibles y que satisfaga los requerimientos. La heurística propuesta consiste en una búsqueda con componentes aleatorios, que emplea ideas provenientes de la metodología conocida como Sistemas de hormigas (Ant Systems). Se presentan resultados experimentales sobre un conjunto de instancias del problema con diferentes características y requerimientos de conectividad, obteniendo en todos los casos resultados óptimos o muy cercanos al óptimo.