A Hybrid Metaheuristic Strategy for Covering with Wireless Devices

Antonio L. Bajuelos (University of Aveiro, Portugal)

Santiago Canales (Universidad Pontifícia Comillas de Madrid, Spain)

Gregorio Hernández (Universidad Politécnica de Madrid, Spain)

Mafalda Martins (University of Aveiro, Portugal)

Abstract: 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.

Keywords: art gallery problems, computational geometry, hybrid metaheuristics and approximation algorithms, visibility and coverage problems

Categories: G.1.6, I.2.8