The gravity p-median model

In this paper we propose a new model for the p-median problem. In the standard p-median problem it is assumed that each demand point is served by the closest facility. In many situations (for example, when demand points are communities of customers and each customer makes his own selection of the facility) demand is divided among the facilities. Each customer selects a facility which is not necessarily the closest one. In the gravity p-median problem it is assumed that customers divide their patronage among the facilities with the probability that a customer patronizes a facility being proportional to the attractiveness of that facility and to a decreasing utility function of the distance to the facility.     

The <Emphasis Type="Italic">p</Emphasis>-Centre Problem—Heuristic and Optimal Algorithms

The p-centre problem, or minimax location-allocation problem in location theory terminology, is the following: given n demand points on the plane and a weight associated with each demand point, find p new facilities on the plane that minimize the maximum weighted Euclidean distance between each demand point and its closest new facility. We present two heuristics and an optimal algorithm that solves the problem for a given p in time polynomial in n. Computational results are presented.     

基于选址效益的联合覆盖模型研究

传统的覆盖模型含有“全有全无”和“单一覆盖”两个假设,即假设需求点在设施的服务半径内才被覆盖,否则不被覆盖;需求点只能被最近的设施覆盖。这两条假设在实际应用中均存在不合理之处。松弛了这两条假设,研究逐渐覆盖和联合覆盖。在保证每个需求点都享受到最低服务水平的情况下,提出了选址效益最大化的联合覆盖模型。由于目标函数中含有分式,通过引入辅助变量的方法,将含有分式目标函数的非线性规划转化成等价的线性规划。最后,通过数值算例分析了最低服务水平限制对最佳选址方案的影响,并得到选址成本、总服务水平和单位成本服务水平随最低服务水平限制的变化,同时对影响模型的重要参数做了敏感性分析。     

Locating semi-obnoxious facilities with expropriation: minisum criterion

This paper considers the problem of locating semi-obnoxious facilities assuming that demand points within a certain distance from an open facility are expropriated at a given price. The objective is to locate the facilities so as to minimize the total weighted transportation cost and expropriation cost. Models are developed for both single and multiple facilities. For the case of locating a single facility, finite dominating sets are determined for the problems on a plane and on a network. An efficient algorithm is developed for the problem on a network. For the case of locating multiple facilities, a branch-and-bound procedure using Lagrangian relaxation is proposed and its efficiency is tested with computational experiments.     

On the collection depots location problem

In this paper we investigate the problem of locating a new facility servicing a set of demand points. A given set of collection depots is also given. When service is required by a demand point, the server travels from the facility to the demand point, then from the demand point to one of the collection depots (which provides the shortest route back to the facility), and back to the facility. The problem is analyzed and properties of the solution point are formulated and proved. Computational results on randomly generated problems are reported.     

An interactive solution approach for a bi-objective semi-desirable location problem

In this study, we consider a semi-desirable facility location problem in a continuous planar region considering the interaction between the facility and the existing demand points. A facility can be defined as semi-desirable if it has both undesirable and desirable effects to the people living in the vicinity. Our aim is to maximize the weighted distance of the facility from the closest demand point as well as to minimize the service cost of the facility. The distance between the facility and the demand points is measured with the rectilinear metric. For the solution of the problem, a three-phase interactive geometrical branch and bound algorithm is suggested to find the most preferred efficient solution. In the first two phases, we aim to eliminate the parts of the feasible region the inefficiency of which can be proved. The third phase has been suggested for an interactive search in the remaining regions with the involvement of a decision maker (DM). In the third phase, the DM is given the opportunity to use either an exact or an approximate procedure to carry out the search. The exact procedure is based on the reference point approach and guarantees to find an efficient point as the most preferred solution. On the other hand, in the approximate procedure, a hybrid methodology is used to increase the efficiency of the reference point approach. The approximate procedure can be used when the DM prefers to see locally efficient solutions so as to save computation time. We demonstrate the performance of the proposed method through example problems.     

The budget constrained r-interdiction median problem with capacity expansion

