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.     

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.     

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.     

A Unified Model for Dispersing Facilities

One of the important classes of facility dispersion problems involves the location of a number of facilities where the intent is to place them as far apart from each other as possible. Four basic forms of the p‐facility dispersion problem appear in the literature. Erkut and Neuman present a classification system for these four classic constructs. More recently, Curtin and Church expanded upon this framework by the introduction of “multiple types” of facilities, where the dispersion distances between specific types are weighted differently. This article explores another basic assumption found in all four classic models (including the multitype facility constructs of Curtin and Church): that dispersion is accounted for in terms of either distance to the closest facility or distances to all facilities (from a given facility), whether applied to a single type of facility or across a set of facility types. In reality, however, measuring dispersion in terms of whether neighboring facilities to a given facility are dispersed rather than whether all facilities are dispersed away from the given facility often makes more sense. To account for this intermediate measure of dispersion, we propose a construct called partial‐sum dispersion. We propose four “partial‐sum” dispersion problem forms and show that these are generalized forms of the classic set of four models codified by Erkut and Neuman. Further, we present a unifying model that is a generalized form of all four partial‐sum models as well as a generalized form of the original four classic model constructs. Finally, we present computational experience with the general model and conclude with a few examples and suggestions for future research. Una de las clases importantes dentro de los problemas de dispersión de instalaciones de servicios/infraestructura es el caso en el que la localización de un número de instalaciones debe cumplir la condición de maximizar la distancia entre cada par. La literatura especializada cita cuatro formas básicas del problema de dispersión llamados tipo p‐instalación (p‐facility) (Shier 1977; Luna y Chaudhry 1984; Kuby 1987; Erkut y Neuman, 1991). Erkut y Neuman (1991) presentan un sistema de clasificación para estas cuatro formas clásicas. Recientemente, Curtin e Iglesia (2006) ampliaron este marco metodológico al incorporar múltiples tipos de instalaciones, permitiendo que las distancias de dispersión entre diferentes tipos específicos de instalaciones sean ponderadas de manera diferente. El artículo presente explora otro supuesto básico que se encuentra en los cuatro modelos clásicos (y las modifcaciones para acomodar instalaciones multi‐tipo de Curtin e Iglesia): la dispersión es cuantificada en términos de la distancia entre una instalación dada y la instalación más cercana, o entre una instalación dada y la totalidad de las instalaciones. Este supuesto se mantiene si las distancias son aplicadas a un solo tipo de instalación o a múltiples tipos de instalaciones. Sin embargo, en realidad, tiene más sentido medir la dispersión en relación a las instalaciones vecinas, en vez de en relación a la totalidad las instalaciones. Para incorporar esta realidad a un nuevo tipo de medida intermedia de dispersión, se propone una medida llamada dispersión de suma parcial (partial‐sum dispersion). Proponemos cuatro tipos de problemas de dispersión de tipo parcial‐sum y demostramos que éstas son formas generalizadas de los cuatro modelos clásicos presentados por Erkut y Neuman (1991). Además, se presenta un modelo unificado que es una forma generalizada de los cuatro modelos tipo partial‐sum, así como una forma generalizada de las cuatro tipos en el modelo clásico. Por último, se presenta los resultados de pruebas computacionales usando el modelo general y se concluye con algunos ejemplos y sugerencias para investigaciones futuras. 设施分散问题中重要的一类是大量设施的布局,其意图是将它们在空间上尽可能离得更远。目前文献中主要讨论了4种基本形式(Shier 1977; Moon and Chaudhry 1984; Kuby 1987; Erkut and Neuman 1991)。Erkut and Neuman (1991)提出了这4种经典结构的一种分类系统。Curtin and Church (2006)引入设施“多种类型”对上述分类框架进行拓展,在特定类别之间的分散距离的权重存在不同。本文探索了在4种经典模型中所发现的另一种基本假设（包含Curtin and Church的多种类型设施结构）：无论是在单一类型设施或包括多种类型设施中,分散度在解释某一给定设施到最近设施的距离或到所有设施的距离方面都是合理的。然而,在现实中设施分散度度量方面,测量某一给定设施的邻近设施的分散度特征相比于测量给定设施的所有其他设施的散布特征通常更有意义。为解释这种分散度的中间度量,本文提出了一种称为“局部和整体”的结构,包括4种分散问题形式,它们是Erkut and Neuman 4种传统类型的广义形式。本文进而提出了一个统一模型,即所有 “局部和整体”模型和经典类型结构一种广义形式。最后,对统一模型进行了计算检验,并基于几个实证进行了总结,还提出了未来的研究建议。     

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.     

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.     

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

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.     

Reliable p-Hub Location Problems in Telecommunication Networks

