Skip to main content

2018 | Buch

Location Covering Models

History, Applications and Advancements

insite
SUCHEN

Über dieses Buch

This book provides a thoughtful and rigorous guide to coverage modeling, reviewing essential models, solution approaches, and related applications. Since the early developments of the Location Set Covering Problem and the Maximal Covering Location Problem, models based upon some form of coverage have been extended and applied in a number of areas, helping to improve services offered to citizens of large cities and regions. Examples include trauma care services, transit systems design, cell tower location, and many others. The book not only describes the strengths and weaknesses of currently available models, but also presents details on major developments, including solution procedures and applications, making it well suited both as a reference text and a textbook for graduate level courses.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Location Modeling and Covering Metrics
Abstract
The field of location science is firmly rooted in several substantive developments, including the ground-breaking work of von Thunen (1826), Launhardt (1872), Weber (1909), Hotelling (1929), Hoover (1948, 1967), Christaller (1933), Lösch (1954), Weiszfeld (1937), Isard (1956), Moses (1958), Cooper (1963, 1964), Manne (1964), Hakimi (1964, 1965), Buffa et al. (1964) and Toregas et al. (1971). These authors may be considered founding fathers of location science, and they dealt with problems involving the competitive uses of land and land allocation, the location of industrial and communication facilities, the spatial arrangement of retail centers across a landscape, the location of competitors and competition through pricing, the layout of factory space, and the early use of computers in structuring and solving location problems. Since these early contributions, the field has expanded into new areas of application, new theoretical models, specialized solution approaches, and conceptual/technical forms of modeling location decisions and representing the spatial domain within Geographical Information Systems (GIS). Finally, as the field of location science has matured so too have the applications in both the public and private sectors.
Richard L. Church, Alan Murray
Chapter 2. Classic Beginnings
Abstract
The central theme of this book is the ability to identify the best location of one or more facilities or objects in order to provide some type or level of coverage. For example, let us suppose that we wish to place guards in an art gallery in such a manner that all areas of the gallery are within sight of one or more guards. In essence, we want the set of guard positions to “cover” or view the entire public area of the gallery. There can, of course, be many different configurations in which guards can view the entire gallery; however, it is of practical necessity to seek a pattern that deploys the fewest number of guards. As a second example, consider the case where we desire to provide fire protection to all neighborhoods of a city. In order to respond to a fire in a timely manner, we may set a standard that each neighborhood of the city should be no more than a mile and a half away from their nearest fire station (where fire trucks and crews can be housed to quickly respond when called). The fire service deployment problem can then be defined as finding the fewest fire stations (and their locations) so that each neighborhood is served or covered within a mile and a half of a station. Both the gallery guard positioning problem and the fire station location problem are examples of the Location Set Covering Problem, one of many covering problems that will be addressed in this book.
Richard L. Church, Alan Murray
Chapter 3. Extended Forms of Coverage
Abstract
Industrial and public sector planning is often complex. Example contexts include making a city safer or designing a manufacturing supply chain. Models can assist in the design of such systems by tracking the major components and generating top performing solutions. Some of the best planning models are simple, easy to understand, and easily applied and solved. At a minimum, a model must capture the main essence of the problem. Two examples of such planning models are the LSCP (location set covering problem) and MCLP (maximal covering location problem) described in Chap. 2. Because they are so simple and powerful as planning models, they have been used in many different ways, from biological reserve design (Underhill 1994) to advertising (Dwyer and Evans 1981) to prosthetic teeth coloring (Cocking et al. 2009) to health clinic location (Bennett et al. 1982). There are, however, a number of elements and conditions that are not captured exactly using these two basic constructs of complete coverage or maximal coverage. Because of this, researchers have proposed a wide variety of extended model forms to better reflect specific elements of a given problem. In this chapter we present some of the work, including multi-service, hierarchical, and multi-factor issues, in coverage modeling.
Richard L. Church, Alan Murray
Chapter 4. Probabilistic Coverage
Abstract
Much of the book is focused on facilities of various types, represented as points, nodes, lines, arcs, paths, tours, areas, etc., providing a wide range of services. The underlying assumption has generally been that facilities, or personnel at/from the facility, are available to serve when needed. This is not too surprising because a sizable number of location covering models are firmly rooted in the initial work Toregas and ReVelle (1972) on the location set covering problem (LSCP), where they were specifically interested in public sector issues involving equity of access to service. In the LSCP facilities were viewed as available for service when needed. In particular, the application of the LSCP to site emergency services, like fire, ambulance and police response, helped to design and relocate such services so that they provide coverage to all. Little has changed, in fact, over the intervening years as emergency service contexts remain of great interest and coverage models have time and again been instrumental in helping to both understand existing service systems as well as develop management plans for emergency response while promoting fairness and equity in service access. Of course, there are many other areas of application for coverage models as well, but the emergency response context has continued to be both challenging and interesting as we better understand such systems and have better supporting data. The focus of this chapter involves the fact that facilities (or personnel) may not always be available when needed. That is, there is a non-zero probability that facility service coverage may not be provided even when every demand is within a desired maximal service standard of a facility. There are clearly many ways in which a facility would be unavailable for service. One situation is that personnel are already busy serving another demand. This is depicted in Fig. 4.1, where the fire engine has traveled from the fire station in response to a fire. However, while busy fighting this fire, another incident (vehicle crash and fire) has occurred across town). It is therefore not possible for a fire crew to respond immediately. Another situation is that a facility may be unavailable due to a failure of some sort, such as equipment being broken, a power outage, a flood, or even an accident.
Richard L. Church, Alan Murray
Chapter 5. Anti-cover
Abstract
The anti-covering location problem (ACLP) is a well-recognized coverage-based dispersion model. Admittedly, reaching this conclusion requires a little work, but in fact this problem is related to the node packing, vertex packing, stable/independent set and r-separation problems, with considerable attention being devoted to each of these related problems (see Padberg 1973; Erkut 1990; Nemhauser and Sigismondi 1992; Murray 1995; Erkut et al. 1996; Murray and Kim 2008; Niblett 2014; Niblett and Church 2015). The name anti-cover can be attributed to Moon and Chaudhry (1984) who attempted to distinguish it from other well-known coverage problems. The name, therefore, reflects a sort of opposing goal compared to the set covering problem. The anti-covering location problem seeks to maximize the total weighted benefit of facilities sited in a region, doing so in a manner that ensures at least a minimum pre-specified distance or travel time between facilities and demand is maintained. If the benefit is the same for each potential facility location, then this is equivalent to maximizing the number of facilities that can be sited while maintaining minimum separation restrictions between all facilities and demand or between a sited facility and all other sited facilities. Of course, the goal of the location set covering problem detailed in Chap. 2 is to minimize the number of facilities needed for complete coverage of all demand, assuming the costs for selecting facilities is the same for every potential site. In this sense, then, the two problems have contrasting intents.
Richard L. Church, Alan Murray
Chapter 6. Weighted Benefit, Variable Radius, and Gradual Coverage
Abstract
The previous chapters have primarily focused on application contexts and modeling approaches where predefined, discrete coverage metrics are appropriate. Examples of this include: a fire department adequately serves/covers those properties that are within 5 min of travel from a station, or a surveillance system monitors/covers the areas that can be viewed by one or more cameras. That is, coverage is defined as being achieved or not, a simple binary yes or no property. The fact that coverage is defined as being provided or not to an area or object conceived of as a demand for service makes many coverage problems relatively simple to construct, especially for problems that are discrete in nature. When both demand objects and potential facility sites are discrete locations and finite in number, it is possible to identify which sites are capable of covering specific demand objects. An important question, however, is whether coverage should be so crisply defined. For example, when demand for service requires five and a half minutes to respond to from the closest fire station, it may not be considered covered according to a desired 5 min service time standard. In reality, demand for service along these lines obviously receives some level of degraded response service, but just not complete coverage characteristics associated with an established service standard. This chapter therefore explores how coverage models have been extended to be more flexible by including multiple levels of coverage, or steps of coverage, as well as defining a range where coverage is gradually degraded or lost. The idea that service/coverage is degraded, lost or not provided is itself of potential concern, and raises issues of equity. Essentially, in a public setting, we should be concerned with treating those demands that are not covered as fairly as possible. How do we identify a facility configuration (solution) that is as equitable as possible? This too is a subject of this chapter. Finally, there are cases when the coverage capabilities at a given location can be a function of investment. That is, we might be able to expand what a facility can cover by enhancing or upgrading associated equipment. For example, a viewshed (or coverage range) of a fire lookout tower might be extended by increasing its height. An emergency broadcast tower, as another example, might be outfitted with a superior transmitter providing a stronger signal, thereby increasing its range of reception. Such enhancements or upgrades likely are more costly, but do represent ways service capabilities may be altered. This chapter also addresses modeling where there may be options for increasing the coverage range of a facility along with making location siting decisions.
Richard L. Church, Alan Murray
Chapter 7. Capture, Capacities, and Thresholds
Abstract
There can be a number of different problem settings under which covering models can be defined and applied. Many of the models that are discussed in this chapter were originally inspired by issues associated with retail and competition. Although one at first blush may think of retail siting and coverage models as having little in common, except for something obvious like a pizza chain attempting to locate facilities so that it can deliver pizzas everywhere in a city within 30 min, there are surprisingly many retail elements that can be defined and addressed using coverage constructs.
Richard L. Church, Alan Murray
Chapter 8. Continuous Space Coverage
Abstract
An important distinction in location analysis and modeling has long been discrete versus continuous approaches. In previous chapters, for the most part, the reviewed coverage problems have been discrete in the sense that the places at which a facility may be sited are known and finite in number, and the demand locations to be served are also known and finite. This has enabled discrete integer programming formulations of models to be developed, allowing for efficient and exact solution in many cases. In some circumstances, however, neither potential facility sites nor demand locations are necessarily known and finite. Thus, one aspect of a continuous space location model is that facilities may be sited anywhere. An example is depicted in Fig. 8.1 where all locations within the region are feasible. The implication is that there are an infinite number of potential facility locations to be considered, in contrast to an assumed finite set of potential locations in discrete approaches (see Chap. 2). Another aspect of a continuous space problem is that demand too is not limited to a finite set of locations. Rather, demand is assumed to be continuously distributed across geographic space, varying over a study area. One example of this is shown in Fig. 8.2, where the height of the surface reflects demand for service. As is evident in the figure, some level of demand can be observed everywhere and this varies across space. Another example is given in Fig. 8.3. The Census unit color reflects the amount of demand in each area. Within a unit the demand varies in some manner, but given limited knowledge, a small geographic area and relative homogeneity, it is often thought that demand is uniformly distributed in the unit. Thus, Fig. 8.3 reflects discontinuities in demand variability, but it remains varying across space. Irrespective of representation, the implication is that demand for service is everywhere, and in some cases can possibly be defined/described by a mathematical function. From a practical standpoint, the study area could be a demand region, collection of areal units, set of line segments, or any group of spatial objects. This clearly makes dealing with demand and its geographic variability particularly challenging, especially when compared to a discrete representation view based on points. This contrasting view can be observed in Fig. 8.4 as centroids for each Census unit are identified, and demand is assumed to occur at these precise points in traditional modeling approaches.
Richard L. Church, Alan Murray
Chapter 9. Disruption, Protection, and Resilience
Abstract
A number of location covering models have been developed to address problems of security and safety. Bell et al. (2011) applies the LSCP to identify aircraft alert sites to respond to security threats to the U.S. border and other key assets. Bao et al. (2015) dealt with the problem of locating watchtower locations for forest fire detection and monitoring. Zhang and Du (2012) describe an approach to locate a set of radars, and assign power levels to each of them so that all crucial points along a river are monitored, or covered, while minimizing the total power being used. Other interesting examples can be found in Agnetis et al. (2009), Bar-Noy et al. (2013), and Pan (2010). Addressed is the location of a set of facilities that can guard, protect or respond in an emergency, developed under the assumption that system components are always available and ready to act. In addition, it is almost always assumed that the network infrastructure will always be usable and that services such as emergency response can be made using the best routes on an unimpeded network. That is, the system always works and there are no disruptions to service.
Richard L. Church, Alan Murray
Chapter 10. Coverage of Network-Based Structures: Paths, Tours and Trees
Abstract
Generally speaking, location analysis and modeling is often characterized as a network based problem. Classic location books have reinforced this characterization, such as that by Handler and Mirchandani (1979) titled Location on Networks and that of Daskin (1995) titled Network and Discrete Location, as well as many other books and papers (the seminal work of Hakimi 1965, likely influenced this too). In fact, location modeling tools in ArcGIS, as an example, are part of the Network Analyst toolbox and strictly require an underlying network in order to structure and solve associated location (coverage) models. However, as reflected in the much of this book, there is no inherent need or assumption that location decision making be restricted to a network, even if attribute data is derived from a corresponding network. This chapter deviates from much of the book in this respect, and assumes the underlying representation of an analysis region, including demand and potential facility locations, is based on a network. Most network location problems involve the positioning of one or more facilities at nodes or along arcs in order to optimize a level of service or access. Often, however, site selection is restricted to the nodes of the network. In the early 1980s Morgan and Slater (1980), Current (1981), and Slater (1982) broke new ground within location science when they independently suggested that facilities may be represented by some type of network structure. Examples include a path, a tree, a tour, or even the network itself. Slater (1982) suggested that facilities “… can be of an extended nature, rather than occupying a single point of a network.” They suggested, for example, that facilities may be modeled as network paths representing railroad lines, pipelines, or transit routes. Slater (1982) proposed that four classes of locational problems should be considered within the context of network location: point-serves-point, point-serves-structure, structure-serves-point, and structure-serves-structure (see also Slater 1981, 1983). In this chapter we address the problem of designing a structure to serve points. One of the first examples in the literature is that of Morgan and Slater (1980) who defined the “core” of a tree network as the shortest path connecting two endpoints of the tree, minimizing the sum of distances to all other nodes of the tree.
Richard L. Church, Alan Murray
Chapter 11. Grand Challenges
Abstract
The main objective in writing this text was to describe many of the developments in location science that have been proposed, modeled, and applied using a covering framework. Covering models are based upon the use of some standard of service, ranging from a maximal response time standard in locating ambulances to a minimal decibel standard used in placing warning sirens. Many covering problems can broadly be classified into two types: (1) cover each and every demand using the smallest number of facilities, the Location Set Covering Problem (LSCP); or (2) maximize the demand that is covered while locating a fixed number of facilities, the Maximal Covering Location Problem (MCLP). These two problems and related models emerged in the early 1970s and have formed the basis for a considerable portion of this book. Applications have involved the location of surveillance cameras, cell phone towers, fire stations, health clinics, ambulances, and sirens, just to name a few. They have even included the selection of biological reserve sites, designing teeth color shades, and laying out fabric cutting patterns. Altogether, the location science literature reflects a rich history and long term development of covering models, involving the fields of geography, engineering, business, computer science, health planning, environmental science, conservation biology, regional science and economics, and urban planning.
Richard L. Church, Alan Murray
Backmatter
Metadaten
Titel
Location Covering Models
verfasst von
Prof. Richard L. Church
Prof. Alan Murray
Copyright-Jahr
2018
Electronic ISBN
978-3-319-99846-6
Print ISBN
978-3-319-99845-9
DOI
https://doi.org/10.1007/978-3-319-99846-6