Algorithmic approaches for the single source capacited plant location problem

Resumen

El objetivo de la tesis "Algorithmic Approaches for the Single Source Capacitated Plant Location Problem" es proponer y comapar distintos enfoques algorítmicos para la salución del problema de localización de plantas con restricciones de capacidad y fuente única, Se proponen diversos enfoques para la obtención de cotas, tanto superiores como inferiores, y un algoritmo para resolver el problema de forma exacta. Asimismo, se estudia de manera independiente el problema de asignación generalizada, que es un caso particular del su problema de asignación del problema de localización estudiado, y se propone un algorimto para su resolución. Para el problema estudiado se proponen los siguientes métodos: 1,- Un algoritmo basado en la metodología de algoritmos evolutivos. 2,- Algoritmo basados en la metodología GRASP (Greedy Randomized Adaptive Search Procedure). 3,- Un algoritmo basado en la metodología de temple simulado (Simulated Annealing). 4,- Algoritmos basados en el método de búsqueda tabú. 5,- Algoritmos híbridos que combinan la metodología GRASP con el método de búsqueda tabú. 6,- Un algoritmo para obtener cotas inferiores y superiores que empleea la metodología de generación de columnas. 7,- Un algoritmo enumerativo basado en la metodología "Branch-and-Price". Los algoritmos propuestos para el problema estudiado se evalúan utilizando dos conjuntos de problemas de prueba. De acuerdo con los resultados obtenidos se observa que los algoritmos híbridos son los métodos que proporcionan los mejores resultados en términos de calidad de las soluciones obtenidas y de robustez del algoritmo. El método de generación de columnas proporcio a soluciones comparables en calidad de aquellas proporiconadas por los algortimos híbridos y es el más robusto de los algoritmos aproximados. Asimismo, proporciona excelentes cotas inferiores que permiten reducir considerablemente el esfuerzo enumerativo del algorit