Applying GRASP to solve the multi-item three-echelon uncapacitated facility location problem

This paper considers a production–distribution problem that consists of defining the flow of produced products from manufacturing plants to clients (markets) via a set of warehouses. The problem also consists of defining the location of such warehouses that have unlimited storage capacity. This problem is known in the literature as the three-echelon uncapacitated facility location problem (TUFLP), and is known to be NP-hard when the objective function is to minimize the total cost of warehouse location and production and distribution of products. This paper proposes a Greedy Randomized Adaptive Search Procedure (GRASP) to solve the multi-item version of the TUFLP. Computational experiments are conducted using known instances from the literature. Solutions obtained using GRASP are compared against both optimal solutions and lower bounds obtained using mathematical programming. Results show that proposed algorithm performs well, obtaining good solutions (and even the optimal values) in less computational time than the mixed-integer linear programming model.     

井位不确定环境下的油田仓库选址问题

油田工作中,合理的仓库选址决策不仅能节约物流成本,而且能提高油田作业效率。现有研究通常基于当前的油井位置(简称井位),没有考虑未来井位变化对仓库选址的影响。同时井位受到地下储层条件及油气公司远景规划等因素影响,未来的井位具有很强的不确定性。此外,仓库选址决策属中长期决策,将长期影响油田的物流费用、管理工作甚至开发工作,而且油田生产要求仓库能持续供应物资,所以油田仓库选址应考虑井位的不确定性和仓库服务中断等因素。本文首先根据油田井位分布和钻井规划采用随机模拟方法模拟未来井位,建立并求解考虑设施中断的离散选址模型。然后以鄂南油区物资仓库选址问题为例,模拟井位并求解仓库选址问题,从8个候选点中选出3个建库/租库。最后,分析井位和需求量变化对仓库选址结果的影响。井位不确定环境下油田物资仓库选址问题的研究,不仅对油田物流系统管理的研究具有一定的理论意义,也对油田的物流决策有重要的现实意义。     

Logistics distribution network design with two commodity categories

In this paper, we study the design of a logistics distribution network consisting of a supplier, a set of potential warehouses, and a set of retailers. There are commodities from two product categories, that is, category A and category B, flowing across the network. The demand for commodities in product category A is stable. The demand for commodities in product category B is highly uncertain. We show that the network design problem to distribute the commodities in both product categories can be formulated as the uncapacitated facility location problem with monotone submodular costs and tackled using a cutting plane algorithm. We propose a strongly polynomial time algorithm for the nonlinear discrete optimization problem, which must be solved in each iteration of the cutting plane algorithm. We also provide the computational results, and summarize the insights based on the proposed model and the solution algorithm.     

带有异常点的平方度量设施选址问题

传统的设施选址问题一般假设所有顾客都被服务,考虑到异常点的存在不仅会增加总费用（设施的开设费用与连接费用之和）,也会影响到对其他顾客的服务质量。研究异常点在最终方案中允许不被服务的情况,称之为带有异常点的平方度量设施选址问题。该问题是无容量设施选址问题的推广。问题可描述如下：给定设施集合、顾客集,以及设施开设费用和顾客连接费用,目标是选择设施的子集开设以满足顾客的需求,使得设施开设费用与连接费用之和最小。利用原始对偶技巧设计了近似算法,证明了该算法的近似比是9。     

Computationally Efficient Solution of a Multiproduct,Two-Stage Distribution—Location Problem

A two-stage distribution planning problem, in which customers are to be served with different commodities from a number of plants, through a number of intermediate warehouses is addressed. The possible locations for the warehouses are given. For each location, there is an associated fixed cost for opening the warehouse concerned, as well as an operating cost and a maximum capacity. The demand of each customer for each commodity is known, as are the shipping costs from a plant to a possible warehouse and thereafter to a customer. It is required to choose the locations for opening warehouses and to find the shipping schedule such that the total cost is minimized. The problem is modelled as a mixed-integer programming problem and solved by branch and bound. The lower bounds are calculated through solving a minimum-cost, multicommodity network flow problem with capacity constraints. Results of extensive computational experiments are given.     

