Lagrangean relaxation and hybrid simulated annealing tabu search procedure for a two-echelon capacitated facility location problem with plant size selection

In this paper, we study a two-echelon capacitated facility location problem with plant size selection (TECFLP-PSS). Given a set of potential sites for plants, each of which is associated with several possible sizes and corresponding unit production costs, a set of potential sites for capacitated depots and a set of customers with demands, the TECFLP-PSS aims to optimise the plant locations and sizes, the depot locations and the product flows from the opened plants to the opened depots and then to the end customers under single-source constraints. The objective is to satisfy all customers’ demands with a minimum total cost of facility opening, production and transportation. We develop a mixed integer programming model and propose a Lagrangean relaxation approach combined with new valid inequalities and core problem to achieve tight lower and upper bounds for this problem. We then improve the upper bound with a hybrid simulated annealing tabu search procedure. Computational experiments on benchmarks and randomly generated instances are conducted to validate the effectiveness and efficiency of the proposed method.