Variable neighborhood search variants for Min-power symmetric connectivity problem

• Published in: Computers & operations research 2017-02, Vol.78, p.557-563
• Main Authors: Erzin, A.I., Mladenovic, N., Plotnikov, R.V.
• Format: Article
• Language: English
• Subjects: Computer Science; Energy efficiency; NP-hard problem; Variable neighborhood search; Wireless sensor network
• ISSN: 0305-0548; 1873-765X
• DOI: 10.1016/j.cor.2016.05.010

We consider the problem of optimal communication tree construction in a given undirected weighted graph. Such a problem occurs while minimizing the power consumption of data transmission in different distributed networks in the case when network elements are able to adjust their transmission ranges. In this paper, the most general strongly NP-hard formulation, when edge weights have arbitrary non-negative values, is considered. We propose new heuristics, mostly based on variable neighborhood search, for getting an approximate solution of the problem. Extensive comparative analysis between the proposed methods was performed. Numerical experiments demonstrated the high efficiency of the proposed heuristics. •Proposed new local search that is based on elementary tree transformation (ETT). In terms of solution quality it significantly outperforms the previous one (named as LI), but uses more computation time.•Several basic VNS- and general VNS-based heuristics are proposed and tested. Some of these new heuristics give results of better quality than the recent state-of-the-art (hybrid heuristic [4]) technique, especially for solving more realistic large size problems.•A simulation has been executed. Its results demonstrated high efficiency of the majority of the proposed methods.