Continuous location model of a rectangular barrier facility

This paper develops a bi-objective model for determining the location, size, and shape of a finite-size facility. The objectives are to minimize both the closest and barrier distances. The closest distance represents the accessibility of customers, whereas the barrier distance represents the interference to travelers. The distributions of the closest and barrier distances are derived for a rectangular facility in a rectangular city where the distance is measured as the rectilinear distance. The analytical expressions for the distributions demonstrate how the location, size, and shape of the facility affect the closest and barrier distances. A numerical example shows that there exists a trade-off between the closest and barrier distances.     

A multi-objective integrated facility location-hardening model: Analyzing the pre- and post-disruption tradeoff

Two methods of reducing the risk of disruptions to distribution systems are (1) strategically locating facilities to mitigate against disruptions and (2) hardening facilities. These two activities have been treated separately in most of the academic literature. This article integrates facility location and facility hardening decisions by studying the minimax facility location and hardening problem (MFLHP), which seeks to minimize the maximum distance from a demand point to its closest located facility after facility disruptions. The formulation assumes that the decision maker is risk averse and thus interested in mitigating against the facility disruption scenario with the largest consequence, an objective that is appropriate for modeling facility interdiction. By taking advantage of the MFLHP’s structure, a natural three-stage formulation is reformulated as a single-stage mixed-integer program (MIP). Rather than solving the MIP directly, the MFLHP can be decomposed into sub-problems and solved using a binary search algorithm. This binary search algorithm is the basis for a multi-objective algorithm, which computes the Pareto-efficient set for the pre- and post-disruption maximum distance. The multi-objective algorithm is illustrated in a numerical example, and experimental results are presented that analyze the tradeoff between objectives.     

Planar weber location problems with line barriers

The Weber problem for a given finite set of existing facilities in the plane is to find the location of a new facility such that the weithted sum of distances to the existing facilities is minimized.

A variation of this problem is obtained if the existing facilities are situated on two sides of a linear barrier. Such barriers like rivers, highways, borders or mountain ranges are frequently encountered in practice.

Structural results as well as algorithms for this non-convex optimization problem depending on the distance function and on the number and location of passages through the barrier are presented.     

Financial scenario generation for stochastic multi-stage decision processes as facility location problems

The quality of multi-stage stochastic optimization models as they appear in asset liability management, energy planning, transportation, supply chain management, and other applications depends heavily on the quality of the underlying scenario model, describing the uncertain processes influencing the profit/cost function, such as asset prices and liabilities, the energy demand process, demand for transportation, and the like. A common approach to generate scenarios is based on estimating an unknown distribution and matching its moments with moments of a discrete scenario model. This paper demonstrates that the problem of finding valuable scenario approximations can be viewed as the problem of optimally approximating a given distribution with some distance function. We show that for Lipschitz continuous cost/profit functions it is best to employ the Wasserstein distance. The resulting optimization problem can be viewed as a multi-dimensional facility location problem, for which at least good heuristic algorithms exist. For multi-stage problems, a scenario tree is constructed as a nested facility location problem. Numerical convergence results for financial mean-risk portfolio selection conclude the paper.     

Kohonen maps for solving a class of location-allocation problems

Location-Allocation problems occur whenever more than one facility need be located to serve a set of demand centers and it is not known or fixed a priori their allocation to the supply centers. This paper deals with a continuous space problem in which demand centers are independently served from a given number of independent, uncapacitated supply centers. Installation costs are assumed not to depend on neither the actual location nor the actual throughput of the supply centers. Transportation costs are considered to be proportional to the square Euclidean distance travelled and a minisum criterium is adopted. The problem is recognized as identical to certain Cluster Analysis and Vector Quantization problems. Such a relationship leads to applying Kohonen Maps, which are Artificial Neural Networks capable of extracting the main features, i.e. the structure, of the input data through a self-organizing process based on local adaptation rules. This approach has previously been applied to other combinatorial problems such as the Travelling Salesperson Problem.     

Determining an optimum location for an undesirable facility in a workroom environment

This paper deals with the problem of placing an undesirable but necessary piece of equipment, process or facility into a working environment. Locating a piece of equipment that produces contaminants or creates stresses for nearby workers, placing a storage facility for flammable materials or locating hazardous waste in the workroom environment, are all typical examples of the undesirable facility location problem. The degree of undesirability between an existing facility or worker and the new undesirable entity is reflected through a weighting factor. The problem is formally defined to be the selection of a location within the convex region that maximizes the minimum weighted Euclidean distance with respect to all existing facilities. A ‘Maximin’ model is formulated and two solution procedures introduced. A geometrical approach and an algorithmic approach are described in detail. An example is provided for each solution procedure and the computational efficiency of the algorithm is discussed and illustrated.     

