The maximin gradual cover location problem

In this paper, we consider the multiple facility location problem with gradual cover. Gradual cover means that up to a certain distance from the facility a demand point is fully covered. Beyond another distance the demand point is not covered at all. Between these two distances the demand point is partially covered. When there are (p) facilities, the cover of each demand point can be calculated by a given formula. One objective in this setting is to find locations for (p) facilities that maximize the total cover. In this paper we consider another objective of maximizing the minimum cover of every demand point. This guarantees that every demand point is covered as much as possible and there are no demand points with low cover. The model is formulated and heuristic algorithms are proposed for its solution. We solved a real-life problem of locating cell phone towers in northern Orange County, California and demonstrated the solution approach on a set of 40 test problems.