Breakout variable neighbourhood search for the minimum interference frequency assignment problem

Pages468-488
DOIhttps://doi.org/10.1108/JSIT-10-2017-0094
Date12 November 2018
Published date12 November 2018
AuthorYasmine Lahsinat,Dalila Boughaci,Belaid Benhamou
Subject MatterInformation & knowledge management,Information systems,Information & communications technology
Breakout variable neighbourhood
search for the minimum
interference frequency
assignment problem
Yasmine Lahsinat and Dalila Boughaci
Université des Sciences et de la Technologie Houari Boumediene, Algiers, Algeria, and
Belaid Benhamou
Aix-Marseille Université, Laboratoire LIS, Marseille, France
Abstract
Purpose This paper aims to describe two enhancements of the variable neighbourhood search (VNS)
algorithm to solve efciently theminimum interference frequency assignment problem (MI-FAP)which is a
major issue in the radio networks,as well as a well-known NP-hard combinatorial optimisationproblem. The
challenge is to assign a frequency to each transceiverof the network with limited or no interferences at all.
Indeed, consideringthat the number of radio networks users is ever increasing and thatthe radio spectrum is
a scarce andexpensive resource, the latter should becarefully managed to avoid any interference.
Design/methodology/approach The authors suggest two new enhanced VNS variants for MI-FAP,
namely, the iterated VNS (It-VNS) and the breakout VNS (BVNS). These two algorithms were designed based on
the hybridising and the collaboration approaches that have emerged as two powerful means to solve hard
combinatorial optimisation problems. Therefore, these two methods draw their strength from other meta-
heuristics. In addition, the authors introduced a new mechanism of perturbation to enhance the performance of
VNS. An extensive experiment was conducted to evaluate the performance of the proposed methods on some
well-known MI-FAP datasets. Moreover, they carried out a comparative study with other metaheuristics and
achieved the Friedmans non-parametric statistical test to check the actual effect of the proposed enhancements.
Findings The experiments showed that the twoenhanced methods (It-VNS) and (BVNS) achieved better
results than the VNS method. The comparativestudy with other meta-heuristics showed that the results are
competitive and very encouraging. The Friedmans non-parametric statistical test reveals clearly that the
results of the three methods(It-VNS, BVNS and VNS) are signicantly different. Theauthors therefore carried
out the Nemenyis post hoc test which allowed us to identify those differences. The impactof the operated
change on both the It-VNS and BVNS was thusconrmed. The proposed BVNS is competitive and able to
produce goodresults as compared with both It-VNS andVNS for MI-FAP.
Research limitations/implications Approached methodsand particularly newly designed ones may
have some drawbacks that weaken the results, in particular when dealing with extensive data. These
limitationsshould therefore be eliminated through an appropriateapproach with a view to design appropriate
methodsin the case of large-scale data.
Practical implications The authors designedand implemented two new variants of the VNS algorithm
before carryingout an exhaustive experimental study. The ndings highlighted the potentialopportunities of
these two enhanced methods which could be adapted and applied to other combinatorial optimisation
problems,real world applications or academic problems.
Originality/value This paper aims at enhancing the VNS algorithm through two new approaches,
namely, the It-VNSand the BVNS. These two methods were applied to the MI-FAP which is a crucial problem
arising in a radio network.The numericalresults are interesting and demonstrate the benets of the proposed
approachesin particular BVNS for MI-FAP.
Keywords Optimisation, Breakout VNS, It-VNS, MI-FAP, VNS
Paper type Research paper
JSIT
20,4
468
Received10 October 2017
Revised10 February 2018
10March 2018
20September 2018
Accepted15 October 2018
Journalof Systems and
InformationTechnology
Vol.20 No. 4, 2018
pp. 468-488
© Emerald Publishing Limited
1328-7265
DOI 10.1108/JSIT-10-2017-0094
The current issue and full text archive of this journal is available on Emerald Insight at:
www.emeraldinsight.com/1328-7265.htm
1. Introduction
The minimum interference frequency assignment problem (MI-FAP) which may arise in
operational researchis one of the combinatorial optimisation problems. It was rst identied
by Metzger in the sixties (Metzger, 1970) and has been the subjectof several studies (Aardal
et al.,2007;Eisenblatter et al., 2002;Leese and Hurley, 2002).The radio spectrum is a scarce
resource with a limited rangeof frequencies. This is particularly true for the MI-FAP where
a range of predened, limited and authorised frequencies is available. Moreover, a huge
number of transceivers(TRXs) distributed over a wide geographic area need to be managed.
Since those TRXs of the radio network shouldcommunicate over such a restricted range of
frequencies, a frequencyshould be attributed to each one of them with no, or at least, limited
interferences. Indeed, if the TRXs are conned in a narrow geographical area and use the
same frequency or frequencies that fail to conform to the frequency separation constraints
they would interferewith one another.
The MI-FAP has been modelledusing various formulations while taking into account the
nature of its primary objective which aimsat limiting the number of channels, the range of
the spectrum (span) or the total number of interferences. Authors in Aardal et al. (2007)
provided a good description of the various formulations. In this paper, we focussed on the
MI-FAP where the key objective is to assign frequencies to the TRXs in such a way to
minimise the interference level. The MI-FAP is a generalisation of the graph-colouring
problem (Hale, 1980) and theoretically well known to be NP-Hard (Hale, 1980). Its interest
from the theoretical point of view drove us to meet the challenge of designing and testing
some algorithms likelyto solve it efciently in practice.
Both the evolutionary and the trajectory methods have been proposed to dealwith the MI-
FAP. In this respect, some approaches were proposed, such as the EAs and Ant Colony
optimisationalgorithms (ACO/EAs) (Lunaet al .,2007), as well as a cultural algorithm (Alami
and El Imrani, 2008). Moreover, two recent works suggested a harmony search algorithm to
handle the MI-FAP(Lahsinat et al., 2017a,2017b). Some other works usedtrajectory methods
including the Tabu search algorithm (Castelino et al.,1996;Montemanni, et al.,2003;
Montemanni and Smith, 2010;Mabed et al.,2011). Other researchers proposed simulated
annealing algorithms (Duque-Anton et al.,1993;Beckmann and Killat, 1999). Some other
studies using different methods, such as a branch and cut algorithm (Fschetti et al.,2000),
parallel hyper-heuristic approaches (Segura et al.,2011), some hybrid approaches (Luna et al.,
2011) are to be mentioned along with other methods like those suggested by Audhya et al.
(2013);Flood and Allen (2013) and Wu et al. (2013), as well as the path relinking algorithm
(Xiangjingand Jin-Kao, 2015). Severalother works could also be added to that list.
In this paper, we proposed an adaptation of the variable neighbourhood search (VNS)
algorithm to solve the MI- FAP. We also reviewed its potentialities, as well as the extent to
which it may provide a practical solution to the problem. In so doing, we tried to improve the
results of the VNS algorithm when dealing with the MI-FAP. More specically, we introduced
some changes to the standard VNS algorithm in an attempt to improve it. We also incorporated
variousfeaturesofsomewell-establishedsinglebased meta-heuristics int othe basic VN S.
To begin with, we introduced a perturbationmechanism in the VNS method to obtain an
iterated VNS variant known as (It-VNS).In other words, we applied a perturbation operator
to the current local optimum at a given phase ofthe VNS algorithm so as to bring diversity
and avoid to be trapped in a local optimum. Hence, for eachdecision variable in the current
solution, the procedure itself determines whether to modify its value or not with a given
probability. To this end, the It-VNS variant was endowedwith two parameters designed to
control the perturbation.
Frequency
assignment
problem
469

To continue reading

Request your trial

VLEX uses login cookies to provide you with a better browsing experience. If you click on 'Accept' or continue browsing this site we consider that you accept our cookie policy. ACCEPT