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

Resumen

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

Estudiante de Doctorado en Inteligencia Artificial

Lucas Martín se graduó en Matemáticas e Ingeniería Informática en la Universidad Complutense de Madrid en 2024. Actualmente trabaja como investigador centrado en problemas de optimización.

Isaac Lozano-Osorio

Doctor en Inteligencia Artificial

Isaac Lozano se graduó en el Doble grado de Ingeniería Informática e Ingeniería de Computadores por la Universidad Rey Juan Carlos. Al finalizar el doble grado, fue galardonado con el premio al Mejor Proyecto Fin de Carrera. Posteriormente, realizó un Máster en Investigación en Inteligencia Artificial (UIMP) y es doctor por la Universidad Rey Juan Carlos. Sus principales intereses de investigación se centran en la interfaz entre las Ciencias de la Computación, la Inteligencia Artificial y la Investigación Operativa. La mayoría de sus publicaciones tratan sobre el desarrollo de procedimientos metaheurísticos para problemas de optimización modelados por grafos.

J. Manuel Colmenar

Catedrático de Universidad

Mis intereses de investigación se centran en las metaheurísticas aplicadas a problemas de optimización. He trabajado en diferentes problemas de optimización combinatoria aplicando algoritmos trajectoriales como GRASP o VNS. Además, estoy muy interesado en las aplicaciones de la Evolución Gramatical, específicamente en el dominio de los modelos y la predicción, como alternativa a los enfoques de aprendizaje automático.