Efficient Greedy Randomized Adaptive Search Procedure for the Generalized Regenerator Location Problem

DOI

10.1080/18756891.2016.1256568How to use a DOI?

Keywords

GRASP; regenerator; telecommunications; metaheuristic; generalized regenerator location problem

Abstract

Over the years, there has been an evolution in the manner in which we perform traditional tasks. Nowadays, almost every simple action that we can think about involves the connection among two or more devices. It is desirable to have a high quality connection among devices, by using electronic or optical signals. Therefore, it is really important to have a reliable connection among terminals in the network. However, the transmission of the signal deteriorates when increasing the distance among devices. There exists a special piece of equipment that we can deploy in a network, called regenerator, which is able to restore the signal transmitted through it, in order to maintain its quality. Deploying a regenerator in a network is generally expensive, so it is important to minimize the number of regenerators used. In this paper we focus on the Generalized Regenerator Location Problem (GRLP), which tries to find the minimum number of regenerators that must be deployed in a network in order to have a reliable communication without loss of quality. We present a GRASP metaheuristic in order to find good solutions for the GRLP. The results obtained by the proposal are compared with the best previous methods for this problem. We conduct an extensive computational experience with 60 large and challenging instances, emerging the proposed method as the best performing one. This fact is finally supported by non-parametric statistical tests.

Copyright

© 2016. the authors. Co-published by Atlantis Press and Taylor & Francis

Open Access

This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Download article (PDF)
View full text (HTML)

TY  - JOUR
AU  - J.D. Quintana
AU  - J. Sánchez-Oro
AU  - A. Duarte
PY  - 2016
DA  - 2016/12/01
TI  - Efficient Greedy Randomized Adaptive Search Procedure for the Generalized Regenerator Location Problem
JO  - International Journal of Computational Intelligence Systems
SP  - 1016
EP  - 1027
VL  - 9
IS  - 6
SN  - 1875-6883
UR  - https://doi.org/10.1080/18756891.2016.1256568
DO  - 10.1080/18756891.2016.1256568
ID  - Quintana2016
ER  -