工厂地址集中的k-种产品选址问题的近似算法

k-种产品工厂选址问题是：给定一个客户集合和一个可以建立工厂的地址集合,每个客户需要k-种产品,一个工厂只能为客户提供一种产品。考虑的工厂假设相对集中,即假设任何工厂之间的距离都不大于工厂与客户之间的距离。对于没有建厂费用的问题,当k=2时证明了它是一个NP完全问题,对任意的k给出了一个最坏性能比不大于2-1/k的近似算法。对于有建厂费用的问题,给出了一个最坏性能比不大于2的近似算法。     

Exact optimal solutions of the minisum facility and transfer points location problems on a network

We consider hierarchical facility location problems on a network called Multiple Location of Transfer Points (MLTP) and Facility and Transfer Points Location Problem (FTPLP), where q facilities and p transfer points are located and each customer goes to one of the facilities directly or via one of the transfer points. In FTPLP, we need to find an optimal location of both the facilities and the transfer points while the location of facilities is given in MLTP. Although good heuristics have been proposed for the minisum MLTP and FTPLP, no exact optimal solution has been tested due to the size of the problems. We show that the minisum MLTP can be formulated as a p‐median problem, which leads to obtaining an optimal solution. We also present a new formulation of FTPLP and an enumeration‐based approach to solve the problems with a single facility.     

Solving an extended multi-row facility layout problem with fuzzy clearances using GA

Multi-row facility layout problem (MRFLP) is a class of facility layout problems, which decides upon the arrangement of facilities in some fixed numbers of rows in order to minimize material handling cost. Nowadays, according to the new layout requirements, the facility layout problems (FLPs) have many applications such as hospital layout, construction site layout planning and layout of logistics facilities. Therefore, we study an extended MRFLP, as a novel layout problem, with the following main assumptions: 1) the facilities are arranged in a two-dimensional area and without splitter rows, 2) multiple products are available, 3) distance between each pair of facilities, due to inaccurate and flexible manufacturing processes and other limitations (such as WIPs, industrial instruments, transportation lines and etc.), is considered as fuzzy number, and 4) the objective function is considered as minimizing the material handling and lost opportunity costs. To model these assumptions, a nonlinear mixed-integer programming model with fuzzy constraints is presented and then converted to a linear mixed-integer programming model. Since the developed model is an NP-hard problem, a genetic algorithm approach is suggested to find the best solutions with a minimum cost function. Additionally, three different crossover methods are compared in the proposed genetic algorithm and finally, a sensitivity analysis is performed to discuss important parameters.     

软容量限制设施选址问题的竞争决策算法

软容量设施选址问题是NP-Hard问题之一，具有广泛的应用价值。为了求解软容量设施选址问题，提出一种基于数学性质的竞争决策算法。首先研究该问题的数学性质，运用这些数学性质不仅可以确定某些设施必定开设或关闭，还可以确定部分顾客由哪个设施提供服务，从而缩小问题的规模，加快求解速度。在此基础上设计了求解该问题的竞争决策算法，最后经过一个小规模的算例测试并与精确算法的结果比较，得出了最优解；针对大规模的问题快速地求出了可行解，得到了令人满意的结果。     

Planar expropriation problem with non-rigid rectangular facilities

In this paper, we introduce the planar expropriation problem with non-rigid rectangular facilities. The facilities considered in this study are two-dimensional facilities of rectangular shape. Moreover, we allow the facility dimensions to be decision variables and introduce the concept of non-rigid facilities. Based on the geometric properties of such facilities, we developed a new formulation for this continuous covering location model which does not require employing distance measures. This model is intended to determine the location and formation of facilities simultaneously. For solving this new model, we proposed a continuous branch-and-bound framework utilizing linear approximations for the tradeoff curve associated with the facility formation alternatives. Further, we developed new problem generation and bounding strategies suitable for our particular problem structure. Computational experience shows that the branch-and-bound procedure we developed performs better than conventional mixed-integer nonlinear programming solvers BARON and SBB for solving this particular location model.     

Hierarchical facility location problem: Models,classifications, techniques,and applications

