Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Garnet: integrating random walk encoding and graph rewiring for routing optimization

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年4月3日

查看全文
  • Abdelaadim Khriss,
  • Aissa Kerkour Elmiad,
  • Mohammed Badaoui,
  • Toufik Mzili,
  • Hamzah A. Alkhazaleh

摘要

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.