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.     

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.     

Aggregation Decomposition and Aggregation Guidelines for a Class of Minimax and Covering Location Models

Facility location problems often involve movement between facilities to be located and customers/demand points, with distances between the two being important. For problems with many customers, demand point aggregation may be needed to obtain a computationally tractable model. Aggregation causes error, which should be kept small. We consider a class of minimax location models for which the aggregation may be viewed as a second‐order location problem, and use error bounds as aggregation error measures. We provide easily computed approximate “square root” formulas to assist in the aggregation process. The formulas establish that the law of diminishing returns applies when doing aggregation. Our approach can also facilitate aggregation decomposition for location problems involving multiple “separate” communities.     

The Majority Theorem for the Single (p = 1) Median Problem and Local Spatial Autocorrelation

Except for about a half dozen papers, virtually all (co)authored by Griffith, the existing literature lacks much content about the interface between spatial optimization, a popular form of geographic analysis, and spatial autocorrelation, a fundamental property of georeferenced data. The popular p-median location-allocation problem highlights this situation: the empirical geographic distribution of demand virtually always exhibits positive spatial autocorrelation. This property of geospatial data offers additional overlooked information for solving such spatial optimization problems when it actually relates to their solutions. With a proof-of-concept outlook, this paper articulates connections between the well-known Majority Theorem of the 1-median minisum problem and local indices of spatial autocorrelation; the LISA statistics appear to be the more useful of these later statistics because they better embrace negative spatial autocorrelation. The relationship articulation outlined here results in the positing of a new proposition labeled the egalitarian theorem.     

A Synthesis of Aggregation Methods for Multifacility Location Problems: Strategies for Containing Error

When solving a location problem using aggregated units to represent demand, it is well known that the process of aggregation introduces error. Research has focussed on individual components of error, with little work on identifying and controlling total error. We provide a focussed review of some of this literature and suggest a strategy for controlling total error. Consideration of alternative criteria for evaluating aggregation schemes shows that the method selected should be compatible with the objectives of the analyses in which it is used. Experiments are described that show that two different measures of error are related in a nonlinear way to the number of aggregate demand points (q), for any value of the number of facilities (p). We focus on the parameter q/p and show that it is critical for determining the expected severity of the error. Many practical implementations of location algorithms operate within the range of q/p where the rate of change of error with respect to q/p is highest.     

CENTER POINTS, EQUILIBRIUM POSITIONS, AND THE OBNOXIOUS LOCATION PROBLEM

ABSTRACT. Real variable analysis has een used to great benefit in a variety of classical problems in location theory. In this paper we explore basic complex variable techniques in one formulation of the obnoxious location problem. A general definition of center points is first given and used to formulate several alternate versions of the obnoxious location problem. A logarithmic transformation is then used to demonstrate some equivalences between these families of distinct location problems (defined via center points). A prototype logarithmic potential function which results from this formulation is then investigated, and it is demonstrated that the extremal solutions with this objective reside on the boundary of its domain of definition. An application using zero- and one-dimensional centers is discussed, and a generalization to the spatial obnoxious problem is also briefly examined. We define a zero-dimensional center as a critical point of the logarithmic potential function, and it is shown that these centers are equivalent to the solutions of the Complex Moment Problem.     

COMPETITIVE LOCATION UNDER UNCERTAINTY OF COSTS

ABSTRACT. In this paper, we study the centroid problem from competitive location theory for a linear market with uniform demand, assuming that the leader has imperfect information about the follower's fixed and marginal costs. It is shown that the general version of this problem can be formulated as a nonlinear programming problem and the exact solution can be obtained analytically in a special case. A simple strategy is also given for the general problem, and it is proven that this strategy has a guaranteed error bound. It is demonstrated that uncertainty of costs might lead to market failure in the centroid problem, but this disappears if the game is repeated and the firms learn from observing each other's moves. It is also shown that it is possible for the leader to obtain optimal expected profit at a low perceived risk, with only sufficient, and not necessarily perfect, information. These two observations lead to our primary conclusion from the study that although cost uncertainty is a realistic feature of most competitive location models, there are very effective ways of dealing with it.     

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.     

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.     

The Effect on Attribute Prediction of Location Uncertainty in Spatial Data

A datum is considered spatial if it contains location information. Typically, there is also attribute information, whose distribution depends on its location. Thus, error in location information can lead to error in attribute information, which is reflected ultimately in the inference drawn from the data. We propose a statistical model for incorporating location error into spatial data analysis. We investigate the effect of location error on the spatial lag, the covariance function, and optimal spatial linear prediction (that is, kriging). We show that the form of kriging after adjusting for location error is the same as that of kriging without adjusting for location error. However, location error changes entries in the matrix of explanatory variables, the matrix of co‐variances between the sample sites, and the vector of covariances between the sample sites and the prediction location. We investigate, through simulation, the effect that varying trend, measurement error, location error, range of spatial dependence, sample size, and prediction location have on kriging after and without adjusting for location error. When the location error is large, kriging after adjusting for location error performs markedly better than kriging without adjusting for location error, in terms of both the prediction bias and the mean squared prediction error.     

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.     

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.     