In this article, we elaborate on a budget constrained extension of the r-interdiction median problem with fortification (RIMF). The objective in the RIMF is to find the optimal allocation of protection resources to a given service system consisting of p facilities so that the disruptive effects of r possible attacks to the system are minimized. The defender of the system needs to fortify q facilities of the present system to offset the worst-case loss of r non-fortified facilities due to an interdiction in which the attacker’s objective is to cause the maximum possible disruption in the service level of the system. The defender-attacker relationship fits a bilevel integer programming (BIP) formulation where the defender and attacker take on the respective roles of the leader and the follower. We adopt this BIP formulation and augment it with a budget constraint instead of a predetermined number of facilities to be fortified. In addition, we also assume that each facility has a flexible service capacity, which can be expanded at a unit cost to accommodate the demand of customers who were serviced by some other interdicted facility before the attack. First, we provide a discrete optimization model for this new facility protection planning scenario with a novel set of closest assignment constraints. Then, to tackle this BIP problem we use an implicit enumeration algorithm performed on a binary tree. For each node representing a different fortification scheme, the attacker’s problem is solved to optimality using Cplex 11. We report computational results obtained on a test bed of 96 randomly generated instances. The article concludes with suggestions for future research.     

A minimum length covering subgraph of a network

This paper concerns the problem of locating a central facility on a connected networkN. The network,N, could be representative of a transport system, while the central facility takes the form of a connected subgraph ofN. The problem is to locate a central facility of minimum length so that each of several demand points onN is covered by the central facility: a demand point atv _i inN is covered by the central facility if the shortest path distance betweenv _i and the closest point in the central facility does not exceed a parameterr _i . This location problem is NP-hard, but for certain special cases, efficient solution methods are available.     

An Iterated Local Search for the Budget Constrained Generalized Maximal Covering Location Problem

Capacitated covering models aim at covering the maximum amount of customers’ demand using a set of capacitated facilities. Based on the assumptions made in such models, there is a unique scenario to open a facility in which each facility has a pre-specified capacity and an operating budget. In this paper, we propose a generalization of the maximal covering location problem, in which facilities have different scenarios for being constructed. Essentially, based on the budget invested to construct a given facility, it can provide different service levels to the surrounded customers. Having a limited budget to open the facilities, the goal is locating a subset of facilities with the optimal opening scenario, in order to maximize the total covered demand and subject to the service level constraint. Integer linear programming formulations are proposed and tested using ILOG CPLEX. An iterated local search algorithm is also developed to solve the introduced problem.     

The minimum equitable radius location problem with continuous demand

We analyze the location of p facilities satisfying continuous area demand. Three objectives are considered: (i) the p-center objective (to minimize the maximum distance between all points in the area and their closest facility), (ii) equalizing the load service by the facilities, and (iii) the minimum equitable radius – minimizing the maximum radius from each point to its closest facility subject to the constraint that each facility services the same load. The paper offers three contributions: (i) a new problem – the minimum equitable radius is presented and solved by an efficient algorithm, (ii) an improved and efficient algorithm is developed for the solution of the p-center problem, and (iii) an improved algorithm for the equitable load problem is developed. Extensive computational experiments demonstrated the superiority of the new solution algorithms.     

A constant factor approximation algorithm for the fault-tolerant facility location problem

We consider a generalization of the classical facility location problem, where we require the solution to be fault-tolerant. In this generalization, every demand point j must be served by r_j facilities instead of just one. The facilities other than the closest one are “backup” facilities for that demand, and any such facility will be used only if all closer facilities (or the links to them) fail. Hence, for any demand point, we can assign nonincreasing weights to the routing costs to farther facilities. The cost of assignment for demand j is the weighted linear combination of the assignment costs to its r_j closest open facilities. We wish to minimize the sum of the cost of opening the facilities and the assignment cost of each demand j. We obtain a factor 4 approximation to this problem through the application of various rounding techniques to the linear relaxation of an integer program formulation. We further improve the approximation ratio to 3.16 using randomization and to 2.41 using greedy local-search type techniques.     

Mixed integer programming-based solution procedure for single-facility location with maximin of rectilinear distance

In this paper, we study the 1-maximin problem with rectilinear distance. We locate a single undesirable facility in a continuous planar region while considering the interaction between the facility and existing demand points. The distance between facility and demand points is measured in the rectilinear metric. The objective is to maximize the distance of the facility from the closest demand point. The 1-maximin problem has been formulated as an MIP model in the literature. We suggest new bounding schemes to increase the solution efficiency of the model as well as improved branch and bound strategies for implementation. Moreover, we simplify the model by eliminating some redundant integer variables. We propose an efficient solution algorithm called cut and prune method, which splits the feasible region into four equal subregions at each iteration and tries to eliminate subregions depending on the comparison of upper and lower bounds. When the sidelengths of the subregions are smaller than a predetermined value, the improved MIP model is solved to obtain the optimal solution. Computational experiments demonstrate that the solution time of the original MIP model is reduced substantially by the proposed solution approach.     

