A Hybrid Metaheuristic Strategy for Covering with Wireless Devices

In this paper we focus on approximate solutions to solve a new class of art gallery problems inspired by wireless localization. instead of the usual guards we consider wireless devices whose signal can cross a certain number, k, of walls.these devices are called k-transmitters. we propose an algorithm for constructing the visibility region of a k-transmitter located on a point of a simple polygon. then we apply a hybrid metaheuristic strategy to tackle the problem of minimizing the number of k-transmitters, located at vertices, that cover a given simple polygon, and compare its performance with two pure metaheuristics. we conclude that the approximate solutions obtained with the hybrid strategy, for 2-transmitters and 4-transmitters, on simple polygons, monotone polygons, orthogonal polygons and monotone orthogonal polygons, are better than the solutions obtained with the pure strategies.