Applying GRASP to solve the multi-item threeechelon 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.

Este documento considera un problema de producción-distribución que consiste en definir el flujo de productos producidos desde las plantas de fabricación a los clientes (mercados) a través de un conjunto de almacenes. El problema también consiste en definir la ubicación de dichos almacenes que tienen una capacidad de almacenamiento ilimitada. Este problema se conoce en la literatura como el problema de ubicación de instalaciones sin capacidad de tres niveles (TUFLP), y se sabe que es NP-hard cuando la función objetivo es minimizar el costo total de la ubicación del almacén y la producción y distribución de productos. Este documento propone un procedimiento de búsqueda adaptativa aleatoria codiciosa (GRASP) para resolver la versión de varios elementos del TUFLP. Los experimentos computacionales se llevan a cabo utilizando instancias conocidas de la literatura. Las soluciones obtenidas con GRASP se comparan con las soluciones óptimas y los límites inferiores obtenidos con la programación matemática. Los resultados muestran que el algoritmo propuesto funciona bien, obteniendo buenas soluciones (e incluso los valores óptimos) en menos tiempo computacional que el modelo de programación lineal de enteros mixtos.