Article ID: | iaor201727 |
Volume: | 69 |
Issue: | 2 |
Start Page Number: | 222 |
End Page Number: | 236 |
Publication Date: | Mar 2017 |
Journal: | Networks |
Authors: | Galinier Philippe, L Zhipeng, Wu Xinyun |
Keywords: | combinatorial optimization, search, sets, heuristics: local search |
The minimum connected dominating set problem (MCDSP) has become increasingly important in recent years due to its applicability to mobile ad hoc networks and sensor grids. This paper presents a restricted swap‐based neighborhood (RSN) tailored for solving MCDSP. This novel neighborhood structure is embedded into tabu Search (TS) and a perturbation mechanism is employed to enhance diversification. The proposed RSN‐TS algorithm is tested on four sets of public benchmark instances widely used in the literature. The results demonstrate the efficacy of the proposed algorithm in terms of both solution quality and computational efficiency. In particular, the RSN‐TS algorithm was able to improve the best known results on 41 out of the 97 problem instances while matching the best known results on all the remaining 56 instances. Furthermore, the article analyzes some key features of the proposed approach in order to identify its critical success factors.