Lin-Kernighan算法初始解的启发式构造策略

Heuristic construction method for the initial tour of the Lin-Kernighan algorithm

Lin-Kernighan算法被认为是求解旅行商问题效率最高的启发式算法之一,而初始解构造策略是影响Lin-Kernighan算法路径改进效率重要环节。以往的研究中通常采用某一种启发式策略构造初始解,但目前尚无相关研究对不同启发式构造策略在Lin-Kernighan算法中的性能给出对比。以经典的旅行商问题为对象,分析了8种常用启发式构造策略解的生成情况,得出其中最远插入法,最近插入法,最邻近法和节约算法适用于Lin-Kernighan算法的初始解构造。通过对TSPLIP中6个经典TSP实例仿真,进一步验证了这4种启发式构造策略均可以在保证解具有较高质量的情况下,显著缩小搜索空间和计算时间,提高寻优效率。此外,实验结果表明节约算法由于初始解构造效果较好,较其他启发式构造策略具有更快的收敛速度,而最近插入法在寻优率方面优于其他策略。

Initialization construction strategy is an important phase of the Lin-Kernighan algorithm, which is known as one of the most efficient heuristic methods to solve the traveling salesman problem. In most past research, only one construction strategy was adopted, but there was little research on what strategies could be used in the Lin-Kemighan al- gorithm and how differently they perform. 8 construction strategies were analyzed, and 4 of them were found applicable for Lin-Kemighan initialization. Numerical experiments and computational results with 6 TSPLIP instances showed that the 4 construction strategies proposed were effective and efficient initialization methods. Additionally, it was proved that the Clark Wright algorithm had the best convergence speed, while the nearest insertion algorithm had the best optimiza- tion rate.