Order Distance in Regular Point Patterns

This article examines the k th nearest neighbor distance for three regular point patterns: square, triangular, and hexagonal lattices. The probability density functions of the k th nearest distance and the average k th nearest distances are theoretically derived for k =1, 2, …, 7. As an application of the k th nearest distance, we consider a facility location problem with closing of facilities. The problem is to find the optimal regular pattern that minimizes the average distance to the nearest open facility. Assuming that facilities are closed independently and at random, we show that the triangular lattice is optimal if at least 68% of facilities are open by comparing the upper and lower bounds of the average distances.     

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.     

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.     

Bi‐objective Model for Optimal Number and Size of Circular Facilities

This article presents a bi‐objective model for determining the number and size of finite size facilities. The objectives are to minimize both the average closest distance to facilities and the probability that a random line intersects facilities. The former represents the accessibility of customers, whereas the latter represents the interference to travelers. The average closest distance and the probability of intersecting facilities are derived for circular facilities randomly distributed in a circular city. The analytical expressions for the average closest distance and the probability of intersecting facilities demonstrate how the number and size of facilities affect the accessibility of customers and the interference to travelers. The model focuses on the tradeoff between the accessibility and interference, and the tradeoff curve provides planners with alternatives for the number and size of facilities.     

Determining Market Areas Captured by Competitive Facilities: A Continuous Equilibrium Modeling Approach

Many existing models concerning locations and market areas of competitive facilities assume that customers patronize a facility based on distance to that facility, or perhaps on a function of distances between the customer and the different facilities available. Customers are generally assumed to be located at certain discrete demand points in a two-dimensional space, or continuously distributed over a one-dimensional line segment. In this paper these assumptions are relaxed by employment of a continuum optimization model to characterize the equilibrium choice behavior of customers for a given set of competitive facilities over a heterogeneous two-dimensional space. Customers are assumed to be scattered continuously over the space and each customer is assumed to choose a facility based on both congested travel time to the facility and on the attributes of the facility. The model is formulated as a calculus of variations problem and its optimality conditions are shown to be equivalent to the spatial customer-choice equilibrium conditions. An efficient numerical method using finite element technique is proposed and illustrated with a numerical example.     

COMPETITIVE FACILITIES: MARKET SHARE AND LOCATION WITH RANDOM UTILITY*

ABSTRACT. A new approach is proposed for calculating the expected market share. It is assumed that consumers patronize a facility according to a utility function, selecting the facility with the highest utility value. However, consumers'ratings of the utility components are stochastic by some random distribution. Therefore, the buying power of customers located at the same point is divided among several facilities. A probability that a consumer patronizes a certain facility can be calculated. Consequently, the expected market share by competing facilities can be estimated. This calculation is more than 1,000 times faster than repeating a simulation enough times to achieve a reasonable accuracy. The distance decay calculated using the new approach is approximately exponential. A procedure for finding the optimal location anywhere in the plane for a new facility that maximizes the market share is also introduced.     

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.     

THE OPTIMAL LOCATIONS OF BRANCH FACILITIES AND MAIN FACILITIES WITH CONSUMER SEARCH*

ABSTRACT. This paper examines the socially optimal locations of branch facilities (or small stores) and main facilities (or large stores) on a finite linear market that is uniformly populated from position 0 to position 1. Each consumer has a probability w of finding the desired service (or product) at a branch facility, and a probability 1 of finding the desired service (or product) at a main facility. Two types of consumer search are considered: phone search and visit search. Different assumptions are made about the numbers of branch facilities and main facilities (each involving one or two facilities of each type). Under visit search, the socially optimal locations of branch facilities tend to be closer to main facilities than under phone search, and this tendency is more pronounced for smaller values of w.     

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.     

Interfacility Interaction in Models of Hub and Spoke Networks

Providers of transportation services may reduce their average unit costs by bundling flows and channeling them between hubs (also known as concentrators or routers). The resulting facility locations are interdependent because of the flows between them. This paper analyzes mathematical models of hub systems in an effort to enhance understanding of the optimal location of interactive facilities. The paper examines the behavior of solutions to several alternative models that require the location of a hub at either of two similar locations. A model employing a concave cost function favors the assembly of flows, penalizes fractional facility locations, and produces local minima that have integer facilities.     

A Cost-Benefit Location-Allocation Model for Public Facilities: An Econometric Approach

