Two New Location Covering Problems: The Partial P-Center Problem and the Partial Set Covering Problem

Two new covering problems are introduced. The partial covering P-center problem minimizes a coverage distance in such a way that a given fraction of the population is covered. The partial set covering problem seeks the minimum number of facilities needed to cover an exogenously specified fraction of the population within a given coverage distance. The problems are formulated as integer linear programming problems. Bisection search algorithms are outlined for the two problems. The search algorithm repeatedly solves a Lagrangian relaxation of the maximal covering problem. Computational results for the Lagrangian relaxation of the maximal covering problem and for the bisection search algorithms are presented on problems with up to 150 nodes.     

The Maximal Covering Problem with Some Negative Weights

This article presents the maximal covering problem on a network when some of the weights can be negative. Integer programming formulations are proposed and tested with ILOG CPLEX. Heuristic algorithms, an ascent algorithm, and simulated annealing are proposed and tested. The simulated annealing approach provides the best results for a data set comprising 40 problems.     

Theoretical and Computational Links between the p-Median,Location Set-covering,and the Maximal Covering Location Problem

It has been shown that the p-median problem, the location set-covering and the maximal covering location problems are important facility location models. This paper gives a historical perspective of the development of these models and identifies the theoretical links between them. It is shown that the maximal covering location problem can be structured and solved as a p-median problem in addition to the several approaches already developed. Computational experience for several maximal covering location problems is given.     

A Covering Tour Model for Planning Mobile Health Care Facilities in SuhumDistrict, Ghama

The provision of adequate primary health care in developing countries is often troublesome. The problem is to provide a sufficient number of facilities to be geographically accessible, yet few enough to be properly stocked and staffed. In many less developed countries accessibility problems are exacerbated by extensive rainy seasons in which travel is only possible on paved roads. Using the covering tour model we investigate the use of mobile facilities to resolve this dilemma in Suhum District, Ghana. The model minimizes a mobile facility's travel while serving all population centers within range of a feasible stop. Computational results show that in the rainy season the model cannot provide full coverage; over six percent of the population is beyond a covering distance of eight kilometers. In the dry season, 99 percent of the population can be served by a tour at a covering distance of seven kilometers.Beyond a distance of four kilometers, the dry season problem becomes a trade-off between the distance traveled by healthcare patrons and mobile facilities. These results illustrate the importance of flexibility of mobile systems: if accessibility cannot be provided in all seasons it may still be provided at favorable times of the year.     

Analysis of Errors Due to Demand Data Aggregation in the Set Covering and Maximal Covering Location Problems

In this paper, we extend the concepts of demand data aggregation error to location problems involving coverage. These errors, which arise from losses in locational information, may lead to suboptimal location patterns. They are potentially more significant in covering problems than in p-median problems because the distance metric is binary in covering problems. We examine the Hillsman and Rhoda (1978) Source A, B, and C errors, identify their coverage counterparts, and relate them to the cost and optimality errors that may result. Three rules are then presented which, when applied during data aggregation, will reduce these errors. The third rule will, in fact, eliminate all loss of locational information, but may also limit the amount of aggregation possible. Results of computational tests on a large-scale problem are presented to demonstrate the performance of rule 3.     

On Covering Problems and the Central Facilities Location Problem

A number of variations of facilities location problems have appeared in the research literature in the past decade. Among these are problems involving the location of multiple new facilities in a discrete solution space, with the new facilities located relative to a set of existing facilities having known locations. In this paper a number of discrete solution space location problems are treated. Specifically, the covering problem and the central facilities location problem are shown to be related. The covering problem involves the location of the minimum number of new facilities among a finite number of sites such that all existing facilities (customers) are covered by at least one new facility. The central facilities location problem consists of the location of a given number of new facilities among a finite number of sites such that the sum of the weighted distances between existing facilities and new facilities is minimized. Computational experience in using the same heuristic solution procedure to solve both problems is provided and compared with other existing solution procedures.     

Probabilistic, Maximal Covering Location—Allocation Models forCongested Systems

When dealing with the design of service networks, such as health andemergency medical services, banking or distributed ticket-selling services, the location of servicecenters has a strong influence on the congestion at each of them, and, consequently, on thequality of service. In this paper, several probabilistic maximal coveringlocation—allocation models with constrained waiting time for queue length are presentedto consider service congestion. The first model considers the location of a given number ofsingle-server centers such that the maximum population is served within a standard distance, andnobody stands in line for longer than a given time or with more than a predetermined number ofother users. Several maximal coverage models are then formulated with one or more servers perservice center. A new heuristic is developed to solve the models and tested in a 30-node network.     

p‐Functional Clusters Location Problem for Detecting Spatial Clusters with Covering Approach

