A TSP solving model based on multiscale feature fusion and adaptive context awareness

Abstract

Transformer-based deep reinforcement learning for the Traveling Salesman Problem (TSP) often struggles to capture spatial topology and avoid local optima. To address this, we propose a novel model featuring a Multi-Scale Grid Attention Encoder (MSGAE) to fuse local and global spatial features, alongside a bottleneck-enhanced adaptive decoder (BMA) to prevent local optima. Optimized via multi-start Monte Carlo sampling, the model balances solution quality, efficiency, and generalization. Experiments demonstrate a highly competitive 0.25% optimality gap on TSP100, and the model exhibits excellent generalization capability in real-world applications.