Solving the bi‐objective capacitated p‐median problem with multilevel capacities using compromise programming and VNS

A bi‐objective optimisation using a compromise programming (CP) approach is proposed for the capacitated p‐median problem (CPMP) in the presence of the fixed cost of opening facility and several possible capacities that can be used by potential facilities. As the sum of distances between customers and their facilities and the total fixed cost for opening facilities are important aspects, the model is proposed to deal with those conflicting objectives. We develop a mathematical model using integer linear programming (ILP) to determine the optimal location of open facilities with their optimal capacity. Two approaches are designed to deal with the bi‐objective CPMP, namely CP with an exact method and with a variable neighbourhood search (VNS) based matheuristic. New sets of generated instances are used to evaluate the performance of the proposed approaches. The computational experiments show that the proposed approaches produce interesting results.     

The facility and transfer points location problem

In this paper, we investigate the location of a facility and several transfer points to serve as collector points for customers who need the services of the facility. For example, demand for emergency services is generated at a set of demand points that need the services of a central facility (such as a hospital). Patients are transferred to a helicopter pad (transfer point) at normal speed, and from there they are transferred to the facility at increased speed. The model involves the location of multiple transfer points and one facility. Locating one transfer point when the set of demand points and the location of the facility are known was investigated in Berman et al. (2004a). Location of several transfer points when the location of the facility is given is investigated in Berman et al. (2004b). In this paper, we propose heuristic approaches for the solution of this problem and report computational experiments on a test set of 40 problems.     

Optimal location policy for three competitive facilities

Competitive facility location problems have been investigated in many papers. In most, authors have applied location models with two competitors. In this paper three companies, which are mutually competitive, intend to locate their facilities in a linear market. It is well-known that Nash equilibrium solution for location problem does not include three competitive facilities. In this paper we present the optimal location strategies for three facilities. In our model we assume that the demands are continuously distributed in a linear market and the facilities are locating according to a specific order of sequence, A, B and C. We apply the Stackelberg equilibrium solutions for competitive location problems with three facilities. In our model, we consider the decision problems in three stages. In the first stage, we decide the optimal location of facility A, which is located optimally in respect to the remaining two facilities B and C. In the second stage, we determine the optimal location of facility B which is optimally located in respect to facility C, by utilizing the information on the location of facility A. Finally in the third stage problem we decide the location of facility C, optimally located by utilizing the information on the location of A and B. In the first stage, we need the optimal solutions of the second and third stages. In the second stage we need the optimal solution of the third stage problem. Therefore, first we solve the third stage problem which is the simplest. After that, we solve the second stage problem utilizing the optimal solution strategy of the third stage problem. In this paper we present the optimal location strategies for three facilities.     

A quadtree-based allocation method for a class of large discrete Euclidean location problems

A special data compression approach using a quadtree-based method is proposed for allocating very large demand points to their nearest facilities while eliminating aggregation error. This allocation procedure is shown to be extremely effective when solving very large facility location problems in the Euclidian space. Our method basically aggregates demand points where it eliminates aggregation-based allocation error, and disaggregates them if necessary. The method is assessed first on the allocation problems and then embedded into the search for solving a class of discrete facility location problems namely the p-median and the vertex p-center problems. We use randomly generated and TSP datasets for testing our method. The results of the experiments show that the quadtree-based approach is very effective in reducing the computing time for this class of location problems.     

Supply facility and input/output point locations in the presence of barriers

This paper studies a facility location model in which two-dimensional Euclidean space represents the layout of a shop floor. The demand is generated by fixed rectangular-shaped user sites and served by a single supply facility. It is assumed that (i) communication between the supply point and a demand facility occurs at an input/output (I/O) point on the demand facility itself, (ii) the facilities themselves pose barriers to travel and (iii) distance measurement is as per the L₁-metric. The objective is to determine optimal locations of the supply facility as well as I/O points on the demand facilities, in order to minimize total transportation costs. Several, increasingly more complex, versions of the model are formulated and polynomial time algorithms are developed to find the optimal locations in each case.Scope and purposeIn a facility layout setting, often a new central supply facility such as a parts supply center or tool crib needs to be located to serve the existing demand facilities (e.g., workstations or maintenance areas). The demand facilities are physical entities that occupy space, that cannot be traveled through, and that receive material from the central facility, through a perimeter I/O (input/output or drop-off/pick-up) point. This paper addresses the joint problem of locating the central facility and determining the I/O point on each demand facility to minimize the total material transportation cost. Different versions of this problem are considered. The solution methods draw from and extend results of location theory for a class of restricted location problems. For practitioners, simple results and polynomial time algorithms are developed for solving these facility (re) design problems.     

