Cooperative covering problems on networks

In this article, we consider the cooperative maximum covering location problem on a network. In this model, it is assumed that each facility emits a certain ‘signal’ whose strength decays over distance according to some ‘signal strength function.’ A demand point is covered if the total signal transmitted from all the facilities exceeds a predefined threshold. The problem is to locate facilities so as to maximize the total demand covered. For the 2‐facility problem, we present efficient polynomial algorithms for the cases of linear and piecewise linear signal strength functions. For the p‐facility problem, we develop a finite dominant set, a mixed‐integer programming formulation that can be used for small instances, and two heuristics that can be used for large instances. The heuristics use the exact algorithm for the 2‐facility case. We report results of computational experiments.