Solving Method of Traveling Salesman Problem Based on Performer Graph Self-attention Mechanism

Abstract The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem that seeks to find the shortest possible route for a salesman to visit each city exactly once and return to the starting point. This problem serves as a crucial benchmark for assessing the efficiency of optimization algorithms in real-world scenarios. As an NP-hard problem, solving larger instances of TSP within several minutes is challenging for traditional algorithms. This paper presents a deep learning approach combining Graph Self-Attention (GSA) with the Performer's linear complexity attention mechanism. The GSA module, built on Graph Convolutional Networks (GCNs), captures complex node relationships to enhance feature representations and encoding capabilities. The Performer's mechanism in the decoder improves efficiency in solving large-scale TSP instances. Additionally, we introduce a Partial Optimization with Or-opt (POO) method to optimize parts of the solution, avoiding local minima and enhancing accuracy. Experimental results indicate that our method performs comparably to current leading methods. Moreover, comparative experiments validate the significance of the GSA module in enhancing model performance and leveraging graph structural information.