Maximal Coverage Location Problem

Abstract

The maximal covering location problem was first introduced by Church and ReVelle in 1973 at the North American Regional Science Council meetings and subsequently published in Papers in Regional Science (formerly Papers of the Regional Science Association) in 1974. It has proven to be a seminal contribution to location analysis and modeling, in terms of both technical merit and practical significance. With more than 1,500 citations in the academic literature, it has truly stood the test of time and may actually be as relevant or more so today than when it was first presented/published. Not only is it the subject of broad application and extension, but it has also been integrated in a number of geographic information system–based commercial software packages, including ArcGIS and TransCAD, for general use. This article provides an overview of the maximal covering location problem, highlighting the use, application, solution, evolution, and extension of this important location analytic approach.

Keywords

location models spatial analysis methods modeling in GIS optimization other methods urban and regional spatial structure spatial structure land use planning urban and regional issues policy and applications

Introduction

Location analysis and modeling has a long history of theoretical and methodological development that has produced a wide array of methods to support analysis, planning, and decision making in public- and private-sector contexts. Referred to as location theory historically and location analytics in more contemporary contexts, location analysis and modeling has been used both to support prescriptive planning efforts seeking to site service facilities and to provide descriptive insights regarding service performance of existing operations. In both descriptive and prescriptive capacities, location theory has had a major role in regional science, with a long history founded upon the work of von Thunen, Weber, Christallar, Losch, Hotelling, among others (Ghosh and Rushton 1987; Isard 2003; Murray 2010). Overviews of location modeling can be found in Owen and Daskin (1998), Hamacher and Drezner (2002), Church and Murray (2009), Murray (2010), and Eiselt and Marianov (2011).

A primary category of location analytic approaches involves coverage, where a facility provides service based on spatial proximity. Facilities might correspond to fire stations, health care clinics, cellular antennae, or a chain of restaurants. Each facility then has a spatial footprint that reflects the area that it primarily “serves.” This may be based on travel time, as is the case for police, ambulance, and fire response, or could be based on line of sight or audibility factors. Such spatial footprints reflect service and may be regular or irregular in shape and contiguous or fragmented in terms of areal extent. One of the most highly cited location modeling approaches is to optimize coverage, the maximal covering location problem (MCLP), detailed in Church and ReVelle (1974). A concise problem statement is: Maximize coverage of demand within a desired service standard S by locating a fixed number of facilities. This approach has proven to be a seminal contribution in regional science and beyond, in terms of both technical merit and practical significance (see Isserman 2003; Ratick, Osleeb, and Si 2016; Snyder and Haight 2016; Wei 2016). As a result, it has been included in the Modern Classics in Regional Science series edited by Haynes et al. (1996). With more than 1,550 citations to date in the academic literature, it has truly stood the test of time and may actually be as relevant or more so today than when it was first published. Not only is it the subject of broad application and extension, but it has also been integrated in a number of geographic information system (GIS)-based commercial software packages, including ArcGIS and TransCAD, given its general utility.

The assumption in the original specification of the model is that a network of nodes and arcs represent geographic space, where nodes are concentrations of anticipated service demand and/or potential facility sites and arcs reflect travel between nodes. With this in mind, notation for use in mathematical specification is now introduced:

i = index of demand nodes (entire set I),

j = index of potential facility sites (entire set J),

d_ij = shortest distance or travel time from demand node i to potential facility j,

a_i = population to be served at demand node i,

p = number of facilities to be located,

N_i = set of potential facilities that suitably cover demand node i,

S = service distance or time standard.

Through evaluation and assessment, it is possible to identify a priori which potential facility sites suitably serve/cover any particular demand node i, the result of which is reflected in the set N_i . Such assessment involves determining whether a potential facility site j is within the service distance/time standard S of node i, or formally if d_ij is less than S. Worth noting is that coverage may be nonspatial as well, derived based upon other criteria (see Church, Stoms, and Davis 1996; Ando et al. 1998). In addition to the above notation, decision variables are needed to track or account for facility siting decisions as well as to assess whether demand nodes are suitably served. These variables are as follows:

