Problema General de Steiner en Grafos :Resultados y algoritmos GRASP para la versión arista-disjunta

Abstract

El Problema Generalizado de Steiner en Grafos (GSP) es un problema NP-hard de cobertura minimal de grafos con requerimientos de redundancia de conectividad, muy adecuado para modelar problemas reales de diseño topológico de redes de comunicación. La resolución determinística del problema sólo es factible para instancias de tamaño muy limitado, siendo en general para casos reales necesario recurrir a técnicas heurísticas para la generación de soluciones de bajo costo con un consumo razonable de recursos de cómputo y tiempo de ejecución. Los problemas se clasifican como de nodo-conectividad o arista-conectividad, según exijan o no los requerimientos de redundancia que no se compartan nodos intermedios entre caminos múltiples para conectar a las mismas parejas de nodos, modelándose así situaciones en las que tanto nodos como aristas pueden fallar, o solamente las aristas pueden hacerlo. En este trabajo, haciendo uso de una técnica metaheurística conocida como GRASP (Greedy Randomized Adaptive Search Procedure), extendemos las ideas planteadas en un trabajo previo para la versión de nodo-conectividad del GSP, hacia la versión de arista-conectividad. Se estudia la relación entre ambas versiones del problema, así como las complejidades introducidas por el modelo de arista-conectividad y se proponen mejoras a los algoritmos existentes. Proponemos también un mecanismo alternativo de creación voraz de soluciones y un mecanismo recursivo general para la implementación de metaheurísticas que generen soluciones para el GSP, sobre lo cual esperamos basar futuros trabajos de investigación.