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.

1 Introduction

Cover location models are one of the main branches of location analysis. A demand point is covered by a facility within a certain distance (Church and ReVelle 1974; ReVelle et al. 1976). Facilities need to be located in an area to provide as much cover as possible. Such models are used for cover provided by emergency facilities such as ambulances, police cars, or fire trucks. They are also used to model cover by transmission towers such as cell phone towers, TV or radio transmission towers, and radar coverage among others. For a review, see Plastria (2002), García and Marín (2015) and Snyder (2011).

Most location problems assume that demand is located at a mathematical point. This is done mainly to facilitate analysis. It is reasonable to assume that facilities are “points” because in most applications the facilities occupy a small area compared to the demand area. For example, a cell phone tower can be assumed to be located at a “point” while only part of the customers residing in a neighborhood may be within a cover distance from the cell phone tower. In this paper, we assume that demand is generated in an area so that the distance to the facility depends on the location of a particular customer in the area. The total number of customers covered by several facilities depends both on the distances of the facilities from the demand area and their directions. For example, if two facilities are located one to the north of the neighborhood and one to the south, one facility may cover customers located at the northern part of the neighborhood while the other one covers customers in the south and the total number of customers is usually the sum of the two. If the two facilities are located in the same direction, there will be a significant overlap, and the total number of customers covered is less than the sum of the two.

There are other location models that consider demand areas rather than demand points. Solving the minisum Weber location problem (Weber 1929; Drezner et al. 2002) assuming that demand points and/or facilities are represented by areas was analyzed in Drezner (1986), Wesolowsky and Love (1971), Love (1972), Carrizosa et al. (1995), Nickel et al. (2003) and Puerto et al. (2018), by locating an annulus in the plane (Alkhalifa and Brimberg 2017) and locating a rectangular barrier (Miyagawa 2017). The gravity (Huff) competitive facility location problem (Huff 1964, 1966) where demand is generated in discs is analyzed in Drezner and Drezner (1997). Random demand generated in areas is discussed in Puerto and Rodríguez-Chía (2011). The problem of maximum cover of a planar area with p discs of a given cover radius is analyzed and solved in Drezner and Suzuki (2010). Another related problem is the p-center problem in an area (Suzuki and Drezner 1996). The problem is to find the smallest disc radius so that p discs cover the whole area. If we wish to find the minimum number of discs with a given radius that cover the whole area, the p-center solution approach can be used in a binary search.

In gradual cover models, up to a certain distance the demand point is fully covered and beyond a greater distance it is not covered at all. Between these two extreme distances the demand point is partially covered. The first paper to discuss gradual cover (also referred to as partial cover) was Church and Roberts (1984). The facilities must be located within a finite set of potential locations. The network version with a step-wise cover function is discussed in Berman and Krass (2002). The network and discrete models with a general non-increasing cover function were analyzed in Berman et al. (2003). The single-facility planar model with a linearly decreasing cover function between the distance of full coverage and the distance of no coverage was optimally solved in Drezner et al. (2004), and its stochastic version analyzed and optimally solved in Drezner et al. (2010). Additional references include Karasakal and Karasakal (2004), Eiselt and Marianov (2009), Drezner and Drezner (2014) and Berman et al. (2018).

A different covering model where facilities “cooperate” in providing cover was proposed in Berman et al. (2010). Each facility emits a signal (such as light posts in a parking lot) whose strength declines according to a distance decay function. A demand point is covered if the combined signal from all facilities exceeds a certain threshold. Recent papers on the cooperative cover are Morohosi and Furuta (2017), Karatas (2017), Wang and Chen (2017) and Bagherinejad et al. (2018). In all other covering models, including the one proposed in our paper, no combined signal is assumed.

In this paper, we consider gradual (partial) cover. Suppose that customers residing at a demand “point” reside in a disc (centered at the demand point) and the facility is located at a point. The facility covers customers within a given distance. The proportion of cover provided by one facility is the ratio between the intersection area of two discs and the area of the demand disc. At some distance the facility covers the whole disc, and at some larger distance it covers none. If demand is partially covered by two or more facilities, the total cover (area) depends on the distances between the facilities and the demand point, and on the directions of the facilities from the demand point. The total cover of all demand by p facilities is a weighted sum of the individual covers of demand points. Note that when the radius of the disc representing the demand point is zero, models based on this definition of cover reduce to the standard cover models.

