Cooperative cover location problems: The planar case

Abstract

A cooperative-covering family of location problems is proposed in this paper. Each facility emits a (possibly non-physical) “signal” which decays over the distance and each demand point observes the aggregate signal emitted by all facilities. It is assumed that a demand point is covered if its aggregate signal exceeds a given threshold; thus facilities cooperate to provide coverage, as opposed to the classical coverage location model where coverage is only provided by the closest facility. It is shown that this cooperative assumption is appropriate in a variety of applications. Moreover, ignoring the cooperative behavior (i.e., assuming the traditional individual coverage framework) leads to solutions that are significantly worse than the optimal cooperative cover solutions; this is illustrated with a case study of locating warning sirens in North Orange County, California. The problems are formulated, analyzed and solved in the plane for the Euclidean distance case. Optimal and heuristic algorithms are proposed and extensive computational experiments are reported.

Keywords:

• Cover
• planar location
• cooperative cover

Acknowledgment

This research was supported, in part, by the Natural Sciences and Engineering Research Council of Canada.

Notes

*Optimal by Table 5.

†Number of times (out of 100 runs) that maximum is obtained.

‡Percentage below best known solution.