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

Authors: Jairo R. Montoya-Torres, Andres Aponte, Paula Rosas, Juan Pablo Caballero-Villalobos

Addresses: Escuela Internacional de Ciencias Economicas y Administrativas, Universidad de La Sabana, km 7 autopista norte de Bogota, Chia (Cundinamarca), Colombia. ' Fundacion LOGyCA, Avenida El Dorado No. 70-16, Bogota, Colombia. ' Escuela Internacional de Ciencias Economicas y Administrativas, Universidad de La Sabana, km 7 autopista norte de Bogota, Chia (Cundinamarca), Colombia. ' Departamento de Ingenieria Industrial, Pontificia Universidad Javeriana, Carrera 7 No. 40-62, Bogota, Colombia

Abstract: This 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.

Keywords: two-echelon uncapacitated facility location; greedy randomised adaptive search procedure; GRASP; heuristics; experiments; metaheuristics.

DOI: 10.1504/IJADS.2010.036849

International Journal of Applied Decision Sciences, 2010 Vol.3 No.4, pp.297 - 310

Published online: 12 Nov 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article