Variable neighborhood search approach with intensified shake for monitor placement. Issue 3 (1st December 2022)

• Record Type: Journal Article
• Authors: Casado, Alejandra; Mladenović, Nenad; Sánchez‐Oro, Jesús; Duarte, Abraham
• Is Part Of: Networks. Volume 81:Issue 3(2023)
• Page Start: 319
• Page End: 333
• Publication Date: 2022-12-01
• Subjects: intensified shake -- metaheuristics -- monitor placement -- variable neighborhood search; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22134
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: Several problems are emerging in the context of communication networks and most of them must be solved in reduced computing time since they affect to critical tasks. In this research, the monitor placement problem is tackled. This problem tries to cover the communications of an entire network by locating a monitor in specific nodes of the network, in such a way that every link remains surveyed. In case that a solution cannot be generated in the allowed computing time, a penalty will be assumed for each link uncovered. The problem is addressed by considering the variable neighborhood search framework, proposing a novel constructive method, an intelligent local search to optimize the improvement phase, and an intensified shake to guide the search to more promising solutions. The proposed algorithm is compared with a hybrid search evolutionary algorithm over a set of instances derived from real‐life networks to prove its performance.