An Efficient Fixed Set Search for the Covering Location with Interconnected Facilities Problem

Abstract

This paper studies the Coverage Location Problem with Interconnected Facilities (CPIF). It belongs to the family of Facility Location Problems, but being more realistic to nowadays situations as surveillance, or natural disaster control. This problem aims at locating a set of interconnected facilities to minimize the number of demand points that are not covered by the selected facilities. Two facilities are considered as interconnected if the distance between them is smaller than or equal to a predefined distance, while a facility covers a demand point if the distance to it is smaller than a certain threshold. The wide variety of real-world applications that fit into this model makes them attractive for designing an algorithm able to solve the problem efficiently. To this end, a metaheuristic algorithm based on the Fixed Set Search framework is implemented. The proposed algorithm will be able to provide high-quality solutions in short computational times, being competitive with the state-of-the-art.