A Lagrangean Relaxation Approach for a Two-Stage Capacitated Facility Location Problem with Choice of Facility Size

摘要

In this paper, we study a two-stage capacitated facility location problem with choice of facility size. Given a set of potential sites for plants and a set of potential sites for depots, each of the plants and the depots has several possible sizes, and a set a customers with demands, the aim of the problem is to determine the locations of the plants and the depots as well as their sizes, the product flows from the opened plants, via the opened depots to the customers under the single-sourcing constraints, so that all of the customers' demands are satisfied with the minimum sum of the fixed opening costs of the facilities, the producing costs at the plants, the handling costs at the depots, the transportation costs from the plants to the depots and the customer-depot assignment costs. A mixed integer programming model for the problem is formulated and a LaGrange an relaxation approach is proposed to achieve a lower bound and an upper bound of the problem. The performance of the LaGrange an relaxation approach is evaluated on 200 randomly generated instances. The computational results demonstrate that the LaGrange an relaxation approach is effective with the average gaps around 1.30%.