Optimal Number of Hierarchical Facilities with Failures

This article proposes a continuous approximation model for determining the number of hierarchical facilities when lower level facilities are subject to failures. The average distance from customers to the nearest open facility is derived for two types of customer behavior. The optimal number of facilities that minimizes the average distance is then obtained. The analytical expression for the optimal number of facilities demonstrates how the location of facilities, the failure probability, and the customer behavior affect the optimal hierarchy and the average distance. The result shows that introducing the hierarchy can reduce the average distance if the failure probability is small and the penalty for failing to use facilities is large. The model provides a fundamental understanding of the optimal hierarchy and is useful for designing hierarchical facility systems.     

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.     

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.     

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.     

Distribution of the Sum of Distances to the First and Second Nearest Facilities

This article presents a derivation of the distribution of the sum of the distances to the first and second nearest facilities. Facilities are represented as points configured in regular and random patterns, and distance is measured as the Euclidean and rectilinear distances on a continuous plane. The sum of the distances represents the service level of facility location when customers are serviced by the first and second nearest facilities. Thus, the distribution of the sum is useful for facility location problems with nonclosest facility service. The distribution of the sum of road network distances also is calculated to evaluate the efficiency of actual facility locations. Este artículo presenta una derivación de la distribución de la suma de las distancias a la primera y segunda instalación más cercana. Las instalaciones son presentadas como puntos en configuraciones espaciales regulares y aleatorias, y la distancias son medidas usando el método euclidiano y el rectilínea sobre un plano continuo. La suma de las distancias representa el nivel de servicio en cada punto, en los casos en los que los clientes son atendidos en la instalación primera y segunda más cercana. El uso de la distribución de la suma de distancias es útil para resolver problemas de localización para casos en los que los clientes son atendidos por las instalaciones de servicios que nos son las más cercanas. Como demostración se calcula la distribución de la suma de las distancias de una red de carreteras para evaluar la eficiencia de la localización de instalaciones en un caso del mundo real. 本文讨论了一种最邻近距离总和与次邻近设施距离总和分布情况的推导方法。具体设施以规则和随机两种模式的点状要素来表示,距离采用连续平面中的欧氏及直线距离测度。距离之和反映了最邻近及次邻近设施为用户提供该设施区位的服务水平。因此,距离和的分布在无最邻近设施服务的设施选址问题中具有参考价值。路网距离和的分布也可计算用于现有设施区位的效率评估。     

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 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.     

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.     

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.     

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.     

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.     

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.     

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.     

A Comparison of Simple Lattice Transport Networks for a Uniform Plain

The objective is to compare construction and transport costs for triangular, orthogonal, and hexagonal regular lattices as transport networks serving a uniform, unbounded plain. The lattices are standardized so that the average distance from the elementary area to the edge is the same for each. This standardization results in equal construction costs for the three networks; thus, the comparison can be made in terms of route factors, which favors the triangular lattice over the other two.     

EQUILATERAL TRIANGLE VS. HEXAGON: A MOST SIMPLE DEMONSTRATION

ABSTRACT. This note presents a most simple proof of the superiority of hexagons over equilateral triangles of the same size in terms of minimization of the average distance between consumers and facilities. It also stresses that, under the same assumptions, facilities are closer to each other in a triangular grid than in an hexagonal grid and that this fact should not be neglected.     

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.     

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.     

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.     

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.