\begin{array}{l} X_{j} = {\begin{cases} 1 if potential facility site j selected \\ 0 otherwise \end{cases} \\ Y_{i} = {\begin{cases} 1 if demand node i s suitably covered by one or more sited facilities \\ 0 otherwise \end{cases} \end{array}

With notation and decision variables, the mathematical formulation of the MCLP is:

Maximize \sum_{i} a_{i} Y_{i}

Subject to \sum_{j \in N_{i}} X_{j} - Y_{i} \geq 0 \forall i

\sum_{j} X_{j} = p

X_{j} = {0, 1} \forall j

Y_{i} = {0, 1} \forall i

The objective, (1), is to maximize total demand in the region suitably served or covered. The Y_i decision variable accounts for whether demand node i is served by a sited facility, so the goal is a maximization of the demand weighted sum of those nodes served by sited facilities, $\sum_{i} a_{i} Y_{i}$ . Constraint (2) accounts for whether or not a demand node is covered by any sited facilities. Since X_j indicates a decision to locate (or not) at potential facility site j, the sum of those selected facilities capable of serving node i $(X_{j} = 1 for j \in N_{i})$ is a bound on the coverage variable Y_i . Specifically, if the sum $(\sum_{j \in N_{i}} X_{j})$ is not greater than zero, then no sited facilities can serve node i. Constraint (3) specifies that p facilities are to be sited. The sum of the facility siting decisions, $\sum_{j} X_{j}$ , must equal exactly p. This is equivalent to a budget restriction if the cost of siting each facility is essentially the same. Constraints (4) restrict decision variables to be binary integers.

Unknown for a particular application of this model is which potential facility sites to select, $X_{i} (X_{1}, X_{2}, X_{3} \dots X_{| I |})$ , and which demand are to be served, $Y_{j} (Y_{1}, Y_{2}, Y_{3} \dots Y_{| J |})$ . A solution approach is therefore necessary to help identify the best solution. In this case, the MCLP is a linear-integer programming model, enabling a range of commercial software packages to be used for its solution.

The abstraction of geographic space, reducing the complexities of the real world to something more simplified and manageable, has been important for the MCLP, and location theory and regional science more generally. Because demand is conceived to be at a discrete and finite number of points (nodes), with travel-along arcs of the network, this makes assessment and interpretation of coverage rather straightforward. A facility node j is either able to serve a demand node i, d_ij ≤ S, or it is not. Yet, there is evidence that point simplification and/or manipulation introduces unintended measurement and interpretation errors (Daskin et al. 1989; Current and Schilling 1990; Tong and Murray 2009). Church (1999) and Murray (2010) highlight, in fact, that demand and facility sites could be any sort of object (e.g., point, line, polygon, etc.). Recent research demonstrates specific issues associated with the application of the MCLP. Worth noting in particular is the work by Tong and Murray (2009), Alexandris and Giannikos (2010), Cromley, Lin, and Merwin (2012), and Yin and Mu (2015) suggesting that non-point-based contexts cannot be sufficiently addressed under classic assumptions through the direct use of the MCLP.

The significance and implications of advancements in addressing coverage optimization for regional science are important and the motivation for this article. Enhanced computing enables faster system response, larger study regions examined, and more variables to be considered. GIS proliferation and widespread adoption mean that there now exist better, more detailed data. These data are based on less simplification and more accurate abstractions of reality. As a result, for many planning and policy contexts, there is a better understanding of spatiotemporal, behavioral, and other kinds of relationships and political processes. From a modeling perspective, this has meant that analytical tools must evolve, and the MCLP is a good example of this. Simple point-based representation of geographic space has proven to be insufficient, leading to errors and uncertainty in analysis (see Tong and Murray 2009; Cromley, Lin, and Merwin 2012). Nevertheless, there are ways to address the fundamental goals of regional coverage optimization, essentially involving the use of better geographic information as well as taking advantage of derived spatial knowledge/insights. This is no doubt important given the practical significance of the MCLP as it is capable of encapsulating analysis, planning, and decision-making contexts, but also that the MCLP is reflective of other commonly relied upon regional science methods.

This article provides an overview of an important location modeling and analysis approach, the MCLP. The next section reviews the wide range of application contexts that have been addressed using this model. This is followed by a description of solution approaches that have been relied upon. The evolution of model and solution capabilities attributable to advances in GIScience are then examined. Noteworthy extensions are then detailed. This article ends with discussion and concluding comments.

Application

The MCLP has been particularly remarkable for the breadth of planning, management, and decision-making contexts to which it has been applied. Chung (1986) and Schilling, Jayaraman, and Barkhi (1993) summarize some of the various planning milieus that the MCLP has been utilized to address. Considerably more work has appeared since. A select summary of work relying on the MCLP is given in Table 1 in order to highlight the array of applications, beginning in the 1970s to now.

Table 1.

Application Evolution of Reported MCLP Usage for Planning and Analysis.

Application	Facility	References
Pollution control	Monitoring equipment	Hougland and Stephens (1976)
Response equipment	Airtanker/oil spill equipment/vehicle	Hodgson and Newstead (1978), Belardo et al. (1984), Dimopoulou and Giannikos (2001)
Financial services	Branch office	Sweeney, Mairose, and Martin (1979), Pastor (1994), Alexandris, Dimopoulou, and Giannikos (2008)
Vision	Test point	Kolesar (1980)
Advertising	Magazine	Dwyer and Evans (1981)
Health care	Clinic	Bennett, Eaton, and Church (1982), Osleeb and McLafferty (1992)
Emergency medical services	Ambulance	Eaton et al. (1985), Adenso-Diaz and Rodriguez (1997)
Data management	Cluster group	Chung (1986)
Forest fire detection	Watchtower	Goodchild and Lee (1989), Bao et al. (2015)
Fabrication	Hole punch tool	Daskin, Jones, and Lowe (1990)
Rainfall	Gauge	Hogan (1990)
Retail	Outlet	Hodgson (1990)
Water quality	Monitoring equipment	Lee and Deininger (1992)
Community warning	Siren	Current and O’Kelly (1992)
Road maintenance	Depot	Rose, Bennett, and Evans (1992)
Conservation	Reserve	Church, Stoms, and Davis (1996), Ando et al. (1998)
Image processing	Spectral endmember	Roberts et al. (1998)
Telecommunication	Cellular base station	Tutschku (1998)
Apparel layout	Trim group pieces	Grinde and Daniels (1999)
Automotive	Refueling station	Kuby and Lim (2005)
Product design	Attribute	Camm et al. (2006)
Security and safety	Camera	Murray and Tong (2007)
Dentistry	Shade tab	Cocking et al. (2010)
Law enforcement	Police patrol	Curtin, Hayslett-McCall, and Qiu (2010)
Fire fighting	Fire station	Murray, Tong, and Grubesic (2012)
Cardiac arrest	Automated external defibrillator	Dao et al. (2012), Chan et al. (2013)
Aviation	Airport	Grubesic, Murray, and Matisziw (2013)
Wildlife management	Street crossing structure	Downs et al. (2014)

Note: MCLP = maximal covering location problem.

Table 1 summary identifies the general application context (Application), the facility being sited (Facility), and key reference(s) reporting this application. Again, the table is not meant to be comprehensive in terms of representing all of the various application areas utilizing the MCLP nor does it include all references in the literature where similar studies may have been undertaken. The intent, rather, is to merely give an overview that highlights the range and diversity of MCLP application. Historically, there has been much reliance on the MCLP to support emergency response contexts, such as the positioning and dispatching of ambulances, siting fire stations, policing, and so on. In fact, Church and ReVelle (1974) intimate that the MCLP would be particularly valuable in such areas when it was originally proposed and formulated. Of course, application has extended well beyond, with the MCLP being used to support air quality and natural resource management, advertising, fabrication, image processing, and even dentistry, among others. Another point to be taken from Table 1 is the continued relevance of the MCLP over the past four decades, with new applications continuing to emerge.

Figure 1 displays the historical trend of citations to Church and ReVelle (1974) over the years as reported by Google Scholar, with 1,534 total citations reported through 2014 (as of May 11, 2015). Already in 2015, there are 47 citations, but this is not included in Figure 1 as the year is not complete. To give a sense of how the MCLP continues to be used, an examination of the 152 reported studies in 2014 was carried out. A coarse characterization is that emergency services were some 28 percent of the contexts. Theory-oriented work extending the MCLP, relaxing assumptions, establishing properties, and so on, represented 18.4 percent of studies. Service facility siting, such as retail stores, was the theme of 13.6 percent of the cases. In 7.5 percent of the studies, public facilities were of interest, like libraries, parks, and so on. The remaining 32 percent was broken down in the following categories: clinics (6.7 percent), transportation (5.4 percent), fueling/refueling stations (4.7 percent), algorithm/heuristic development (4.7 percent), sensor siting (4 percent), nature reserve/wildlife protection (3.3 percent) and other (districting, telecommunication, sirens, and disease surveillance; 3.3 percent).

Figure 1.

Citations to Church and ReVelle (1974). Source: Google Scholar May 11, 2015.

In order to provide more depth about the way in which the MCLP is being utilized to support planning and decision making, details of select problem applications are now provided. The three illustrative studies focus on telecommunications, surveillance, and emergency services, respectively.

An evaluation of telecommunications was examined in Grubesic and Murray (2002), specifically broadband access provided through digital subscriber lines, xDSL. Of particular interest was emerging issues of an Internet digital divide between those with quality high-speed access and those with comparatively poor-quality access. The focus was on which telephone company central offices in an urban region providers would be equipped with xDSL, given limited capital to invest in equipment. A major implication of this investment is that only those areas within 18,000 feet of an equipped central office would have quality access to xDSL. The MCLP was applied to assess potential inequities that would emerge under different development conditions and strategies.

Policing was considered in Murray and Tong (2007) with monitoring sensors utilized for surveillance of an area or region. The sensors record information and feed this to a control room where it is processed and evaluated by human personnel. In this case, the police department of a university campus monitors a wall display panel with live feeds from positioned video cameras. The visibility possible from a camera is a function of type, height, and physical obstructions. The MCLP was used to select sites for a limited number of sensors, video cameras, in order to maximize surveillance potential.

The evaluation, assessment, and planning of fire stations was reported in Murray, Tong, and Grubesic (2012). A community experiencing continuing population growth and development sought to make future station location decisions given a limited budget. They needed to expand their current fire response system and wanted to be able to answer a call for service within five minutes to the greatest extent possible. To accomplish this, the MCLP was used to identify siting configurations satisfying future needs.

The Essential Air Service program was examined in Grubesic, Murray, and Matisziw (2013). This program was a response to the Airline Deregulation Act of 1978, effectively providing airports in rural/remote communities a financial bridge to support continued commercial airline service. Fiscal deficits and tough economic times prompted planning for decreased services. Since the Essential Air Service program seeks to serve people and businesses within seventy miles of rural airport, the MCLP was used to assess system efficiency and identify effective strategies for continued support of select airports, given limited funds.

This section provided an overview of the various application contexts that the MCLP has been utilized to address. Clearly, the areas are growing and diversifying, reflecting the continued relevance and significance of this particular analytical approach. Citation trends suggest this will continue over the coming decades.

Solution

With such a broad range of problem contexts being addressed, there continues to be a need for better, faster, and more efficient techniques for solving the MCLP. Exact and heuristic solution techniques for general coverage models are discussed in Schilling, Jayaraman, and Barkhi (1993) and Farahani et al. (2012), with specific mention of some that have been used to solve the MCLP. ReVelle, Scholssberg, and Williams (2008) provide one of the more recent reviews of methods that expressly solve the MCLP. A summary of many of the methods that have been employed are included in Table 2, along with associated references reporting the developed approaches. The noteworthy point to be taken from Table 2 is that the application of the MCLP has required the development of specific approaches tailored to more efficiently solve problem instances. This is not particularly surprising because the MCLP is NP-complete, meaning that a given application instance is likely to be difficult to solve, optimally or approximately.

Table 2.

Solution Approaches for the MCLP.

Approach	References
Linear programming	Church and ReVelle (1974)
Greedy	Church and ReVelle (1974)
Integer programming	Kolesar (1980)
Implicit enumeration	Dwyer and Evans (1981)
Lagrangian relaxation	Pirkul and Schilling (1989), Galvao and ReVelle (1996), Downs and Camm (1996)
Simulated annealing	Murray and Church (1996)
Tabu search	Adenso-Diaz and Rodriguez (1997)
GRASP	Resende (1998)
Genetic algorithms	Jaramillo, Bhadury, and Batta (2002), Jia, Ordóñez, and Dessouky (2007), Tong, Murray, and Xiao (2009)
Column generation	Pereira, Lorena, and Senne (2007)
Heuristic concentration	ReVelle, Scholssberg, and Williams (2008)

Note: MCLP = maximal covering location problem.

A standard exact approach for deriving solutions of an application instance of the MCLP has been to rely on commercial general purpose optimization software, such as Gurobi Optimizer, IBM ILOG CPLEX, FICO Xpress, and so on. Similarly, open source software exists as well, like LP_Solve. Using these approaches effectively involves setting up the problem using a scripting or programming language, then call a solver library associated with the software package. Typically, problems solved along these lines would make use of linear programing or linear-integer programming (branch and bound). Assuming convergence, the problem solutions would be exact, or provably optimal.

Another approach for solving the MCLP is to use a heuristic. While not provably optimal, heuristics offer approximate solutions that are hoped to be of high quality. Big data and real-time planning environments have meant that finding good solutions fast is of great practical value. For this reason, there remains a need for improved solution techniques, reflected in the continued development reported in Table 2.

It is worth mentioning that access to and solution of the MCLP is also possible in commercial GIS software packages. For example, structuring and solving an MCLP application instance in ArcGIS and TransCAD, among others, is easily accomplished. In ArcGIS, there are location-allocation functions in network analyst, and in particular “maximize coverage” would enable an MCLP to be set up as the problem type. Similarly, in TransCAD, one would use “facility location analysis” to accomplish this. There are in fact a number of reported application studies that have relied on this basic approach using GIS, such as Gerrard et al. (1997) and Garcia-Palomares, Gutiérrez, and Latorre (2012). It is important to note that GIS packages facilitating access to the MCLP typically solve problems using a heuristic (see Murray 2010).

Evolution

The evolving use and application of the MCLP is particularly evident in Tables 1 and 2 as well as in Figure 1. In many ways, this has happened in concert with the development, growth, and maturation of GIS. Church and Murray (2009) and Longley et al. (2015), among others, discuss that GIS is a combination of hardware, software, and procedures enabling data management and spatial query. Key components of GIS include data capture, modeling, management, manipulation, analysis, and display. What is noteworthy about GIS beyond the basics of generating and dealing with spatial information are the capabilities that it provides for supporting a range of analytical functions, many of which facilitate MCLP specification and application. Highlighted in Murray (2010) are capabilities in GIS to undertake suitability analysis as well as operations associated with containment, overlay, distance, buffering, and spatial interpolation, among others. This enables feasible potential facility sites, J, to be identified. As well, potential demand (a _i), proximity (d_ij ), and identification of potential facility sites capably of serving an area (N_i ) can also be readily derived.

Much spatial information now exists, expediting coverage location analysis as well. While a discussion of geographic information and how to obtain it can be found in GIS texts, such as Church and Murray (2009) and Longley et al. (2015), geolibraries or geoportals often curate federal, state, and/or local government produced spatial information. One example is DATA.GOV. Beyond this, GPS, satellites, aircraft, and drones represent a rich source of data. Vendors too have a variety of detailed data. Finally, there are much individual user-generated spatial data, often referred to volunteered geographic information. The point is that far more geographic data are accessible than it was when the MCLP was first conceived in the early 1970s.

Enhanced computing capabilities, GIS, and a wealth of spatial information combine to facilitate carrying out analysis in real time, enabling the MCLP to be applied in creative ways. Add to this a better understanding of practical problem contexts with less abstraction/simplification and the stage has been set for broad utilization of the MCLP. It is an important modeling approach that reflects planning and management nuances and can be supported by data and analytical tools.

Another facet of the evolution of the MCLP is a recognition of potential issues associated with its application, specifically errors that may arise due to the representation of geographic space. Early research by Daskin et al. (1989) and Current and Schilling (1990) recognized that results and insights derived using the MCLP may be impacted by spatial aggregation of input data (demand areas), a common data management and simplification approach. Tong and Murray (2009), Alexandris and Giannikos (2010), Tong and Church (2012), Cromley, Lin, and Merwin (2012), and Yin and Mu (2015) demonstrated that the MCLP is sensitive to how space is abstracted, either as points or as polygons. Such findings associated with aggregation and/or abstraction are suggestive of modifiable areal unit problem (MAUP) impacts (see Murray 2005). That is, the analytical method can be manipulated or varies based upon a change in how geographic space is represented. What this means is that error/uncertainty is likely to be introduced by the use of a digital approximation of geographic space when the MCLP is applied.

In many ways, the MCLP is an attempt to discretize a planning context that may be viewed as a continuous space problem. MAUP and abstraction issues, therefore, are not too surprising. To address this, Murray et al. (2008) and Wei and Murray (2015) detail the continuous space MCLP. A formulation is as follows:

Maximize \sum_{i} A_{i}

Subject to \int \int f_{i} (Δ) d Φ \geq A_{i} \forall i

| Δ | = p

(φ_{j}, λ_{j}) \in Δ, j = 1, \dots p

A_{i} \geq 0, \forall_{i}

where

f_i ( ) = function indicating the amount of demand i served by a given set of sited facilities,

Δ = set of sited facilities (to be selected by the model),

(ϕ _j , λ _j ) = decision variables indicating the locational coordinates of sited facility j,

A_i = decision variable indicating how much demand in area i is suitably served.

This formulation essentially reflects what is mathematically structured in the original specification of the MCLP using discrete points as demand and discrete points as potential facility locations. It also formalizes the description of a continuous space MCLP offered in Watson-Gandy (1982), though it was referred to as the “m-partial cover problem.” What differs is that now demand is non-point based and is represented as a continuous subarea of a region. Further, potential facility sites may be anywhere in the region, not limited to predefined points. The continuous space surface in Figure 2 illustrates this, where demand varies and feasible sites are anywhere in the region. With this in mind, the objective, (5), is to cover as much potential demand as possible. Constraint (6) accounts for how much demand in each area i is suitably served, derived using integration. The number of facilities to be sited is limited to p in constraint (7). Worth noting is that | | indicates the number of members in a set. Finally, conditions on decision variables are specified in constraints (8) and (9).

Figure 2.

Continuous space region (darker color indicates higher demand density).

The formulation of the continuous space MCLP, (5)–(9), is inherently nonlinear. It is therefore very challenging to solve, heuristically or exactly. As a result, many special cases of this general model have been examined and solved in the literature. Friedman (1976), Watson-Gandy (1982), Mehrez and Stulman (1982), and Church (1984) consider the case where facilities may be sited anywhere in continuous space, but demand is discrete and point based. Further, the service coverage of a facility is a circle of given radius. Murray and Tong (2007) extend this case to account for demand as any spatial object, point, line, or polygon, but also allow for the service coverage of a facility to be of any shape. Murray et al. (2008) and Matisziw and Murray (2009) examine the continuous space MCLP assuming that demand is uniformly distributed. Cromley, Lin, and Merwin (2012) and Wei and Murray (2014) study the case when demand is continuously distributed and potential facility sites are discrete, finite, and known a priori.

What is noteworthy about the special cases considered by Mehrez and Stulman (1982), Church (1984), Murray and Tong (2007), Murray et al. (2008), Matisziw and Murray (2009), Cromley, Lin, and Merwin (2012), and Wei and Murray (2014) is that they reflect application contexts of importance but also are amenable to solution approaches exploiting problem features, assumptions, and so on. Interestingly, this exploitation is largely facilitated by the use of GIS in some way. Three GIS functions in particular stand out: overlay, finite dominating set (FDS), and skeleton.

Mentioned earlier was the work of Cromley, Lin, and Merwin (2012) and Wei and Murray (2014) considering continuously distributed demand and potential facility sites that are given. Through the use of polygon overlay, Cromley, Lin, and Merwin (2012) and Wei and Murray (2014) are able to discretize continuous space while also accounting for demand heterogeneity. Discussion and description of overlay can be found in de Berg et al. (2000), Church and Murray (2009), and Longley et al. (2015). A formal description is given two layers of nonoverlapping objects (polygons), L ₁ and L ₂, then O(L ₁ , L ₂) is the overlay operator producing a new layer, L, of faces f ∊ L that are a maximally connected subset $f_{1} \cap f_{2}$ of all faces f ₁ ∊ L ₁ and f ₂ ∊ L ₂ such that $\hat{f} \cap f^{'} = Ø$ for all $\hat{f}, f^{'} \in L$ . Figure 3 depicts this process, where two layers are shown and through overlay result in an output layer containing each unique face, or polygon. With discrete faces, it is then possible to apply the MCLP as originally formulated, (1)–(4). This enables a transformation of the continuous-space MCLP to an MCLP. This is only possible because of overlay and means that an exact solution using the MCLP can be obtained.

Figure 3.

Overlay process.

As detailed previously, Mehrez and Stulman (1982), Church (1984), and Murray and Tong (2007) consider the case where facilities may be sited anywhere in continuous space, but demand is represented as discrete objects. While this technically means that facilities could be sited at an infinite number of locations, Mehrez and Stulman (1982), Church (1984), and Murray and Tong (2007) are able to exploit spatial knowledge about areas that offer enhanced coverage over other areas. This is effectively an FDS, a discrete set of locations that can be proven to contain an optimal solution to the continuous-space MCLP. Murray and Tong outline the general process for identification of the FDS, where first one must identify demand objects that are to be served (given), then derive the coverage boundary for each demand object, and finally identify a point in the intersection of coverage boundaries. The intersection of coverage boundaries is the by-product of overlay, in fact. This set derived from overlay faces represents those facility sites that only need to be considered, reducing infinite continuous space to a finite set of points. A representative point for each face is shown in Figure 4 and would constitute an FDS based upon the abovementioned conditions. With the FDS, it is then possible to apply the MCLP as originally formulated, (1)–(4). Effectively, the continuous-space MCLP is reduced to an MCLP through the identification and use of the FDS.

Figure 4.

Representative point for each finite dominating set (FDS) polygon/face.

Recall that Murray et al. (2008) and Matisziw and Murray (2009) examined the case where demand is uniformly distributed. Observing that the most coverage would be achieved by siting in central locations of a region, Murray et al. (2008) and Matisziw and Murray (2009) were able to prove under certain conditions that the optimal single facility location was along the skeleton (or medial axis) of a region. The skeleton is the locus of points that are the centers of all disks maximally inscribed within a region, where inscription corresponds to touching the region boundary at two or more locations. Derivation of a polygon skeleton is a standard GIS function. The significance of this is that infinite space is reduced to line segments. The skeleton for a region is given in Figure 5. Combined with intelligent line search techniques, this enables an optimal solution to be obtained in some cases (single facility) and good solutions found using heuristic techniques in other cases (p facilities).

Figure 5.

Polygon skeleton (medial axis).

These examples highlight the evolution of the MCLP from a discrete problem specification to a more generalized continuous space MCLP. Because of properties, conditions, rich spatial data, and derived knowledge from geographic information, a number of techniques have been developed and employed to solve special cases of the continuous-space MCLP, both exact and heuristic. It is clear that much more work will continue along these lines because there are limited capabilities for solving the general case problem, the continuous-space MCLP.

Extensions

As noted previously in this article, there are many coverage model reviews in the literature, such as Daskin, Hogan, and ReVelle (1988), Schilling, Jayaraman, and Barkhi (1993), Erkut et al. (2009), and Farahani et al. (2012), among others. What can be inferred is that there is both generalization of the MCLP and extension. Accounting for continuous space, in terms of either potential demand or potential siting of facilities, could be considered both generalization and extension. Above all, the distinction of discrete and continuous space was recognized as part of the evolution of the MCLP, given data and computing advances. Admittedly, this could be cast in other ways. In this section, a discussion is offered to support that there are most certainly other types of generalization and/or extension that can be recognized associated with the MCLP. This arises for many reasons, and could be due to theory, application need, model specification, solution advancement, and so on. Specifically highlighted here are six broad categories of extension. This categorization ranges from parameter and constraint changes to the basic MCLP to the more technically substantial involving probabilistic functions of certainty/uncertainty. It is worth pointing out, however, that even relatively minor modification can be both interesting and computationally significant, necessitating further research and specialized solution approaches.

Parameter and constraint modification

One category of MCLP extension has involved subtle and not so subtle modifications to the MCLP. A combination of the MCLP with the location set covering problem, referred to in Church and ReVelle (1974) as the MCLP with mandatory closeness constraints, is an example of this. In essence, this involves the addition of a set of constraints to the MCLP, (1)–(4), where each demand must be within a designated service standard of a sited facility. Another example is the addition of service facility capacity constraints, as reviewed in Pirkul and Schilling (1991). Noteworthy in this case is that incorporation of capacity constraints on facilities and/or workload has proven to make problem solution much more difficult. Different measures and metrics representing demand have also been considered, such as the criticality index in Oztekin et al. (2010) and data envelopment analysis–based efficiency scores in Grubesic et al. (2016). Finally, recent exploration of temporal dimensions of service and decision making can be found in Zarandi, Davari, and Sisakht (2013).

Multiple objectives

There has been considerable focus in MCLP extension on models that incorporate different objectives, possibly with associated constraints. Examples include the two different demand objectives in Schilling et al. (1980), the weighted benefit MCLP discussed in Church and Roberts (1983), backup models reviewed in Hogan and ReVelle (1986), the combined primary/backup coverage and capacity model of Araz, Selim, and Ozkarahan (2007), and the incorporation of alternative demand metrics in Oztekin et al. (2010), among others. These modeling extensions build on the MCLP, often by adding one or more coverage attributes to consider. The most significant issue is that the problem now becomes more complicated as many objectives must be considered. How to do this is not simple and remains an active area of research. A host of multiple objective methods for identifying trade-off solutions exist, with the weighting method and constraint method being among the most common. However, the associated problem instances may be difficult to solve, and understanding trade-off solution space is not trivial.

Probabilistic certainty

Much of the extension of MCLP has been devoted to accounting for aspects of probabilistic certainty. This ranges from demand for service being uncertain to possibilities that a service facility may not be available when needed. As an example, an ambulance is out on an emergency call when another call for service arrives reflects such a scenario. To address these types of situations, extensions of the MCLP have attempted to account for various aspects of uncertainty, including the maximum expected and maximum availability approaches reviewed in Daskin, Hogan, and ReVelle (1988). Queuing-based approach has also been developed (see Marianov and Serra 1998). A comparative study of select approaches in this area is offered in Erkut et al. (2009). Other forms of accounting for uncertainty also include the notion of hedging, as structured within an MCLP framework by Ratick, Osleeb, and Si (2016).

Service coverage

Observed behavior and performance suggests that in some application contexts, service is not uniform up to the prespecified distance or time standard S, but rather could degrade in some manner, be amplified, or could otherwise be impacted by local conditions. Church and Roberts (1983) focused on one aspect of this for the MCLP by varying coverage levels, where different time/distance intervals account for different service quality characteristics. A more generalized overview of this as well as associated research can be found in Berman, Drezner, and Krass (2010), highlighting gradual, cooperative, and variable radius approaches for extending the MCLP. Davari, Zarandi, and Turksen (2013) and Averbakh et al. (2014) offer approaches for solving one or more combinations of these cases.

Path structure

An important class of MCLP extension involves simultaneous routing and siting of facilities that provide coverage. Current, ReVelle, and Cohon (1985) sought to minimize route path length and maximize potential demand covered by facilities located along the route. Multiple path coverage was considered in Wu and Murray (2005) while route extension along these lines was structured in Matisziw, Murray, and Kim (2006). A timber harvesting context was evaluated in Bont, Heinimann, and Church (2015). Finally, Lin and Wong (2014) incorporate equity and coverage considerations in bus feeder design. Certainly, a challenge is combining routing with coverage planning as both are difficult spatial optimization problems in their own right.

Interdiction

While probabilistic certainty recognizes that a facility might be busy or in use, and therefore would delay response, interdiction reflects that a facility is no longer able to provide any service due to failure, damage, sabotage, and so on. Church, Scaparra, and Middleton (2004) proposed an extension of the MCLP to identify a subset of facilities that degrade system coverage the most. O’Hanley and Church (2011) extend this work to explicitly account for pre- and post-interdiction levels of coverage and detail solution algorithms. Lei, Tong, and Church (2014) extend the MCLP to account for spatially varying facility interdiction/failure probabilities. The goal in interdiction modeling is to identify weakness in the system in some cases while in others, it is to plan for service coverage patterns with damage or sabotage in mind. In either case, the intent is facility hardening and/or design that is more resilient to failure/damage.

While this review could continue with many additional categories and distinguishing characteristics of MCLP extensions, due to space restrictions the categories will be limited to those mentioned earlier. Recent reviews on coverage modeling offer other interpretations and additional insights.

Conclusions

The MCLP introduced in Church and ReVelle (1974) has proven to be a seminal contribution to location analysis and modeling. Subsequent work has applied the MCLP to a range of problem contexts, developed better solution techniques, relaxed assumptions and established additional theoretical foundations, and extended the MCLP in various ways. Arguably, enhanced computing and improved spatial data have contributed to a better understanding of problems and as a result have led to extensions of the MCLP. What has not changed, however, is the importance of coverage goals underlying many problem contexts when service facilities are being sited and/or evaluated. Providing service to the greatest amount of potential demand with limited resources resonates. The areas of MCLP application are growing and diversifying, reflecting the continued relevance and significance of this particular coverage model. Supporting model extensions and solution development remain strong as well. Citation trends suggest this will continue over the coming decades with many exciting developments associated with the MCLP lying ahead.

Footnotes

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Adenso-Diaz

Rodriguez

. 1997. “A Simple Heuristic for the MCLP: Application to the Location of Ambulance Bases in a Rural Region.” Omega 25:181–87.

Alexandris

Dimopoulou

Giannikos

. 2008. “A Three-phase Methodology for Developing or Evaluating Bank Networks.” International Transactions in Operational Research 15:215–37.

Alexandris

Giannikos

. 2010. “A New Model for Maximal Coverage Exploiting GIS Capabilities.” European Journal of Operational Research 202:328–38.

Ando

Camm

J. D.

Polasky

Solow

. 1998. “Species Distribution, Land Values, and Efficient Conservation.” Science 279:2126–28.

Araz

Selim

Ozkarahan

. 2007. “A Fuzzy Multi-objective Covering-based Vehicle Location Model for Emergency Services.” Computers & Operations Research 34:705–26.

Averbakh

Berman

Krass

Kalcsics

Nickel

. 2014. “Cooperative Covering Problems on Networks.” Networks 63:334–49.

Bao

Xiao

Lai

Zhang

Kim

. 2015. “Optimizing Watchtower Locations for Forest Fire Monitoring Using Location Models.” Fire Safety Journal 71:100–9.

Belardo

Harrald

Wallace

W. A.

Ward

. 1984. “A Partial Covering Approach to Siting Response Resources for Major Maritime Oil Spills.” Management Science 30:1184–96.

Bennett

V. L.

Eaton

D. J.

Church

R. L.

. 1982. “Selecting Sites for Rural Health Workers.” Social Science & Medicine 16:63–72.

10.

Berman

Drezner

Krass

. 2010. “Generalized Coverage: New Developments in Covering Location Models.” Computers & Operations Research 37:1675–87.

11.

Bont

L. G.

Heinimann

H. R.

Church

R. L.

. 2015. “Concurrent Optimization of Harvesting and Road Network Layouts under Steep Terrain.” Annals of Operations Research 232:41–64.

12.

Camm

J. D.

Cochran

J. J.

Curry

D. J.

Kannan

. 2006. “Conjoint Optimization: An Exact Branch-and-bound Algorithm for the Share-of-choice Problem.” Management Science 52:435–47.

13.

Chan

T. C.

Lebovic

Tang

S. K.

Chan

J. Y.

Cheng

H. C.

Morrison

L. J.

Brooks

S. C.

. 2013. “Identifying Locations for Public Access Defibrillators Using Mathematical Optimization.” Circulation 127:1801–9.

14.

Chung

C. H.

1986. “Recent Applications of the Maximal Covering Location Planning (MCLP) Model.” Journal of the Operational Research Society 37:735–46.

15.

Church

R. L.

1984. “The Planar Maximal Covering Location Problem.” Journal of Regional Science 24:185–201.

16.

Church

R. L.

1999. “Location Modelling and GIS.” In Geographical Information Systems, edited by Longley

P. A.

Goodchild

M. F.

Maguire

D. J.

Rhind

D. W.

, 293–303. New York: Wiley.

17.

Church

R. L.

Murray

A. T.

. 2009. Business Site Selection, Location Analysis, and GIS. New York: Wiley.

18.

Church

R. L.

ReVelle

C. R.

. 1974. “The Maximal Covering Location Problem.” Papers in Regional Science 32:101–18.

19.

Church

R. L.

Roberts

K. L.

. 1983. “Generalized Coverage Models and Public Facility Location.” Papers in Regional Science 53:117–35.

20.

Church

R. L.

Scaparra

M. P.

Middleton

R. S.

. 2004. “Identifying Critical Infrastructure: The Median and Covering Facility Interdiction Problems.” Annals of the Association of American Geographers 94:491–502.

21.

Church

R. L.

Stoms

D. M.

Davis

F. W.

. 1996. “Reserve Selection as a Maximal Covering Location Problem.” Biological Conservation 76:105–12.

22.

Cocking

Helling

Oswald

Rammelsberg

Reinelt

Hassel

A. J.

. 2010. “Using Discrete Optimization for Designing Dental Shade Guides.” Color Research & Application 35:233–39.

23.

Cromley

R. G.

Lin

Merwin

D. A.

. 2012. “Evaluating Representation and Scale Error in the Maximal Covering Location Problem Using GIS and Intelligent Areal Interpolation.” International Journal of Geographical Information Science 26:495–517.

24.

Current

O’Kelly

. 1992. “Locating Emergency Warning Sirens.” Decision Sciences 23:221–34.

25.

Current

J. R.

ReVelle

C. R.

Cohon

J. L.

. 1985. “The Maximum Covering/Shortest Path Problem: A Multiobjective Network Design and Routing Formulation.” European Journal of Operational Research 21:189–99.

26.

Current

J. R.

Schilling

D. A.

. 1990. “Analysis of Errors Due to Demand Data Aggregation in the Set Covering and Maximal Covering Location Problems.” Geographical Analysis 22:116–26.

27.

Curtin

K. M.

Hayslett-McCall

Qiu

. 2010. “Determining Optimal Police Patrol Areas with Maximal Covering and Backup Covering Location Models.” Networks and Spatial Economics 10:125–45.

28.

de Berg

Van Kreveld

Overmars

Schwarzkopf

O. C.

. 2000. Computational Geometry: Algorithms and Applications. 2nd ed. Berlin, Germany: Springer.

29.

Dao

T. H. D.

Zhou

Thill

J. C.

Delmelle

. 2012. “Spatio-temporal Location Modeling in a 3D Indoor Environment: The Case of AEDs as Emergency Medical Devices.” International Journal of Geographical Information Science 26:469–94.

30.

Daskin

M. S.

Haghani

A. E.

Khanal

Malandraki

. 1989. “Aggregation Effects in Maximum Covering Models.” Annals of Operations Research 18:113–39.

31.

Daskin

M. S.

Hogan

ReVelle

. 1988. “Integration of Multiple, Excess, Backup, and Expected Covering Models.” Environment and Planning B 15:15–35.

32.

Daskin

Jones

P. C.

Lowe

T. J.

. 1990. “Rationalizing Tool Selection in a Flexible Manufacturing System for Sheet-metal Products.” Operations Research 38:1104–15.

33.

Davari

Zarandi

M. H. F.

Turksen

I. B.

. 2013. “A Greedy Variable Neighborhood Search Heuristic for the Maximal Covering Location Problem with Fuzzy Coverage Radii.” Knowledge-based Systems 41:68–76.

34.

Dimopoulou

Giannikos

. 2001. “Spatial Optimization of Resources Deployment for Forest-fire Management.” International Transactions in Operational Research 8:523–34.

35.

Downs

B. T.

Camm

J. D.

. 1996. “An Exact Algorithm for the Maximal Covering Problem.” Naval Research Logistics 43:435–61.

36.

Downs

Horner

Loraamm

Anderson

Kim

Onorato

. 2014. “Strategically Locating Wildlife Crossing Structures for Florida Panthers Using Maximal Covering Approaches.” Transactions in GIS 18:46–65.

37.

Dwyer

F. R.

Evans

J. R.

. 1981. “A Branch and Bound Algorithm for the List Selection Problem in Direct Mail Advertising.” Management Science 27:658–67.

38.

Eaton

D. J.

Daskin

M. S.

Simmons

Bulloch

Jansma

. 1985. “Determining Medical Service Vehicle Deployment in Austin, Texas.” Interfaces 15:96–108.

39.

Eiselt

H. A.

Marianov

, eds. 2011. Foundations of Location Analysis. New York: Springer.

40.

Erkut

Ingolfsson

Sim

Erdoğan

. 2009. “Computational Comparison of Five Maximal Covering Models for Locating Ambulances.” Geographical Analysis 41:43–65.

41.

Farahani

R. Z.

Asgari

Heidari

Hosseininia

Goh

. 2012. “Covering Problems in Facility Location: A Review.” Computers & Industrial Engineering 62:368–407.

42.

Friedman

1976. “On the Analysis and Solution of Certain Geographical Optimal Covering Problems.” Computers & Operations Research 3:283–94.

43.

Galvao

R. D.

ReVelle

. 1996. “A Lagrangean Heuristic for the Maximal Covering Location Problem.” European Journal of Operational Research 88:114–23.

44.

Garcia-Palomares

J. C.

Gutiérrez

Latorre

. 2012. “Optimizing the Location of Stations in Bike-sharing Programs: A GIS Approach.” Applied Geography 35:235–46.

45.

Gerrard

R. A.

Church

R. L.

Stoms

D. M.

Davis

F. W.

. 1997. “Selecting Conservation Reserves Using Species-covering Models: Adapting the ARC/INFO GIS.” Transactions in GIS 2:45–60.

46.

Ghosh

Rushton

, eds. 1987. Spatial Analysis and Location-allocation Models. New York: Van Nostrand Reinhold.

47.

Goodchild

M. F.

Lee

. 1989. “Coverage Problems and Visibility Regions on Topographic Surfaces.” Annals of Operations Research 18:175–86.

48.

Grinde

R. B.

Daniels

Karen

. 1999. “Solving an Apparel Trim Placement Problem Using a Maximum Cover Problem Approach.” IIE Transactions 31:763–69.

49.

Grubesic

T. H.

Murray

A. T.

. 2002. “Constructing the Divide: Spatial Disparities in Broadband Access.” Papers in Regional Science 81:197–221.

50.

Grubesic

T. H.

Murray

A. T.

Matisziw

T. C.

. 2013. “A Strategic Approach for Improving Rural Air Transport in the United States.” Transport Policy 30:117–24.

51.

Grubesic

Wei

Murray

Wei

. 2016. “Essential Air Service in the United States: Exploring Strategies to Enhance Spatial and Operational Efficiencies.” International Regional Science Review 39:108–30.

52.

Hamacher

H. W.

Drezner

, eds. 2002. Facility Location: Applications and Theory. Berlin, Germany: Springer.

53.

Haynes

K. E.

Button

Nijkamp

Qiangsheng

, eds. 1996. Regional Dynamics. Cheltenham, UK: Edgar.

54.

Hodgson

M. J.

1990. “A Flow-capturing Location-allocation Model.” Geographical Analysis 22:270–79.

55.

Hodgson

M. J.

Newstead

R. G.

. 1978. “Location-allocation Models for One-strike Initial Attack of Forest Fires by Airtankers.” Canadian Journal of Forest Research 8:145–54.

56.

Hogan

1990. “Reducing Errors in Rainfall Estimates through Rain Gauge Location.” Geographical Analysis 22:33–49.

57.

Hogan

ReVelle

. 1986. “Concepts and Applications of Backup Coverage.” Management Science 32:1434–44.

58.

Hougland

E. S.

Stephens

N. T.

. 1976. “Air Pollutant Monitor Siting by Analytical Techniques.” Journal of the Air Pollution Control Association 26:52–53.

59.

Isard

2003. History of Regional Science and the Regional Science Association International. Berlin, Germany: Springer.

60.

Isserman

A. M.

2003. “Intellectual Leaders of Regional Science: A Half-century Citation Study.” Papers in Regional Science 83:91–126.

61.

Jaramillo

J. H.

Bhadury

Batta

. 2002. “On the Use of Genetic Algorithms to Solve Location Problems.” Computers & Operations Research 29:761–79.

62.

Jia

Ordóñez

Dessouky

M. M.

. 2007. “Solution Approaches for Facility Location of Medical Supplies for Large-scale Emergencies.” Computers & Industrial Engineering 52:257–76.

63.

Kolesar

1980. “Testing for Vision Loss in Glaucoma Suspects.” Management Science 26:439–50.

64.

Kuby

Lim

. 2005. “The Flow-refueling Location Problem for Alternative-fuel Vehicles.” Socio-economic Planning Sciences 39:125–45.

65.

Lee

B. H.

Deininger

R. A.

. 1992. “Optimal Locations of Monitoring Stations in Water Distribution System.” Journal of Environmental Engineering 118:4–16.

66.

Lei

T. L.

Tong

Church

R. L.

. 2014. “Designing Robust Coverage Systems: A Maximal Covering Model with Geographically Varying Failure Probabilities.” Annals of the Association of American Geographers 104:922–38.

67.

Lin

J. J.

Wong

H. I.

. 2014. “Optimization of a Feeder-bus Route Design by Using a Multiobjective Programming Approach.” Transportation Planning and Technology 37:430–49.

68.

Longley

P. A.

Goodchild

M. F.

Maguire

D. J.

Rhind

D. W.

. 2015. Geographic Information System and Science. 4th ed. Chichester, UK: John Wiley.

69.

Marianov

Serra

. 1998. “Probabilistic, Maximal Covering Location-allocation Models for Congested Systems.” Journal of Regional Science 38:401–24.

70.

Matisziw

T. C.

Murray

A. T.

. 2009. “Area Coverage Maximization in Service Facility Siting.” Journal of Geographical Systems 11:175–89.

71.

Matisziw

T. C.

Murray

A. T.

Kim

. 2006. “Strategic Route Extension in Transit Networks.” European Journal of Operational Research 171:661–73.

72.

Mehrez

Stulman

. 1982. “The Maximal Covering Location Problem with Facility Placement on the Entire Plane.” Journal of Regional Science 22:361–65.

73.

Murray

A. T.

2005. “Geography in Coverage Modeling: Exploiting Spatial Structure to Address Complementary Partial Service of Areas.” Annals of the Association of American Geographers 95:761–72.

74.

Murray

A. T.

2010. “Advances in Location Modeling: GIS Linkages and Contributions.” Journal of Geographical Systems 12:335–54.

75.

Murray

A. T.

Church

R. L.

. 1996. “Applying Simulated Annealing to Location-planning Models.” Journal of Heuristics 2:31–53.

76.

Murray

A. T.

Matisziw

T. C.

Wei

Tong

. 2008. “A Geocomputational Heuristic for Coverage Maximization in Service Facility Siting.” Transactions in GIS 12:757–73.

77.

Murray

A. T.

Tong

. 2007. “Coverage Optimization in Continuous Space Facility Siting.” International Journal of Geographical Information Science 21:757–76.

78.

Murray

A. T.

Tong

Grubesic

T. H.

. 2012. “Spatial Optimization: Expanding Emergency Services to Address Regional Growth and Development.” In Studies in Applied Geography and Spatial Analysis, edited by Stimson

Haynes

, 109–22. Camberley, UK: Edward Elgar.

79.

O’Hanley

J. R.

Church

R. L.

. 2011. “Designing Robust Coverage Networks to Hedge against Worst-case Facility Losses.” European Journal of Operational Research 209:23–36.

80.

Osleeb

McLafferty

. 1992. “A Weighted Maximal Covering Model to Aid in UNICEF’S Dracunculiasis (Guinea Worm) Eradication Effort.” Papers in Regional Science 71:243–57.

81.

Owen

S. H.

Daskin

M. S.

. 1998. “Strategic Facility Location: A Review.” European Journal of Operational Research 111:423–47.

82.

Oztekin

Pajouh

F. M.

Swim

L. K.

. 2010. “An RFID Network Design Methodology for Asset Tracking in Healthcare.” Decision Support Systems 49:100–9.

83.

Pastor

J. T.

1994. “Bicriterion Programs and Managerial Location Decisions: Application to the Banking Sector.” Journal of the Operational Research Society 45:1351–62.

84.

Pereira

M. A.

Lorena

L. A. N.

Senne

E. L. F.

. 2007. “A Column Generation Approach for the Maximal Covering Location Problem.” International Transactions in Operational Research 14:349–64.

85.

Pirkul

Schilling

. 1989. “The Capacitated Maximal Covering Location Problem with Backup Service.” Annals of Operations Research 18:141–54.

86.

Pirkul

Schilling

D. A.

. 1991. “The Maximal Covering Location Problem with Capacities on Total Workload.” Management Science 37:233–48.

87.

Ratick

Osleeb

. 2016. “The Maximal Cover Location Model with Hedging Siting Facilities under Uncertainty, a Lead Poisoning Screening Network for the Dominican Republic.” International Regional Science Review 39:77–107.

88.

Resende

1998. Computing Approximate Solutions of the Maximum Covering Problem with GRASP.” Journal of Heuristics 4:161–77.

89.

ReVelle

Scholssberg

Williams

. 2008. “Solving the Maximal Covering Location Problem with Heuristic Concentration.” Computers & Operations Research 35:427–35.

90.

Roberts

D. A.

Gardner

Church

Ustin

Scheer

Green

R. O.

. 1998. “Mapping Chaparral in the Santa Monica Mountains Using Multiple Endmember Spectral Mixture Models.” Remote Sensing of Environment 65:267–79.

91.

Rose

Bennett

D. W.

Evans

A. T.

. 1992. “Locating and Sizing Road Maintenance Depots.” European Journal of Operational Research 63:151–63.

92.

Schilling

D. A.

Jayaraman

Barkhi

. 1993. “A Review of Covering Problem in Facility Location.” Location Science 1:25–55.

93.

Schilling

D. A.

Revelle

Cohon

Elzinga

D. J.

. 1980. “Some Models for Fire Protection Locational Decisions.” European Journal of Operational Research 5:1–7.

94.

Snyder

S. A.

Haight

R. G.

. 2016. “Application of the Maximal Covering Location Problem to Habitat Reserve Site Selection a Review.” International Regional Science Review 39:28–47.

95.

Sweeney

D. J.

Mairose

R. L.

Martin

R. K.

. 1979. “Strategic Planning in Bank Location.” Proceedings of the 1979 American Institute for Decision Sciences Conference 2:74–6.

96.

Tong

Church

R. L.

. 2012. “Aggregation in Continuous Space Coverage Modeling.” International Journal of Geographical Information Science 26:795–816.

97.

Tong

Murray

A. T.

. 2009. “Maximising Coverage of Spatial Demand for Service*.” Papers in Regional Science 88:85–97.

98.

Tong

Murray

Xiao

. 2009. “Heuristics in Spatial Analysis: A Genetic Algorithm for Coverage Maximization.” Annals of the Association of American Geographers 99:698–711.

99.

Tutschku

1998. “Demand-based Radio Network Planning of Cellular Mobile Communication Systems.” In INFOCOM’98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, Vol. 3, 1054–61. IEEE.

100.

Watson-Gandy

C. D. T.

1982. “Heuristic Procedures for the M-partial Cover Problem on a Plane.” European Journal of Operational Research 11:149–57.

101.

Wei

2016. “Coverage Location Models Alternatives, Approximation, and Uncertainty.” International Regional Science Review 39:48–76.

102.

Wei

Murray

A. T.

. 2014. “Evaluating Polygon Overlay to Support Spatial Optimization Coverage Modeling.” Geographical Analysis 46:209–29.

103.

Wei

Murray

A. T.

. 2015. “Continuous Space Maximal Coverage: Insights, Advances and Challenges.” Computers & Operations Research 62:325–36.

104.

Murray

A. T.

. 2005. “Optimizing Public Transit Quality and System Access: The Multiple-route, Maximal Covering/Shortest-path Problem.” Environment and Planning B: Planning and Design 32:163–78.

105.

Yin

. 2015. “An Empirical Comparison of Spatial Demand Representations in Maximal Coverage Modeling.” Environment and Planning B: Planning and Design. doi:10.1068/b130004p.

106.

Zarandi

M. H. F.

Davari

Sisakht

S. A. H.

. 2013. “The Large-scale Dynamic Maximal Covering Location Problem.” Mathematical and Computer Modelling 57:710–19.