A solution method for the traveling salesman problem based on multi-scale features and dynamic optimization

Abstract

As a classic NP-hard problem, the Traveling Salesman Problem (TSP) exhibits exponentially increasing complexity with node quantity, making optimal solutions difficult for large-scale instances. Traditional exact and heuristic algorithms still struggle to balance computational cost with global optimality. Recently, deep learning has enabled end-to-end sequence modeling for TSP, yet existing models face limitations in global feature modeling, cross-scale generalization, and decoding stability. To address these issues, this study proposes a multi-scale deep optimization model based on an encoder-decoder architecture. In the encoding phase, an Exponential Moving Average (EMA) mechanism enhances global spatial correlation via multi-scale feature smoothing and dynamic weighting while suppressing feature noise. In the decoding phase, a Triplet-Reasoning attention mechanism captures high-order spatial dependencies through three-branch interaction (node, edge, path), balancing local coherence with global optimization. Additionally, a dynamic sampling strategy mitigates training-inference distribution shifts to improve generalization. Experimental results on benchmark datasets show that the proposed model outperforms mainstream deep learning methods in path length and optimality gap, demonstrating superior stability and global optimality, particularly on medium and large-scale instances. This work validates the effectiveness of the multi-scale EMA and Triplet-Reasoning mechanisms, providing a new direction for deep learning-based graph optimization research.