Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The mail-order DVD rental company Netflix chooses distribution center locations so that most of its customers receive their DVDs within one business day via first-class U.S. Mail. Similarly, many municipalities aim to have fire crews reach 911 callers within a specified time, such as four minutes. Both of these are examples of the notion of coverage, a concept central to several classes of facility location models; it indicates whether a demand location is within a pre-specified radius (measured by distance, travel time, cost, or another metric) of its assigned facility. Homeowners are covered if they are within four minutes of the nearest fire station, and Netflix customers are covered if they are within one mailing day of a distribution center. Note that in the fire-station example, municipalities typically want to cover all residents (while minimizing the number of service stations to open), whereas Netflix wants to cover as many customers as possible (subject to a limit on the number of warehouses it may operate at any time, as specified by its capital budget). The fire-station problem is an example of the set covering location problem (SCLP), while Netflix’s problem is an example of the maximal covering location problem (MCLP). This chapter discusses both problems.

The set covering location problem was first introduced by Hakimi (1965) and was later formulated as an integer programming problem by Toregas et al. (1971). The maximal covering location problem was introduced by Church and ReVelle (1974). Both models, and their variants, have been applied extensively to public-sector facility location problems, such as the location of emergency medical service vehicles (Eaton et al. 1985), fire stations (Schilling et al. 1980), bus stops (Gleason 1975), wildlife reserves (Church et al. 1996), and emergency air services (Flynn and Ratick 1988). They have been applied in a much more limited extent in the private sector; see, e.g., Nozick and Turnquist (2001).

The set covering location problem and the maximal covering location problem are closely related to the p-center problem, which aims to locate at most p facilities to minimize the maximum distance, among all customers, between the customer and its assigned facility. In the p-center problem, the coverage radius itself constitutes the objective function. The Introduction of this book provides a more thorough discussion of the relationships among these classical models.

Like most location problems, the SCLP and MCLP may be defined as continuous problems (in which facilities may be located anywhere on the plane) or as discrete problems (in which they may be located only at the nodes of a network). In this chapter we consider the latter approach.

The remainder of this chapter is organized as follows. In Sect. 6.2, we discuss classical papers on the set covering location problem (in Sect. 6.2.1) and the maximal covering location problem (in Sect. 6.2.2), present the results of computational experiments, and discuss more recent variations. Section 6.3 discusses the impact that these models have had and the bodies of research they have inspired, focusing on generalized notions of coverage. Finally, we conclude with Sect. 6.4, suggesting some possible future research directions.

2 Historical Contributions

This section first presents the classical models for the set covering location problem by Hakimi (1965) and Toregas et al. (1971). It then continues with a discussion of the maximal covering location problem by Church and ReVelle (1974) in Sect. 6.2.2.

2.1 The Set Covering Location Problem

Although the generic (non-location) set-covering problem had been formulated prior to Hakimi’s (1965) seminal paper on the set covering location problem, Hakimi’s work is important for, among other things, introducing the notion of coverage into facility location models. Hakimi’s proposed solution method, which involved the use of Boolean functions, never proved to be efficient enough to warrant its use in practice; rather, the set covering location problem is generally solved using integer programming techniques, first proposed by Toregas et al. (1971). We discuss Hakimi’s model and briefly outline the Boolean-function approach in Sect. 6.2.1.1. Section 6.2.1.2 presents the integer programming method of Toregas et al.

2.1.1 The Contribution by Hakimi (1965)

We consider a graph G = (V, A) and assume that every node in V is both a customer (demand) node and a potential site for a facility. (However, one can easily extend the models below to handle the cases in which some customers are not facilities or some facilities are not customers and therefore do not need to be covered. Below, we use terms like “customer i” and “facility j” as shorthand for “the customer located at node i” and “the facility located at node j.”) Let n = |V |. The distance between nodes i and j is given by d ij, and the maximum allowable distance between a customer and its nearest opened facility—the “coverage distance”—is given by s. If (i, j) ÎA, then d ij is the length of the arc (i, j), and otherwise it is the shortest distance from i to j on the graph. (We use the term “distance” throughout, but the parameters d ij and s may just as well represent travel times, costs, or another measure of proximity.) Therefore, facility j covers customer i if d ji £ s. We define

$$ {V_i} = \{ j \in V:{d_{ji}} \le s\} , $$

that is, V i is the set of nodes that cover customer i. Note that every V i is nonempty, assuming that d ii = 0 for all i.

The objective of the set covering location problem is to find the minimum-cost (or minimum-cardinality) set of locations such that every node in V is covered by some node in the set. The application that Hakimi cites for the set covering location problem is that of locating policemen along a highway network so that every intersection (vertex of the graph) is within one distance unit of a policeman. Subsequently, the problem has found a much broader range of applications, as discussed earlier.

We will assume that facilities may be located only at the nodes of the network, not along the edges. Note that it may be optimal to locate along edges, since the well known “Hakimi property”—which states that an optimal solution always exists in which facilities are located at the nodes, rather than along the edges, of the network—does not apply to the set covering location problem. (Hakimi introduced his famous property in an earlier paper (Hakimi 1964) in the context of the p-median problem, not of the SCLP.) A very simple counterexample consists of two nodes connected by a single edge of length 1 and a coverage distance of 0.5. If facilities are allowed on the edges, the unique optimal solution consists of one facility (located in the middle of the edge), whereas the optimal nodal solution consists of two facilities, one at each node. On the other hand, a problem in which facilities may be located on edges may be converted to a node-only problem by inserting dummy nodes onto the edges, taking advantage of the fact that there are only a finite number of possible optimal locations along edges. Readers are referred to Church and Meadows (1979) for details.

In some applications, it is desirable to use a different coverage distance for each customer—for example, if customers have service agreements that specify different response times. In this case, the coverage distance is customer dependent, s i, and the set V i is given by V i = {jÎV: d ji £ s i}. The analysis below changes in only minor ways.

The set covering location problem is closely related to the graph-theoretic vertex cover problem, whose objective is to find a subset of nodes in the graph such that every node in the graph is adjacent to some node in the set and such that no strict subset of the set has the same property. Such a set of nodes is called a cover. The optimization version of the vertex cover problem seeks the minimum-cardinality cover, and this problem is a special case of the SCLP in which s = 1 and d ij = 1 for all (i, j) ÎA. Indeed, although he is usually credited for introducing the more general SCLP, this special case is the problem considered by Hakimi (1965), since he presented the problem explicitly in a facility location context. In this section we will assume, following Hakimi, that s = d ij = 1, though in subsequent sections we will allow s and d ij to be arbitrary. Hakimi notes that the assumption that d ij = 1 is not too restrictive, since if the arc lengths are greater than 1, one could simply introduce dummy nodes along the arcs one unit apart, assuming that the arc lengths are integers. Of course, this modeling trick comes at considerable computational expense, especially since Hakimi’s method relies on an enumerative approach whose computational complexity increases exponentially with the number of nodes.

