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

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

作　　者：曾华[1] 崔文[2] 付连宁[1] 吴耀华[1] 

机构地区：[1]山东大学控制科学与工程学院,山东济南250061 [2]山东大学现代物流研究中心,山东济南250061

出　　处：《山东大学学报（工学版）》2012年第2期30-35,共6页Journal of Shandong University（Engineering Science）

基　　金：山大研究生自主创新基金资助项目(31400070613065);山东大学优秀研究生科研创新基金资助项目(10000080398154)

摘　　要：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.

关 键 词：Lin-Kernighan算法 初始解 启发式算法 旅行商问题 性能评价 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]