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

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

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.     

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.     

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.     

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

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

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.     

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.     

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 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.