<p>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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Neural Re-Insertion Improvement Algorithm for Large-Scale TSP

  • Wen-Zhao Liu,
  • Cong-Ying Han,
  • Tian-De Guo

摘要

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.