Dynamic Topology-Aware Linear Attention Network for Efficient Traveling Salesman Problem Optimization
Shilong Zhao, Qianqian Duan · Mathematics · 2026
The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem with broad applications in logistics and smart agriculture. However, despite significant progress in Transformer-based deep reinforcement learning methods, two major challenges remain. First, standard linear embedding layers struggle to capture dynamic local geometric relationships between nodes. Second, the quadratic complexity of self-attention in the decoder hinders efficiency in large-scale TSP instances. To address these issues, this paper proposes a Dynamic Topology-Aware Linear Attention Network (DTALAN). The encoder employs a Channel-aware Topological Refinement Graph Convolution (CTRGC) module to model local geometric structures and a Global Attention Mechanism (GAM) for adaptive feature recalibration. The decoder introduces a temporal locality-aware attention mechanism that focuses only on recently visited nodes, reducing self-attention complexity from quadratic to linear while preserving solution quality. The policy network is trained using the REINFORCE algorithm with baseline and the Adam optimizer. Experiments on random instances and the TSPLIB benchmark show that DTALAN outperforms leading deep reinforcement learning methods in both optimality gap and inference efficiency. For TSP100, it achieves an optimality gap of 0.55%, producing near-optimal solutions. Ablation studies confirm that both the improved CTRGC and enhanced GAM modules are essential to these results.