Facility location models for distribution planning

A strategic issue which is of interest to distribution planners is where to best site warehouses. Model formulations, and solution approaches, which address the issue vary widely in terms of mathematical and computational complexity. This paper reviews some of the significant contributions which have been made to the relevant and current state of knowledge.     

Facility location models for distribution system design

The design of the distribution system is a strategic issue for almost every company. The problem of locating facilities and allocating customers covers the core topics of distribution system design. Model formulations and solution algorithms which address the issue vary widely in terms of fundamental assumptions, mathematical complexity and computational performance. This paper reviews some of the contributions to the current state-of-the-art. In particular, continuous location models, network location models, mixed-integer programming models, and applications are summarized.     

Facility location models for planning a transatlantic communications network

This paper presents two facility location models for the problem of determining how to optimally serve the requirements for communication circuits between the United States and various European and Middle Eastern countries. Given a projection of future requirements, the problem is to plan for the economic growth of a communications network to satisfy these requirements. Both satellite and submarine cable facilities may be used. The objective is to find an optimal placement of cables (type, location, and timing) and the routing of individual circuits between demand points (over both satellites and cables) such that the total discounted cost over a T-period horizon is minimized. This problem is cast as a multiperiod, capacitated facility location problem. Two mathematical models differing in their provisions for network reliability are presented. Solution approaches are outlined and compared by means of computational experience. Use of the models both in planning the growth of the network and in the economic evaluation of different cable technologies is also discussed.     

Facility location with increasing production costs

Facility location models determine the set of locations on a network that minimize the sum of the costs of investment, production, and distribution to meet a known set of demands. In this paper, we introduce a new type of facility location model, which combines aspects of the well-studied simple uncapacitated and capacitated facility location problems. Its distinctive feature is that unit production costs are modeled as increasing with scale of output. Such cost functions have practical value in handling cases in which capacity can be “stretched” by incurring some additional cost (e.g., by adding workers). Indeed, it is shown that average total costs are minimized at a point where average production costs are rising. Four different formulations for this problem are proposed. Using linear programming plus branch-and-bound as a solution method, the four formulations are tested and compared on a set of 216 problems with randomly generated data.     

Facility location problems: A parameterized view

Facility location problems have been investigated in the Operations Research literature from a variety of algorithmic perspectives, including those of approximation algorithms, heuristics, and linear programming. We introduce the study of these problems from the point of view of parameterized algorithms and complexity. Some applications of algorithms for these problems in the processing of semistructured documents and in computational biology are also described.     

An effective heuristic for large-scale capacitated facility location problems

The Capacitated Facility Location Problem (CFLP) consists of locating a set of facilities with capacity constraints to satisfy the demands of a set of clients at the minimum cost. In this paper we propose a simple and effective heuristic for large-scale instances of CFLP. The heuristic is based on a Lagrangean relaxation which is used to select a subset of “promising” variables forming the core problem and on a Branch-and-Cut algorithm that solves the core problem. Computational results on very large scale instances (up to 4 million variables) are reported.     

A cross entropy-based metaheuristic algorithm for large-scale capacitated facility location problems

In this paper, we present a metaheuristic-based algorithm for the capacitated facility location problem. The proposed scheme is made up by three phases: (i) solution construction phase, in which a cross entropy-based scheme is used to ‘intelligently’ guess which facilities should be opened; (ii) local search phase, aimed at exploring the neighbourhood of ‘elite’ solutions of the previous phase; and (iii) learning phase, aimed at fine-tuning the stochastic parameters of the algorithm. The algorithm has been thoroughly tested on large-scale random generated instances as well as on benchmark problems and computational results show the effectiveness and robustness of the algorithm.     

带次模惩罚和随机需求的设施选址问题

考虑带次模惩罚和随机需求的设施选址问题,目的是开设设施集合的一个子集,把客户连接到开设的设施上并对没有连接的客户进行惩罚,使得开设费用、连接费用、库存费用、管理费用和惩罚费用之和达到最小. 根据该问题的特殊结构,给出原始对偶3-近似算法. 在算法的第一步,构造了一组对偶可行解;在第二步中构造了对应的一组原始整数可行解,这组原始整数可行解给出了最后开设的设施集合和被惩罚的客户集合. 最后,证明了算法在多项式时间内可以完成,并且算法所给的整数解不会超过最优解的3倍.     

Facility location for market capture when users rank facilities by shorter travel and waiting times

A firm wants to locate several multi-server facilities in a region where there is already a competitor operating. We propose a model for locating these facilities in such a way as to maximize market capture by the entering firm, when customers choose the facilities they patronize, by the travel time to the facility and the waiting time at the facility. Each customer can obtain the service or goods from several (rather than only one) facilities, according to a probabilistic distribution. We show that in these conditions, there is demand equilibrium, and we design an ad hoc heuristic to solve the problem, since finding the solution to the model involves finding the demand equilibrium given by a nonlinear equation. We show that by using our heuristic, the locations are better than those obtained by utilizing several other methods, including MAXCAP, p-median and location on the nodes with the largest demand.     

A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method

We propose a cutting-plane approach (namely, Benders decomposition) for a class of capacitated multi-period facility location problems. The novelty of this approach lies on the use of a specialized interior-point method for solving the Benders subproblems. The primal block-angular structure of the resulting linear optimization problems is exploited by the interior-point method, allowing the (either exact or inexact) efficient solution of large instances. The consequences of different modeling conditions and problem specifications on the computational performance are also investigated both theoretically and empirically, providing a deeper understanding of the significant factors influencing the overall efficiency of the cutting-plane method. The methodology proposed allowed the solution of instances of up to 200 potential locations, one million customers and three periods, resulting in mixed integer linear optimization problems of up to 600 binary and 600 millions of continuous variables. Those problems were solved by the specialized approach in less than one hour and a half, outperforming other state-of-the-art methods, which exhausted the (144 GB of) available memory in the largest instances.     

