Jairo Rafael Montoya-Torres*¹, Andrés Felipe Aponte Penagos**², Paula Alejandra Rosas Castro***¹

1 Universidad de La Sabana (Colombia)

2 Fundación LOGyCA (Colombia)

* Profesor asociado y director del Programa de Administración de Mercadeo y Logística Internacionales de la Escuela Internacional de Ciencias Económicas y Administrativas de la Universidad de La Sabana, Chía (Colombia). Doctor en Ingeniería Industrial de la Ecole des mines de Saint-Etienne, Francia. Master of Science del Institut National Polytechnique de Grenoble, Francia. Ingeniero Industrial de la Universidad del Norte, Colombia. jairo.montoya@unisabana.edu.co

** Consultor Fundación LOGyCA-GS1. Ingeniero industrial de la Pontificia Universidad Javeriana, Bogotá (Colombia). espetegos@hotmail.com

*** Investigador en formación del grupo de investigación "Logística y Mercadeo" de la Escuela Internacional de Ciencias Económicas y Administrativas de la Universidad de La Sabana, Chía (Colombia). Ingeniera industrial de la Pontificia Universidad Javeriana, Bogotá, D.C. (Colombia). paulejarosas@hotmail.com

Correspondencia: Universidad de La Sabana, Escuela de Ciencias Económicas y Administrativas, Autopista norte de Bogotá, D.C., Chía (Colombia). Tel: (571) 8615-555, Ext. 1849.

Subvenciones y apoyos recibidos: El trabajo fue financiado mediante los contratos CEA-24-2008 y CEA-46-2009 del Fondo de Investigaciones de la Universidad de La Sabana (Colombia).

Este artículo considera el problema de localización de instalaciones no capacitado en una cadena logística de tres eslabones (Three-echelon Uncapacitated Facility Location Problem, TUFLP). El problema de optimización consiste en definir los flujos de productos desde las plantas de manufactura hacia los clientes a través de centros de distribución (CD), cuya ubicación debe determinarse adicionalmente. La función objetivo es la minimización del costo total conformado por el costo fijo de localización de los centros de distribución y los costos variables de producción y distribución de productos. Puesto que este es un problema NP-completo, se propone la utilización de un procedimiento voraz adaptativo probabilista (GRASP) para resolver el caso particular monoproducto. Se desarrollan experimentos computacionales con instancias conocidas en la literatura. Los resultados muestran que el algoritmo propuesto permite obtener buenas soluciones (e incluso valores óptimos) en menor tiempo de cálculo que un procedimiento exacto basado en programación lineal entera mixta.

Palabras clave: localización de instalaciones, GRASP, heurístico, experimentos.

This paper considers the three-echelon uncapacitated facility location problem (TUFLP), which consists on both defining the flow of products from manufacturing plants to clients via a set of warehouses and the location of such warehouses. The objective function is to minimize the total cost of warehouse location and production and distribution. Since the problem is NP-hard, this paper proposes a Greedy Randomized Search Procedure (GRASP) to solve the single-item case. Computational experiments are conducted using known instances from the literature. Results show that the proposed algorithm performs well obtaining very good solutions (and even optimal values) in less computational time than an exact method based on mixed-integer linear programming.

Keywords: Facility location, GRASP, heuristic, experiments.

El problema de localización de instalaciones no capacitadas en tres eslabones (Three-echelon Uncapacitated Facility Location Problem, TUFLP) es una extensión del problema clásico multiproducto de producción-distribución, el cual es uno de los problemas más importantes en la Teoría de Localización [1]. En el caso general, el problema se define de la siguiente forma: una empresa puede fabricar relativamente pocos productos y un cierto número de plantas de producción. Los productos son despachados desde las plantas ya sea directamente hacia los puntos de consumo (mercado) o hacia centros de distribución y de ellos hacia los puntos de consumo (o consumidores). Las preguntas clave a responder son las siguientes:

1. ¿Cuántos centros de distribución se deben tener?

2. ¿Dónde deben localizarse esos centros de distribución?

3. ¿Cómo debe ser el flujo de productos a lo largo del sistema?

En la decisión del flujo de productos se encuentran implícitas otras decisiones acerca de qué productos deben ser fabricados en las plantas y para cuál(es) de los puntos de consumo. La figura 1 es una representación esquemática del sistema.