Risk management in uncapacitated facility location models with random demands

In this paper we consider a location-optimization problem where the classical uncapacitated facility location model is recast in a stochastic environment with several risk factors that make demand at each customer site probabilistic and correlated with demands at the other customer sites. Our primary contribution is to introduce a new solution methodology that adopts the mean–variance approach, borrowed from the finance literature, to optimize the “Value-at-Risk” (VaR) measure in a location problem. Specifically, the objective of locating the facilities is to maximize the lower limit of future earnings based on a stated confidence level. We derive a nonlinear integer program whose solution gives the optimal locations for the p facilities under the new objective. We design a branch-and-bound algorithm that utilizes a second-order cone program (SOCP) solver as a subroutine. We also provide computational results that show excellent solution times on small to medium sized problems.     

Semi-obnoxious single facility location in Euclidean space

This paper deals with the problem of determining within a bounded region the location for a new facility that serves certain demand points. For that purpose, the facility planners have two objectives. First, they attempt to minimize the undesirable effects introduced by the new facility by maximizing its minimum Euclidean distance with respect to all demand points (maximin). Secondly, they want to minimize the total transportation cost from the new facility to the demand points (minisum). Typical examples for such “semi-obnoxious” facilities are power plants that, as polluting agents, are undesirable and should be located far away from demand points, while cost considerations force planners to have the facility in close proximity to the customers. We describe the set of efficient solutions of this bi-criterion problem and propose an efficient algorithm for its solution.

Scope and purpose

It is becoming increasingly difficult to site necessary but potentially polluting (semi-obnoxious) facilities such as power plants, chemical plants, waste dumps, airports or train stations. More systematic decision-aid tools are needed to generate several options that balance the public's concerns with the interests of the developer or location planner. In this paper, a model is presented that generates the best possible sites (efficient solutions) with respect to two conflicting criteria: maximize distance from population centers and minimize total transportation costs. Having all efficient solutions at hand, the two sides can select one that best compromises their criteria. A very interesting property found is that most of these efficient solutions are on edges of a Voronoi diagram. An algorithm is developed that constructs the complete trajectory of efficient solutions.     

Genetic algorithm to solve the p-centre and p-radius problem on a network

The p-centre problem is to locate p facilities on a network so as to minimize the largest distance from a demand point to its nearest facility. The problem is NP-complete for an arbitrary network. In this paper, genetic algorithms (GAs) to solve this problem are developed via two different representations. The nodes are taken as weighted, and the demand points are assumed to coincide with the nodes. Computational results obtained from the proposed GAs for different network sizes and different values of p are presented and compared for two different representations.     

On solving unreliable planar location problems

In this paper, we generalize conventional P-median location problems by considering the unreliability of facilities. The unreliable location problem is defined by introducing the probability that a facility may become inactive. We proposed efficient solution methods to determine locations of these facilities in the unreliable location model. Space-filling curve-based algorithms are developed to determine initial locations of these facilities. The unreliable P-median location problem is then decomposed to P 1-median location problems; each problem is solved to the optimum. A bounding procedure is used to monitor the iterative search, and to provide a consistent basis for termination. Extensive computational tests have indicated that the heuristics are efficient and effective for solving unreliable location problems.Scope and purposeThis paper addresses an important class of location problems, where p unreliable facilities are to be located on the plane, so as to minimize the expected travel distance or related transportation cost between the customers and their nearest available facilities. The unreliable location problem is defined by introducing the probability that a facility may become inactive. Potential application of the unreliable location problem is found in numerous areas. The facilities to be located can be fire station or emergency shelter, where it fails to provide service during some time window, due to the capacity or resource constraints. Alternatively, the facilities can be telecommunication posts or logistic/distribution centers, where the service is unavailable due to breakdown, repair, shutdown of unknown causes. In this paper, we prescribed heuristic procedures to determine the location of new facilities in the unreliable location problems. The numerical study of 2800 randomly generated instances has shown that these solution procedures are both efficient and effective, in terms of computational time and solution quality.     

Kinetic Facility Location