Facility location problems in the plane based on reverse nearest neighbor queries

For a finite set of points S, the (monochromatic) reverse nearest neighbor (RNN) rule associates with any query point q the subset of points in S that have q as its nearest neighbor. In the bichromatic reverse nearest neighbor (BRNN) rule, sets of red and blue points are given and any blue query is associated with the subset of red points that have it as its nearest blue neighbor. In this paper we introduce and study new optimization problems in the plane based on the bichromatic reverse nearest neighbor (BRNN) rule. We provide efficient algorithms to compute a new blue point under criteria such as: (1) the number of associated red points is maximum (MAXCOV criterion); (2) the maximum distance to the associated red points is minimum (MINMAX criterion); (3) the minimum distance to the associated red points is maximum (MAXMIN criterion). These problems arise in the competitive location area where competing facilities are established. Our solutions use techniques from computational geometry, such as the concept of depth of an arrangement of disks or upper envelope of surface patches in three dimensions.     

A large-scale application of the partial coverage uncapacitated facility location problem

The traditional, uncapacitated facility location problem (UFLP) seeks to determine a set of warehouses to open such that all retail stores are serviced by a warehouse and the sum of the fixed costs of opening and operating the warehouses and the variable costs of supplying the retail stores from the opened warehouses is minimized. In this paper, we discuss the partial coverage uncapacitated facility location problem (PCUFLP) as a generalization of the uncapacitated facility location problem in which not all the retail stores must be satisfied by a warehouse. Erlenkotter's dual-ascent algorithm, DUALOC, will be used to solve optimally large (1600 stores and 13?000 candidate warehouses) real-world implemented PCUFLP applications in less than two minutes on a 500?MHz PC. Furthermore, a simple analysis of the problem input data will indicate why and when efficient solutions to large PCUFLPs can be expected.     

Solving large-scale maximum expected covering location problems by genetic algorithms: A comparative study

This paper compares the performance of genetic algorithms (GAs) on large-scale maximum expected coverage problems to other heuristic approaches. We focus our attention on a particular formulation with a nonlinear objective function to be optimized over a convex set. The solutions obtained by the best genetic algorithm are compared to Daskin's heuristic and the optimal or best solutions obtained by solving the corresponding integer linear programming (ILP) problems. We show that at least one of the GAs yields optimal or near-optimal solutions in a reasonable amount of time.     

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.     

Branch-and-Cut-and-Price for Capacitated Connected Facility Location

We consider a generalization of the Connected Facility Location Problem (ConFL), suitable to model real world network extension scenarios such as fiber-to-the-curb. In addition to choosing a set of facilities and connecting them by a Steiner tree as in ConFL, we aim to maximize the resulting profit by potentially supplying only a subset of all customers. Furthermore, capacity constraints on potential facilities need to be considered. We present two mixed integer programming based approaches which are solved using branch-and-cut and branch-and-cut-and-price, respectively. By studying the corresponding polyhedra we analyze both approaches theoretically and show their advantages over previously presented models. Furthermore, using a computational study we are able to additionally show significant advantages of our models over previously presented ones from a practical point of view.     

On solving a large-scale problem on facility location and customer assignment with interaction costs along a time horizon

A 0-1 quadratic programming model is presented for solving the strategic problem of timing the location of facilities and the assignment of customers to facilities in a multi-period setting. It is assumed that all parameters are known and, on the other hand, the quadratic character of the objective function is due to considering the interaction cost incurred by the joint assignment of customers belonging to different categories to a facility at a period. The plain use of a state-of-the-art MILP engine with capabilities for dealing with quadratic terms does not give any advantage over the matheuristic algorithm proposed in this work. In fact, the MILP engine was frequently running out of memory before reaching optimality for the equivalent mixed 0-1 linear formulation, being its best lower bound at that time instant too far from the incumbent solution for the large-sized instances which we have worked with. As an alternative, a fix-and-relax algorithm is presented. A deep computational comparison between MILP alternatives is performed, such that fix-and-relax provides a solution value very close to (and, frequently, a better than) the one provided by the MILP engine. The time required by fix-and-relax is very affordable, being frequently two times smaller than the time required by the MILP engine.     

基于失效情景的应急设施选址问题

非常规突发事件巨大的破坏力以及发生时间、地点和规模的不确定性,使应急系统内设施有可能被破坏而失效,因此选址时必须考虑设施失效情景的发生.给出以最大限度覆盖用户需求为目标,基于失效设施数目具有不确定性情景的设施选址双层随机规划模型;通过计算模型上下界,给出减小规模的等价模型,降低了双层规划求解难度;最后实验验证了模型的合理性,并给出新增选址方案.     

Robust Optimization for the Connected Facility Location Problem

In this paper we present a robust optimization (RO) model for the Connected Facility Location (ConFL) problem within the framework introduced by Bertsimas and Sim [Bertsimas, D. and M. Sim, Robust discrete optimization and network flows, Mathematical Programming 98 (2003), pp. 49–71], and show how to use a heuristic in conjunction with a lower bounding mechanism to rapidly find high-quality solutions. The use of a heuristic and a lower bound mechanism within this RO approach decreases significantly its computational time and broadens its applicability to other NP-hard problems. Here we present some of our computational results that attest to the efficiency of the approach, particularly on the Robust ConFL problem.