Resumen de Un algoritmo heurístico lagrangiano para el problema de localización de plantas con capacidades

Jaume Barceló Bugeda , Josep Casanovas Garcia

• Las técnicas lagrangianas se han aplicado con frecuencia al problema de localización de plantas cuando no intervienen las capacidades, y en algunos casos han demostrado su utilidad incluso cuando se tienen en cuenta restricciones adicionales. Nuestro trabajo estudia la aplicación de estas técnicas al problema de localización de plantas cuando intervienen las capacidades, en el caso particular en que el modelo considerado es entero puro. Se han tenido en cuenta varias descomposiciones lagrangianas, y para alguna de ellas se han diseñado algoritmos heurísticos para resolver los subproblemas lagrangianos.

  Las heurísticas consisten en un procedimiento con dos fases. En la primera (fase de localización) se define un conjunto de multiplicadores a partir del análisis del dual de la relajación LP, y se efectúa una selección de emplazamientos para las plantas, mientras que la segunda (fase de afectación) asigna los centros a las plantas considerando el subproblema resultante como un caso particular del problema generalizado de asignación. Varias heurísticas han sido estudiadas en esta segunda fase, basadas en la descomposición en una colección de subproblemas de tipo knapsack mediante la definición de un conjunto de penalizaciones, o en el análisis del duality gap intentando reducirlo. Se incluyen los resultados de las experiencias realizadas