A Machine Learning Enhanced Variable Neighborhood Search Approach for the Uncapacitated Facility Location Problem

Abstract

The Uncapacitated Facility Location Problem (UFLP) is widely recognized as a relevant problem in logistics, resource distribution, and telecommunications network planning. Given a set of potential facility locations and a set of customers, the goal is to determine which facilities to open to serve all customers while minimizing both opening and assignment costs. Since this problem is classified as NP-hard, obtaining exact solutions at large scales could not be possible, thereby motivating the use of approximation techniques and metaheuristics. Although early studies used exact formulations derived from the UFLP model, recent research has emphasized the efficacy of approximate and metaheuristic algorithms, which achieve high-quality solutions with substantially reduced computational effort. This work introduces a Variable Neighborhood Search approach to tackle this problem. With the aim of guiding the search toward higher-quality solutions, machine learning techniques have been incorporated to this process. Experimental results on well-known benchmark datasets demonstrate that our method reaches solutions very close to the optimal values, with significantly shorter execution times, outperforming state-of-the-art algorithms validated by the pairwise non-parametric Wilcoxon statistical test.

Lucas Martín-García

Artificial Intelligence Phd Student

Lucas Martin graduated in Mathematics and Computer Science in the Complutense University of Madrid in 2024. He is working here as a researcher focusing in optimization problems.

Isaac Lozano-Osorio

Phd in Artificial Intelligence

Isaac Lozano graduated with a double degree in Computer Engineering and Computer Engineering from the Universidad Rey Juan Carlos, where he was awarded the prize for the Best Final Project. Subsequently, he completed a Master in Artificial Intelligence Research (UIMP). His main research interests are focused on the interface between Computer Science, Artificial Intelligence and Operations Research. Most of his publications deal with the development of metaheuristic procedures for graph modeled optimization problems.

J. Manuel Colmenar

Full Professor

My research interests are focused on metaheuristics applied to optimization problems. I have worked on different combinatorial optimization problems applying trajectorial algorithms such us GRASP or VNS. Besides, I am very interested in applications of Grammatical Evolution, specifically in model and prediction domain, as alternative to machine learning approaches.