Este artículo considera el problema TUFLP con un único producto. Debido a la complejidad computaciones de tipo NP-duro, este artículo propone la implementación de un procedimiento heurístico voraz adaptativo probabilista (greedy randomized adaptive search procedure, GRASP). Propuesto por Feo y Resende [2], [3], GRASP es un método multiarranque diseñado para resolver problemas difíciles de optimización combinatoria, en el que cada iteración consiste básicamente en dos fases: construcción y búsqueda local. En la fase de construcción se encuentra una solución factible, para la cual se investiga el vecindario hasta cuando se halle un óptimo local durante esta fase de búsqueda en el vecindario. La mejor de todas las soluciones es registrada como el resultado de la iteración. GRASP es uno de los numerosos procedimientos metaheurísticos de éxito que aparecieron en los últimos años. En este artículo se propone la aplicación de este metaheurístico para resolver el TUFLP.

Este artículo está organizado de la siguiente forma. La sección 2 presenta la formulación matemática del problema y la revisión de la literatura relacionada. En la sección 3 se describe en detalle el algoritmo GRASP propuesto. La metodología para la realización del estudio experimental se presenta en la sección 4, mientras que los resultados obtenidos se muestran en la sección 5. El artículo termina en la sección 6 presentando las conclusiones y perspectivas del trabajo.

El problema de localización de instalaciones no capacitadas en tres eslabones (three-echelon uncapacitated facility location problema, TUFLP) pertenece a la familia de problemas de producción-distribución en los cuales los centros de distribución tienen capacidad ilimitada. El problema puede ser formulado como un modelo matemático, para lo que se requiere la siguiente notación:

Variables de decisión:

representa el flujo del producto k desde la planta m hacia el mercado (cliente) i a través del centro de distribución j.

X_j es igual a 1 si un centro de distribución es localizado en el sitio candidato j, y es igual a 0 si no.

Empleando la notación descrita, el TUFLP es formulado como sigue [1]:

La función objetivo (1) minimiza la suma de los costos fijos de localización de los centros de distribución y de los costos variables de flujo de productos. Es importante notar que la noción de costos variables incorporados en el modelo a través del parámetro permite incluir los costos unitarios de producción de la planta m, los costos unitarios de transporte entre la planta m y un centro de distribución localizado en el punto j, cualquier costo unitario variable relacionado con el centro de distribución localizado en el sitio j, y los costos de transporte entre el sitio j y el punto de consumo o mercado i. Todos estos costos unitarios pueden depender del producto particular bajo estudio en casos concretos de producción. El lado izquierdo de las restricciones (2) corresponde al flujo a través del centro de distribución localizado en el sitio candidato j. Las restricciones (2) establecen que este flujo sólo es positivo si un centro de distribución es localizado en el sitio candidato j. Las restricciones (3) establecen que la cantidad total de producto k despachada hacia el mercado i desde todas las plantas y todos los centros de distribución debe ser mayor o igual que la demanda del producto k en el mercado i. De forma similar, las restricciones (4) consideran la capacidad de producción de la plantas. Para el caso de este artículo, en ambos conjuntos de restricciones (3) y (4), se considera la fabricación de un solo producto (i.e., k=1). Finalmente, las restricciones (5) y (6) corresponden a las restricciones de no negatividad y de valores binarios admisibles para las variables de decisión.

El TULFP es un problema de tipo NP-completo [4], es decir que no es posible encontrar las soluciones óptimas para instancias de gran tamaño en un tiempo de cálculo razonable por lo cual varios enfoques de solución han sido considerados en la literatura. Vidal y Goetschalckx [5] presentan una revisión de modelos cuyo foco es el impacto en la administración global de la cadena de suministros. Chen [6] clasifica los modelos existentes en la literatura para resolver problemas de producción-distribución en cinco grandes categorías basándose en los niveles de toma de decisión, en la estructura de la red y en los parámetros del problema. La mayoría de los métodos de resolución están fundamentados en modelos de programación lineal entera mixta (MILP) para instancias pequeñas y medianas. Algoritmos heurísticos y metaheurísticos también han sido propuestos para resolver problemas de gran tamaño entre los que se encuentran procedimientos basados en la descomposición de Benders, relajación de Lagrange, modelos jerárquicos, algoritmos genéticos o de recocido simulado [7]-[12]. El problema con múltiples periodos de tiempo también ha sido estudiado en la literatura [13]-[20]. El único caso mono-producto con múltiples periodos es presentado por Haq [21]; igualmente todos los problemas estudiados en estos artículos se refieren al problema con múltiples productos.