In the remainder of this section, we describe Hakimi’s (1965) approach to solving the set covering location problem. As noted earlier, this method is not commonly used today and is discussed here primarily for its historical interest.

Recall that V i is the set of nodes that cover node i; given the assumption of unit arc-lengths and unit coverage distance, V i is simply the set of nodes that are adjacent to i, plus i itself. Let S be a subset of the node set V. For each node i, we define a Boolean (binary) variable x i that equals 1 if iÎS and 0 otherwise. With a slight abuse of notation, we can write

$$ S = \bigcup\limits_{i \in V} {{x_i}i} , $$

where x ii is taken to equal the set {i} if x i = 1 and the null set otherwise. We also define X i as the sum of the Boolean variables for the nodes in V i; that is,

$$ {X_i} = \sum\limits_{j \in {V_i}} {{x_j}} . $$

Here, å represents Boolean summation, analogous to the “or” operator, in which 1 + 1 = 1. Then X i = 1 if and only if S contains a node that covers node i. Finally, we define the Boolean function f, which takes as inputs the vector of Boolean variables for the nodes and returns a single Boolean value:

$$ f({x_1}, \ldots ,{x_n}) = \prod\limits_{i \in V} {{X_i}} . $$

Since node i is covered if and only if X i = 1, we have the following theorem:

Theorem 1:

S contains a covering of V if and only if f (x 1,…, x n) = 1.

The advantage of using the function f is that it allows us to use Boolean algebra to construct coverings of V. Although this approach still involves enumerating all coverings, it allows us to do so without enumerating all subsets of V to identify them. In particular, we will create a “minimum sum of products,” i.e., the smallest possible sum of products of x i variables that is logically equivalent to f (x 1,…, x n). This method involves eliminating terms that are implied by others, then using Boolean algebra to simplify the resulting formula until we have an expression consisting of the sum of simple products of variables such that no product is implied by (contains) any other. The method is best explained by use of an example.

Example 1:

We illustrate the method using the sample network in Fig. 6.1.

Fig. 6.1
figure 1

Sample network

Full size image

Using the adjacencies depicted in Fig. 6.1, X 1 = x 1 + x 3, X 2 = x 2 + x 4, and so on. Therefore,

$$ \begin{aligned}f({x_1}, \ldots ,{x_n}) = \;&({x_1} + {x_3})({x_2} + {x_4})({x_3} + {x_1} + {x_2} + {x_4} + {x_5})\\ &({x_4} + {x_2} + {x_3} + {x_5})({x_5} + {x_3} + {x_4}). \end{aligned} $$

Using Theorem 1 to find all coverings of the graph, we need to find all possible values of {x 1,…, x 5} that make f (x 1,…, x n) = 1, meaning that all terms in the above product equal 1.

To begin, note that the first term is contained in the third. Since we need each term to equal 1, the third term equals 1 if the first does; we can therefore eliminate the third term. Similarly, the fourth term contains the fifth, so we can eliminate the fourth term. The resulting expression is

$$ f({x_1}, \ldots ,{x_n}) = ({x_1} + {x_3})({x_2} + {x_4})({x_3} + {x_4} + {x_5}). $$

Boolean algebra contains two distributive laws. One says that, for any Boolean variables x, y, and z,

$$ x + (yz) = (x + y)(x + z). $$

Applying this law to the last two terms, we get

$$ f({x_1}, \ldots ,{x_n}) = ({x_1} + {x_3})({x_4} + {x_2}{x_3} + {x_2}{x_5}). $$

The other Boolean distributive law says that

$$ x(y + z) = xy + xz. $$

Applying this law to multiply the two terms, and repeatedly applying both Boolean identity laws (which say that x + x = x and that xx = x), we obtain

$$ f({x_1}, \ldots ,{x_n}) = {x_1}{x_4} + {x_1}{x_2}{x_3} + {x_1}{x_2}{x_5} + {x_3}{x_4} + {x_2}{x_3} + {x_2}{x_3}{x_5}. $$

Finally, by the Boolean redundancy law (x + xy = x), we can remove the second and last terms:

$$ f({x_1}, \ldots ,{x_n}) = {x_1}{x_4} + {x_1}{x_2}{x_5} + {x_3}{x_4} + {x_2}{x_3}. $$

Therefore, the covers for the graph in Fig. 6.1 are

$$ \{ {\rm{1}},{\rm{4}}\} ,\,\{ {\rm{1}},{\rm{2}},{\rm{5}}\} ,\,\{ {\rm{3}},{\rm{4}}\} ,\,\{ {\rm{2}},{\rm{3}}\} . $$

All but {1, 2, 5} are minimum covers.

Hakimi was optimistic that this enumerative approach would prove to be practical: “…since the subject of simplification of Boolean functions has been widely studied and there are efficient digital computer programs for such a purpose, the above formulation is feasible.” Twenty-first century readers, however, will recognize that the enumerative approach is impractical for large instances. Moreover, since the vertex cover problem is NP-complete (Garey and Johnson 1979), no polynomial-time exact algorithm for the set covering location problem is known to exist. However, more efficient approaches than Hakimi’s exist; we discuss a mathematical-programming-based approach in the next section.

2.1.2 The Contribution by Toregas et al. (1971)

Toregas et al. (1971) formulate the set covering location problem as an integer programming problem and use standard mathematical programming methods to solve it. We discuss their approach next.

The integer programming problem has one set of decision variables:

