Skewed Variable Neighborhood Search Method for the Weighted Generalized Regenerator Location Problem

Abstract

This paper deals with the Weighted Generalized Regenerator Location Problem (WGRLP) that arises in the design of optical telecommunication networks. During the transmission of optical signal, its quality deteriorates with the distance from the source, and therefore, it has to be regenerated by installing regenerators at some of the nodes in the network. The WGRLP involves weights assigned to potential regenerator locations, reflecting the costs of regenerator deployment. The objective of WGRLP is to minimize the sum of weights assigned to locations with installed regenerators, while ensuring a good quality communication among terminal nodes. As telecommunication networks usually involve large number of nodes, an efficient optimization method is required to deal with real-life problem dimensions. In this paper, a Skewed Variable Neighborhood Search method (SVNS) is proposed as solution approach for the WGRLP. The designed SVNS uses adequate data structures for solution representation and efficient procedures for objective function update, feasibility check, and solution repair. Computational results on the WGRLP data set from the literature show that the proposed SVNS reaches all known optimal solutions on small and medium size instances in short running times and outperforms existing heuristic approaches for the WGRLP. In addition, SVNS is tested on large scale WGRLP instances not considered in the literature so far. The presented computational results indicate the potential of SVNS as solution method for WGRLP and related network design problems.