Este artículo propone el uso de la metaheurística GRASP (Greedy Randomized Adaptive Search Procedure) para resolver el problema TUFLP. GRASP ha sido empleada para resolver varios problemas de optimización combinatoria en programación de la producción, asignación, clustering, empaquetamiento, particionamiento, enrutamiento de vehículo y otros. Algunas de las aplicaciones de GRASP para la resolución de problemas de localización se presentan en [22]-[24].

Los principios de GRASP y su aplicación al problema bajo estudio en este artículo se presentan en la siguiente sección.

GRASP (Greedy Randomized Adaptive Search Procedure) fue propuesto por Feo y Resende [2], [3] y constituye uno de los múltiples procedimientos metaheurísticos propuestos en la literatura académica en los últimos años para la resolución de problemas difíciles. GRASP es un método multiarranque que en su versión básica cada iteración está constituida de dos fases: (I) una fase constructiva con la que se obtiene una buena (no necesariamente la mejor) solución, y (II) una fase de búsqueda local durante la cual los vecindarios de la solución son examinados hasta obtener un óptimo local. Las iteraciones continúan guardando siempre el registro de la mejor solución obtenida hasta que se alcance el criterio de parada. En esta sección se presenta la adaptación diseñada de la versión básica de GRASP para resolver el problema TUFLP. Una de las grandes ventajas de este metaheurístico es su facilidad para ser implementado puesto que sólo dos parámetros deben ser definidos: el criterio de parada (para este caso el número máximo de iteraciones sin mejorar la solución), y el parámetro a empleado para la generación aleatoria de la lista de candidatos.

La rutina general de GRASP se muestra en la figura 2. Cada una de estas fases y los parámetros requeridos serán explicados en detalle en las subsecciones siguientes, incluso el objetivo de cada subrutina y la forma en que se implementó para el caso particular del problema bajo estudio.

3.1. Fase de construcción

Con este primer paso del procedimiento, se pretende obtener una solución inicial factible. Las soluciones son construidas de forma iterativa agregando un elemento en cada paso. Para seleccionar esos elementos, se emplea una función voraz (greedy), que mide la contribución local de cada elemento a la solución parcial. Con base en dicha contribución, los mejores candidatos son identificados y se crea una lista restringida de candidatos (RCL). El procedimiento es adaptativo puesto que los beneficios asociados a todos los elementos son actualizados en cada iteración de la fase de construcción con el fin de reflejar los cambios ocasionados por la selección del elemento anterior. El componente probabilista de GRASP es caracterizado por la selección aleatoria de uno de los mejores candidatos de la lista, pero no necesariamente el mejor de todos ellos (el primero de la lista).

Para el problema en estudio, la fase de construcción comienza con la selección, uno por uno, de los clientes según su demanda, en orden creciente, dada por el parámetro h_i^k. Posteriormente, se evalúan los otros candidatos y sus contribuciones a la función objetivo a través de los costos de transporte y los costos fijos de localización de los centros de distribución empleando los parámetros y fj. Dichos candidatos presentan las diferentes opciones de satisfacción de la demanda del mercado. Por lo tanto, es necesario evaluar todas las posibles combinaciones de plantas y centros de distribución mediante una estrategia voraz (greedy), basada en los valores de las variables de decisión . La lista restringida de candidatos (RCL) se construye a partir del valor del parámetro α, que determina el nivel de aceptación de los candidatos. Cada candidato tendrá asignada una probabilidad según su contribución a la función objetivo para que posteriormente sea agregado a la solución. Cuando un candidato es agregado a una solución parcial, el valor correspondiente a la variable de decisión y los valores de los parámetros de demanda , capacidad de producción y costo fijo son actualizados. Los valores de estos parámetros dependerán del valor de de acuerdo con las siguientes reglas:

1. Si el valor de la variable de decisión es igual a la capacidad , entonces el valor de la capacidad de la planta para fabricar el producto k' será cero y el nuevo valor de la demanda del cliente i' para este producto será . Un valor positivo de este cálculo significa que la demanda no ha sido completamente satisfecha y, por lo tanto, el algoritmo correrá una nueva iteración.

2. Si el valor de la variable de decisión es igual a la demanda , entonces la demanda está satisfecha completamente y la capacidad restante será calculada como . Un valor positivo de este cálculo significa que la planta tiene aún capacidad disponible para fabricar productos.

3. Si un centro de distribución es seleccionado con un costo fijo de apertura , este parámetro será fijado en cero en la siguiente iteración con el fin de no seleccionarlo nuevamente.

