Abstract: Traveling salesman problem (TSP) is an important problem in combinatorial optimization, which serves as the foundation for significant frontier scientific issues, including integrated circuit design and genomics. Learning-based methods have shown impressive results in solving the TSP, demonstrating efficient perception and decision-making abilities. However, as the scale of modern scenarios continues to expand, efficiently improving existing solutions through learning approaches remains a challenging and urgent task. A general framework for re-insertion improvement in the TSP is proposed. Focusing the core decision on the selection of re-insertion positions, we design a neural re-insertion improvement (NRII) algorithm based on deep reinforcement learning. NRII integrates multiple attention mechanisms and neural components to achieve the perception and parameterization of re-insertion positions, followed by model training through a policy optimization method. Extensive numerical experiments validate that the NRII algorithm can be combined with various solving methods to efficiently improve the solution quality across different scales and distributions. Additionally, detailed sensitivity analyses of the hyperparameter in NRII are also conducted.

Key words: Large-scale traveling salesman problem, Re-insertion decision