Hubs are critical elements of telecommunication and transportation networks because they play a vital role in mass traffic movement. The design of more reliable networks in hub-and-spoke systems is a critical issue because current networks, particularly many commercial Internet backbones, are quite vulnerable. In hub-and-spoke-type topologies, any malfunction at a hub may cause degradation of the entire network's ability to transfer flows. This article presents a new hub location problem, termed the reliable p-hub location problem , which focuses on maximizing network performance in terms of reliability by locating hubs for delivering flows among city nodes. Two submodels, the p-hub maximum reliability model and the p-hub mandatory dispersion model, are formulated. Based on hypothetical and empirical analyses using telecommunication networks in the United States, the relationship between network performance and hub facility locations is explored. The results from these models could give useful insights into telecommunication network design.     

The Zone Definition Problem in Location-Allocation Modeling

Location-allocation modeling is a frequently used set of techniques for solving a variety of locational problems, some of which can be politically sensitive. The typical application of a location-allocation model involves locating facilities by selecting a set of sites from a larger set of candidate sites, with the selection procedure being a function of “optimality” in terms of the allocation of demand to the selected sites. In this paper we examine the sensitivity of one particular type of location-allocation model, the p-median procedure, to the definition of spatial units for which demand is measured. We show that a p-median solution is optimal only for a particular definition of spatial units and that variations in the definition of spatial units can cause large deviations in optimal facility locations. The broad implication of these findings is that the outcome of any location-allocation procedure using aggregate data should not be relied upon for planning purposes. This has important implications for a large variety of applications.     

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.     

Dispersion of Nodes Added to a Network

For location problems in which optimal locations can be at nodes or along arcs but no finite dominating set has been identified, researchers may desire a method for dispersing p additional discrete candidate sites along the m arcs of a network. This article develops and tests minimax and maximin models for solving this continuous network location problem, which we call the added-node dispersion problem (ANDP). Adding nodes to an arc subdivides it into subarcs. The minimax model minimizes the maximum subarc length, while the maximin model maximizes the minimum subarc length. Like most worst-case objectives, the minimax and maximin objectives are plagued by poorly behaved alternate optima. Therefore, a secondary MinSumMax objective is used to select the best-dispersed alternate optima. We prove that equal spacing of added nodes along arcs is optimal to the MinSumMax objective. Using this fact we develop greedy heuristic algorithms that are simple, optimal, and efficient (O( mp )). Empirical results show how the maximum subarc, minimum subarc, and sum of longest subarcs change as the number of added nodes increases. Further empirical results show how using the ANDP to locate additional nodes can improve the solutions of another location problem. Using the p-dispersion problem as a case study, we show how much adding ANDP sites to the network vertices improves the p-dispersion objective function compared with (a) network vertices only and (b) vertices plus randomly added nodes. The ANDP can also be used by itself to disperse facilities such as stores, refueling stations, cell phone towers, or relay facilities along the arcs of a network, assuming that such facilities already exist at all nodes of the network.     

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.     

LOCATION AND SPATIAL PRICING FOR PUBLIC FACILITIES

ABSTRACT. Past analysis of public facility location has generally assumed a single goal, such as cost minimization or welfare maximization, and exogenous spatial pricing. This paper considers optimal facility location under a variety of goals. Furthermore, the facility manager is allowed to engage in freight absorption so that the delivered price to consumers need not reflect actual transportation costs. A systematic interaction among management goals, freight absorption, and the optimal size and spacing of public facilities is found.     

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.     

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.     

LOCATION OF PUBLIC FACILITIES WITH SPILLOVER EFFECTS: VARIABLE LOCATION AND PARAMETRIC SCALE*

ABSTRACT This paper studies the location of public facilities of two neighboring local governments which consider not only the influence of the land market but also the spillover effects that each jurisdiction may have on the other. We obtain the following results: (1) in most cases, one of the cities behaves as an isolated city in choosing the facility location while the other enjoys the spillover effect as a free rider; (2) we also find that the equilibrium location in the two noncooperative city case is not socially optimal except for a special case.     

An Equity Model for Locating Environmentally Hazardous Facilities

This paper develops a multiobjective mathematical location model to identify possible locations for environmentally hazardous facilities. Risk and equity are recognized as the most important criteria in determining site selection. In contrast to earlier models, the equity objective explicitly considers the existing distribution of environmental burdens when siting new hazardous facilities. Proposed environmentally hazardous facilities are located so that the burdens associated with new and existing hazards are shared as equally as possible among all areas. The application of the model, in a case study of the Greenpoint/Williamsburg neighborhood in Brooklyn, New York, illustrates the trade‐offs associated with various risk and equity scenarios. Sensitivity analyses demonstrate how the existing distribution of environmental burdens may act as a constraint and limit the degree of equity that may be obtained when locating new 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.