This research develops and operationalizes a facility location-allocation model based on cost-benefit principles derived from welfare economics. Despite the theoretical advantages of cost-benefit location-allocation models, the difficulties associated with estimating household preferences for public facilities have heretofore prevented their application. This research demonstrates that the hedonic-pricing methodology can be effectively used to estimate preferences for public facilities. Specifically, household preferences for Baltimore public middle schools were estimated from the spatial variation in housing prices using the random bidding model. To provide an example of the methodology, the cost-benefit location-allocation objective function was maximized to simultaneously determine the optimal number, quality, and locations of Baltimore middle schools. The cost-benefit approach to facility location constitutes a major improvement over existing methods because it directly incorporates user preferences into the objective function and because the number and quality of facilities can be determined endogenously rather than being specified as a constraint a priori.     

A NOTE ON THE LOCATION OF MEDICAL FACILITIES

In this note, I present a method to estimate the desired distance between medical facilities. The survival rate of patients improves when the facility is larger, however larger facilities result in a longer driving distance to the facility which decreases the survival rate. I identify the desired distance between facilities for which the survival rate is maximized.     

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.     

Geographic information system‐based evaluation of spatial accessibility to maternal health facilities in Siaya County,Kenya

Maternal mortality is a major problem in middle‐income and low‐income countries, and the availability and accessibility of healthcare facilities offering safe delivery is important in averting maternal deaths. Siaya County, in Kenya, has one of the highest maternal mortality rates in the country—far more than the national average. This study aimed to evaluate geographic access to health facilities offering delivery services in Siaya County. A mixed‐methods approach incorporating geographic information system analysis and individual data from semi‐structured interviews was used to derive travel time maps to facilities using different travel scenarios: AccessMod5 and ArcGIS were used for these tasks. The derived maps were then linked to georeferenced household survey data in a multilevel logistic regression model in R to predict the probability of expectant women delivering in a health facility. Based on the derived travel times, 26 per cent (13,140) and 67 per cent (32,074) of the estimated 46,332 pregnant women could reach any facility within one and two hours, respectively, while walking with the percentage falling to seven per cent (3,415) and 20 per cent (8,845) when considering referral facilities. Motorised transport significantly increased coverage. The findings revealed that the predicted probability of a pregnant woman delivering in a health facility ranged between 0.14 and 0.86. Significant differences existed in access levels with transportation‐based interventions significantly increasing coverage. The derived maps can help health policy planners identify underserved areas and monitor future reductions in inequalities. This work has theoretical implications for conceptualising healthcare accessibility besides advancing the literature on mixed methodologies.     

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.     

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.     

On the Logit Approach to Competitive Facility Location

The random utility model in competitive facility location is one approach for estimating the market share captured by a retail facility in a competitive environment. However, it requires extensive computational effort for finding the optimal location for a new facility because its objective function is based on a k -dimensional integral. In this paper we show that the random utility model can be approximated by a logit model. The proportion of the buying power at a demand point that is attracted to the new facility can be approximated by a logit function of the distance to it. This approximation demonstrates that using the logit function of the distance for estimating the market share is theoretically founded in the random utility model. A simplified random utility model is defined and approximated by a logit function. An iterative Weiszfeld-type algorithm is designed to find the best location for a new facility using the logit model. Computational experiments show that the logit approximation yields a good location solution to the random utility model.     

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.     

Results of a New Approach to Solving the p-Median Problem with Maximum Distance Constraints

Considerable interest has been directed in the past to developing approaches for solving the p-median problem with maximum distance constraints. All current solution techniques consider potential facilities to be located only at nodes of the network. This paper deals with the solution of this problem under the condition where facility placement is not restricted to nodes. The examples given show that improvement in weighted distance can be obtained by solving the unrestricted site problem. In addition, feasible solutions can be obtained for smaller numbers of facilities than possible by all nodal facility placement.     

Activity Levels at Hub Facilities in Interacting Networks

Hubs are a special type of central facility which are designed to act as switching points for intemodal flows. For instance, a set of ten interacting cities might all be connected to one of two major hubs. All flows between the cities would then be routed via the hubs. There is an obvious saving in the number of routes necessary to interconnect the cities when hubs are utilized, with a concomitant high level of activity at the facilities. This paper takes a heuristic approach to the evaluation of networks and hub locations to find locally optimal designs. It is shown that minimization of transportation costs may require assignment of nodes to a facility other than the nearest. A discount on the interhub transportation costs promotes a wider spacing of facilities. In a system with several hubs, minimization of total hub usage tends to concentrate demand very heavily into one central facility.