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

Abstract

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.

Keywords:

• facility location
• GRASP
• heuristic
• experiments

Acknowledgements

This work is part of research projects supported by Universidad de La Sabana under grants CEA-24-2008 and CEA-46-2009. Authors wish to thank the anonymous reviewers for their comments which enabled the presentation of this paper to be improved.