Applying Neural Combinatorial Optimization for the Generalized Regenerator Location Problem

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.

Publication
Advances in Artificial Intelligence. CAEPIA 2026. Lecture Notes in Computer Science, vol 16999, Springer Nature Switzerland