Symmetry-Regularized Transformer for Solving Traveling Salesman Problems
Shuyun Li, Maoli Wang, Zixin Liu, Huan Ma, Zhihui Wang, Xubing Dou, Xinchang Zhang · 2025
The Traveling Salesman Problem (TSP), a well-known NP-hard problem, is widely applied across manufacturing, biology, transportation, and other fields. In recent years, deep reinforcement learning (DRL), particularly DRL based on Transformer architectures, has emerged as a popular approach to solving TSP. However, the quadratic computational and space complexities of Transformer models pose challenges for handling larger-scale TSP instances. This paper introduces Sym-Favformer, an end-to-end DRL method based on symmetry regularization in the Transformer. In this approach, the encoder incorporates a Fast Attention Via positive Orthogonal Random features (FAVOR+) mechanism with linear complexity, while the decoder adopts a distance-based dynamic selection mechanism, and employs the Lion optimizer to reduce training time and memory consumption. To enhance performance and generalization, Sym-Favformer applies a random transformation data augmentation technique within the encoder and introduces enhanced context embedding in the decoder. Subsequently, the model is trained using a symmetry-regularized REINFORCE method. Experimental results show that Sym- Favformer significantly outperforms existing end-to-end DRL methods on both randomly generated benchmark instances and TSPLIB datasets, demonstrating strong generalization to larger-scale TSP instances.