Optimal facility location with random throughput costs

In this paper we consider the optimal location and size of facilities where the throughput costs for each facility are random. Given a set of origins and a set of destinations, we want to determine the optimal location and size of a set of intermediate facilities in order to minimize the expected total generalized transportation cost. The generalized transportation cost of a freight unit from an origin to a destination passing through a facility is the sum of two terms: the transportation cost from the origin to the destination through the facility and the throughput cost of the facility. While the first term is deterministic, the second one is stochastic with a Gumbel probability distribution. Looking for the expected value of the optimal solution, a mixed deterministic nonlinear problem for the optimal location of the facilities is derived. Two heuristics, which give very good approximations to the optimum, are proposed.     

A cross decomposition procedure for the facility location problem with a choice of facility type

Consider a capacitated facility location problem in which each customer is assumed to have a unit demand, and each facility capacity has to be chosen from the given set of admissible levels. Under the restriction that each customer's unit demand be met by exactly one facility, the objective is to select a set of facilities to open, along with their capacities, and to assign customer's demand to them so as to minimize the total cost which includes fixed costs of opening facilities as well as variable assignment costs. The problem is modelled as a pure 0–1 program which extends the scope of applicability significantly over that by conventional location models. Based on Cross Decomposition recently developed by Van Roy, a solution procedure is proposed, when exploits the special structure of the problem. Computational results with a set of test problems shows the superiority of our solution procedure to other related ones.     

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.     

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.     

Heuristics for the single source capacitated multi-facility Weber problem

The Single Source Capacitated Multi-facility Weber Problem (SSCMWP) is concerned with locating I capacitated facilities in the plane to satisfy the demand of J customers with the minimum total transportation cost of a single commodity such that each customer satisfies all its demand from exactly one facility. The SSCMWP is a non-convex optimization problem and difficult to solve. In the SSCMWP, customer locations, customer demands and facility capacities are known a priori. The transportation costs are proportional to the distance between customers and facilities. We consider both the Euclidean and rectilinear distance cases of the SSCMWP. We first present an Alternate Location and Allocation type heuristic and its extension by embedding a Very Large Scale Neighborhood search procedure. Then we apply a Discrete Approximation approach and propose both lower and upper bounding procedures for the SSCWMP using a Lagrangean Relaxation scheme. The proposed heuristics are compared with the solution approaches from the literature. According to extensive computational experiments on standard and randomly generated test sets, we can say that they yield promising performance.     

一个关于求解k-种产品选址问题的近似算法

对于k-种产品工厂选址问题,有如下描述：存在一组客户和一组可以建立工厂的厂址。现在有k种不同的产品,要求每一个客户必须由k个不同的工厂来提供k种不同的产品,其中每个工厂都只能为客户提供唯一的一种产品。在该问题中,假定建厂费用以及任意两个结点之间的运输费用都为非负,并且任意两个结点之间的运输费用都满足对称和三角不等式关系的性质。问题的要求是要从若干厂址中选择一组厂址来建立工厂,给每个工厂指定一种需要生产的产品,并且给每一个客户提供一组指派使每个客户都能有k个工厂来为其供应这k种不同的产品。对于此类问题,优化目标是最小化建厂费用以及运输费用。论文在假设建厂费用为零的前提下,提出了求解该类问题的一种最坏性能比为3k/2-1的近似算法。     

Super facilities versus chaining in mitigating disruptions impacts

Dealing disruptions has increasingly attracted researchers’ attention in the last decades due to recent events: weather deregulation, natural disasters, financial crisis, etc. Researchers often dealt with the strategic aspect of the problem while making facility location decisions to build a robust supply chain. In this paper we address the flexibility aspect. We consider the problem of allocating demand arising from a set of products to a set of dedicated facilities. The facilities are subject to disruption and the demand is then lost. To mitigate disruption impacts, we consider the use of a super facility that can hold the demand of products when the dedicated facilities are under failure. In systems with identical products and facilities, we propose an algorithm that can be used to determine the optimal capacity of the super facility so as to minimize the sum of capacity investment, demand allocation and lost sales cost. Finally we compare the performance of the super facility configuration to that of the single chain configuration. The single chain refers to a facility configuration where each facility is configured to fulfill only two products and each product can be assigned to only two facilities and the whole system forms a closed chain.     

Two-stage stochastic minimum cost consensus models with asymmetric adjustment costs