Optimal location-size of a facility on an plane with interaction effects of distance

A binomial model for the interaction effects of distance is used to obtain the probable demand for a facility located on a plane. Such demand expressed as a function of size, location, population profile and distribution on the plane, is shown (using arguments leading to the central limit theorem) to be normal. Optimization of expected cost criteria is then used to obtain optimal locations under uncertainty. Examples are resolved and the practical implications of the model suggested are drawn.     

连续设施选址:模型、方法与应用

给定度量空间和该空间中的若干顾客,设施选址为在该度量空间中确定新设施的位置使得某种目标达到最优。连续设施选址是设施选址中的一类重要问题,其中的设施可在度量空间的某连续区域上进行选址。本文对连续设施选址的模型、算法和应用方面的工作进行了综述。文章首先讨论了连续设施选址中几个重要元素,包括新设施个数、距离度量函数、目标函数;然后介绍了连续选址中的几种经典模型和拓展模型;接着概述了求解连续选址问题的常用优化方法和技术,包括共轭对偶、全局优化、不确定优化、变分不等式方法、维诺图;最后介绍了连续设施选址的重要应用并给出了研究展望。     

Location of a semi-obnoxious facility with elliptic maximin and network minisum objectives

This paper considers the problem of locating a single semi-obnoxious facility on a general network, so as to minimize the total transportation cost between the new facility and the demand points (minisum), and at the same time to minimize the undesirable effects of the new facility by maximizing its distance from the closest population center (maximin). The two objectives employ different distance metrics to reflect reality. Since vehicles move on the transportation network, the shortest path distance is suitable for the minisum objective. For the maximin objective, however, the elliptic distance metric is used to reflect the impact of wind in the distribution of pollution. An efficient algorithm is developed to find the nondominated set of the bi-objective model and is implemented on a numerical example. A simulation experiment is provided to find the average computational complexity of the algorithm.     

Location and allocation for distribution systems with transshipments and transportion economies of scale

Locating transshipment facilities and allocating origins and destinations to transshipment facilities are important decisions for many distribution and logistic systems. Models that treat demand as a continuous density over the service region often assume certain facility locations or a certain allocation of demand. It may be assumed that facility locations lie on a rectangular grid or that demand is allocated to the nearest facility or allocated such that each facility serves an equal amount of demand. These assumptions result in suboptimal distribution systems. This paper compares the transportation cost for suboptimal location and allocation schemes to the optimal cost to determine if suboptimal location and allocation schemes can produce nearly optimal transportation costs. Analytical results for distribution to a continuous demand show that nearly optimal costs can be achieved with suboptimal locations. An example of distribution to discrete demand points indicates the difficulties in applying these results to discrete demand problems.     

Strategic facility location: A review

Facility location decisions are a critical element in strategic planning for a wide range of private and public firms. The ramifications of siting facilities are broadly based and long-lasting, impacting numerous operational and logistical decisions. High costs associated with property acquisition and facility construction make facility location or relocation projects long-term investments. To make such undertakings profitable, firms plan for new facilities to remain in place and in operation for an extended time period. Thus, decision makers must select sites that will not simply perform well according to the current system state, but that will continue to be profitable for the facility's lifetime, even as environmental factors change, populations shift, and market trends evolve. Finding robust facility locations is thus a difficult task, demanding that decision makers account for uncertain future events. The complexity of this problem has limited much of the facility location literature to simplified static and deterministic models. Although a few researchers initiated the study of stochastic and dynamic aspects of facility location many years ago, most of the research dedicated to these issues has been published in recent years. In this review, we report on literature which explicitly addresses the strategic nature of facility location problems by considering either stochastic or dynamic problem characteristics. Dynamic formulations focus on the difficult timing issues involved in locating a facility (or facilities) over an extended horizon. Stochastic formulations attempt to capture the uncertainty in problem input parameters such as forecast demand or distance values. The stochastic literature is divided into two classes: that which explicitly considers the probability distribution of uncertain parameters, and that which captures uncertainty through scenario planning. A wide range of model formulations and solution approaches are discussed, with applications ranging across numerous industries.     

The single facility location problem with time-dependent weights and relocation cost over a continuous time horizon

In this study, we investigate the problem of locating a facility in continuous space when the weight of each existing facility is a known linear function of time. The location of the new facility can be changed once over a continuous finite time horizon. Rectilinear distance and time- and location-dependent relocation costs are considered. The objective is to determine the optimal relocation time and locations of the new facility before and after relocation to minimize the total location and relocation costs. We also propose an exact algorithm to solve the problem in a polynomial time according to our computational results.     

