Variable neighborhood search approach with intensified shake for monitor placement

Abstract

Several problems are emerging in the context of communication networks and mostof 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 tocover the communications of an entire network by locating a monitor in specificnodes of the network, in such a way that every link remains surveyed. In case thata solution cannot be generated in the allowed computing time, a penalty will beassumed for each link uncovered. The problem is addressed by considering the vari-able neighborhood search framework, proposing a novel constructive method, anintelligent local search to optimize the improvement phase, and an intensified shaketo guide the search to more promising solutions. The proposed algorithm is com-pared with a hybrid search evolutionary algorithm over a set of instances derivedfrom real-life networks to prove its performance.