Applying GRASP meta-heuristic to solve the single-item two-echelon uncapacitated facility location problem

Abstract

his paper considers the two-echelon uncapacitated facility location problem (TUFLP), which consists on defining the flow of produced products from manufacturing plants to clients (markets) via a set of warehouses. The problem also consists on defining the location of such warehouses. The objective function is to minimise the total cost of warehouse location and production and distribution of products. This problem is known to be NP-hard since it is a combination of two problems: the uncapacitated facility location problem (UFLP) and the multi-item facility location problem (MFLP). In this paper, we propose a greedy randomised adaptive search procedure (GRASP) to solve the single-item case of the TUFLP. Computational experiments are conducted on random data generated using known instances from the literature. Solutions obtained using GRASP are compared against the optimal solutions 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.