The probabilistic 1-maximal covering problem on a network with discrete demand weights

We discuss the probabilistic 1-maximal covering problem on a network with uncertain demand. A single facility is to be located on the network. The demand originating from a node is considered covered if the shortest distance from the node to the facility does not exceed a given service distance. It is assumed that demand weights are independent discrete random variables. The objective of the problem is to find a location for the facility so as to maximize the probability that the total covered demand is greater than or equal to a pre-selected threshold value. We show that the problem is NP-hard and that an optimal solution exists in a finite set of dominant points. We develop an exact algorithm and a normal approximation solution procedure. Computational experiment is performed to evaluate their performance.     

On models for continuous facility location with partial coverage

This paper presents a new concept of partial coverage distance, where demand points within a given threshold distance of a new facility are covered in the traditional sense, while non-covered demand points are penalized an amount proportional to their distance to the covered region. Two single facility location models, based on the minisum and minimax criteria, are formulated with the new distance function, and the structure of the models is analysed.     

Efficient Location for a Semi-Obnoxious Facility

This paper deals with a location model for the placement of a semi-obnoxious facility in a continuous plane with the twin objectives of maximizing the distance to the nearest inhabitant and minimizing the sum of distances to all the users (or the distance to the farthest user) in a unified manner. For special cases, this formulation includes (1) elliptic maximin and rectangular minisum criteria problem, and (2) rectangular maximin and minimax criteria problem. Polynomial-time algorithms for finding the efficient set and the tradeoff curve are presented.     

Weber problems with mixed distances and regional demand

We consider a location problem where the distribution of the existing facilities is described by a probability distribution and the transportation cost is given by a combination of transportation cost in a network and continuous distance. The motivation is that in many cases transportation cost is partly given by the cost of travel in a transportation network whereas the access to the network and the travel from the exit of the network to the new facility is given by a continuous distance.      

Placing a finite size facility with a center objective on a rectangular plane with barriers

This paper addresses the finite size 1-center placement problem on a rectangular plane in the presence of barriers. Barriers are regions in which both facility location and travel through are prohibited. The feasible region for facility placement is subdivided into cells along the lines of Larson and Sadiq [R.C. Larson, G. Sadiq, Facility locations with the Manhattan metric in the presence of barriers to travel, Operations Research 31 (4) (1983) 652–669]. To overcome complications induced by the center (minimax) objective, we analyze the resultant cells based on the cell corners. We study the problem when the facility orientation is known a priori. We obtain domination results when the facility is fully contained inside 1, 2 and 3-cornered cells. For full containment in a 4-cornered cell, we formulate the problem as a linear program. However, when the facility intersects gridlines, analytical representation of the distance functions becomes challenging. We study the difficulties of this case and formulate our problem as a linear or nonlinear program, depending on whether the feasible region is convex or nonconvex. An analysis of the solution complexity is presented along with an illustrative numerical example.     

E-approximations for multidimensional weighted location problems.

This paper considers the multidimensional weighted minimax location problem, namely, finding a facility location that minimizes the maximal weighted distance to n points. General distance norms are used. An epsilon-approximate solution is obtained by applying a variant of the Russian method for the solution of Linear Programming. The algorithm has a time complexity of O(n log epsilon) for fixed dimensionality k. Computational results are presented.     

A 1-center problem on the plane with uniformly distributed demand points

Center problems or minimax facility location problems are among the most active research areas in location theory. In this paper, we find the best unique location for a facility in the plane such that the maximum expected weighted distance to all random demand points is minimized.     

A multi-objective genetic algorithm for a bi-objective facility location problem with partial coverage

In this study, we present a bi-objective facility location model that considers both partial coverage and service to uncovered demands. Due to limited number of facilities to be opened, some of the demand nodes may not be within full or partial coverage distance of a facility. However, a demand node that is not within the coverage distance of a facility should get service from the nearest facility within the shortest possible time. In this model, it is assumed that demand nodes within the predefined distance of opened facilities are fully covered, and after that distance the coverage level decreases linearly. The objectives are defined as the maximization of full and partial coverage, and the minimization of the maximum distance between uncovered demand nodes and their nearest facilities. We develop a new multi-objective genetic algorithm (MOGA) called modified SPEA-II (mSPEA-II). In this method, the fitness function of SPEA-II is modified and the crowding distance of NSGA-II is used. The performance of mSPEA-II is tested on randomly generated problems of different sizes. The results are compared with the solutions of the most well-known MOGAs, NSGA-II and SPEA-II. Computational experiments show that mSPEA-II outperforms both NSGA-II and SPEA-II.