A Neural Solver With Traversal-Based Feature Representation and Adjacent Attention for Capacitated Arc Routing Problem

Neural combinatorial optimization methods have addressed many routing problems effectively, but the capacitated arc routing problem (CARP) poses a significant challenge due to its distinctive graph structure and task requirements. In this paper, we propose a novel deep reinforcement learning algorithm that incorporates a traversal-based feature representation and an adjacent multi-head attention mechanism. The traversal-based feature representation indexes vertices through traversal and utilizes these indices as features, which encapsulates adjacency and distance information within them. It also enables the creation of fixed-length feature vectors for tasks so that the model can be applied to problems with different scales. The adjacent multi-head attention mechanism is tailored to the graph structure of CARP. It encodes each task with information from its neighboring edges, focusing on adjacent information learning rather than global pattern recognition, which is more feasible for generalizing across diverse graphs. The proposed algorithm is compared with heuristic, meta-heuristic, and other neural combinatorial optimization methods across multiple datasets. The experimental results indicate its strong competitiveness in both effectiveness and generalization ability. Our code is available at <uri xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">https://github.com/QWQZQQ/AEGT</uri>