We present a deterministic kinetic data structure for the facility location problem that maintains a subset of the moving points as facilities such that, at any point of time, the accumulated cost for the whole point set is at most a constant factor larger than the optimal cost. In our scenario, each point can change its status between client and facility and moves continuously along a known trajectory in a d-dimensional Euclidean space, where d is a constant.     

The big cube small cube solution method for multidimensional facility location problems

In this paper we propose a general solution method for (non-differentiable) facility location problems with more than two variables as an extension of the Big Square Small Square technique (BSSS). We develop a general framework based on lower bounds and discarding tests for every location problem. We demonstrate our approach on three problems: the Fermat–Weber problem with positive and negative weights, the median circle problem, and the p-median problem. For each of these problems we show how to calculate lower bounds and discarding tests. Computational experiences are given which show that the proposed solution method is fast and exact.     

韦伯型多点设施优化选址的组合算法研究

韦伯型设施选址问题是组合优化领域中的一类重要问题,其核心内容是如何在离散的需求空间域内,寻找到最优决策关注点,即设施点。对于单点设施最优规划问题,由于不存在设置点之间的作用,仅考虑设施点与需求点之间的引力作用问题即可。对于多点设施的最优规划问题,不仅存在着设施点与需求点之间的引力作用问题,而且从资源优化配置的角度,还存在着设施点之间的斥力问题。因此,需要从系统整体优化的角度进行选择规划。目前解决韦伯型设施多点的优化选址问题,一般是通过寻找局部最优解的逐次递阶法来确定最优设施点。但由于该方法没有考虑到设施点间的斥力问题,容易导致设施点间的粘连。针对此问题,提出了一种PGSA-GA组合算法,通过建立模拟植物生长算法得到全局最优解的单点坐标,将其与需求点结合构建遗传算法优化的多目标规划多点设施选址模型求出Pareto最优解,并依此推广到多次选址方案。     

Simultaneous location of a service facility and a rapid transit line

This paper presents a location problem on the plane where a single service facility and a rapid transit line have to be simultaneously located. The rapid transit line represents an alternative transportation line which can be used by clients whenever it provides a cost-saving or time-saving service, and it is given by a segment with fixed and known length. This type of problems has not previously been considered in the Location Theory literature, as we are only aware of the existence of models that consider the location of service facilities in the presence of an already located alternative transportation system or models dealing with the location of rapid transit lines to minimize the travelling time among a set of points. To solve this problem we will develop an algorithm based on some characterizations of the objective function behavior.     

Geometric complexity of some location problems

Given a set ofn demand points with weightW _i ,i = 1,2,...,n, in the plane, we consider several geometric facility location problems. Specifically we study the complexity of the Euclidean 1-line center problem, discrete 1-point center problem and a competitive location problem. The Euclidean 1-line center problem is to locate a line which minimizes the maximum weighted distance from the line (or the center) to the demand points. The discrete 1-point center problem is to locate one of the demand points so as to minimize the maximum unweighted distance from the point to other demand points. The competitive location problem studied is to locate a new facility point to compete against an existing facility so that a certain objective function is optimized. An (n logn) lower bound is proved for these problems under appropriate models of computation. Efficient algorithms for these problems that achieve the lower bound and other related problems are also given.Supported in part by the National Science Foundation under Grants ECS 83-40031 and DCR 84-20814.     

Locating an n-server facility in a stochastic environment

We consider a demand-responsive service system in which n mobile units (servers) are garaged at one facility. Service demands arrive in time as a homogenous Poisson process, but are located over the service region according to an arbitrary probability law. Given a random service demand, either (1) a mobile unit is dispatched to the demand's location to provide on-scene service or (2) the demand is lost (i.e. it is handled by some back-up system). The resultant queueing system is an M/G/n loss system operating in steady state. The objective is to locate the garage facility so that the average cost of response is minimized, where the cost of response is a weighted sum of mean travel time to a random serviced demand and the cost of a lost demand, the weights being the respective probabilities of occurrence. We show that the optimum facility location reduces to Hakimi's well-known minisum location.     

On Constrained Facility Location Problems

Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The k-Facility Location problem further requires that the number of opened facilities is at most k, where k is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant > 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 + ω + 1 + ε, which significantly improves the previous best known ratio (ω + 1)/α for some 1≤α≤2, and a polynomial-time approximation algorithm for the ω-constrained k- Facility Location problem with approximation ratio ω+1+ε. On the aspect of approximation hardness, we prove that unless NP■DTIME(nO(loglogn)), the ω-constrained Facility Location problem cannot be approximated within 1 + lnω - 1, which slightly improves the previous best known hardness result 1.243 + 0.316ln(ω - 1). The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice.     