Dominance Criteria for the Capacitated Warehouse Location Problem

The paper examines the capacitated warehouse location problem where fixed costs, generally relating to the installation of warehouses and variable costs, consisting mainly of transportation costs, are minimized. The minimization of each kind of cost drives the solution towards opposite directions with respect to the number of warehouses to be opened/closed. Therefore, dominance criteria between fixed and variable costs are examined. This leads to exact tests as well as greedy heuristics, the latter known in the literature as ADD/DROP techniques.     

带覆盖需求约束的设施选址问题

带覆盖需求约束的设施选址问题(FLPWCDL)研究:客户必须在规定的响应半径内被服务,并要求服务站能够覆盖规定的需求数量,如何选择合适的服务站,使总成本(建站成本+路线成本)最小.FLPWCDL广泛应用于应急服务、物流、便利店等服务站的选址.建立了问题的混合整数规划模型,并构造了求解FLPWCDL的Benders分解算法,计算实验显示Benders分解算法具有非常高的求解效率与求解质量.     

Integrated location and two-echelon inventory network design under uncertainty

In this paper, we propose a two-stage stochastic model to address the design of an integrated location and two-echelon inventory network under uncertainty. The central issue in this problem is to design and operate an effective and efficient multi-echelon supply chain distribution network and to minimize the expected system-wide cost of warehouse location, the allocation of warehouses to retailers, transportation, and two-echelon inventory over an infinite planning horizon. We structure this problem as a two-stage nonlinear discrete optimization problem. The first stage decides the warehouses to open and the second decides the warehouse-retailer assignments and two-echelon inventory replenishment strategies. Our modeling strategy incorporates various probable scenarios in the integrated multi-echelon supply chain distribution network design to identify solutions that minimize the first stage costs plus the expected second stage costs. The two-echelon inventory cost considerations result in a nonlinear objective which we linearize with an exponential number of variables. We solve the problem using column generation. Our computational study indicates that our approach can solve practical problems of moderate-size with up to twenty warehouse candidate locations, eighty retailers, and ten scenarios efficiently.     

The uncapacitated facility location problem with demand-dependent setup and service costs and customer-choice allocation

We consider a generalization of the uncapacitated facility location problem, where the setup cost for a facility and the price charged for service may depend on the number of customers patronizing the facility. Customers are represented by the nodes of the transportation network, and facilities can be located only at nodes; a customer selects a facility to patronize so as to minimize his (her) expenses (price for service + the part of transportation costs paid by the customer). We assume that transportation costs are paid partially by the service company and partially by customers. The objective is to choose locations for facilities and balanced prices so as to either minimize the expenses of the service company (the sum of the total setup cost and the total part of transportation costs paid by the company), or to maximize the total profit. A polynomial-time dynamic programming algorithm for the problem on a tree network is developed.     

Elementary Theory of Optimal Silo Storage Design

This study indicates a method for calculating an economic division of warehouses into compartments when different varieties have to be stored simultaneously and separately. The study deals with cases where the total storage capacity demand and the number of varieties are known and fixed, but where the storage capacity demand of each variety is unknown. Problems of this nature exist in the preliminary designing of grain silos, fleets of transport vehicles, utensils in public kitchens, etc. If the warehouse capacity can cope with the total storage capacity demand, but the number of compartments is insufficient, it is possible that part of the material to be stored cannot be accommodated, although certain compartments may only be partly filled; this will be due to the impossibility of storing different varieties together. The materials will have to be stored in other warehouses, at a higher charge per capacity unit than that of the warehouse in question.The division of the warehouse into a large number of compartments will assure storage of most, if not all, the material. On the other hand, increase in the number of compartments (and installations) makes for increased investment in transport installation, partitions and additional storage capacity to compensate for space taken up by these partitions and installations.The object of this study is to introduce a method for calculating the optimal division of a warehouse into compartments, so that the annual costs of storage and capital investment are minimized.It is possible-by introducing not very restrictive statistical assumptions-to calculate the annual costs of storing excluded material elsewhere for different modes of partitioning a warehouse into compartments. The annual building cost of the warehouse is calculated in the ordinary way.In this study a solution is offered for the partitioning of a warehouse into equal compartments. It is to be expected that the extension of this solution to cases of the partition into compartments, differing from each other as to storage capacity, will tend to lower costs.     