When dealing with consensus cost problems with asymmetric adjustment costs, the uncertain scenarios with certain probabilities which are becoming a serious problem decision-makers have to face. However, existing optimization-based consensus models have failed to consider uncertain factors that could influence the final consensus and total consensus cost. In order to better deal with these issues, it is necessary to develop practical consensus optimal models. Thus, we establish three two-stage stochastic minimum cost consensus models with asymmetric adjustment costs that may eventually lead the way to better consensus outcomes. The impact of uncertain parameters (such as individual opinions, unit asymmetric adjustment costs, compromise limits, cost-free thresholds) are investigated by modeling three kinds of uncertain consensus models. We solve the proposed two-stage stochastic consensus problem iteratively using the L-shaped algorithm and show the convergence of the algorithm. Furthermore, a case of pollution control negotiations verifies the practicability of the proposed models. Moreover, the comparison of results with the L-shaped algorithm and CPLEX shows that the L-shaped algorithm is more effective in solving time. Some discussions and comparisons on local and global sensitivity analysis of the uncertain parameters are presented to reveal the features of the proposed models. Finally, the relationships between the minimum cost consensus model and minimum cost consensus models with asymmetric adjustment costs and the proposed models are also provided.     

Regression approximation for a partially centralized inventory system considering transportation costs

Inventory centralization for multiple stores with stochastic demands reduces costs by establishing and maintaining a central ordering/distribution point. However the inventory centralization may increase the transportation costs since either the customer must travel more to reach the product, or the central warehouse must ship the product over longer distance to reach the customer. In this paper, we study a partially centralized inventory system where multiple central warehouses exist and a central warehouse fulfills the aggregated demand of stores. We want to determine the number, the location of central warehouses and an assignment of central warehouses and a set of stores. The objective is the minimization of the sum of warehouse costs and transportation cost. With the help of the regression approximation of cost function, we transform the original problem to more manageable facility location problems. Regression analysis shows that the approximated cost function is close to the original one for normally distributed demands.     

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.     

Supplier selection and procurement decisions with uncertain demand,fixed selection costs and quantity discounts

In this paper, we study the supplier selection and procurement decision problem with uncertain demand, quantity discounts and fixed selection costs. In addition, a holding cost is incurred for the excess inventory if the buyer orders more than the realized demand and the shortage must be satisfied by an emergent purchase at a higher price otherwise. The objective is to select the suppliers and to allocate the ordering quantity among them to minimize the total cost (including selecting, procurement, holding and shortage costs, etc.). The problem is modeled as a Mixed Integer Programming (MIP) and is shown to be NP-hard. Some properties of the optimal policy are provided and an optimal algorithm is proposed based on the generalized Bender's decomposition. Numerical experiments are conducted to show the efficiency of the algorithm and to obtain some managerial insights.     

Approximation Algorithms for Soft-Capacitated Facility Location in Capacitated Network Design

Answering an open question published in Operations Research (54, 73–91, 2006) in the area of network design and logistic optimization, we present the first constant-factor approximation algorithms for the problem combining facility location and cable installation in which capacity constraints are imposed on both facilities and cables. We study the problem of designing a minimum cost network to serve client demands by opening facilities for service provision and installing cables for service shipment. Both facilities and cables have capacity constraints and incur buy-at-bulk costs. This Max SNP-hard problem arises in diverse applications and is shown in this paper to admit a combinatorial 19.84-approximation algorithm of cubic running time. This is achieved by an integration of primal-dual schema, Lagrangian relaxation, demand clustering and bi-factor approximation. Our techniques extend to several variants of this problem, which include those with unsplitable demands or requiring network connectivity, and provide constant-factor approximate algorithms in strongly polynomial time. X. Chen is Visiting Fellow, University of Warwick.     

Solution approaches for facility location of medical supplies for large-scale emergencies

In this paper, we propose models and solution approaches for determining the facility locations of medical supplies in response to large-scale emergencies. We address the demand uncertainty and medical supply insufficiency by providing each demand point with services from a multiple quantity of facilities that are located at different quality levels (distances). The problem is formulated as a maximal covering problem with multiple facility quantity-of-coverage and quality-of-coverage requirements. Three heuristics are developed to solve the location problem: a genetic algorithm heuristic, a locate–allocate heuristic, and a Lagrangean relaxation heuristic. We evaluate the performance of the model and the heuristics by using illustrative emergency examples. We show that the model provides an effective method to address uncertainties with little added cost in demand point coverage. We also show that the heuristics are able to generate good facility location solutions in an efficient manner. Moreover, we give suggestions on how to select the most appropriate heuristic to solve different location problem instances.     

Heuristics for a continuous multi-facility location problem with demand regions

We consider a continuous multi-facility location allocation problem where the demanding entities are regions in the plane instead of points. The problem can be stated as follows: given m (closed, convex) polygonal demand regions in the plane, find the locations of q facilities and allocate each region to exactly one facility so as to minimize a weighted sum of squares of the maximum Euclidean distances between the demand regions and the facilities they are assigned to.We propose mathematical programming formulations of the single and multiple facility versions of the problem considered. The single facility location problem is formulated as a second order cone programming (SOCP) problem, and hence is solvable in polynomial time. The multiple facility location problem is NP-hard in general and can be formulated as a mixed integer SOCP problem. This formulation is weak and does not even solve medium-size instances. To solve larger instances of the problem we propose three heuristics. When all the demand regions are rectangular regions with their sides parallel to the standard coordinate axes, a faster special heuristic is developed. We compare our heuristics in terms of both solution quality and computational time.     

