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.