Ship-pack optimization in a two-echelon distribution system

In large distribution systems, distribution centers (DC) deliver some merchandize to their retail stores in size-specific packages, also called ship-packs. These ship-packs include cases (e.g., cartons containing 24 or 48 units), inners (packages of 6 or 8 units) or eaches (individual units). For each Stock Keeping Unit (SKU), a retailer can decide which of these ship-pack options to use when replenishing its retail stores. Working with a major US retailer, we have developed a cost model that balances DC handling costs, store handling costs and inventory-related costs at both the DC and the stores, and therefore can help to determine the optimum warehouse ship-pack for each SKU. We implement our model for a sample of 529 SKUs, and show that by changing ship-pack size for about 30 SKUs, the retailer can reduce its total cost by 0.3% - 0.4%. Interestingly, we find that most of the cost savings occurs at the DC level.     

The freight consolidation and containerization problem

In today’s global free market, third-party logistics providers (3PLs) are becoming increasingly important. This paper studies a problem faced by a 3PL operating a warehouse in Shanghai, China, under contract with a major manufacturer of children’s clothing based in the United States. At the warehouse, the 3PL receives textile parcel shipments from the suppliers located in China; each shipment is destined for different retail stores located across the United Sates. These shipments must be consolidated and loaded into containers of varying sizes and costs, and then sent along shipping routes to different destination ports. An express company, such as UPS and FedEx, unloads the shipments from the containers at the destination ports and distributes them to their corresponding stores or retailers by parcel delivery. The objective is to find an allocation that minimizes the total container transportation and parcel delivery costs. We formulate the problem into an integer programming model, and also propose a memetic algorithm approach to solve the problem practically. A demonstration of a good solution to this problem was a decisive factor in the awarding of the contract to the 3PL in question.     

Warehouse location with production,inventory, and distribution decisions: a case study in the lube oil industry

In this paper, a supply chain management problem from a real case study is modeled and solved. A company in Pakistan wanted to outsource part of its warehousing activity to a third party logistics (3PL) provider. Consequently, the company had to decide on where to rent space in the 3PL warehouses. Knowing that such a strategic decision is affected by tactical and operational decisions, the problem is presented as a facility location problem integrating production, inventory, and distribution decisions. The problem is formulated as a mixed integer linear programming model which minimizes the total cost composed of location, distribution, production, and inventory costs. Several constraints specific to the situation and policy of the company were considered. A thorough analysis was done on the results obtained with respect to formulation efficiency, sensitivity analysis, and distribution of costs. In addition to the solution of the company problem, a set of 1215 problem instances was generated by varying five types of relevant costs in a full factorial manner. The solution of the generated problems always suggests to open in the same two locations and the integrality gaps averaged 0.062 % with a maximum of 0.102 %. On average, the major components of the total cost are production cost (96.6 %), transportation costs (2.7 %), and inventory holding costs (0.38 %). The total warehouse opening cost accounted for less than 0.05 % of the total costs.     

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.     

Approximation algorithm for facility location with service installation costs

In this paper, we study the uncapacitated facility location problem with service installation costs depending on the type of service required. We propose a polynomial-time approximation algorithm with approximation ratio 1.808 which improves the previous approximation ratio of 2.391 of Shmoys, Swamy, and Levi.     

Exact solution methods for uncapacitated location problems with convex transportation costs

