Premium
Improved heuristics for the regenerator location problem
Author(s) -
Duarte A.,
Martí R.,
Resende M.G.C.,
Silva R.M.A.
Publication year - 2014
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12085
Subject(s) - heuristics , traverse , computer science , grasp , regenerative heat exchanger , signal (programming language) , mathematical optimization , node (physics) , graph , algorithm , mathematics , theoretical computer science , engineering , mechanical engineering , heat exchanger , geodesy , structural engineering , programming language , geography
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.