Optimal pricing policies for services with consideration of facility maintenance costs

For survival and success, pricing is an essential issue for service firms. This article deals with the pricing strategies for services with substantial facility maintenance costs. For this purpose, a mathematical framework that incorporates service demand and facility deterioration is proposed to address the problem. The facility and customers constitute a service system driven by Poisson arrivals and exponential service times. A service demand with increasing price elasticity and a facility lifetime with strictly increasing failure rate are also adopted in modelling. By examining the bidirectional relationship between customer demand and facility deterioration in the profit model, the pricing policies of the service are investigated. Then analytical conditions of customer demand and facility lifetime are derived to achieve a unique optimal pricing policy. The comparative statics properties of the optimal policy are also explored. Finally, numerical examples are presented to illustrate the effects of parameter variations on the optimal pricing policy.     

Allocation of discrete demand with changing costs

This paper investigates the allocation of discrete demand among facilities by stipulating that the unit mill price charged to users by a facility is a function of the total number of users patronizing that facility. This method of allocating customers to facilities can be used, in conjunction with global search strategies, to find the best location for a new facility.     

Capacitated facility location problem with general setup cost

This paper presents an extension of the capacitated facility location problem (CFLP), in which the general setup cost functions and multiple facilities in one site are considered. The setup costs consist of a fixed term (site setup cost) plus a second term (facility setup costs). The facility setup cost functions are generally non-linear functions of the size of the facility in the same site. Two equivalent mixed integer linear programming (MIP) models are formulated for the problem and solved by general MIP solver. A Lagrangian heuristic algorithm (LHA) is also developed to find approximate solutions for this NP-hard problem. Extensive computational experiments are taken on randomly generated data and also well-known existing data (with some necessary modifications). The detailed results are provided and the heuristic algorithm is shown to be efficient.     

A branch-and-cluster coordination scheme for selecting prison facility sites under uncertainty

A multi-period stochastic model and an algorithmic approach to location of prison facilities under uncertainty are presented and applied to the Chilean prison system. The problem consists of finding locations and sizes of a preset number of new jails and determining where and when to increase the capacity of both new and existing facilities over a time horizon, while minimizing the expected costs of the prison system. Constraints include maximum inmate transfer distances, upper and lower bounds for facility capacities, and scheduling of facility openings and expansion, among others. The uncertainty lies in the future demand for capacity, because of the long time horizon under study and because of the changes in criminal laws, which could strongly modify the historical tendencies of penal population growth. Uncertainty comes from the effects of penal reform in the capacity demand. It is represented in the model through probabilistic scenarios, and the large-scale model is solved via a heuristic mixture of branch-and-fix coordination and branch-and-bound schemes to satisfy the constraints in all scenarios, the so-called branch-and-cluster coordination scheme. We discuss computational experience and compare the results obtained for the minimum expected cost and average scenario strategies. Our results demonstrate that the minimum expected cost solution leads to better solutions than does the average scenario approach. Additionally, the results show that the stochastic algorithmic approach that we propose outperforms the plain use of a state-of-the-art optimization engine, at least for the three versions of the real-life case that have been tested by us.     

Efficient approximate solution methods for the multi-commodity capacitated multi-facility Weber problem

The capacitated multi-facility Weber problem is concerned with locating I capacitated facilities in the plane to satisfy the demand of J customers with the minimum total transportation cost of a single commodity. This is a nonconvex optimization problem and difficult to solve. In this work, we focus on a multi-commodity extension and consider the situation where K distinct commodities are shipped subject to capacity constraints between each customer and facility pair. Customer locations, demands and capacities for each commodity, and bundle restrictions are known a priori. The transportation costs, which are proportional to the distance between customers and facilities, depend on the commodity type. We address several location-allocation and discrete approximation heuristics using different strategies. Based on the obtained computational results we can say that the alternate solution of location and allocation problems is a very efficient strategy; but the discrete approximation has excellent accuracy.     

Lagrangean relaxation heuristics for the p-cable-trench problem

We address the p-cable-trench problem. In this problem, p facilities are located, a trench network is dug and cables are laid in the trenches, so that every customer - or demand - in the region is connected to a facility through a cable. The digging cost of the trenches, as well as the sum of the cable lengths between the customers and their assigned facilities, are minimized. We formulate an integer programming model of the problem using multicommodity flows that allows finding the solution for instances of up to 200 nodes. We also propose two Lagrangean Relaxation-based heuristics to solve larger instances of the problem. Computational experience is provided for instances of up to 300 nodes.