Generalized covering location problem with multiple-coverage: Exact and heuristic method

This paper considers some extensions of the basic covering set location problem. The purpose of the covering set location models is to select a set of facilities (public facilities, antennas, etc.) to be implemented in order to satisfy all or a part of the demand of a given area. A facility has a constant coverage radius R and a demand node is covered, if it is within distance R of an established facility. We introduce an original model, in which we take into account: (i) the costs incurred to establish a facility, (ii) the costs incurred if a demand node is not covered, (iii) the cost or gain incurred if a demand node is covered by more than one facility. We introduce some properties of an optimal solution and derive heuristic algorithms and a branch and bound method from these properties. We illustrate this approach with numerical examples.