Comparing different metaheuristic approaches for the median path problem with bounded length

In this paper we consider the Bounded Length Median Path Problem which can be defined as the problem of locating a path-shaped facility that departures from a given origin and arrives at a given destination in a network. The length of the path is assumed to be bounded by a given maximum length. At each vertex of the network (customer-point) the demand for the service is given and the cost to reach the closest service-point is computed. The objective is to minimize the sum of these costs over all the customer-points in the network.     

p-Median theorems for competitive locations

In competitive location theory, one wishes to optimally choose the locations ofr facilities to compete againstp existing facilities for providing service (or goods) to the customers who are at given discrete points (or nodes). One normally assumes that: (a) the level of demand of each customer is fixed (i.e. this demand is not a function of how far a customer is from a facility), and (b) the customer always uses the closest available facility. In this paper we study competitive locations when one or both of the above assumptions have been relaxed. In particular, we show that for each case and under certain assumptions, there exists a set of optimal locations which consists entirely of nodes.This work was supported by a National Science Foundation Grant ECS-8121741.     

The equitable location problem on the plane

This paper considers the problem of locating M facilities on the unit square so as to minimize the maximal demand faced by each facility subject to closest assignments and coverage constraints. Focusing on uniform demand over the unit square, we develop upper and lower bounds on feasibility of the problem for a given number of facilities and coverage radius. Based on these bounds and numerical experiments we suggest a heuristic to solve the problem. Our computational results show that the heuristic is very efficient, as the average gap between its solutions and the lower bound is 4.34%.     

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.     

Continuous covering and cooperative covering problems with a general decay function on networks

A cooperative covering location problem anywhere on the networks is analysed. Each facility emits a signal that decays by the distance along the arcs of the network and each node observes the total signal emitted by all facilities. A node is covered if its cumulative signal exceeds a given threshold. The cooperative approach differs from traditional covering models where the signal from the closest facility determines whether or not a point is covered. The objective is to maximize coverage by the best location of facilities anywhere on the network. The problems are formulated and analysed. Optimal algorithms for one or two facilities are proposed. Heuristic algorithms are proposed for location of more than two facilities. Extensive computational experiments are reported.     

Location-allocation on a line with demand-dependent costs

This paper extends the location-allocation formulation by making the cost charged to users by a facility a function of the total number of users patronizing the facility. Users select their facility based on facility charges and transportation costs. We explore equilibria where each customer selects the least expensive facility (cost and transportation) and where the facility is at a point that minimizes travel costs for its customers. The problem in its general form is quite complex. An interesting special case is studied: facilities and customers are located on a finite line segment and demand is distributed on the line by a given density function.     

Discrete cooperative covering problems

A family of discrete cooperative covering problems is analysed in this paper. Each facility emits a signal that decays by the distance and each demand point observes the total signal emitted by all facilities. A demand point is covered if its cumulative signal exceeds a given threshold. We wish to maximize coverage by selecting locations for p facilities from a given set of potential sites. Two other problems that can be solved by the max-cover approach are the equivalents to set covering and p-centre problems. The problems are formulated, analysed and solved on networks. Optimal and heuristic algorithms are proposed and extensive computational experiments reported.     

Algorithms for a Facility Location Problem with Stochastic Customer Demand and Immobile Servers

This paper studies a facility location problem with stochastic customer demand and immobile servers. Motivated by applications to locating bank automated teller machines (ATMs) or Internet mirror sites, these models are developed for situations in which immobile service facilities are congested by stochastic demand originating from nearby customer locations. Customers are assumed to visit the closest open facility. The objective of this problem is to minimize customers' total traveling cost and waiting cost. In addition, there is a restriction on the number of facilities that may be opened and an upper bound on the allowable expected waiting time at a facility. Three heuristic algorithms are developed, including a greedy-dropping procedure, a tabu search approach and an -optimal branch-and-bound method. These methods are compared computationally on a bank location data set from Amherst, New York.