Regionalization or districting problems commonly require each individual spatial unit to participate exclusively in a single region or district. Although this assumption is appropriate for some regionalization problems, it is less realistic for delineating functional clusters, such as metropolitan areas and trade areas where a region does not necessarily have exclusive coverage with other regions. This paper develops a spatial optimization model for detecting functional spatial clusters, named the p‐functional clusters location problem (p‐FCLP), which has been developed based on the Covering Location Problem. By relaxing the complete and exhaustive assignment requirement, a functional cluster is delineated with the selective spatial units that have substantial spatial interaction. This model is demonstrated with applications for a functional regionalization problem using three journey‐to‐work flow datasets: (1) among the 46 counties in South Carolina, (2) the counties in the East North Central division of the US Census, and (3) all counties in the US. The computational efficiency of p‐FCLP is compared with other regionalization problems. The computational results show that detecting functional spatial clusters with contiguity constraints effectively solves problems with optimality in a mixed integer programming (MIP) approach, suggesting the ability to solve large instance applications of regionalization problems.     

Location Modeling Utilizing Maximum Service Distance Criteria

The location set-covering problem (LSCP) and the maximal covering location problem (MCLP) have been the subject of considerable interest. As originally defined, both problems allowed facility placement only at nodes. This paper deals with both problems for the case when facility placement is allowed anywhere on the network. Two theorems are presented that show that when facility placement is unrestricted, for either the LSCP or MCLP at least one optimal solution exists that is composed entirely of points belonging to a finite set of points called the network intersect point set (NIPS). Optimal solution approaches to the unrestricted site LSCP and MCLP problems that utilize the NIPS and previously developed solution methodologies are presented. Example solutions show that considerable improvement in the amount of coverage or the number of facilities needed to insure total coverage can be achieved by allowing facility placement along arcs of the network. In addition, extensions to the arc-covering model and the ambulance-hospital model of ReVelle, Toregas, and Falkson are developed and solved.     

THE MINIMAX-MIN LOCATION PROBLEM*

We consider a new objective function for the placement of a public facility with reference to variations in accessibility : the minimization of the range between the maximal and the minimal distances to users. Some properties of the solution are given; algorithms for the Euclidean and rectilinear distance cases are presented.     

Regional Coverage Maximization: Alternative Geographical Space Abstraction and Modeling

Analysis results are often found to vary with the way we abstract geographical space. When continuous geographic phenomena are abstracted, processed, and stored in a digital environment, some level of discretization is often employed. Information loss in a discretization process brings about uncertainty/error, and as a result research findings may be highly dependent on the particular discretization method used. This article examines one spatial problem concerning how to achieve the maximal regional coverage given a limited number of service facilities. Two widely used geographical space abstraction approaches are examined, the point‐based representation and the area‐based representation, and issues associated with each representation scheme are analyzed. To accommodate the limitations of the existing representation schemes, a mixed representation strategy is proposed along with a new maximal covering model. Experiments are conducted to site warning sirens in Dublin, Ohio. Results demonstrate the effectiveness of the mixed representation scheme in finding high‐quality solutions when the regional coverage level is medium or high.     

Multi‐Type,Multi‐Zone Facility Location

The placement of facilities according to spatial and/or geographic requirements is a popular problem within the domain of location science. Objectives that are typically considered in this class of problems include dispersion, median, center, and covering objectives—and are generally defined in terms of distance or service‐related criteria. With few exceptions, the existing models in the literature for these problems only accommodate one type of facility. Furthermore, the literature on these problems does not allow for the possibility of multiple placement zones within which facilities may be placed. Due to the unique placement requirements of different facility types—such as suitable terrain that may be considered for placement and specific placement objectives for each facility type—it is expected that different suitable placement zones for each facility type, or groups of facility types, may differ. In this article, we introduce a novel mathematical treatment for multi‐type, multi‐zone facility location problems. We derive multi‐type, multi‐zone extensions to the classical integer‐linear programming formulations involving dispersion, centering and maximal covering. The complexity of these formulations leads us to follow a heuristic solution approach, for which a novel multi‐type, multi‐zone variation of the non‐dominated sorting genetic algorithm‐II algorithm is proposed and employed to solve practical examples of multi‐type, multi‐zone facility location problems.     

Designing Reliable Center Systems: A Vector Assignment Center Location Problem

The p‐center problem is one of the most important models in location theory. Its objective is to place a fixed number of facilities so that the maximum service distance for all customers is as small as possible. This article develops a reliable p‐center problem that can account for system vulnerability and facility failure. A basic assumption is that located centers can fail with a given probability and a customer will fall back to the closest nonfailing center for service. The proposed model seeks to minimize the expected value of the maximum service distance for a service system. In addition, the proposed model is general and can be used to solve other fault‐tolerant center location problems such as the (p, q)‐center problem using appropriate assignment vectors. I present an integer programming formulation of the model and computational experiments, and then conclude with a summary of findings and point out possible future work.     

Computational Comparison of Five Maximal Covering Models for Locating Ambulances

This article categorizes existing maximum coverage optimization models for locating ambulances based on whether the models incorporate uncertainty about (1) ambulance availability and (2) response times. Data from Edmonton, Alberta, Canada are used to test five different models, using the approximate hypercube model to compare solution quality between models. The basic maximum covering model, which ignores these two sources of uncertainty, generates solutions that perform far worse than those generated by more sophisticated models. For a specified number of ambulances, a model that incorporates both sources of uncertainty generates a configuration that covers up to 26% more of the demand than the configuration produced by the basic model.     

