Estudio de métodos exactos y aproximados para la resolución del problema de localización sin capacidades

Abstract

Este trabajo estudia el problema UFLP (problema de localización sin capacidades), que constituye la base de los problemas de localización. Dado que se trata de un problema computacionalmente costoso los métodos exactos no son especialmente útiles para tamaños grandes del problema. El foco del trabajo se encuentra en las heurísticas de búsqueda local y las metaheurísticas, que permiten resolver problemas de optimización grandes en tiempos practicables. Se estudian los algoritmos mediante su implementación en C y la resolución de ficheros de datos de diferentes características y se comparan con los métodos exactos. Finalmente, se determina qué metaheurística es más apropiada para la resolución de este problema.

This work studies the UFLP (Uncapacitated Facility Location Problem), wich lays the basis of localisation problems. Since this is a computationally costly problem the exact methods are not particularly useful for big instances of the problem. The focus of this work is on local search heuristics and metaheuristics, which enable solving big optimisation problems in reasonable times. Diferent algorithms are studied through their implementation in C and the solution of datasets of diverse features and they are compared to the exact methods. Finally, it is determined which metaheuristic is the most adequate for the solution of this problem.