In this paper we study exact solution methods for uncapacitated facility location problems where the transportation costs are nonlinear and convex. An exact linearization of the costs is made, enabling the formulation of the problem as an extended, linear pure zero–one location model. A branch-and-bound method based on a dual ascent and adjustment procedure is developed, and compared to application of a modified Benders decomposition method. The specific application studied is the simple plant location problem (SPLP) with spatial interaction, which is a model suitable for location of public facilities. Previously approximate solution methods have been used for this problem, while we in this paper investigate exact solution methods. Computational results are presented.     

考虑应急设施中断风险与防御的可靠性选址模型研究

为提高应急设施运行的可靠性和抵御中断风险的能力, 研究中断情境下的应急设施选址-分配决策问题。扩展传统无容量限制的固定费用选址模型, 从抵御设施中断的视角和提高服务质量的视角建立选址布局网络的双目标优化模型, 以应急设施的建立成本和抵御设施中断的加固成本最小为目标, 以最大化覆盖服务质量水平为目标, 在加固预算有限及最大最小容量限制约束下, 构建中断情境下应急设施的可靠性选址决策优化模型。针对所构建模型的特性利用非支配排序多目标遗传算法(NSGA-Ⅱ)求解该模型, 得到多目标的Pareto前沿解集。以不同的算例分析和验证模型和算法的可行性。在获得Pareto前沿的同时对不同中断概率进行灵敏度分析, 给出Pareto最优解集的分布及应急设施选址布局网络的拓扑结构。     

Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type

This paper presents exact and heuristic solution procedures for a multiproduct capacitated facility location (MPCFL) problem in which the demand for a number of different product families must be supplied from a set of facility sites, and each site offers a choice of facility types exhibiting different capacities. MPCFL generalizes both the uncapacitated (or simple) facility location (UFL) problem and the pure-integer capacitated facility location problem. We define a branch-and-bound algorithm for MPCFL that utilizes bounds formed by a Lagrangian relaxation of MPCFL which decomposes the problem into UFL subproblems and easily solvable 0-1 knapsack subproblems. The UFL subproblems are solved by the dual-based procedure of Erlenkotter. We also present a subgradient optimization-Lagrangian relaxation-based heuristic for MPCFL. Computational experience with the algorithm and heuristic are reported. The MPCFL heuristic is seen to be extremely effective, generating solutions to the test problems that are on average within 2% of optimality, and the branch-and-bound algorithm is successful in solving all of the test problems to optimality.     

A facility location model with safety stock costs: analysis of the cost of single-sourcing requirements

We consider a supply chain setting where multiple uncapacitated facilities serve a set of customers with a single product. The majority of literature on such problems requires assigning all of any given customer??s demand to a single facility. While this single-sourcing strategy is optimal under linear (or concave) cost structures, it will often be suboptimal under the nonlinear costs that arise in the presence of safety stock costs. Our primary goal is to characterize the incremental costs that result from a single-sourcing strategy. We propose a general model that uses a cardinality constraint on the number of supply facilities that may serve a customer. The result is a complex mixed-integer nonlinear programming problem. We provide a generalized Benders decomposition algorithm for the case in which a customer??s demand may be split among an arbitrary number of supply facilities. The Benders subproblem takes the form of an uncapacitated, nonlinear transportation problem, a relevant and interesting problem in its own right. We provide analysis and insight on this subproblem, which allows us to devise a hybrid algorithm based on an outer approximation of this subproblem to accelerate the generalized Benders decomposition algorithm. We also provide computational results for the general model that permit characterizing the costs that arise from a single-sourcing strategy.     

Using a facility location algorithm to solve large set covering problems

Erlenkotter has developed an efficient exact (guarantees optimality) algorithm to solve the uncapacitated facility location problem (UFLP). In this paper, we use his algorithm to solve large instances of an important subset of the UFLP; the set covering problem (SCP). In addition, we present further empirical evidence that a heuristic algorithm developed by Vasko and Wilson for the SCP is capable of quickly generating good solutions to large SCP's.