The primary objective in a typical hierarchical facility location problem is to determine the location of facilities in a multi-level network in a way to serve the customers at the lowest level of hierarchy both efficiently (cost minimization objective) and effectively (service availability maximization objective). This paper presents a comprehensive review of over 40 years of hierarchical facility location modeling efforts. Published models are classified based on multiple characteristics including the type of flow pattern, service availability, spatial configuration, objective function, coverage, network levels, time element, parameters, facilities, capacity, and real world application. A second classification is also presented on the basis of solution methods adopted to solve various hierarchical facility location problems. The paper finally identifies the gaps in the current literature and suggests directions for future modeling efforts.     

Stochastic facility and transfer point covering problem with a soft capacity constraint

Existing models for transfer point location problems (TPLPs) do not guarantee the desired service time to customers. In this paper, a facility and TPLP is formulated based on a given service time that is targeted by a decision maker. Similar to real‐world situations, transportation times and costs are assumed to be random. In general, facilities are capacitated. However, in emergency services, they are not allowed to reject the customers for out of capacity reasons. Therefore, a soft capacity constraint for the facilities and a second objective to minimize the overtime in the facility with highest assigned demand are proposed. To solve the biobjective model with random variables, a variance minimization technique and chance‐constraint programming are applied. Thereafter, using fuzzy multiple objective linear programming, the proposed biobjective model is converted to a single objective. Computational results on 30 randomly designed experimental problems confirm satisfactory performance of the proposed model in reducing the variance of solutions as well as the overtime in the busiest facility.     

Local search heuristics for the mobile facility location problem

In the mobile facility location problem (MFLP), one seeks to relocate (or move) a set of existing facilities and assign clients to these facilities so that the sum of facility movement costs and the client travel costs (each to its assigned facility) is minimized. This paper studies formulations and develops local search heuristics for the MFLP. First, we develop an integer programming (IP) formulation for the MFLP by observing that for a given set of facility destinations the problem may be decomposed into two polynomially solvable subproblems. This IP formulation is quite compact in terms of the number of nonzero coefficients in the constraint matrix and the number of integer variables; and allows for the solution of large-scale MFLP instances. Using the decomposition observation, we propose two local search neighborhoods for the MFLP. We report on extensive computational tests of the new IP formulation and local search heuristics on a large range of instances. These tests demonstrate that the proposed formulation and local search heuristics significantly outperform the existing formulation and a previously developed local search heuristic for the problem.     

A bilevel fixed charge location model for facilities under imminent attack

We investigate a bilevel fixed charge facility location problem for a system planner (the defender) who has to provide public service to customers. The defender cannot dictate customer-facility assignments since the customers pick their facility of choice according to its proximity. Thus, each facility must have sufficient capacity installed to accommodate all customers for whom it is the closest one. Facilities can be opened either in the protected or unprotected mode. Protection immunizes against an attacker who is capable of destroying at most r unprotected facilities in the worst-case scenario. Partial protection or interdiction is not possible. The defender selects facility sites from m candidate locations which have different costs. The attacker is assumed to know the unprotected facilities with certainty. He makes his interdiction plan so as to maximize the total post-attack cost incurred by the defender. If a facility has been interdicted, its customers are reallocated to the closest available facilities making capacity expansion necessary. The problem is formulated as a static Stackelberg game between the defender (leader) and the attacker (follower). Two solution methods are proposed. The first is a tabu search heuristic where a hash function calculates and records the hash values of all visited solutions for the purpose of avoiding cycling. The second is a sequential method in which the location and protection decisions are separated. Both methods are tested on 60 randomly generated instances in which m ranges from 10 to 30, and r varies between 1 and 3. The solutions are further validated by means of an exhaustive search algorithm. Test results show that the defender's facility opening plan is sensitive to the protection and distance costs.     

A review of hierarchical facility location models

In this study, we review the hierarchical facility location models. Although there have been a number of review papers on hierarchical facility problems, a comprehensive treatment of models has not been provided since the mid-80s. This review fills the gap in the literature. We first classify the hierarchical facility problems according to the features of systems studied, which are based on flow pattern, service availability at each level of the hierarchy, and spatial configuration of services in addition to the objectives to locate facilities. We then investigate the applications, mixed integer programming models, and solution methods presented for the problem. With an overview of the selected works, we consolidate the main results in the literature.     

The multi-period incremental service facility location problem

