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

摘要

In telecommunications, a traditional method to connect mul-titerminal 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 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.