Two-Stage Attention Model to Solve Large-Scale Traveling Salesman Problems

The Traveling Salesman Problem (TSP) widely exists in real-world scenarios. Various methods, such as exact methods, heuristic methods, and deep learning-based methods, can solve TSPs efficiently. However, as the size of the problems increases, these methods become increasingly time-consuming due to the high complexity of large-scale TSPs. This paper proposes a two-stage attention model (TSAM) that incorporates the divide-and-conquer strategy and attention model to solve large-scale TSPs efficiently. Experimental results demonstrate that TSAM can rapidly produce promising solutions for TSP instances ranging from 500 to 10,000 nodes.