In this paper we introduce the multi-period incremental service facility location problem where the goal is to set a number of new facilities over a finite time horizon so as to cover dynamically the demand of a given set of customers. We prove that the coefficient matrix of the allocation subproblem that results when fixing the set of facilities to open is totally unimodular. This allows to solve efficiently the Lagrangean problem that relaxes constraints requiring customers to be assigned to open facilities. We propose a solution approach that provides both lower and upper bounds by combining subgradient optimization to solve a Lagrangean dual with an ad hoc heuristic that uses information from the Lagrangean subproblem to generate feasible solutions. Numerical results obtained in the computational experiments show that the obtained solutions are very good. In general, we get very small percent gaps between upper and lower bounds with little computation effort.     

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

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

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.     

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 simple and deterministic competitive algorithm for online facility location

This paper presents a deterministic and efficient algorithm for online facility location. The algorithm is based on a simple hierarchical partitioning and is extremely simple to implement. It also applies to a variety of models, i.e., models where the facilities can be placed anywhere in the region, or only at customer sites, or only at fixed locations. The paper shows that the algorithm is O (log n)-competitive under these various models, where n is the total number of customers. It also shows that the algorithm is O (1)-competitive with high probability and for any arrival order when customers are uniformly distributed or when they follow a distribution satisfying a smoothness property. Experimental results for a variety of scenarios indicate that the algorithm behaves extremely well in practice.     

Locating a semi-obnoxious facility with expropriation

This paper considers the problem of locating semi-obnoxious facilities assuming that “too close” demand nodes can be expropriated by the developer at a given price. The objective is to maximize the minimum weighted distance from the facility to the non-expropriated demand nodes given a limited budget while taking into account the fact that customers do not want to be too far away from the facility. Two models of this problem on a network are presented. One is to minimize the difference between the maximum and the minimum weighted distances. The other one is to maximize the minimum weighted distance subject to an upper bound constraint on the maximum weighted distance. The dominating sets are determined and efficient algorithms are presented.     

Efficient location and allocation strategies for undesirable facilities considering their fundamental properties

The phrase “not in my backyard” (NIMBY) refers to the well-known social phenomena in which residents oppose the construction or location of undesirable facilities near their homes. Examples of such facilities include electric transmission lines, recycling centers and crematoria. Due to the opposition typically encountered in constructing an undesirable facility, the facility planner should understand the nature of the NIMBY phenomena and consider it as a key factor in determining facility location. We examine the characteristics of NIMBY phenomena and suggest two alternative mathematical optimization models with the objective of minimizing the total degree of NIMBY sentiments. Genetic algorithms are proposed to solve our linear and nonlinear integer programs. The results obtained via genetic algorithms for our linear integer programs are compared with those of CPLEX to evaluate their performance. The nonlinear programs are tested with various allocation policies. Sensitivity analysis is conducted about several system parameters.     

Sequential versus simultaneous approach in the location and design of two new facilities using planar Huff-like models

Companies frequently decide on the location and design for new facilities in a sequential way. However, for a fixed number of new facilities, the company might be able to improve its profit by taking its decisions for all the facilities simultaneously. In this paper we compare three different strategies: simultaneous location and independent design of two facilities in the plane, the same with equal designs, and the sequential approach of determining each facility in turn. The basic model is profit maximization for the chain, taking market share, location costs and design costs into account. The market share captured by each facility depends on the distance to the customers (location) and its quality (design), through a probabilistic Huff-like model. Recent research on this type of models was aimed at finding global optima for a single new facility, holding quality fixed or variable, but no exact algorithm has been proposed to find optimal solutions for more than one facility. We develop such an exact interval branch-and-bound algorithm to solve both simultaneous location and design two-facility problems. Then, we present computational results and exhibit the differences in locations and qualities of the optimal solutions one may obtain by the sequential and simultaneous approaches.     

A leader-follower game in competitive facility location

We address the problem of locating new facilities of a firm or franchise that enters a market where a competitor operates existing facilities. The goal of the new entrant firm is to decide the location and attractiveness of its new facilities that maximize its profit. The competitor can react by opening new facilities, closing existing ones, and adjusting the attractiveness levels of its existing facilities, with the aim of maximizing its own profit. The demand is assumed to be aggregated at certain points in the plane and the new facilities of both the firm and the competitor can be located at predetermined candidate sites. We employ the gravity-based rule in modeling the behavior of the customers where the probability that a customer visits a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. We formulate a bilevel mixed-integer nonlinear programming model where the firm entering the market is the leader and the competitor is the follower. We propose heuristics that combine tabu search with exact solution methods.