The contribution of the paper is twofold. In all existing gradual cover models, the formula for the joint cover by several facilities considers only the distances to the facilities and not their direction. Ignoring the directions of the facilities may lead to inaccurate estimation of joint cover when demand at “demand points” is generated in an area. The total cover by two facilities when the facilities are located in the same direction is different from the total cover when they are located in opposite directions. To simplify the analysis, most facility location models assume that demand is generated at points. Researchers and practitioners justify it by “assuming” that the average distance from the facility to the demand area is the distance to the “demand point”. For example, in Drezner and Drezner (1997) it is shown that the distance is larger than its average and assuming demand areas rather than demand points provides more accurate solutions. A second contribution is the evaluation of the union of the intersection areas of circles which may be useful in other models as well. For example, if the competitive location model based on cover (Drezner et al. 2011, 2012, 2015) is extended to continuous demand, such an evaluation is needed. Also, there are many practical extensions, listed in Sect. 5, to the basic problem presented here which rely on the methods developed in this paper.

The paper is organized as follows. In the next section, we analyze and test the calculation of the joint cover of a demand point. It is based on a rarely used specialized numerical integration (Gaussian quadrature based on Legendre polynomials) that requires the calculation of the joint cover of circles’ circumferences by several facilities. We then propose in Sect. 3 three heuristic procedures for optimizing the total cover by a given number of facilities. In Sect. 4 we tested the proposed solution approach on a case study of covering Orange County, California, by cell phone towers and compared the results with existing approaches. We conclude the paper in Sect. 5.

2 Joint cover

In this section, we show how to determine the joint cover of one demand “point”. The evaluation of the joint cover is repeated for each demand point in the area. The total cover of all demand points, or any other objective, can be calculated.

2.1 Single facility

Suppose that the demand is a disc of radius R with the demand point at its center. The points in the disc are covered within a distance D from the facility. The facility is at distance d from the demand point. The partial cover of the demand point is the intersection area between the two discs divided by $\pi R^2$.

Consider the case $D\ge R$. When $d\le D-R$ the whole disc is covered. When $d\ge D+R$ none of the disc is covered. For $D-R< d< D+R$ part of the disc is covered. The area A covered by the facility is (see Appendix for the derivation):