Finalmente, antes de terminar la fase de construcción es necesario verificar que la solución sea factible. Esto se logra verificando que , lo cual significa que toda la demanda ha sido satisfecha, como se muestra en la figura 3.

3.2. Lista de candidatos

El objetivo de la lista restringida de candidatos (RCL) es reducir el número de candidatos potenciales que pueden ser agregados a la solución en construcción. Esta técnica de escogencia permite que se obtengan diferentes soluciones en cada iteración de GRASP, pero no necesariamente compromete el poder del componente adaptativo del método. Según lo reportado en la literatura, esta selección puede realizarse de dos formas. La primera consiste en la selección de un parámetro fijo que represente el número de candidatos en la lista. En este caso, la lista tendrá siempre el mismo tamaño en cada iteración. La segunda opción está basada en la definición de un parámetro a e [0, l] para obtener una cota como el criterio de selección de los candidatos en la lista RCL.

En el caso de problemas de minimización, como en el nuestro, cuando el método de construcción está basado en el valor de a, la lista de candidatos contendrá todos los candidatos con criterio de evaluación inferior que esta cota. Es entonces necesario conocer los valores mínimos y máximos de las evaluaciones, como lo muestra el pseudocódigo de la figura 4. La selección apropiada del parámetro a para la lista RCL es crítica y de gran importancia para obtener soluciones de buena calidad en tiempo de cálculo razonable, porque la distribución de las soluciones en cada iteración de GRASP depende de la naturaleza de la lista RCL. Si α=0, entonces GRASP se comporta como un algoritmo voraz completamente determinista, y en todas las iteraciones se obtendrá el mismo valor de la función objetivo.

3.3. Búsqueda local

Como sucede en el caso de muchos métodos determinísticos, no es posible garantizar que la solución generada por GRASP en la fase de construcción sea óptima localmente con respecto a su vecindario. Por lo tanto, siempre es benéfico aplicar un método de búsqueda local para mejorar cada solución construida. Un algoritmo de búsqueda local trabaja de forma iterativa a través de un reemplazo sucesivo de la solución actual por una mejor de su vecindario. Este termina cuando no se logra encontrar mejoramiento alguno en el vecindario.

Para el problema bajo estudio, se observa que una vez los centros de distribución han sido localizados (i.e., se obtienen los valores de las variables de decisión binarias), el problema se convierte en el modelo clásico del problema de transporte para el cual se conocen algoritmos eficientes [25]. Así, una solución óptima local para este problema de transporte puede ser obtenida empleando métodos como ramificación y acotamiento, algoritmos de punto interior, o cualquier otro para resolverlo.

Con el fin de analizar el desempeño del método GRASP propuesto para el problema TUFLP se generaron instancias aleatorias. Puesto que este artículo estudia el problema TUFLP monoproducto, se emplearon las mismas instancias propuestas por Marín [26]. Las dimensiones del problema fueron definidas como (número de productos x número de plantas x número de centros de distribución x número de clientes), donde k=1 (referido al problema mono-producto), m={10,20}, j={16,25,50} y i=50. Los costos fijos de localización son generados a partir de una distribución uniforme entre 7500 y 25000. Los costos variables () fueron generados a partir de una distribución uniforme entre 25 y 150. Las demandas (h_i^k) fueron generadas a partir de una distribución uniforme entre 0 y 200. Finalmente, las capacidades de fabricación de cada planta fueron generadas empleando la siguiente ecuación: donde es una variable aleatoria generada a partir de una distribución uniforme con parámetros 0-1.

Adicionalmente, la ejecución de GRASP requiere la definición de dos parámetros: el máximo número de iteraciones sin mejoramiento de la solución y α. Para el primero se tomaron valores de 10 y 50 iteraciones, mientras que para el segundo se tomaron tres valores de α: 0, 0.1 y 0.5. Recordemos que cuando α=0 GRASP se comporta como un algoritmo voraz (greedy) determinístico. De esta forma se tiene cinco combinaciones de estos parámetros. Debido al comportamiento probabilista de GRASP se corrieron cinco réplicas para cada combinación de los parámetros del experimento.

Los experimentos fueron realizados en un computador personal Genuine Intel de 1829 MHz. La programación de GRASP se realizó en el lenguaje Visual Basic for Applications versión 6.3. Las soluciones obtenidas por medio de GRASP fueron comparadas con la solución óptima obtenida empleando el modelo de programación lineal entera mixta (MILP) presentado en la sección 2. El modelo MILP se resolvió empleando Glpsol (GNU Linear Programming Kit) versión 4.9. Adicionalmente, el desempeño de GRASP fue comparado al de una cota inferior para la función objetivo obtenida relajando el conjunto de restricciones (6) del modelo MILP; esto es, permitiendo que las variables de decisión binarias tomen valores entre cero y uno (i.e.,).

