The Capacitated m Two-Node Survivable Star Problem: A Hybrid Metaheuristic Approach

In telecommunications, a traditional method to connect multiterminal systems is to use rings. The goal of the Capacitated m Ring Star Problem (CmRSP) is to connect terminals by m rings which meet at a distinguished node, and possibly by some pendant links, at minimum cost. In this paper, we introduce a relaxation for the CmRSP, called Capacitated m Two-Node Survivable Star Problem (CmTNSSP for short). The CmTNSSP belongs to the \(\mathcal {NP}\)-Hard class of computational problems. Therefore, we address a GRASP hybrid metaheuristic which alternates local searches that obtain incrementally better solutions, and exact resolution local searches based on Integer Linear Programming models. In consonance with predictions provided by Clyde Monma, the network can be equally robust but cheaper than in the original CmRSP.