Elimination of Source A and B Errors in p-Median Location Problems

The p-median problem is a powerful tool in analyzing facility location options when the goal of the location scheme is to minimize the average distance that demand must traverse to reach its nearest facility. It may be used to determine the number of facilities to site, as well as the actual facility locations. Demand data are frequently aggregated in p-median location problems to reduce the computational complexity of the problem. Demand data aggregation, however, results in the loss of locational information. This loss may lead to suboptimal facility location configurations (optimality errors) and inaccurate measures of the resulting travel distances (cost errors). Hillsman and Rhoda (1978) have identified three error components: Source A, B, and C errors, which may result from demand data aggregation. In this article, a method to measure weighted travel distances in p-median problems which eliminates Source A and B errors is proposed. Test problem results indicate that the proposed measurement scheme yields solutions with lower optimality and cost errors than does the traditional distance measurement scheme.     

Reducing Errors in Rainfall Estimates through Rain Gauge Location

Facility location models are examined as a framework for generating rain gauge networks designed to reduce errors in mean areal precipitation (MAP) estimation. Errors in estimating MAP may be divided into two types: (i) capture error, not observing a storm which occurs in a gauged area, and (ii) extrapolation error, using a rain gauge measurement to represent a heterogeneous area. In this paper, five rain gauge location models are developed to minimize these errors. The models include adaptations of the maximal covering location problem, the p-median model, and three models derived from multicriteria cluster analysis. The models are tested using precipitation data from an experimental watershed maintained by the U.S. Department of Agriculture in Arizona. Analysis of the results reveals, for the particular watershed, that (1) in sparse networks, location of rain gauges can play a larger role than number of rain gauges in reducing errors in MAP estimates; (2) models based on mean hydrologic data provide nearly as good networks as models based on spatially correlated data; and (3) models yielding the best networks for estimating precipitation for flood predictions are different from the models providing the best precipitation estimates for low flow forecasts.     

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.     

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.     

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.     

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.     

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.     

Dynamic Models of Agricultural Location in a Spatial Interaction Framework

Recent research demonstrates that spatial interaction models may also be made to function as location models by the addition of appropriate hypotheses about structural adjustment. An appealing feature of the approach is that dynamics are explicitly incorporated. In this paper, the attempt is made to recast a problem from classical economic-geographic theory—that of agricultural location—within a spatial interaction framework. It is shown that a wide variety of models is potentially available, and the properties of a range of these models are selectively explored.     

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.     

Transportation Networks and the Location of Human Activities

The impact of transportation networks on the location of human activities is a surprisingly neglected topic in economic geography. Using the simple plant location problem, this paper investigates such an impact in the case of a few idealized networks. It is seen that a grid network tends to foster a dispersed pattern of activities, while the center of a radial network acts as an attractor. The case of two economies characterized by different network configurations that form a custom union is then analyzed. It is shown that the structural properties of the networks still hold, though some locations are pulled toward the common border. This suggests that no such relocation should be expected within the European Union if the state members endorse similar fiscal and social policies after the formation of the single market.     

Hub Location Problem with Allowed Routing between Nonhub Nodes

In this study, we relax one of the general assumptions in the hub location literature by allowing routed flows between nonhub nodes. In hub networks, different flows are consolidated and routed via collection, interhub, and distribution arcs. Due to consolidation, some flows travel long paths despite closeness of their origin and destination. In this study, we allow direct flows by penalizing by a scalar factor of original cost of transshipment between these arcs. We present mathematical models for median, center, and set covering versions of the problem for single‐ and multi‐allocation cases. We test the models with the CAB and TR data sets. We discuss the properties of established direct connections for different models by using another mathematical model where the number of direct flows is bounded and interpret the effect of changes in problem parameters.     

Extensions to the Hub Location Problem: Formulations and Numerical Examples