Esta sección presenta los resultados obtenidos en el estudio computacional. El primer análisis que debe ser realizado corresponde al impacto del valor de α en la obtención de la solución, puesto que es uno de los dos importantes parámetros de GRASP. La figura 5 presenta el valor de la función objetivo en función de los tres valores de a considerados. Se puede observar que el mínimo costo se obtiene, para todas las instancias, cuando α=0.1. Recordemos que α=0 significa que el algoritmo se comporta de forma determinística. De otra parte, el componente aleatorio de GRASP aumenta en la medida que en el valor de a es elevado (esto es, si α → 1). Es entonces importante definir muy bien el valor de este parámetro para obtener buenas soluciones.

Las tablas 1 y 2 presentan un resumen de los valores promedio de la función objetivo (costo total). Las últimas columnas corresponden a la desviación porcentual del valor promedio dado por GRASP (F (GRASP)) contra el valor solución dado tanto por el modelo MILP (F(OPT)) como por el modelo relajado (F(LB)). Este valor se calcula como:

Como se puede observar en la tabla 1, con valor del parámetro α=0.1 y condición de terminación de 10 iteraciones sin mejoramiento de la función objetivo, GRASP obtiene el valor óptimo en 25% de los casos, mientras que en un total del 75% de los casos su solución no estuvo alejada más que del 9% del valor óptimo. Es de notar que en el 100% de los casos, el valor de la función objetivo obtenida con GRASP estuvo dentro del 2% del valor óptimo. Sin embargo, con 50 iteraciones sin mejoramiento de la solución (ver tabla 2), GRASP no se desempeñó tan bien como se esperaba. Esto puede deberse al comportamiento aleatorio del algoritmo.

Con respecto a los tiempos de cálculo computacional, la tabla 3 presenta algunas estadísticas que permiten comparar el comportamiento de GRASP con el modelo MILP y con el modelo relajado (LB). Se puede observar que en 27% de los casos, GRASP requiere menos tiempo de cálculo que la solución exacta.

Este artículo propuso un procedimiento voraz adaptativo probabilista (GRASP) para resolver el problema de localización de instalaciones no capacitadas de tres eslabones (TUFLP) monoproducto, que hace parte de la familia de problemas de producción-distribución. El desempeño del metaheurístico propuesto fue analizado empleando datos generados aleatoriamente provenientes de la literatura. En comparación con la solución óptima obtenida empleando un modelo de programación lineal entera mixta (MILP), los resultados de los experimentos muestran que el procedimiento propuesto se desempeña muy bien, e incluso encuentra la solución óptima en menor tiempo de cálculo que el modelo MILP. En trabajos futuros se puede considerar la extensión del algoritmo propuesto para estudiar el problema con múltiples productos [27], y la consideración de más de tres eslabones en la cadena logística. Adicionalmente, se puede considerar la inclusión de alternativas híbridas para el algoritmo, como ha sido propuesto en la literatura para la resolución de otros problemas, puesto que GRASP puede fácilmente incluirse como parte de otros procedimientos metaheurísticos.

Agradecimientos

Los autores agradecen los comentarios tanto de Juan P. Caballero como del evaluador anónimo y de la editora de la revista, con los que se mejoró la presentación del artículo.

[1] M. Daskin, Network and Discrete Location: Models, Algorithms, and Applications. New York: Ed. Wiley-Interscience, 1995, pp. 247-382.

[2] T.A. Feo and M.G.C. Resende, "A probabilistic heuristic for a computationally difficult set covering problem", Operations Research Letters, vol. 8, pp. 67-71, 1989.

[3] T.A. Feo and M.G.C. Resende, "Greedy randomized adaptive search procedures", Journal of Global Optimization, vol. 6, pp. 109-133, 1995.

[4] G. Cornuejols, G. Nemhauser and L. Wolsey, "The uncapacitated facility location problem", en Discrete Location Theory, P.B. Mirchandani, R.L. Francis, Eds. New York: John Wiley and Sons, Inc., 1990, pp. 119-71.

[5] C.J. Vidal and M. Goetschalckx, "Strategic production-distribution models: A critical review with emphasis on global supply chain models", European Journal of Operational Research, vol. 98, pp. 1-18, 1997.

