Abstract
Neural Combinatorial Optimization (NCO) has shown promising results in graph-based optimization problems, although its application to facility location problems remains limited. This work studies the use of NCO for the Generalized Regenerator Location Problem (GRLP), a network design problem where the objective is to minimize the number of active regenerators required to connect all demand nodes. A constructive algorithm guided by a Graph Neural Network (GNN) is proposed, where the model is trained through Reinforcement Learning (RL) on generated GRLP instances and later combined with a local search phase. The method is compared with exact, heuristic, and metaheuristic approaches from the literature. The results show that the NCO approach is competitive with the state of the art and, in the largest instances, obtains better constructive solutions than a Greedy Randomized Adaptive Search Procedure (GRASP) method using the same improvement phase. Despite the explainability and hardware limitations associated with these models, these results indicate that NCO algorithms can learn better construction strategies than problem-specific heuristics without the need for expert knowledge.
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.
Abraham Duarte
Full Professor
Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.
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.