Although a tremendous amount of analytical research is being conducted on the hub location problem, few models exist that extend the number of characteristics found in actual hub-and-spoke networks. Four extensions are presented in this paper: (1) a capacitated network model; (2) a minimum threshold model; (3) a model that endogenously determines the number of open hubs for the network; and (4) a model that incorporates a flow-dependent cost function for the spokes as well as the interhub links. Both the capacitated and the minimum threshold models drop the assumption of a completely interconnected network commonly found in hub location models. Numerical results show that total network costs are often minimized by closing a few interhub links. The third extension is the first known hub location model to determine the optimal number of hubs based on the needs of the network. In this model, the number of open hubs depends on the distribution of flows in the network and how cost effectively the flows can be moved across the network. Previous models that endogenously determined the number of open hubs utilized a fixed cost for establishing each hub in order to limit the number of hubs in the network. The final extension recognizes the potential of all links to amalgamate flows and includes a separate flow-dependent cost function for the spokes in addition to the one for the interhub links. Numerical results are shown for all four models.     

The Regionally Constrained p-Median Problem

In many applications involving the location of public facilities, the activity that is being located is added to the landscape of existing public facilities and services. Further, there also exists a political and behavioral landscape of differing jurisdictions, representations, and perceptions. This paper presents a new form of the p-median problem which addresses two types of “regional” constraints that can arise in public facilities planning. A formulation is given for this specially constrained median problem along with a solution approach. Several examples are presented with computational results which indicate that this type of constrained problem could lead to better facilities planning.     

The Optimal Nodal Location of Public Facilities With Price-Sensitive Demand

The purpose of this paper is to present some models for the location of public facilities in nodal networks that explicitly maximize social welfare by accounting for price-elastic demand functions. The models presented here are general; yet they are mathematically equivalent to the plant location problem and are therefore amenable to solution procedures developed for the plant location problem. The models presented here distinguish between two institutional environments that reflect the degree of power of the consumer to choose which facility to patronize. If consumers can be assigned arbitrarily to facilities and can be denied service, then the environment is one of public fiat. If consumers must be served at the facility of their choice, then a “serve-allcomers” environment exists. Separate models for each environment are specified, and the relationship between optimal assignments and pricing policies is developed.     

Explorations and Syntheses of Linear Programming And Spatial Interaction Models of Residential Location

Various “linear programming” models of residential location are explored in some detail. It is then shown that entropy maximizing “sub-optimal” versions of these can be developed, which may be more realistic at typical levels of resolution used for analysis but can still be given some of the interpretations of the programming models. Further, any programming model can be seen as a limiting case of some entropy maximizing model in which some of the parameters tend to infinity. Some empirical tests of both kinds of models are presented, and the limiting relationships are discussed.     

A Model for Location of Capacitated Alternative-Fuel Stations

Increased interest in alternative fuels is attributable, in part, to rising oil prices and increasing concern about global warming. A lack of a refueling infrastructure, however, has inhibited the adoption of alternative-fuel vehicles. Little economic incentive exists to mass-produce alternative-fuel vehicles until a network of stations exists that can refuel a reasonable number of trips. The flow refueling location model (FRLM) was developed to minimize the investment necessary to create a refueling infrastructure by optimizing the location of fueling stations. The original uncapacitated FRLM assumes that the presence of a refueling station is sufficient to serve all flows passing through a node, regardless of their volume. This article introduces the capacitated flow refueling location model that limits the number of vehicles refueled at each station. It also introduces a modified objective function maximizing vehicle-miles traveled instead of trips, applies both models to an intercity network for Arizona, and formulates several other extensions.     

Multiple Facilities Location in the Plane Using the Gravity Model

Two problems are considered in this article. Both problems seek the location of p facilities. The first problem is the p median where the total distance traveled by customers is minimized. The second problem focuses on equalizing demand across facilities by minimizing the variance of total demand attracted to each facility. These models are unique in that the gravity rule is used for the allocation of demand among facilities rather than assuming that each customer selects the closest facility. In addition, we also consider a multiobjective approach, which combines the two objectives. We propose heuristic solution procedures for the problem in the plane. Extensive computational results are presented.     

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.     

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.     

Location and Pricing Decisions of a MultiStore Monopoly in a Spatial Market

Abstract.  This article presents an analysis of location and pricing decisions of a monopolist about to open several stores in a compact geographical space. The number of stores is made endogenous by the introduction of fixed costs. A novel methodology is developed, by which the firm's location and price decisions are represented as continuous functions defined over the geographical space. This modeling artifact generates a negligible error but simplifies the solution considerably and allows the derivation of several intuitive results. Although the focus is on one‐dimensional markets, it is shown that the method can easily be adapted to two‐dimensional markets.