$$ {x_j} = \left\{ {\kern -4pt} \begin{array}{l} 1,\quad {\rm{if\;a\;facility\;is\;opened\;at\;node}}\;j \\0,\quad {\rm{otherwise}} \\\end{array} \right. $$

for jÎV. Note that variable x j has no relation to the Boolean variables x i defined in Sect. 6.2.1.1.

The integer programming problem is formulated as follows:

$$ {\rm{SCLP}}:\min \;z = \sum\limits_{j \in V} {{x_j}}$$
(6.1)
$$ {\rm{s}}{\rm{.t}}{\rm{.}}\,\sum\limits_{j \in {V_i}} {{x_j}}\ge 1\quad \forall i \in V$$
(6.2)
$$ x_j \in \{ 0,{\rm{1}}\} \quad \forall j \in J $$
(6.3)

The objective function (6.1) computes the total number of facilities opened. Constraints (6.2) require at least one node from the coverage set V i to be opened for each node i. Constraints (6.3) are standard integrality constraints. Here, we do not assume that s = d ij = 1 (as we did in Sect. 6.2.1.1); any values for these parameters may be used in determining the coverage sets V i.

This formulation is virtually identical to that of the classical set covering problem; here it is discussed in the context of location theory in particular. It is well known that the set-covering problem typically has a small integrality gap; that is, the optimal objective value of the linear programming relaxation (denoted by z LP) is close to that of the integer program itself (Bramel and Simchi-Levi 1997), and often the linear programming relaxation even has all-integer solutions. In fact, ReVelle (1993) argues that many facility location problems have this property and discusses “integer-friendly programming” techniques for several classical problems. However, there do exist instances of the set covering location problem whose linear programming relaxations do not have all-integer optimal solutions (otherwise the problem would not be NP-hard). An example follows.

Example 2:

Consider the network depicted in Fig. 6.2. In this example, s = 1. An optimal solution to the linear programming relaxation of SCLP is given by x 1 = x 2 = x 3 = 0.5, x 4 = 0, with an objective value of z LP = 1.5.

Fig. 6.2
figure 2

Network for example 2

Full size image

Since the coefficient of each x j is 1 in the objective function of SCLP, it is clear that the objective function value is integer for any solution to the integer program. Since z LP is a lower bound on z*, the optimal objective function value for the integer program, and since z* must be integer, we can assert that

$$ z^* \ge \left\lceil {{z_{{\rm{LP}}}}} \right\rceil , $$

where \(\left\lceil a \right\rceil \) denotes the smallest integer greater than or equal to a. Therefore, Toregas et al. propose adding the following cut to SCLP:

$$ \sum\limits_{j \in J} {{x_{}}}\ge \left\lceil {{z_{{\rm{LP}}}}} \right\rceil . $$
(6.4)

We denote the resulting problem SCLP-C. The new cut may eliminate some fractional solutions, and the linear programming relaxation to SCLP-C may have an all-integer solution as a result.

For the example in Fig. 6.2, the problem SCLP-C does indeed have an integer solution: x 1 = x 2 = 1, x 3 = x 4 = 0, for example, with z* = 2. (It also has optimal fractional solutions, e.g., x j = 0.5 for all j, but the simplex method would find integer solutions since these represent extreme points of the feasible region.)

Toregas et al. therefore propose a two-step solution procedure for the set covering location problem.

Step 1: :

Solve the linear programming relaxation of SCLP. If the optimal solution is integer, STOP.

Step 2: :

Otherwise, solve the linear programming relaxation of SCLP-C using the optimal objective value from step 1 in the right-hand side of (6.4).

Even with constraint (6.4), the linear programming relaxation may not have an integer solution. Toregas et al. report that they found no such instance in their computational experiments, though we found several such instances in ours, see Sect. 6.2.1.3 “Computational Experiment”. In fact, Rao (1974) gives two counterexamples: in one, the addition of cut (6.4) results in a fractional solution; in the other, the addition of cut (6.4) results in an integer but non-optimal solution. (See also the reply to Rao’s note by Toregas et al. 1974).

Toregas et al. also discuss the relationship between the set covering location problem and a variant of the p-median problem in which each customer may only be served by facilities that are within a distance of s. The formulation is obtained simply by forcing the assignment variable to be 0 for facility–customer pairs that are more than s units apart, or, alternately, by indexing the assignment variables for each customer i over facilities j in V i, as opposed to all facilities j in V. (We omit the formulation here.)

The optimal objective value of this p-median variant changes with s. For sufficiently large s, the objective function value is no different from the p-median without distance constraints; as s decreases, the objective function value increases as a step function; and for sufficiently small s, the problem is infeasible. Toregas et al. argue that the solution to the set covering location problem provides some information about the feasibility of this problem. In particular, for a given value of p, the smallest value of s for which the p-median variant is feasible is equal to the smallest value of s for which SCLP has an optimal objective value of p. On the other hand, the solution to a set covering location problem does not provide any information about the breakpoints of the step function that relates the p-median objective to s.

2.1.3 Experiments and Variants

In the “Computational Experiment” section below, we discuss the results of our computational experiment related to SCLP. In “Row and Column Reduction”, we discuss a technique for reducing the problem size of the set covering location problem, and in “Facility Fixed Costs”, we discuss a variant involving fixed costs.

2.1.3.1 Computational Experiment

We performed a computational experiment to confirm the results reported by Toregas et al.—namely, that the linear programming gap for SCLP is small, and that cut (6.4) produces integer solutions. For each value of n = 50, 100, 200, 400, 800, we generated 100 random instances of the set covering location problem. Parameters were generated as follows:

  • x- and y-coordinates were drawn from U[0,100],

  • distances were calculated using the Euclidean metric, and

  • the coverage distance s was drawn from U[0,140] (140 » maximum possible distance between two points in 100 ´ 100 grid).

For each instance, we solved the linear programming relaxation of SCLP using CPLEX v. 10.2.0 to obtain z LP. If the optimal solution to the linear program was not integer, we added cut (6.4) and solved the linear programming relaxation to SCLP-C to obtain z LP   −   C. If the optimal solution was still not integer, we solved SCLP as an integer program to obtain z*. (If either of the linear programming relaxations resulted in integer solutions, their objective values give us z*.)

The results are shown in Table 6.1. The columns labeled “% Integer” list the percentage of instances for which the linear programming relaxation produced an integer optimal solution. The columns labeled “Avg LP Gap” and “Max LP Gap” list the average and maximum, respectively, of the linear programming gap, measured as (z LP − z*)/z* for SCLP and (z LP   −   C − z*)/z* for SCLP-C.

Table 6.1 Performance of linear programming relaxations of SCLP and SCLP-C
Full size table

The linear programming gap for SCLP is small and tends to decrease with lower values of n. The largest gap we found was 33.5% for a problem with n = 800. The addition of cut (6.4) reduces the linear programming gap substantially (from 0.0132 to 0.0004, on average), but does not guarantee integer solutions—even with the cut, 11.2% of instances had fractional optimal solutions. Several of these instances also had integer optimal solutions, though CPLEX did not find these. In general, CPLEX solved the integer programming problem in well under one minute on a laptop computer, even for the largest problems.

2.1.3.2 Row and Column Reduction

The size of SCLP can often be reduced substantially by using row- and column-reduction techniques. These methods exploit the coverage structure by eliminating rows and columns that are dominated by others. In particular:

  • A facility j 1 dominates another facility j 2 if it covers all of the customers that j 2 does; that is, if j 2ÎV i implies j 1ÎV i for all iÎV. In this case, there is no reason to open facility j 2 since j 1 covers all the same customers and possibly more. Therefore we can set \({x_{{j_2}}} = 0\), or equivalently, eliminate the column corresponding to j 2.

  • A customer i 1 dominates another customer i 2 if every facility that covers i 1 also covers i 2; that is, if \({V_{{i_1}}} \subseteq {V_{{i_2}}}\). In this case, if constraint (6.2) holds for i 1 it also holds for i 2, and therefore we can eliminate the row corresponding to i 2.

Row and column reduction techniques are appropriate for the SCLP because of the binary nature of coverage. Most facility location problems with distance objectives cannot generally accommodate these techniques, except heuristically, since under most metrics it is impossible for a facility to dominate another, i.e., to be closer to every customer than another facility is.

These techniques were proposed by Toregas and ReVelle (1972). See also Daskin (1995) and Eiselt and Sandblom (2004) for thorough discussions and examples of row- and column-reduction techniques.

2.1.3.3 Facility Fixed Costs

If the facilities each have a different fixed cost f j, then the problem becomes choosing facilities to cover all demands at minimum possible cost. This problem can be formulated simply by replacing the objective function (6.1) with the objective

$$ {\rm{Minimize}}\;z = \sum\limits_{j \in V} {{f_j}{x_j}.}$$

The set covering location problem as formulated above is a special case in which f j = 1 for all j. The linear-programming-based solution methods described in Sect. 6.2.3 can easily accommodate this variation. So can the Boolean-function approach: at the final step, we simply choose the cover that has the smallest total fixed cost.

2.2 The Maximal Covering Location Problem

Whereas the set covering location problem has the form

SCLP::

minimize the number of facilities opened,

s.t. cover all demand,

the Maximal Covering Location Problem MCLP has the inverse form:

MCLP::

maximize the demand covered,

s.t. a limit on number of facilities opened.

The set covering location problem treats all demand nodes as equivalent since the coverage constraint applies equally to all. In contrast, in the maximal covering location problem nodes are weighted by the demand that they generate, and the objective favors coverage of larger demands over smaller ones. As the number of allowable facilities increases, the demand covered naturally increases as well. The modeler can plot a tradeoff curve depicting the performance of a range of solutions along these two dimensions; the decision maker can then choose a solution based on this tradeoff.

In Sect. 6.2.2.1, we discuss the maximal covering location problem as formulated by Church and ReVelle (1974). Section 6.2.2.2 then describes some computational experiments and several variants of the model.

2.2.1 Church and ReVelle (1974)

This section commences with a formal statement of the maximal covering location problem as a mathematical programming model. The next section discusses heuristics, followed by an exact algorithm in “Linear Programming Approach”. “Mandatory Closeness Constraints” investigates the effects of a constraint that enforces an additional level of coverage.

2.2.1.1 Introduction and Formulation

Our notation in this section is identical to that in Sect. 6.2.1, with the addition of two new parameters: a i is the demand at node i per unit time, and p is the maximum allowable number of facilities. We also introduce a new set of decision variables:

$$ {y_i} = \left\{{\kern -4pt} \begin{array}{l} 1,\quad {\rm{if\;customer\;}}i{\rm{\;is\;covered\;by\;some\;facility}} \\0,\quad {\rm{otherwise}} \\\end{array} \right. $$

The maximal covering location problem is formulated by Church and ReVelle (1974) as follows:

$$ {\rm{MCLP}}:{\rm{Max}}\;z = \sum\limits_{i \in V} {{a_i}{y_i}}$$
(6.5)
$$ {\rm{s}}{\rm{.t}}{\rm{.}}\,\,\sum\limits_{j \in {V_i}} {{x_j} \ge {y_i}} \quad \forall i \in V $$
(6.6)
$$ \sum\limits_{j \in V} {{x_j} = p}$$
(6.7)
$$ {x_j} \in \{ 0,{\rm{1}}\} \quad \forall j \in V $$
(6.8)
$$ {y_i} \in \{ 0,{\rm{1}}\} \quad \forall i \in V $$
(6.9)

The objective function (6.5) computes the total demand covered. Constraints (6.6) prohibit a customer from counting as “covered” unless some facility that covers it has been opened. Constraint (6.7) requires exactly p facilities to be opened. Constraints (6.8) and (6.9) are standard integrality constraints. (In fact, it suffices to relax constraints (6.9) to 0 £ y i £ 1, since integer values for the y i are optimal if the x j are integer.)

Church and ReVelle cite White and Case (1973) as formulating a similar model to MCLP that maximizes the number of demand nodes covered, rather than the total demand. Case and White’s model is therefore a special case of the maximal covering location problem in which a i = 1 for all i.

Church and ReVelle also present an alternate formulation that uses a new decision variable \({\bar y_i}\) defined as \({\bar y_i} = 1 - {y_i}\); that is,

$$ {\bar y_i} = \left\{ {\kern -4pt} \begin{array}{l} 1,\quad {\rm{if\;customer\;}}i{\rm{\;is\;not\;covered\;by\;any\;facility}} \\0,\quad {\rm{otherwise}} \\\end{array} \right. $$

In the alternate formulation, constraints (6.6) are replaced by

$$ \sum\limits_{j \in {V_i}} {{x_j}}+ {\bar y_i} \ge 1\quad \forall i \in V. $$

The revised constraints state that if node i is not covered by any facility (i.e., \(\sum\nolimits_{j \in {V_i}} {{x_j}} = 0\)), then \({\bar y_i}\) must equal 1. The objective function (6.5) can be rewritten as

$${\rm{maximize}} \,\,\sum\limits_{i \in V} {{a_i}(1 - {{\bar y}_i}) =} \sum\limits_{i \in V} {{a_i} \,- \sum\limits_{i \in V}}{{a_i}{{\bar y}_i}},$$
(6.10)

or equivalently,

$$ {\rm{minimize}}\,\,\sum\limits_{i \in V} {{a_i}{{\bar y}_i}} , $$
(6.11)

since the first term in (6.10) is a constant. The revised objective (6.11) minimizes the uncovered demand. The revised formulation is then given by

$$ {\rm{MCLP2}}:{\rm{Min}}\;{\rm{z = }}\sum\limits_{i \in V} {{a_i}{{\bar y}_i}}$$
(6.12)
$$ {\rm{s}}{\rm{.t}}{\rm{.}}\;\sum\limits_{j \in {V_i}} {{x_j} + {{\bar y}_i}}\ge 1\quad \forall i \in V $$
(6.13)
$$ \sum\limits_{j \in V} {{x_j}}= p $$
(6.14)
$$ {x_j} \in \{ 0,{\rm{1}}\} \quad \forall j \in V $$
(6.15)
$$ {y_i} \in \{ 0,{\rm{1}}\} \quad \forall i \in V. $$
(6.16)

The two formulations are mathematically equivalent, as are their linear programming relaxations.

Megiddo et al. (1983) proved that the maximal covering location problem is NP-hard. The next two sections describe heuristic and exact approaches to solving the problem, all of which are discussed by Church and ReVelle (1974).

2.2.1.2 Heuristic Solution Methods

Like many facility location problems, the maximal covering location problem lends itself nicely to greedy heuristics such as the Greedy Adding heuristic, which Church and ReVelle (1974) credit to Church’s (1974) doctoral dissertation. The Greedy Adding heuristic begins with all facilities closed, then opens p facilities in sequence, choosing at each iteration the facility that increases coverage the most. For a discussion of greedy and other heuristics for facility location problems, see Current et al. (2002)

Solutions obtained with the Greedy Adding heuristic are nested in the sense that all of the facilities in the solution to the p-facility problem are also opened in the solution to the (p + 1)-facility problem. Optimal solutions to the maximal covering location problem are not, in general, nested in this way. Therefore, Church and ReVelle also suggest an alternate heuristic, called the Greedy Adding with Substitution heuristic, which attempts to rectify this problem by allowing an open facility to be closed and a closed facility to be opened at each iteration. Like any heuristic, Greedy Adding and the Greedy Adding with Substitution are not guaranteed to find the optimal solution. The latter, however, tends to perform well in practice, and both heuristics execute very quickly.

2.2.1.3 Linear Programming Approach

Church and ReVelle propose solving MCLP2 directly using linear programming and branch-and-bound. Like the set covering location problem, the linear programming relaxation of the maximal covering location problem often yields all-integer solutions: Church and ReVelle report that approximately 80% of their test instances had integer solutions; we found an even higher percentage in our computational tests (Sect. 6.2.2.2 “Computational Experiment”). Branch-and-bound may be applied to resolve fractional solutions to the linear programming relaxation, but Church and ReVelle also suggest a method that is effective when solving the same problem for consecutive values of p.

The method takes as input a fractional solution to the p-facility problem and an integer solution to the (p − 1)-facility problem. It is effective when the (p − 1)-facility solution covers all but a few nodes. We illustrate the method using an example.

Example 3:

Consider an instance of the maximal covering location problem for which the total demand across all nodes is 100 units. Suppose we have found an integer solution to the 4-facility problem and that it covers all but two nodes, for a total of 91 demand units covered. These two uncovered nodes (we will call them 1 and 2) have demands of 3 and 6, respectively. Suppose further that the linear programming relaxation to the 5-facility problem is fractional and covers 98 demand units. Finally, suppose that the minimum a i among all nodes i is 3.

The optimal integer solution with p = 5 cannot cover all of the nodes, since the linear programming relaxation has an objective value of 98. In fact, the integer solution may cover at most 97 demand units, since at best it leaves the 3-demand node uncovered. We can create an integer solution to the p = 5 problem by adding node 2 to the p = 4 solution. Since the p = 4 solution covered 91 demands, not including node 2, this new solution covers 91 + 6 = 97 demands. This solution must be optimal for p = 5 since 97 is an upper bound on the objective value. An optimal solution for the problem with p = 6 can now be found by adding node 1 to the p = 5 solution; the resulting solution covers all demands.

Church and ReVelle refer to this method as the “inspection” method. It can be summarized as follows. Let z IP(p) be the optimal p-facility objective value of MCLP, that is, the optimal demand covered by p facilities, and let z LP(p) be the optimal p-facility objective value of the linear programming relaxation of MCLP. We assume that we know the integer optimal solution with p − 1 facilities and that the optimal solution to the linear programming relaxation with p facilities is not integer. Let a min = min{a i: iÎV} and  \({a_{\rm{\Sigma }}} = \sum\nolimits_{i \in V} {{a_i}} \). We summarize the inspection method in the following theorem. (Church and ReVelle illustrate this method with an example, rather than stating it formally as a theorem.)

Theorem 2:

Suppose the following conditions hold:

  1. 1.

    \(Z_{\rm LP}(p) < {a_\Sigma}\), and

  2. 2.

    \({Z_{\rm IP}}(p - 1) + {a_i} = {a_\Sigma } - {a_{\min }}\) for some node i that is not covered in the optimal solution to the (p − 1)-facility problem,

then an optimal solution to the p-facility problem consists of the optimal solution to the (p −1)-facility problem plus node i.

Church and ReVelle report that, of the 20% of their test instances where linear programming relaxations did not have integer solutions, half could be solved using the inspection method. The other half was solved via branch-and-bound.

2.2.1.4 Mandatory Closeness Constraints

Church and ReVelle discuss a variant of the maximal covering location problem in which we require that all customers be covered within a secondary coverage distance t (t ³ s). For example, we might want to maximize the demand covered within 50 miles but require all demands to be covered within 100 miles. This model, known as the MCLP with Mandatory Closeness Constraints, can be viewed as a hybrid between the maximal covering location problem and the set covering location problem, since it has a max-coverage objective plus a hard coverage constraint.

The problem can be formulated simply by adding the following constraint to either formulation of the MCLP:

$$ \sum\limits_{j \in {U_i}} {{x_j}}\ge 1\quad \forall i \in V, $$

where U i = {jÎV: d ji £ t}. The resulting model can be solved using linear programming and branch-and-bound.

Suppose we solve SCLP and find that, for a given instance, the minimum number of facilities that covers all demand nodes with a coverage distance of t is p*. Generally there are many optimal solutions to this problem. The maximal covering location problem with mandatory closeness constraints gives us a mechanism for choosing among these, by selecting the solution that also maximizes the demands covered within some distance s. In particular, we solve MCLP with mandatory closeness constraints using p* as the number of facilities to open and t as the secondary coverage distance.

2.2.2 Experiments and Variants

2.2.2.1 Computational Experiment

We performed a computational experiment to verify Church and ReVelle’s claim that the MCLP often results in all-integer solutions. We set n = 50, 100, 200, 400, 800. For each value of n, we generated 100 random instances and tested three different values of p. The random instances were generated as described in Sect. 6.2.1.3 “Computational Experiment”, with one additional parameter: Demands a i were drawn from U[0,100].

We solved the linear programming relaxation of MCLP2 using CPLEX v. 10.2.0 and, if the solution was not all integer, we solved the integer program. The results are displayed in Table 6.2. The column labeled “p” gives the value of p in MCLP2. The column labeled “Avg LP Gap > 0” gives the average integrality gap among only those instances with a positive integrality gap, or “—” if there were no such instances. All other columns are interpreted as in Table 6.1.

Table 6.2 Performance of linear programming relaxation of MCLP2
Full size table

The linear programming relaxation of MCLP seems to generate integer solutions even more frequently than the relaxation of SCLP (at least for our test instances): an average of 95.3% of the time. When it fails to do so, the integrality gap can be quite large, though this is partly a function of the minimization objective, which may have optimal values near zero and hence any suboptimal solution may have a large error on a percentage basis.

Note that for some instances the linear programming relaxation had fractional solutions but an integrality gap of 0, as evidenced by the fact that some rows have “% Integer” <100% but an average linear programming gap of 0. For these instances, an optimal integer solution exists for the linear programming relaxation but CPLEX returned a fractional optimal solution instead.

2.2.2.2 Tradeoff Curve

Figure 6.3 displays the optimal objective function value of MCLP2—the number of demand units uncovered—as p varies for a particular random instance with n = 100 and s = 15. As expected, the uncovered demand decreases as p increases. For p ³ 18, all demands are covered. The convex shape is typical of tradeoff curves for the maximal covering location problem, meaning that additional facilities provide decreasing marginal returns in terms of additional coverage.

Fig. 6.3
figure 3

Tradeoff curve: demands uncovered vs. p

Full size image
2.2.2.3 Lagrangian Relaxation Approach

The maximal covering location problem can also be solved using Lagrangian relaxation. The key idea is to remove a set of constraints and add a penalty to the objective function for violating the constraints. The resulting problem is easier to solve but may produce solutions that are infeasible for MCLP. By adjusting the objective-function penalties iteratively, the solutions found approach the optimal solution for the maximal cover location problem. The use of Lagrangian relaxation for MCLP was detailed by Galvão and ReVelle (1996), although Daskin et al. (1989) also report computational results from a similar method without providing details. See Fisher (1981, 1985) for an excellent overview of Lagrangian relaxation.

We illustrate the Lagrangian relaxation method using formulation MCLP, though it can also be applied to MCLP2. We relax constraints (6.6) using Lagrangian multipliers li to obtain the following Lagrangian subproblem:

$$ \begin{aligned} {\rm{MCLP} - LR}:{\rm{Max}}\;z & = \sum\limits_{i \in V} {{a_i}{y_i}}+ \sum\limits_{i \in V} {{\lambda_i}\left({\sum\limits_{j \in {V_i}} {{x_j}}- {y_i}} \right)}\\ &=\sum\limits_{i \in V} {({a_i} - {\lambda _i}){y_i}}+\sum\limits_{j \in V} {\left( {\sum\limits_{i \in V:j \in {V_i}}{{\lambda _i}} } \right)} {x_j} \\ \end{aligned} $$
(6.17)
$$ {\rm{s}}{\rm{.t}}{\rm{.}}\,\sum\limits_{j \in V} {{x_j}}= p $$
(6.18)
$$ {x_j} \in \{ 0,{\rm{1}}\} \quad \forall j \in V $$
(6.19)
$$ {y_i} \in \{ 0,{\rm{1}}\} \quad \forall i \in V $$
(6.20)

This problem decouples by x and y since there are no constraints involving both sets of variables. As a result, it can be solved easily. The optimal y-values are given by

$$ {y_i} = \left\{ {\kern -1pt} \begin{array}{l} 1,\quad {\rm{if\;}}{a_i} - {\lambda _i}> 0, \\0,\quad {\rm{otherwise}}{\rm{.}} \\\end{array} \right. $$

To find the optimal x-values, we set x j = 1 for the p facilities with the largest values of \(\sum\nolimits_{i \in V:j \in {V_i}} {{\lambda _i}} \). The optimal objective value of MCLP-LR provides an upper bound on that of MCLP. Feasible (lower bound) solutions can be found by setting x j = 1 for the p facilities that are opened in the upper-bound solution and setting y i = 1 for each customer i that is covered by some existing facility. Lagrange multipliers can be updated using subgradient optimization, and branch-and-bound can be used if the Lagrangian procedure fails to yield a suitably small optimality gap; see Daskin (1995) for more details. Daskin et al. (1989) report that the procedure works quite well, especially when the lower-bound heuristic is supplemented by a substitution heuristic.

2.2.2.4 Budget Constraints

We can incorporate fixed costs into the model in a similar manner as we did for the set covering location problem in “Facility Fixed Costs”. Here, the fixed cost appears in the constraints rather than the objective function. In particular, we replace constraint (6.7) or (6.14) with

$$ \sum\limits_{j \in V} {{f_j}{x_j}}\le B, $$

where B is a budget imposed exogenously on the total fixed costs. This constraint can be easily handled by the linear programming approach discussed in Sect. 6.2.2.1, but it somewhat complicates the Lagrangian approach in Sect. 6.2.2.2 since determining the optimal x values now requires us to solve the following knapsack problem:

$$ {\rm{Max}}\,\sum\limits_{j \in V} {\left( {\sum\limits_{i \in V:j \in {V_i}} {{\lambda _i}} } \right)} {x_j} $$
$$ {\rm{s}}{\rm{.t}}{\rm{.}}\,\sum\limits_{j \in V} {{f_j}{x_j}}\le B $$
$$ {x_j} \in \{ 0,1\} \quad \forall j \in V. $$

Although this problem can be solved quite quickly using modern codes, it is still NP-hard, and it may slow the Lagrangian procedure significantly.

2.2.2.5 Relationship to p-Median Problem

The maximal covering location problem can be formulated as a special case of the p-median problem through a simple transformation of the distance matrix. In particular, we set

$$ {d_{ji}} = \left\{ {\kern -4pt}{\begin{array}{*{20}{c}} {0,} & {{\rm{if }}j \in {N_i}} \\ {1,} & \quad {{\rm{otherwise.}}} \\\end{array}} \right.$$

That is, we redefine the distance metric so that the distance from node j to node i is 0 if j covers i and 1 otherwise. The p-median problem is then formulated as usual (see, e.g., Daskin 1995). The optimal solution will cover as many demand units as possible using p facilities. Any algorithm for the p-median problem can then be applied to solve the maximal covering location problem.

3 Extensions

The literature contains many enhancements to the set covering and maximal covering location problems. In this section, we focus in particular on generalizations of the notion of coverage. One common criticism of the two types of problems is that they assume that all customers within a facility’s coverage radius can be served by the facility, and served equally. In practice, facilities are not always available when needed, especially in the public-sector arena where facilities may represent such essential services as ambulances and fire crews. One approach to this issue is backup coverage, in which customers are required or encouraged to be covered by more than one open facility. Another approach is expected coverage, which accounts for probabilistic information. Moreover, in many cases the coverage benefit changes as the distance between a customer and its assigned facility changes. This dependency is captured by the notion of gradual coverage. We briefly discuss models for backup, expected, and gradual coverage in the next three subsections. For thorough reviews of backup and expected coverage models, see Daskin et al. (1988) or Berman and Krass (2002).

3.1 Backup Coverage Models

Both the set covering location problem and the maximal covering location problem have been extended to consider solutions in which customers are covered by more than one facility. One may require backup coverage in order for a customer to count as “covered,” or one may simply reward solutions for backup coverage.

3.1.1 Required Backup Coverage

It is simple to formulate a required-backup version of either covering problem. In the set covering location problem, we simply modify constraints (6.2) to read

$$ \sum\limits_{j \in {V_i}} {{x_j}}\ge m\quad \forall i \in V, $$

where m is the desired number of times that each customer is to be covered. In the maximal covering location problem, we can replace constraints (6.6) with

$$ \sum\limits_{j \in {V_i}} {{x_j}}\ge m{y_i}\quad \forall i \in V, $$

where y i must equal 0 unless at least m facilities that cover customer i are open. This constraint is likely to weaken the linear programming relaxation of MCLP, however.

3.1.2 Rewards for Backup Coverage

We focus on models in which m = 2. Extensions to these models to consider m > 2 are straightforward but often yield weaker linear programming relaxations, as discussed above. Let

$$ {w_i} = \left\{{\kern -4pt} \begin{array}{l} 1,\quad {\rm{if\;customer\;}}i{\rm{\;is\;covered\;by\;two\;or\;more\;facilities}} \\0,\quad {\rm{otherwise}}{\rm{.}} \\\end{array} \right. $$

The models formulated below contain a reward in the objective function for each customer who is covered twice. However, the backup coverage reward is strictly a secondary objective; in no case should a solution with more facilities have a better objective than one with fewer facilities, even if it has better backup coverage.

Daskin and Stern (1981) propose the following model for the set covering location problem with backup coverage:

$${\rm{ SCLP} \hbox{-} BC}:{\rm{Min}}\;{z} = (|V| + 1)\sum\limits_{j \in V}{{x_j}}- \sum\limits_{i \in V} {{w_i}}$$
(6.21)
$$ {\rm{s}}{\rm{.t}}{\rm{.}}\,\,\sum\limits_{j \in {V_i}} {{x_j}}- {w_i} \ge 1\quad \forall i \in V $$
(6.22)
$$ {x_j} \in \{ 0,{\rm{1}}\} \quad \forall j \in V $$
(6.23)
$$ {w_i} \in \{ 0,{\rm{1}}\} \quad \forall i \in V. $$
(6.24)

The objective function (6.21) enforces the hierarchical nature of the primary objective (minimizing the number of facilities) and the secondary one (maximizing twice-covered customers). It does so by multiplying the primary objective by a constant large enough that even if the primary objective is as small as possible (equal to 1), the secondary objective can never exceed it. Therefore, the solution will never open more facilities than necessary solely to improve the secondary objective. Constraints (6.22) require each customer to be covered at least once, and prohibit w i from equaling 1 unless customer i is covered at least twice.

Another advantage of this formulation is that its solutions avoid facilities that are dominated by others in the sense described in “Row and Column Reduction”. As a result, the linear programming relaxation to SCLP-BC is more likely to have all-integer solutions than that of SCLP is. Readers are referred to Daskin and Stern (1981) for justifications for both of these claims.

A similar hierarchical version of the maximal covering location problem was introduced by Storbeck (1982) and reformulated by Daskin et al. (1988). We modify their formulation somewhat in what follows.

$${\rm{ MCLP \hbox{-} BC}}:{\rm{Max}}\;z = (|V| + 1)\sum\limits_{i \in V} {{a_i}{y_i}}+ \sum\limits_{i \in V} {{w_i}}$$
(6.25)
$$ {\rm{s}}{\rm{.t}}{\rm{.}}\,\,\sum\limits_{j \in {V_i}} {{x_j}}- {y_i} - {w_i} \ge 0\quad \forall i \in V $$
(6.26)
$$ \sum\limits_{j \in V} {{x_j}}= p $$
(6.27)
$$ {x_j} \in \{ 0,{\rm{1}}\} \quad \forall j \in V $$
(6.28)
$$ {y_j} \in \{ 0,{\rm{1}}\} \quad \forall i \in V $$
(6.29)
$$ {w_j} \in \{ 0,{\rm{1}}\} \quad \forall i \in V. $$
(6.30)

The objective function (6.25) maximizes a sum of the primary coverage (first term) and backup coverage (second term); the weight on the first term ensures that primary coverage will never be sacrificed in order to achieve backup coverage. Note that the secondary coverage objective considers nodes covered, rather than demand units covered. This is required in order for the weighting to achieve the desired hierarchy. Constraints (6.26) stipulate that customer i may be considered covered (y i = 1) only if at least one facility in V i is open, and may be considered twice covered (w i = 1) only if two such facilities are open. Since the objective function coefficient for y i is greater than that for w i, the model will always set y i = 1 before it sets w i = 1, thus ensuring the desired coverage hierarchy.

3.2 Expected Coverage Models

The class of expected coverage models is descended primarily from the Maximum Expected Covering Location Problem (MEXCLP) introduced by Daskin (1982). Daskin’s primary application is in the siting of emergency medical service vehicles. The MEXCLP maximizes the expected coverage of each node, defined using probabilistic information about facility availability, subject to a constraint on the number of facilities.

The MEXCLP assumes that the average system-wide probability that a given facility (vehicle) is busy is given by q. If a customer is covered by k facilities, then the probability that all those facilities are busy at a given point in time is given by q k, and the probability that at least one facility is available is 1 − q k. The maximum expected covering location problem defines new variables to keep track of the number of covering facilities for each customer. Define variables

$$ {y_{im}} = \left\{ {\kern -4pt}\begin{array}{l} 1,\quad {\rm{if\;customer\;}}i{\rm{\;is\;covered\;by\;at\;least\;}}m{\rm{\;facilities}} \\0,\quad {\rm{otherwise}} \\\end{array} \right. $$

for all iÎV and m = 1,…, p. Note that if customer i is covered by exactlyk facilities, then y im = 1 for m = 1,…, k and y im = 0 for m = k + 1,…, p. Then

$$ \sum\limits_{m = 1}^p {(1 - q){q^{m - 1}}{y_{im}}}= \sum\limits_{m = 0}^{k - 1} {(1 - q){q^m} = 1 - {q^k}}$$

using a standard formula for geometric sums. In other words, the first summation in the equation above expresses the probability that customer i is covered by an available facility in terms of the decision variables y im. Using this approach, Daskin formulates the MEXCLP as follows:

$$ MEXCLP:{\rm{Max}}\;z = \sum\limits_{i \in V} {\sum\limits_{m = 1}^p {(1 - q){q^{m - 1}}{a_i}{y_{im}}} }$$
(6.31)
$$ {\rm{s}}{\rm{.t}}{\rm{.}}\,\sum\limits_{m = 1}^p {{y_{im}}}- \sum\limits_{j \in {V_i}} {{x_j}}\le 0\quad \forall i \in V $$
(6.32)
$$ \sum\limits_{j \in V} {{x_j}}= p $$
(6.33)
$$ {x_j} \in \{ 0,{\rm{1}}\} \quad \forall j \in V $$
(6.34)
$$ {y_j} \in \{ 0,{\rm{1}}\} \quad \forall i \in V. $$
(6.35)

The objective function (6.31) calculates the expected coverage. Constraints (6.32) allow the total number of y im variables, for fixed i, to be no more than the total number of opened facilities that cover i. At first it may seem that the model needs a constraint of the form

$$ {y_{im}} \le {y_{i\!,m + 1}}\quad \forall i \in V,m = 1, \ldots ,p - 1 $$

in order to ensure that y im is set to 1 for the correct values of m; that is, for the k smallest values of m, where k is the number of opened facilities that cover i. However, such a constraint is not necessary since the objective function coefficient is larger for smaller values of m; the model will automatically set y im = 1 for the k smallest values of m.

Daskin (1983) proposes a heuristic for MEXCLP based on node exchanges, and several metaheuristics have been proposed subsequently; see, e.g., Aytug and Saydam (2002), and Rajagopalan et al. (2007).

The primary criticism that has been leveled at the MEXCLP concerns the assumption of a uniform system-wide availability probability, since availability might vary based on geographic area or on the demand assigned to each facility. ReVelle and Hogan (1989) address this concern in the Maximum Availability Location Problem (MALP), a chance-constrained version of MCLP. They formulate two versions of the model, one in which the availability probability is assumed to be the same throughout the system; the main difference between this model and MEXCLP is that MALP maximizes the number of demand units that are covered with at least a certain probability, whereas MEXCLP includes the expected coverage in the objective. ReVelle and Hogan’s second MALP model estimates the busy probability separately for each customer by assuming that facilities within the coverage radius of a given customer are available only to that customer. Obviously this assumption is not true, but it provides an easy, and fairly accurate, estimate of the availability probability. The two models are nearly identical once the availability probabilities are calculated. Galvão et al. (2005) present a framework that attempts to unify MEXCLP and MALP.

Batta et al. (1989) embed Larson’s (1974, 1975) hypercube queuing model into MEXCLP to compute the availability probabilities endogenously. They find that their model disagrees substantially with MEXCLP in terms of the expected coverage predicted, but nevertheless results in similar sets of facilities chosen. Marianov and ReVelle (1996) formulate a version of the MEXCLP that endogenously calculates the availability property using a queuing model at each facility. The region around each customer node is treated as an M/M/s/s queue, where s is the number of servers located within the coverage radius. Their model implicitly assumes that that the call rate in the neighborhood is not substantially different from that in adjacent neighborhoods. The resulting model is structurally similar to the MALP but uses different (but pre-computable) values for the coverage radius.

3.3 Gradual Covering Models

The models discussed in this chapter so far all assume that coverage is a binary concept: either a customer is covered or it is not, and the distance from the customer to the covering facility is irrelevant. In practice, though, customers who are located very close to a facility such as a fire station may be served better than those located farther away, even if both customers are within the nominal coverage radius. In this case, the benefit from coverage decreases with the customer–facility distance, as illustrated in Fig. 6.4a. Moreover, some facilities such as garbage dumps are most beneficial when they are close (to reduce transportation costs) but not too close (to reduce odors and truck traffic), as illustrated in Fig. 6.4b.

Fig. 6.4
figure 4

Benefit of coverage versus distance: a strictly decreasing, b non-monotonic

Full size image

Church and Roberts (1983) introduce the Weighted Benefit Maximal Coverage (WBMC) Model, which extends the maximal covering location problem to accommodate non-binary coverage benefits. The objective is to maximize the sum of all customers’ coverage benefits (defined as the benefit per unit of demand times the demand of that customer) subject to a constraint on the number of facilities located. The formulation is a relatively straightforward modification of MCLP and includes a coverage variable (y) and a constraint for each customer–distance pair. (Each “distance” is really a range of distances, as in Fig. 6.4.) The number of variables and constraints therefore grows linearly with the number of distance ranges. If the benefits are not monotonically decreasing with the distance, as in Fig. 6.4b, then an additional set of constraints is required to ensure that customers are assigned to their nearest opened facilities, a property that is automatic if benefits are monotonically decreasing. The resulting formulations are more complex than MCLP, but Church and Roberts find that they still retain their “integer-friendliness:” the linear programming relaxation is generally very tight and often all-integer.

4 Conclusions and Future Research Directions

In this chapter we have discussed two classical models for locating facilities to ensure coverage of customer nodes. One model, the set covering location problem, requires every customer to be covered and does so with the minimum number of facilities, while the other, the maximal covering location problem maximizes the demand covered subject to a limit on the number of facilities. Both models have garnered considerable attention in the location theory literature, and both models (and their extensions) have been widely applied in practice, especially in public-sector applications such as the location of emergency medical services.

Both covering problems are reasonably easy to solve, in the sense that modern general-purpose integer programming solvers such as CPLEX can solve problems with hundreds or thousands of nodes to optimality in a few minutes on a desktop computer. This stems in part from the fact that the linear programming relaxations of both problems tend to be tight, and even yield integer optimal solutions for a large percentage of instances. Therefore, although these problems are NP-hard, they are among the easiest problems in that class.

On the other hand, many of the extensions of these models are much more computationally challenging. Daskin’s (1982) MEXCLP model, for example, or the queuing-based congestion models discussed by Berman and Krass (2002), have more complex structures than SCLP or MCLP and therefore cannot be solved using off-the-shelf solvers, except for small instances. One important direction for future research, therefore, is the development of effective, accurate algorithms and heuristics for extensions of SCLP and MCLP.

Of particular interest are stochastic and robust variants of coverage models. Although the literature on stochastic facility location models is extensive (see, e.g., Snyder 2006 for a review), most such models consider cost-based objectives rather than coverage-based ones. (Notable exceptions are the expected-coverage models described in Sect. 6.3.2, and their variants.) An important topic for future study is therefore the incorporation of stochastic elements—such as demands, travel times, server availabilities, and supply disruptions—into coverage models. The resulting models are likely to be significantly more complex than their deterministic counterparts, but the stochastic programming and robust optimization literatures are vast, and many of their more sophisticated tools have yet to be tapped by the location science community.

The distinction between cost- and coverage-based models made in the previous paragraph is an important one since it is often equivalent to the distinction between private- and public-sector applications—the former is primarily concerned with cost minimization while the latter is often encouraged or mandated to provide adequate coverage to all demand locations (ReVelle et al. 1970). Public-sector and humanitarian applications have gained increased attention in the operations research community in recent years—for example, the 2008 INFORMS Annual Meeting featured “Doing Good with OR” as a central theme, as did the February 2008 issue of OR/MS Today. The application of coverage models to emergency medical services and other services has been a success story in public operations research for decades, and recent renewed interest provides an opportunity for existing and new coverage models to be applied for the public good.