$$\begin{aligned} A=\left\{ \begin{array}{l|l} \pi R^2&{}d\le D-R\\ \frac{1}{2} R^2\left[ 2\theta -\sin 2\theta \right] +\frac{1}{2} D^2\left[ 2\phi -\sin 2\phi \right] &{}D-R\le d\le D+R\\ 0&{}d\ge D+R\\ , \end{array}\right. \end{aligned}$$

(1)

where

$$\begin{aligned} \theta =\arccos \frac{d^2+R^2-D^2}{2dR};~~~~\phi =\arccos \frac{d^2+D^2-R^2}{2dD}~. \end{aligned}$$

(2)

Note that when $D<R$ it is impossible to cover the whole disc because the area covered by the facility is smaller than the disc. When $d\le R-D$ the area covered is $\pi D^2$. In this case, it is easiest to switch between D and R for the calculation of the area.

2.2 Multiple facilities

When two facilities exist in the area, the area covered by both depends on the directions of the two facilities from the demand point. A formula can be developed for this case but it is quite complex. It is even more complex if more than two facilities exist in the area. See, for example, Fig. 1. The demand point of radius $R=1$ is located at the origin and the facilities’ locations and radii are given in Table 1.

Fig. 1

An example

Table 1 Five facilities in the example

Let the individual cover of a demand point by facility $1\le i\le p$ be $Cov_i$ and the total cover of that demand point by all facilities be Cov. In Drezner and Drezner (2014) and Berman et al. (2018), the largest estimate for the joint cover (assuming independent cover events) is

$$\begin{aligned} \mathrm{Cov}=1-\prod \limits _{i=1}^p(1-\mathrm{Cov}_i). \end{aligned}$$

(3)

However, this estimate considers only individual covers by distances and does not consider the directions to the facilities. Also, partial cover by several facilities cannot result in full cover.

The total cover area of a demand point of radius R can be found by integration. Suppose that p facilities exist in the area. Consider a circle of radius r for $0\le r\le R$ centered at the demand point. Let $\gamma (r)$ be the proportion of the circumference of the circle of radius r which is covered. The total cover area A is

$$\begin{aligned} A=\int \limits _0^R2\pi r\gamma (r)\mathrm{d}r, \end{aligned}$$

(4)

and the joint cover of a demand point of radius R is

$$\begin{aligned} \mathrm{Cov}=\frac{A}{\pi R^2}=\frac{1}{\pi R^2}\int \limits _0^R2\pi r\gamma (r)\mathrm{d}r. \end{aligned}$$

(5)

For example, if $\gamma (r)=1$ for every r, $A=\pi R^2$ and $\mathrm{Cov}=1$.

This definition of joint cover satisfies the three common sense properties proposed in Berman et al. (2018):

• (i) the joint cover should be between 0 and 1;

• (ii) if the partial cover from a facility (remaining at the same location) increases, the joint cover cannot decrease;

• (iii) adding facilities that provide no cover cannot change the joint cover of a demand point;

  we add that

• (iv) if a demand point is fully covered by one facility, then the joint cover is full;

• (v) if a demand point is partially covered by only one facility (and the other facilities provide no cover), then the joint cover is equal to the partial cover by that facility;

• (vi) if no facility provides full cover, partial cover by at least two facilities can provide full cover;

• (vii) the joint cover cannot exceed the sum of all partial covers.

Note that the rule expressed by Eq. (3) does not satisfy property (vi) because full cover cannot be achieved by partial covers.

We suggest to find the total area (4) and the joint cover (5) by numerical integration.

2.2.1 Finding the union of arcs

The covered part of the circumference of a circle of radius $0\le r\le R$ is a union of disjoint arcs. To find the union we calculate the arcs covered by each facility. The union is constructed by adding the arcs one by one finding the union of the arcs evaluated so far with each additional arc. Let $\psi _j$ be the center of arc j, the angle of the line connecting the two centers.

The following steps are taken:

• $t=\frac{d_j^2+r^2-D_j^2}{2d_jr}$ is calculated.

• If $t\le -1$, $\gamma (r)=1$ and there is no need to evaluate additional facilities.

• If $t\ge 1$ no arc is covered (when $t=1$ one point is covered) and facility j can be skipped.

• If $-1<t<1$, then $\theta _j(r)=\arccos t$. The covered arc is between $\psi _j-\theta _j(r)$ and $\psi _j+\theta _j(r)$. If $\pi$ or $-\pi$ are inside this range, the range is split into two ranges both between $-\pi$ and $\pi$.

The following procedure for finding the union of arcs was found to be the most efficient among procedures that were tested. For example, the union of mutually exclusive arcs is not kept sorted which saves time compared with keeping them sorted throughout the process. See also the time-saving measures introduced in Sect. 2.2.2.

At the start, the union consists of the first arc. Suppose that the union of several arcs scanned so far consists of k non-intersecting arcs: $[\alpha _j,\beta _j]$ for $j=1,\ldots ,k$, satisfying $\beta _j>\alpha _j$ but are not sorted, i.e., $\alpha _{j+1}$ is not necessarily greater than $\beta _j$. When an additional arc $[\theta _L,\theta _R]$ is added to the union, it is checked against the list of arcs in the union one by one. Suppose that an arc $[\alpha _j,\beta _j]$ is compared with the additional arc. If $\theta _L>\beta _j$ or $\alpha _j>\theta _R$ the arcs do not intersect and the next arc in the union is compared with the additional arc. Otherwise, the union of the two arcs $[{\overline{\theta }}_L,{\overline{\theta }}_R]=[\min \{\theta _L,\alpha _j\},\max \{\theta _R,\beta _j\}]$ replaces the additional arc $[\theta _L,\theta _R]$ and the arc $[\alpha _j,\beta _j]$ removed from the union. The “modified” additional arc $[{\overline{\theta }}_L,{\overline{\theta }}_R]$ is compared with the remaining list of arcs. Time is saved by the observation that all the arcs that were already checked need not be checked against the modified additional arc. This is formally proved in the following Lemma.

Lemma 1

The modified arc $[\min \{\theta _L,\alpha _j\},\max \{\theta _R,\beta _j\}]$ does not intersect with an arc $[\alpha _m,\beta _m]$ for $m<j$ that was already compared with $[\theta _L,\theta _R]$.

Proof

Since $[\alpha _m,\beta _m]$ was compared with $[\theta _L,\theta _R]$, either (i) $\theta _L>\beta _m$ or (ii) $\theta _R<\alpha _m$. Similarly, either (iii) $\alpha _j>\beta _m$ or (iv) $\beta _j<\alpha _m$. If (i) and (iii) hold, $\min \{\theta _L,\alpha _j\}>\beta _m$ and the modified arc does not intersect with $[\alpha _m,\beta _m]$. A similar argument holds if (ii) and (iv) hold. If (i) and (iv) hold, $\theta _L>\beta _m>\alpha _m>\beta _j$ which means that $[\theta _L,\theta _R]$ and $[\alpha _j,\beta _j]$ do not intersect and thus the modified arc is equal to the original arc which was already compared with $[\alpha _m,\beta _m]$. A similar argument holds if (ii) and (iii) hold. $\square$

Once all arcs in the union are checked and the “modified” additional arc is found (it may have been modified several times), it is added to the union forming a new union which includes the modified additional arc. Some of the arcs in the old union might have been removed.

Once the union of all arcs is found, $\gamma (r)$ is the sum of the lengths of individual arcs in the union divided by $2\pi r$. Since each arc is represented by two end-angles (in radians) both between $-\pi$ and $\pi$, $\gamma (r)$ is the sum of the differences between the two end-angles divided by $2\pi$.

2.2.2 Time-saving measures

• 1. A time-saving measure when calculating the union of arcs is detailed in Sect. 2.2.1 and proven in Lemma 1.

• 2. In preparation for calculating the joint cover of a demand point, the set of p selected facilities is evaluated. For each facility $1\le j\le p$:

  • (a) $\Delta _j=D_j-d_j$ is calculated.

  • (b) if $\Delta _j\ge R$ for any j, the demand point is fully covered. There is no need for numerical integration.

  • (c) if $\Delta _j\le -R$ the facility provides no partial cover and can be removed from the set of selected facilities for evaluating the joint cover of this demand point.

  • (d) The maximal $\Delta _j$: $\Delta _{\max }=\max \nolimits _{1\le j\le p}\{\Delta _j\}$ is found.

• 3. In the numerical integration: if the radius r for an integration point satisfies $r\le \Delta _{\max }$, the circumference of the circle of radius r is fully covered and $\gamma (r)=1$. There is no need to calculate the union of arcs.

All these time-saving measures and not keeping the union of the arcs sorted saved more than half of the run time.

2.3 Numerical integration

The integral (5) can be calculated by Simpson’s rule (Clenshaw and Curtis 1960; Beyer 1981) to any desired accuracy or by Gaussian quadrature based on Legendre polynomials (Abramowitz and Stegun 1972). Note that the Gaussian quadrature based on K points is exact for any polynomial up to a power of $K-1$. In Eq. (4), small values of r affect the result less than large values of r. We, therefore, use the transformation $r^2=uR^2$ and get

$$\begin{aligned} \mathrm{Cov}=\int \limits _0^1\gamma (R\sqrt{u})\mathrm{d}u. \end{aligned}$$

(6)

Table 2 Adjusted Legendre–Gaussian quadrature parameters

The Legendre–Gaussian Quadrature abscissas and weights (Abramowitz and Stegun 1972) are converted from the range $(-1,1)$ to the range (0, 1) and the square root of the abscissas taken yielding the coordinates and weights in Table 2. In general, if there are K points in the Gaussian quadrature,

$$\begin{aligned} \mathrm{Cov}\approx \sum \limits _{j=1}^Kw_j\gamma (Ru_j). \end{aligned}$$

We evaluated the joint cover obtained by numerical integration of the example problem given in Table 1 and Fig. 1. A demand point is located at (0, 0) with a radius $R=1$. Five facilities are located in the area. The area of the demand disc not covered by the facilities is mostly above the origin tilted to the left and is marked with a “+” in Fig. 1. By simulation, randomly generating one billion points in the unit circle, we found that the proportion covered by the facilities is 0.8831 (proportion not covered 0.1169). The standard error of these values is $1.0\times 10^{-5}$. By numerical integration, with $K=5$ integration points we got 0.8876 and with $K=10$ integration points 0.8817.

Table 3 Comparison of numerical integration with simulation

To further evaluate the integration approximation, we calculated the joint cover for the radius of the leftmost circle in Fig. 1 between $D_3=2.0$ and $D_3=3.3$. The comparison with simulations of one billion points each is presented in Table 3. The maximum deviation from the simulation results is 0.0066 for $K=5$ and 0.0025 for $K=10$. Both approximations are acceptable. In real applications, the values of R, $D_j$, etc., are probably less accurate than these deviations. If one wishes, larger values of K can be used yielding better approximations. Abramowitz and Stegun (1972) give Gaussian–Legendre integration formulas up to $K=96$. In the website https://pomax.github.io/bezierinfo/legendre-gauss.html parameters for all $K\le 64$ points are given. In the experiments we applied $K=10$. Note that run time is approximately proportional to K.

2.4 The issue of co-location

In the classic covering models there is no advantage to locate more than one facility at the same location. However, in some gradual cover location models (for example, Eiselt and Marianov 2009; Drezner and Drezner 2014; Berman et al. 2018) cover may increase if several facilities are located at the same location. In our formulation, there is no advantage to locate more than one facility at the same location. If the cover distance is the same for all facilities, the circles intersecting with the demand disc are the same and the cover area does not increase. If the circles have different cover radii, only the largest cover radius determines the cover.

3 Heuristic approaches for maximizing total cover

Consider a problem with n demand points and m potential locations for facilities. Once the cover by each selection of p potential locations can be calculated and since co-location is not beneficial for cover, the problem reduces to selecting the best set of p locations out of m potential locations. If p and m are relatively small, total enumeration or a branch and bound algorithm can be used. We constructed and tested three heuristic algorithms based on ascent, tabu search, and simulated annealing. These algorithms are based on evaluating moves. A move consists of removing one of the p selected potential locations and replacing it with one of the non-selected $m-p$ potential locations. There are $p(m-p)$ possible moves.

Other meta-heuristics such as genetic algorithms (Holland 1975; Goldberg 2006) and variable neighborhood search (Mladenović and Hansen 1997) can also be constructed for solving the directional approach model. It may be possible to develop a special heuristic to solve the problem of finding the minimum number of facilities required to cover all the demand rather than applying a binary search on the value of p.

3.1 The ascent approach

The ascent algorithm is quite straightforward. Suppose that a set of p potential locations is selected. The best improving move is executed and the process continues until no improving move exists.

3.2 Tabu search

Tabu search (Glover and Laguna 1997) allows downward moves hoping to obtain a better solution in subsequent iterations. A tabu list of forbidden moves is maintained. Tabu moves stay in the tabu list for tabu tenure iterations. To avoid cycling, the tabu list contains potential locations that were removed from the selected set during the recent tabu tenure iterations. The process continues for a pre-specified I number of iterations.

Random range for the tabu tenure was suggested by Taillard (1991). There are m potential entries in the tabu vector and $m-p$ of them can be selected to join the selected set. In the following experiments we selected the range $[T_{\min },T_{\max }]$ to be between 5% and 50% of $m-p$.

The easiest way to handle the tabu list, especially if the tabu tenure is not fixed, is to maintain a tabu vector of length m. The entry for each potential location in the tabu vector is the last iteration number at which it was removed from the selected set. A move is “forbidden” if the difference between the value in the tabu vector of the potential location joining the selected set and the current iteration count is less than or equal to the tabu tenure.

• 1. A randomly generated solution is selected as a starting solution and is the best found solution. Set $iter=0$.

• 2. Every potential location in the tabu vector is assigned a large negative number.

• 3. Set $iter=iter+1$.

• 4. If $iter>I$ stop with the best found solution as the result of the algorithm.

• 5. Otherwise, the tabu tenure, T, is randomly selected in the range $[T_{\min },T_{\max }]$.

• 6. All moves are evaluated (one potential location is in and one is out) and the value of the objective function is calculated for each move.

• 7. If a move yields a solution better than the best found one, continue to evaluate all the moves and perform the best improving move. Update the best found solution and go to Step 2.

• 8. If no move yields a solution better than the best found solution, select the move among the non-forbidden moves (comparing iter to the value of in in the tabu vector) which yields the best value of the objective function, whether improving or not.

• 9. iter is entered into the tabu vector of the out potential location in the selected move. Go to Step 3.

Note that as long as there is a move better than the best found solution so far, the tabu algorithm is equivalent to the ascent algorithm because Step 7 will be executed until no better solution by all moves is found.

3.3 Simulated annealing

Simulated annealing (Kirkpatrick et al. 1983) simulates the cooling process of hot melted metals. Three parameters are required: the starting temperature $T_0$, the final temperature $T_F$, and the number of iterations I. Based on these three parameters the temperature reduction factor $\alpha =\left( \frac{T_F}{T_0}\right) ^{1/I}$ is calculated.

• 1. A starting set of potential locations is randomly generated and is also the best found solution; the temperature T is set to $T_0$; and the iteration counter iter is set to 0.

• 2. A random move is generated by randomly selecting a potential location from the selected set to be removed, and a non-selected potential location to join the selected set.

• 3. The change in the value of the objective function $\Delta F$ by the move is calculated.

• 4. If $\Delta F\ge 0$, then if the new solution is better than the best found solution, update the best found solution. Perform the move and go to Step 6.

• 5. If $\Delta F< 0$, then perform the move with probability $\pi =e^{\frac{\Delta F}{T}}$ and do not perform the move with probability $1-\pi$.

• 6. Advance $iter=iter+1$ and multiply T by $\alpha$. If $iter\le I$, go to Step 2. Otherwise, stop with the best found solution as the result of the algorithm.

4 Case study: transmission towers in Orange County, California

We investigated transmission towers such as cell phone towers, TV or radio transmission stations covering Orange County, California. The data from the 2000 census for Orange County, California, are given in Drezner (2004) and were also used in Drezner and Drezner (2007), Berman et al. (2010), Drezner and Drezner (2014), Berman et al. (2018) and Drezner et al. (2006). There are 577 census tracts and their population counts are given. The total population in Orange County is 2,846,289.

We first solved the instances with $2\le p\le 15$ towers by the ascent algorithm, simulated annealing, and tabu search. The ascent algorithm was run 1000 times from different starting solutions for each p. The simulated annealing and tabu search were replicated ten times for each p. The number of iterations for simulated annealing is $1000p(m-p)$ and for the tabu search $I=1,000$. For simulated annealing we used $T_0=0.1$ and experimented with two values for $T_F$: $T_F=0.0001$ and $T_F=0.00001$. The latter value produced slightly better results and all the reported results of simulated annealing are for $T_F=0.00001$. We consider solutions tying for the best one if they are within $10^{-6}$ of the best found solution.

Computer programs were coded in Fortran using double-precision arithmetic and compiled by an Intel 11.1 Fortran Compiler using one thread with no parallel processing. They were run on a desktop with the Intel i7-6700 3.4GHz CPU processor and 16GB RAM.

4.1 Covering North Orange County

We first selected the northernmost 131 census tracts, all with a y-coordinate of at least 30, that were tested in Drezner and Drezner (2014) and Berman et al. (2018). The total population residing in northern Orange County is 639,958. Each census tract is a demand point and a potential location for a tower and thus $m=n=131$.

Full cover within 2 miles and no cover beyond 4 miles were applied in Berman et al. (2018) and Drezner and Drezner (2014). To have comparable results we assign a radius of $R=1$ mile for each demand point and a cover radius of $D_j=3$ miles for each tower. The results by the ascent algorithm, simulated annealing, and tabu search are presented in Table 4. Locations of ten towers that cover all residents are depicted in Fig. 2. Actually, there are many configurations of ten towers that cover all the residents.

Table 4 Covering North Orange County

It is interesting that ten towers cover all the demands while in Drezner and Drezner (2014) and Berman et al. (2018) that used the linear decay and joint cover by (3), the solution for covering all demand is 12 towers. When correlated cover events are assumed, 13 towers are required to cover all demand points. This is a bit surprising because the cover by one tower is mostly lower by (1) than it is by linear decay. For example, when $d=3$ (and $R=1$, $D=3$) the individual cover by a single tower applying linear decay is 0.5 while by (1) it is only 0.4645. The joint cover by two facilities applying (3) is 0.75, while if the towers are located in opposite directions the covers add up and the joint cover is 0.9290. In the example problem (Table 1), the joint cover by (3) calculated by the individual five covers (1) (also given in Table 1) is 0.7970 compared with 0.8831 by the directional approach.

Also, joint cover by (3) is full only if it is fully covered by at least one facility while by the directional approach full joint cover is possible by several partial covers. For example, when the leftmost radius in the example problem (Fig. 1) is increased to 3.3, full cover is achieved even though every partial cover does not exceed 0.66. However, since we report results to five digits, then if five towers provide partial cover of at least 0.9 each, full cover is reported in Drezner and Drezner (2014) and Berman et al. (2018).

Fig. 2

Ten towers covering North Orange County

Run times by our procedure are longer than required in Drezner and Drezner (2014) and Berman et al. (2018). While calculating linear decay and the calculation of the joint cover by (3) are very fast, the calculation of (1) requires calculations of trigonometric functions and calculating the joint cover requires numerical integration using ten circles and the union of many arcs. In Table 4 we report the total run time for ten such replications of tabu search and simulated annealing which required a total of about 5 to 6 min of computer time for $p=15$ instances. One thousand replications of the ascent algorithm required less than 3 min of computer time.

In summary, by examining Table 4, we conclude that tabu search performs best. The ascent algorithm is the fastest. If the number of iterations in the ascent algorithm is ten, the total run time of the ascent algorithm should be about the same as the total time for tabu search and simulated annealing. We estimate from Table 4 that the average number of iterations of the ascent algorithm is about 3 for $p=2$, increases to about 10 for $p=8,9,10$ and declines back to about 5 for $p=15$.

To further evaluate the three heuristic algorithms we repeated the experiments for covering all the 577 census tracts in Orange County.

4.2 Covering all Orange County

In this case, $m=n=577$. We repeated the same tests that were performed for North Orange county for $2\le p\le 15$. The results are summarized in Table 5.

Table 5 Covering all Orange County

Table 6 Covering all Orange County with more than 15 facilities

Fig. 3

Twenty-nine towers covering 99% of Orange County’s demand

The relative performance of the heuristic algorithms for covering all Orange County with $2\le p\le 15$ facilities (Table 5) is different from that of covering North Orange County (Table 4). Simulated annealing performed best and run times for the ascent algorithm are the highest. The number of estimated iterations of the ascent algorithm increased from about 3 for $p=2$ to about 22 for $p=15$ explaining the increase in run times. In one case, $p=14$, the tabu search failed to find the best known solution (it found the objective 0.81306 five times). It is possible that for larger values of n and m, tabu search requires more than $I=1000$ iterations to obtain good results. Since we attempt to require the same approximate run times for the heuristic algorithms, we did not increase the number of iterations for tabu search.

We further solved the cover of all Orange County for $p>15$ facilities by simulated annealing and tabu search to find the number of facilities required to cover 99% to 100% of the population. We tested both the “standard” number of iterations used in previous experiments, and multiplying the number of iterations by a factor of $\frac{6p}{100}$. The results are summarized in Table 6. The best known solution which is the best solution found in all runs is marked in boldface. The locations of 29 towers that cover 99% of Orange County demand are depicted in Fig. 3. Note that there are many configurations of three facilities forming a triangle which is close to an equilateral triangle. Such a configuration covers efficiently the area inside the triangle.

We experimented with simulating annealing using $T_F=0.000001$. The results are generally inferior but better results were obtained for total cover very close to 1. In Table 7, the results for $p\ge 35$ are presented. The best found solution and the number of times it was found are reported.

Table 7 Simulated annealing results for $T_F=0.000001$

4.3 Comparison with the classic set covering models

In classic set covering problems, it is assumed that a demand point is covered by a facility at distance not exceeding D. Let $d_{ij}$ be the distance between demand point i and potential location for a facility j. A matrix $\left\{ a_{ij}\right\}$ is defined as

$$\begin{aligned} a_{ij}=\left\{ \begin{array}{l|l} 1&{}\quad d_{ij}\le D,\\ 0&{}\quad \text{ otherwise. }\end{array}\right. \end{aligned}$$

(7)

A vector of binary variables $x_j$ is defined. The IP formulation is

$$\begin{aligned}&\min \left\{ \sum _{i=1}^m x_j\right\} ,\nonumber \\ \text{ subject } \text{ to }&\\&\sum _{j=1}^m a_{ij}x_j\ge 1 \text{ for } i=1,\ldots n\nonumber \\&x_j \in \{0,1\}.\nonumber \end{aligned}$$

(8)

This IP formulation was solved by CPLEX.

Table 8 Comparing classic set covering to the directional approach

To guarantee full cover for our case study, a cover distance of $D=2$ is required. If a larger distance is used, a demand point may be covered by only one facility and by any gradual (partial) cover model such a demand point is not fully covered. We solved the classic set covering problem for various radii between 2 and 3 miles even though a radius greater than 2 miles does not guarantee full cover. The results are presented in Table 8. In the table we present for each cover distance D the number of facilities required by the classic set covering problem to cover North Orange County and all Orange County. We also present the proportion of cover by the directional approach achieved with the same number of facilities. Note that full coverage by the directional approach is obtained by 10 and 43 facilities for these two instances.

We conclude from Table 8 that the directional approach has a clear advantage over the classic and widely used covering models when full cover is guaranteed. Even when a cover distance of $D=3$ is used, the same number of facilities cover about 99% of the demand with the same number of facilities while the classic cover models may have demand points that less than half of their demand is covered.

As reported in http://www.homefacts.com/fcctowers/California/Orange-County.html, there were 316 FCC cell phone towers in Orange County.

5 Conclusions

In this paper, we construct a useful procedure that finds the proportion of demand cover once the locations of p facilities that provide cover are given. Facility j covers demand within a distance $D_j$ and demand point i is represented by a disc of radius $R_i$. A facility provides full cover within a distance $D_j-R_i$ from the demand point, and provides no cover if its distance from the demand point exceeds $D_j+R_i$. The joint cover by all facilities is calculated taking into account the directions of the facilities that provide partial cover. We built and tested several models using this procedure such as maximizing total demand cover which is the weighted sum of the partial covers of all demand points.

There are numerous practical applications that can be modeled and solved using our procedure. For example, consider the following circumstances:

• 1. A mix of different types of facilities, with a given cost for each type, can be used to minimize cost. Each potential location can have no facility, facility of type I, facility of type II, etc. Possible objectives are (i) cover the most demand at a given budget, (ii) minimize the cost of covering all demand, and (iii) minimize the cost of covering a given percentage of the demand.

• 2. It is possible that the cost of a facility is a known function of the cover radius rather than having a finite set of facilities’ radii. For example, the cost consists of a setup cost plus a variable cost which is proportional to the square of the radius. The cover radii of facilities are additional variables in the model.

• 3. Facilities may have a limited capacity so that the number of customers served by a facility may be limited. Similar models for other contingencies are, for example, Diaz and Fernandez (2006), Fonseca and Captivo (1996), Altýnel et al. (2009) and Melo et al. (2006).

• 4. It is possible that the cover may have a negative effect on some or all demand points in which case it is desirable to minimize the cover of such demand points. This objective is analyzed and solved in Berman et al. (2009) for the classic max-cover model.

• 5. A different type of objective is the maximin objective, i.e., to maximize the minimum cover of all demand points. Such an objective is appropriate when we wish to provide a reasonable cover to the least covered demand point. We may wish to have the highest possible threshold using a given budget or achieve a given threshold, such as 99%, at a minimum cost.

• 6. One may be interested in providing back-ups so that if a facility fails, service can be provided by a second facility. A heuristic solution can be obtained by finding locations for facilities that fully cover all the demand, removing these locations from the set of potential locations, and finding additional locations from the reduced set that cover all the demand. To achieve 99% backup, select the locations that cover 99% of the demand, remove them, and find additional locations that fully cover all the demand. This way each demand point is fully covered and 99% of the demand has back-up.

• 7. The procedure can be employed when the facilities can be located anywhere, not necessarily on a given set of potential locations. Such a problem can be solved heuristically by finding a solution among a set of potential locations, such as the one depicted in Fig. 2, as a starting solution. Then the solution can be “refined” by a gradient search or, for example, Nelder–Mead (Nelder and Mead 1965; Dennis and Woods 1987). Another approach to “refining” the solution, similar to the approach by Cooper (1963, 1964), is to iteratively find the optimal location for one facility at a time while holding the other $p-1$ facilities in their place, until convergence. Global optimization techniques such as “Big Square Small Square” Hansen et al. (1981), “Big Triangle Small Triangle” Drezner and Suzuki (2004), or the method suggested in Drezner (2015), can be used for solving the single-facility location problem.

• 8. Conditional location models (Minieka 1980; Chen and Handler 1993; Berman and Simchi-Levi 1990; Ogryczak and Zawadzki 2002; Drezner 1995) are applicable for all of the situations discussed above. Some facilities exist in the area and we would like to build p additional facilities that, combined with the existing facilities, yield the best value of the objective function of interest.

• 9. Continuous covering location model with risk consideration (Hosseininezhad et al. 2013). Because of uncertain covering radius, customer satisfaction degree of covering radius is introduced by fuzzy concept.

Heuristic approaches, like the ones developed in this paper, can be constructed for getting good solutions to the models described above. Such heuristics should be tailored to the model of interest.

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.