An Iterated Tabu Search Metaheuristic for the Regenerator Location Problem

We study the regenerator location problem (RLP) in optical networks where optical signal can only travel a maximum distance before its quality deteriorates, requiring regenerations by installing regenerators at network nodes. The RLP is to determine the minimum number of nodes for regenerator placement such that for each node pair there is a path on which no subpath without internal regenerators has a length greater than a given maximum distance. The RLP is NP-complete. We propose an iterated metaheuristic that iteratively invokes a regenerator-reducing procedure and tabu search to collaboratively solve the RLP. We compare our approach with other heuristics using benchmark and new RLP instances. Because of the equivalence among RLP, maximum leaf spanning tree problem (MLSTP), minimum connected dominating set problem (MCDSP) and minimum 1-connected 1-dominating set problem (1-1-DSP), we also compare our approach with other algorithms over MLSTP/MCDSP/1-1-DSP instances. Results demonstrate the effectiveness and efficiency of our method.