Variable Neighborhood Search for the Uncapacitated Facility Location Problem

Abstract

The uncapacitated facility location problem is a very studied problem in fields such as logistics, resource distribution, and telecommunication network planning. Given a set of potential facilities and a set of customers, the problem consists of selecting an undetermined number of facilities to open to serve all customers with the objective of minimizing opening and assignment costs. Due to its classification as an NP-hard problem, obtaining exact solutions becomes unfeasible on a large scale, necessitating the exploration of approximate methods and metaheuristics. Within the context of this problem, various exact approaches were initially developed. However, more recently, approximate and metaheuristic algorithms have gained prominence, achieving high-quality solutions with reduced computational cost. This paper proposes a variable neighborhood search strategy that, through the opening and closing of facilities, balances the intensification and diversification of the search. Experimental results on different sets of instances show that the proposal achieves high-quality solutions very close to the optimal ones but with a reduced execution time, comparing favorably with other state-of-the-art algorithms.

Cite This Publication

Martín-García, L., Lozano-Osorio, I., Colmenar, J. M., & Melián-Batista, B. (2025). Variable neighborhood search for the uncapacitated facility location problem. In XVI Spanish Congress on Metaheuristics, Evolutionary and Bio-inspired Algorithms (pp. 179-188).