A directional approach to gradual cover

Abstract

The objective of classic cover location models is for facilities to cover demand within a given distance. Locating a given number of facilities to cover as much demand as possible is referred to as max-cover. Finding the minimum number of facilities required to cover all the demand is the set covering problem. The gradual (or partial) cover replaces abrupt drop from full cover to no cover by defining gradual decline in cover. If classic cover models consider 3 miles as the cover distance, then at 2.99 miles a demand point is fully covered while at 3.01 miles it is not covered at all. In gradual cover, a cover range is set. For example, up to 2 miles the demand is fully covered, beyond 4 miles it is not covered at all, and between 2 and 4 miles it is partially covered. In this paper, we propose, analyze, and test a new rule for calculating the joint cover of a demand point which is partially covered by several facilities. The algorithm is tested on a case study of locating cell phone towers in Orange County, California. The new approach provided better total cover than the cover obtained by existing procedures.

Appendix: Calculating the cover area by one facility

Fig. 4

Calculating the cover area

Suppose that the demand point is located at (0, 0) (in a circle of radius R) and the facility is located at (0, d) with a cover radius D (see Fig. 4). The angle between the two lines emanating from the demand point to the two intersection points between the two circles $2\theta$ ($\theta$ between the line to the intersection point and the x-axis) can be obtained by the cosine theorem

$$\begin{aligned} \theta =\arccos \frac{d^2+R^2-D^2}{2\mathrm{d}R}. \end{aligned}$$

(9)

We find the area when $-1\le \frac{d^2+R^2-D^2}{2\mathrm{d}R} \le 1$ and thus $0\le \theta \le \pi$ exists. The two intersection points are at $(R\cos \theta ,\pm R\sin \theta )$. We distinguish between two cases: $\theta \le \frac{\pi }{2}$ and $\theta \ge \frac{\pi }{2}$ (Fig. 4). For $\theta =\frac{\pi }{2}$, the two cases yield the same result.

Acute angle :

The area right to the line connecting the two intersection points is the difference between the area of the sector $\theta R^2$ and the area of the triangle $\frac{1}{2}R^2\sin 2\theta$.

Obtuse angle :

The area right to the line connecting the two intersection points inside the circle is the sum of the area of the sector $\theta R^2$ and the area of the triangle $-\frac{1}{2}R^2\sin 2\theta$ because $\sin 2\theta <0$.

In both cases, the area is $\theta R^2-\frac{1}{2}R^2\sin 2\theta =\frac{1}{2}R^2(2\theta -\sin 2\theta )$.

Similarly, the angle $2\phi$ between the two lines originating from the facility satisfies $\cos \phi =\frac{d^2+D^2-R^2}{2dD}$ and the same derivation applies to $\phi$. The cover area is the sum of these values.