Garnet: integrating random walk encoding and graph rewiring for routing optimization
Abstract
The Traveling Salesman Problem (TSP) is a fundamental NP-hard routing problem with applications in logistics and transportation. This paper presents GARNET, a graph neural network framework that integrates three components: decomposed relative random walk probabilities (D-RRWP) encoding for multi-hop structural representation, random graph rewiring for enhanced connectivity, and graph-tailored additive sparse attention (GRASS) for feature aggregation. Trained with proximal policy optimization, GARNET achieves competitive optimality gaps on benchmark instances with inference times substantially faster than exact solvers. Ablation studies confirm that each component contributes to performance, and experiments on real-world road networks demonstrate practical applicability.
Fields of Study & Subjects
Vehicle Routing Optimization Methods
Traffic Prediction and Management Techniques
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- Artificial Intelligence Review
- Publisher
- Springer Science and Business Media LLC
- Volume
- 59
- Issue
- 7
- Publication date
- 3 April 2026
- Language
- EN