Maximum Dispersion and Geometric Maximum Weight Cliques

We consider a facility location problem, where the objective is to “disperse” a number of facilities, i.e., select a given number k of locations from a discrete set of n candidates, such that the average distance between selected locations is maximized. In particular, we present algorithmic results for the case where vertices are represented by points in d-dimensional space, and edge weights correspond to rectilinear distances. Problems of this type have been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where k is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where k is part of the input, we present a polynomial-time approximation scheme.     

A minisum model with forbidden regions for locating a semi-desirable facility in the plane

Most facilities in today's technological society may be classified as semi-desirable. That is, the facility provides a benefit or service to society, while adversely affecting the quality of life or social values in a number of possible ways. The paper proposes a location model for a new semi-desirable facility that accounts for the service costs by a standard minisum objective with arbitrary travel distance function. The social costs are imputed by specifying around each demand point or population center a convex forbidden region, also defined by an arbitrary distance metric, in which the new facility may not be located. A general solution algorithm is suggested, and the methodology is applied to circular forbidden regions and special travel distance functions.     

Primal–Dual Algorithms for Connected Facility Location Problems

We consider the Connected Facility Location problem. We are given a graph $G = (V,E)$ with costs $\{c_e\}$ on the edges, a set of facilities $\F \subseteq V$, and a set of clients $\D \subseteq V$. Facility $i$ has a facility opening cost $f_i$ and client $j$ has $d_j$ units of demand. We are also given a parameter $M\geq 1$. A solution opens some facilities, say $F$, assigns each client $j$ to an open facility $i(j)$, and connects the open facilities by a Steiner tree $T$. The total cost incurred is ${\sum}_{i\in F} f_i+ sum_{j\in\D} d_jc_{i(j)j}+M\sum_{e\in T}c_e$. We want a solution of minimum cost. A special case of this problem is when all opening costs are 0 and facilities may be opened anywhere, i.e., $\F=V$. If we know a facility $v$ that is open, then the problem becomes a special case of the single-sink buy-at-bulk problem with two cable types, also known as the rent-or-buy problem. We give the first primal–dual algorithms for these problems and achieve the best known approximation guarantees. We give an 8.55-approximation algorithm for the connected facility location problem and a 4.55-approximation algorithm for the rent-or-buy problem. Previously the best approximation factors for these problems were 10.66 and 9.001, respectively. Further, these results were not combinatorial—they were obtained by solving an exponential size linear rogramming relaxation. Our algorithm integrates the primal–dual approaches for the facility location problem and the Steiner tree problem. We also consider the connected $k$-median problem and give a constant-factor approximation by using our primal–dual algorithm for connected facility location. We generalize our results to an edge capacitated variant of these problems and give a constant-factor approximation for these variants.     

BEAMR: An exact and approximate model for the p-median problem

The p-median problem is perhaps one of the most well-known location–allocation models in the location science literature. It was originally defined by Hakimi in 1964 and 1965 and involves the location of p facilities on a network in such a manner that the total weighted distance of serving all demand is minimized. This problem has since been the subject of considerable research involving the development of specialized solution approaches as well as the development of many different types of extended model formats. One element of past research that has remained almost constant is the original ReVelle–Swain formulation [ReVelle CS, Swain R. Central facilities location. Geographical Analysis 1970;2:30–42]. With few exceptions as detailed in the paper, virtually no new formulations have been proposed for general use in solving the classic p-median problem. This paper proposes a new model formulation for the p-median problem that contains both exact and approximate features. This new p-median formulation is called Both Exact and Approximate Model Representation (BEAMR). We show that BEAMR can result in a substantially smaller integer-linear formulation for a given application of the p-median problem and can be used to solve for either an exact optimum or a bounded, close to optimal solution. We also present a methodological framework in which the BEAMR model can be used. Computational results for problems found in the OR_library of Beasley [A note on solving large p-median problems. European Journal of Operational Research 1985;21:270–3] indicate that BEAMR not only extends the application frontier for the p-median problem using general-purpose software, but for many problems represents an efficient, competitive solution approach.