论文部分内容阅读
Lin-Kernighan算法被认为是求解旅行商问题效率最高的启发式算法之一,而初始解构造策略是影响Lin-Kernighan算法路径改进效率重要环节。以往的研究中通常采用某一种启发式策略构造初始解,但目前尚无相关研究对不同启发式构造策略在Lin-Kernighan算法中的性能给出对比。以经典的旅行商问题为对象,分析了8种常用启发式构造策略解的生成情况,得出其中最远插入法,最近插入法,最邻近法和节约算法适用于Lin-Kernighan算法的初始解构造。通过对TSPLIP中6个经典TSP实例仿真,进一步验证了这4种启发式构造策略均可以在保证解具有较高质量的情况下,显著缩小搜索空间和计算时间,提高寻优效率。此外,实验结果表明节约算法由于初始解构造效果较好,较其他启发式构造策略具有更快的收敛速度,而最近插入法在寻优率方面优于其他策略。
The Lin-Kernighan algorithm is considered as one of the most efficient heuristic algorithms for solving the traveling salesman problem. However, the initial solution construction strategy is an important part of the efficiency improvement of the Lin-Kernighan algorithm. In the past, a certain heuristic strategy was usually used to construct the initial solution. However, there is no relevant research comparing the performance of different heuristic strategies in Lin-Kernighan algorithm. Based on the classical traveling salesman problem, this paper analyzes the generation of eight commonly used heuristic constructive solutions and finds out that the farthest-in, the nearest-neighbor, the nearest-neighbor and the saving algorithms are suitable for the initial solution of Lin-Kernighan algorithm structure. Through the simulation of six classic TSP instances in TSPLIP, it is further verified that these four kinds of heuristic construction strategies can both significantly reduce the search space and computation time and improve the optimization efficiency under the condition of ensuring the high quality of the solution. In addition, the experimental results show that the saving algorithm has a faster convergence rate than the other heuristic constructs due to the better initial solution, and the recent insertion method outperforms other strategies in the search rate.