Adaptive Cell Tower Location Using Geostatistics. 基于地统计学的适应性基站发射塔选址研究

In this article, we address the problem of allocating an additional cell tower (or a set of towers) to an existing cellular network, maximizing the call completion probability. Our approach is derived from the adaptive spatial sampling problem using kriging, capitalizing on spatial correlation between cell phone signal strength data points and accounting for terrain morphology. Cell phone demand is reflected by population counts in the form of weights. The objective function, which is the weighted call completion probability, is highly nonlinear and complex (nondifferentiable and discontinuous). Sequential and simultaneous discrete optimization techniques are presented, and heuristics such as simulated annealing and Nelder–Mead are suggested to solve our problem. The adaptive spatial sampling problem is defined and related to the additional facility location problem. The approach is illustrated using data on cell phone call completion probability in a rural region of Erie County in western New York, and accounts for terrain variation using a line‐of‐sight approach. Finally, the computational results of sequential and simultaneous approaches are compared. Our model is also applicable to other facility location problems that aim to minimize the uncertainty associated with a customer visiting a new facility that has been added to an existing set of facilities.     

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.     

An Evolutionary Algorithm for Site Search Problems

The goal of solving a site search problem is to allocate a contiguous set of land parcels such that the total land acquisition cost, or other objectives, are optimized. This article describes the design and implementation of an evolutionary algorithm (EA) that can be used to solve site search problems. In this article, a graph representation is used to define the spatial structure of solutions to the problem. By using this representation, the contiguity of a site is maintained during the initialization, mutation, and local search operations of the EA. The effectiveness of the EA in finding optimal or near-optimal solutions is demonstrated by testing it on a series of problems whose optimal solutions are known.     

A SIMPLIFICATION AND GENERALIZATION OF THE EXCLUSION THEOREM: A TECHNICAL NOTE

Several researchers have proven that for the integrated production-location problem on the Weberian triangle, intermediate points on the edge of the triangle can never be optimal locations. Authors of previous proofs of this result have used cumbersome trigonometric arguments. We present a much simpler algebraic proof of the result, and present it in terms of the more general n -input model, where the feasible location space is a convex polygon rather than a triangle. In addition, the result generalizes immediately to other cases, such as (1) multifacility production-location problems, (2) stochastic versions of one-facility and multifacility production-location problems, and (3) comparable pure location problems (e.g., the Weber problem).     

AUTOMATIC MINIMIZATION OF THE RIGIDITY ECCENTRICITY OF 3D REINFORCED CONCRETE BUILDINGS

The objective of this paper is to obtain the optimum design of 3D reinforced concrete buildings in terms of their performance under earthquake loading. This goal is achieved by considering the minimisation of the eccentricity between the mass centre and the rigidity centre of each storey layout as the optimisation objective in order to produce torsionally balanced structures. This problem is considered as a combined topology and sizing optimisation problem. The location and the size of the columns and the shear walls of the structure of each storey layout constitute the design variables. Apart from the constraints imposed by the seismic and reinforced concrete structure design codes, architectural restrictions are also taken into account. The test examples showed that a reduction in the structural cost of the building is achieved by minimising the eccentricity between the mass centre and the rigidity centre of each storey layout. Evolutionary optimisation algorithms and in particular a specially tailored algorithm based on Evolution Strategies is implemented for the solution of this type of structural optimisation problems.     

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 Cortland Conference on Political History

Abstract. The 1851 Census of Religious Worship contains an excess of "round" numbers reported for congregation sizes, which indicates that estimates (as opposed to exact head counts) were often returned. The authors estimate the proportion of rounded estimates returned by the Church of England and the dissenting denominations. They develop a structural equation model to estimate for the mean degree of inflation (i. e., overstimation) that resulted from rounding. Anglican figures were most likely inflated by approximately 11 percent, whereas the corresponding figure for dissent was approximately 5.5 percent. The authors examine what sort of counting behavior could have led to such margins of inflation, and why denominational differences exist.     

Assessing the Cluster Correspondence between Paired Point Locations

Some complex geographic events are associated with multiple point locations. Such events include, but are not limited to, those describing linkages between and among places. The term multi‐location event is used in the paper to refer to these geographical phenomena. Through formalization of the multi‐location event problem, this paper situates the analysis of multi‐location events within the broad context of point pattern analysis techniques. Two alternative approaches (Vector autocorrelation analysis and cluster correspondence analysis) to the spatial dependence of paired‐location events (i.e., two‐location events) are explored, with a discussion of their appropriateness to general multi‐location event problems. The research proposes a framework of cluster correspondence analysis for the detection of local non‐stationarities in the spatial process generating multi‐location events. A new algorithm for local analysis of cluster correspondence is proposed. It is implemented on a large‐scale dataset of vehicle theft and recovery location pairs in Buffalo, New York.