Clique and independent set based grasp approaches for the regenerator location problem

Abstract

We consider the Regenerator Location Problem (RLP) in optical fibre communication networks: As optical signals deteriorate in dependence of the distance from the source, regenerator devices need to be installed at a subset of the network nodes so that no segment of any communication path without an intermediate regenerator exceeds an allowed maximum length. The objective is to place a smallest possible number of regenerators in order to satisfy this condition. We propose two new construction heuristics based on identifying and exploiting cliques and independent sets of the network graph. These strategies are further extended to Greedy Randomized Adaptive Search Procedures (GRASP) that also include new destroy and recreate local search phases. Excellent results are obtained in an experimental comparison with a previously described GRASP.