Improved heuristics for the regenerator location problem

Improved heuristics for the regenerator location problem

0.00 Avg rating0 Votes
Article ID: iaor201524347
Volume: 21
Issue: 4
Start Page Number: 541
End Page Number: 558
Publication Date: Jul 2014
Journal: International Transactions in Operational Research
Authors: , , ,
Keywords: heuristics, heuristics: genetic algorithms
Abstract:

Telecommunication systems use optical signals to transmit information. The strength of a signal in an optical network deteriorates and loses power as it goes farther from the source, mainly due to attenuation. Therefore, to enable the signal to arrive its intended destination with good quality, it is necessary to regenerate the signal periodically using regenerators. These components are relatively expensive and therefore it is desirable to deploy as few of them as possible in the network. In the regenerator location problem (RLP), we are given an undirected graph, positive edge lengths, and a parameter specifying the maximum length that a signal can travel before its quality deteriorates and regeneration is required. The problem consists in determining paths that connect all pairs of nodes in the graph and, if necessary, locating single regenerators in some of those nodes such that the signal never travels more than the maximum allowed distance without traversing a regenerator node. In this paper, we present new implementations of previous heuristics and two new heuristics–a GRASP and a biased random‐key genetic algorithm–for the RLP. Computational experiments comparing the proposed solution procedures with previous heuristics described in the literature illustrate the efficiency and effectiveness of our methods.

Reviews

Required fields are marked *. Your email address will not be published.