[6] Z.L. Chen, "Integrated production and distribution operations: Taxonomy, models, and review", en: Handbook of Quantitative Supply Chain Analysis: Modeling in the E-Business Era, D. Simchi-Levy, S.D. Wu, Z.J. Shen, Eds. Boston, USA: Kluwer Acadmic Publishers. 2004, pp. 711-782.

[7] H. Pirkul and V. Jayaraman, "A multi-commodity, multi-plant, capacitated facility location problem: formulation and efficient heuristic solution", Computers Operational Research, vol. 25, n.° 10, pp. 869-78, 1998.

[8] M.A. Cohen and H.L. Lee, "Strategic Analysis of Integrated Production-Distribution Systems: Models and Methods", Operations Research, vol. 36, pp. 216-228, 1988.

[9] M.A. Cohen and H.L. Lee, "Resource Deployment Analysis of Global Manufacturing and Distribution Networks", Journal of Manufacturing and Operations Management, vol. 2, pp. 81-10, 1989.

[10] M. Zuo, W. Kuo and K.L. McRoberts, "Application of Mathematical Programming to a Large-Scale Agricultural Production and Distribution System", Journal of Operational Research Society, vol. 42, pp. 639-648, 1991.

[11] M. Chen and W. Wang, "A linear programming model for integrated steel production and distribution plant", International Journal of Operations and Production Management, vol. 17, pp. 592-610, 1997.

[12] E. Sabri and B.M. Beamon, "A Multi-Objective Approach to Simultaneous Strategic and Operational Planning in Supply Chain Design", Omega, vol. 28, pp. 581-598, 2000.

[13] P. Chandra and M.L. Fisher, "Coordination of Production and Distribution Planning", European Journal of Operational Research, vol. 72, pp. 503-517, 1994.

[14] B.C. Arntzen, G.G. Brown, T.P. Harrison and L.L. Trafton, "Global Supply Chain Management at Digital Equipment Corporation", Interfaces, vol. 25, pp. 69-93, 1995.

[15] G. Barbarosoglu and D. Ozgur, "Hierarchical Design of an Integrated Production and 2-Echelon Distribution System", European Journal of Operational Research, vol. 118, pp. 464-484, 1999.

[16] K. Dogan and M. Goetschalckx, "A Primal Decomposition Method for the Integrated Design of Multi-Period Production-Distribution Systems", IIE Transactions, vol. 31, pp. 1027-1036, 1999.

[17] F. Fumero and C. Vercellis, "Synchronized Development of Production, Inventory, and Distribution Schedules", Transportation Science, vol. 33, pp. 330-340, 1999.

[18] Z.M. Mohamed, "An Integrated Production-Distribution Model for a MultiNational Company Operating under varying exchange rates", International Journal of Production Economics, vol. 58, pp. 81-92, 1999.

[19] L. Ozdamar and T. Yazgac, "A Hierarchical Planning Approach for a Production-Distribution System", International Journal of Production Research, vol. 37, pp. 3759-3772, 1999.

[20] C. Dhaenens-Flipo and G. Finke, "An Integrated Model for an Industrial Production-Distribution Problem", IIE Transactions, vol. 33, pp. 705-715, 2001.

[21] A.N. Haq, "An Integrated Production-Inventory-Distribution Model for Manufacturing of Urea: A Case", International Journal of Production Economics, vol. 39, pp. 39-49, 1991.

[22] J.G. Klincewicz, "Avoiding local optima in the p-hub location problem using tabu search and GRASP", Annals of Operations Research, vol. 40, pp. 283-302, 1992.

[23] M.J.N. Gomes and J.B.C. da Silva, An experimental evaluation of the GRASP metaheuristic applied to the uncapacitated location problem. Technical Report 004/99, Fortaleza, Ceará, Brazil: Department of Statistics and Computation, State University of Ceará, 1999.

[24] M. Resende and R.F. Weneck, "A hybrid heuristic for the p-median problem". Journal of Heuristics, vol. 10, pp. 59-88, 2004.

[25] F. Hillier and G. Lieberman, Introduction to Operations Research. New York: McGraw-Hill Science, 2005, pp. 320-373.

[26] A. Marín, "Lower bounds for the two-stage uncapacitated facility location problem", European journal of Operational Research, vol. 179, pp. 1126-1142, 2007.

[27] J.R. Montoya-Torres, A. Aponte and P. Rosas, "Applying GRASP to solve the multi-item three-echelon uncapacitated facility location problem". Journal of the Operational Research Society. Accepted for publication, 2010. DOI: 10.1057/jors.2010.134.