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.