Programming Models for Facility Dispersion: The p-Dispersion and Maxisum Dispersion Problems

The p-dispersion problem is to locate p facilities on a network so that the minimum separation distance between any pair of open facilities is maximized. This problem is applicable to facilities that pose a threat to each other and to systems of retail or service franchises. In both of these applications, facilities should be as far away from the closest other facility as possible. A mixed-integer program is formulated that relies on reversing the value of the 0–1 location variables in the distance constraints so that only the distance between pairs of open facilities constrain the maximization. A related problem, the maxisum dispersion problem, which aims to maximize the average separation distance between open facilities, is also formulated and solved. Computational results for both models for locating 5 and 10 facilities on a network of 25 nodes are presented, along with a multicriteria approach combining the dispersion and maxisum problems. The p -dispersion problem has a weak duality relationship with the (p-1)-center problem in that one-half the maximin distance in the p-dispersion problem is a lower bound for the minimax distance in the center problem for (p-1) facilities. Since the p-center problem is often solved via a series of set-covering problems, the p-dispersion problem may prove useful for finding a starting distance for the series of covering problems.     

Spatial Search for the Lowest Price

Search for low prices often requires that individuals make decisions not only about the optimal amount of search, but also about the optimal route to be taken through a set of known locations. In this paper, the fixed sample size strategy used in economic models of search is extended to account for the travel costs that are incurred as alternatives are examined. Analytical results for the optimal amount of search are given, and alternative routing algorithms for a modified version of the traveling-salesman problem are evaluated.     

A Simple Trade-off Model for Maximal and Multiple Coverage

A natural slack model, which allows for the trade-off of single coverage of demand for multiple coverage, is developed in this paper. Locational options structured within this multiobjective perspective extend from the most dispersed pattern possible (i.e., the maximal covering solution) to the most clustered (i.e., the multiple covering solution). It is believed that this extension of the location covering approach can better inform decision makers who must address questions of spatial and temporal access to services. A numerical example, demonstrating the use of the model and the identification of the noninferior set of siting choices, is suggested and solved.     

The Multi‐level Location Set Covering Model

The classical Location Set Covering Problem involves finding the smallest number of facilities and their locations so that each demand is covered by at least one facility. It was first introduced by Toregas in 1970. This problem can represent several different application settings including the location of emergency services and the selection of conservation sites. The Location Set Covering Problem can be formulated as a 0–1 integer‐programming model. Roth (1969) and Toregas and ReVelle (1973) developed reduction approaches that can systematically eliminate redundant columns and rows as well as identify essential sites. Such approaches can often reduce a problem to a size that is considerably smaller and easily solved by linear programming using branch and bound. Extensions to the Location Set Covering Model have been proposed so that additional levels of coverage are either encouraged or required. This paper focuses on one of the extended model forms called the Multi‐level Location Set Covering Model. The reduction rules of Roth and of Toregas and ReVelle violate properties found in the multi‐level model. This paper proposes a new set of reduction rules that can be used for the multi‐level model as well as the classic single‐level model. A demonstration of these new reduction rules is presented which indicates that such problems may be subject to significant reductions in both the numbers of demands as well as sites.     

On the Finite Optimality Set of the Vector Assignment p‐Median Problem

The vector assignment p‐median problem (VAPMP) is one of the first discrete location problems to account for the service of a demand by multiple facilities, and has been used to model a variety of location problems in addressing issues such as system vulnerability and reliability. Specifically, it involves the location of a fixed number of facilities when the assumption is that each demand point is served a certain fraction of the time by its closest facility, a certain fraction of the time by its second closest facility, and so on. The assignment vector represents the fraction of the time a facility of a given closeness order serves a specific demand point. Weaver and Church showed that when the fractions of assignment to closer facilities are greater than more distant facilities, an optimal all‐node solution always exists. However, the general form of the VAPMP does not have this property. Hooker and Garfinkel provided a counterexample of this property for the nonmonotonic VAPMP. However, they do not conjecture as to what a finite set may be in general. The question of whether there exists a finite set of locations that contains an optimal solution has remained open to conjecture. In this article, we prove that a finite optimality set for the VAPMP consisting of “equidistant points” does exist. We also show a stronger result when the underlying network is a tree graph.     

The Probabilistic Minisum Flow Interception Problem: Minimizing the Expected Travel Distance until Intercept under Probabilistic Interception

We develop a variant of the flow interception problem (FIP) in which it is more desirable for travelers to be intercepted as early as possible in their trips. In addition, we consider flows being intercepted probabilistically instead of the deterministic view of coverage assumed in the FIP literature. We call the proposed model the probabilistic minisum FIP (PMFIP); it involves minimizing the sum of the expected distance that each flow travels until intercepted at a facility among placed facilities. This extension allows us to evaluate the effect of facility location under any given value of the interception probability and to apply the model to a variety of situations. We apply the proposed model to an example network by assuming a hypothetical situation in which people gather at a stadium from various nodes on the network, and receive some goods or services on the way to the stadium. We analyze optimal solutions obtained by varying the number of facilities and interception probability. It is shown that the expected travel distance until intercept is greatly reduced by means of a few optimally located facilities under a moderate interception probability.