A transformer-based structure-aware model for tackling the traveling salesman problem.

Abstract

Leveraging the Transformer architecture to develop end-to-end models for addressing combinatorial optimization problems (COPs) has shown significant potential due to its exceptional performance. Nevertheless, a multitude of COPs, including the Traveling Salesman Problem (TSP), displays typical graph structure characteristics that existing Transformer-based models have not effectively utilized. Hence, this study focuses on TSP and introduces two enhancements, namely closeness centrality encoding and spatial encoding, to strengthen the Transformer encoder's capacity to capture the structural features of TSP graphs. Furthermore, by integrating a decoding mechanism that not only emphasizes the starting and most recently visited nodes, but also leverages all previously visited nodes to capture the dynamic evolution of tour generation, a Transformer-based structure-aware model is developed for solving TSP. Employing deep reinforcement learning for training, the proposed model achieves deviation rates of 0.03%, 0.16%, and 1.13% for 20-node, 50-node, and 100-node TSPs, respectively, in comparison with the Concorde solver. It consistently surpasses classic heuristics, OR Tools, and various comparative learning-based approaches in multiple scenarios while showcasing a remarkable balance between time efficiency and solution quality. Extensive tests validate the effectiveness of the improvement mechanisms, underscore the significant impact of graph structure information on solving TSP using deep neural networks, and also reveal the scalability and limitations.