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

山东大学学报(工学版) ›› 2012, Vol. 42 ›› Issue (2): 30-35.

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

曾华¹,崔文²,付连宁¹,吴耀华^1*

1. 山东大学控制科学与工程学院, 山东济南 250061; 2. 山东大学现代物流研究中心, 山东济南 250061

收稿日期:2011-05-28 出版日期:2012-04-20 发布日期:2011-05-28
通讯作者: 吴耀华(1963- ),男,辽宁沈阳人,教授,博士生导师,主要研究方向为物流工程,最优化技术与应用等.Email: yaohua.wu@sdu.edu.cn E-mail:yaohua.wu@sdu.edu.cn
作者简介:曾华(1981- ),女,黑龙江肇东人,博士研究生,主要研究方向为数据挖掘与组合优化.E-mail:zenghua@mail.sdu.edu.cn.
基金资助:
山大研究生自主创新基金资助项目(31400070613065);山东大学优秀研究生科研创新基金资助项目(10000080398154)

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

ZENG Hua1, CUI Wen2, FU Lian-ning1, WU Yao-hua1*

1. School of Control Science and Engineering, Shandong University, Jinan 250061, China;
2. The Logistics Institute, Shandong University, Jinan 250061, China

Received:2011-05-28 Online:2012-04-20 Published:2011-05-28

摘要/Abstract

摘要：

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

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

Abstract:

Initialization construction strategy is an important phase of the LinKernighan 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 LinKernighan algorithm and how differently they perform. 8 construction strategies were analyzed, and 4 of them were found applicable for LinKernighan 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 optimization rate.

Key words: LinKernighan, initial path, heuristic algorithm, the traveling salesman problem, performance evaluation

曾华1,崔文2,付连宁1,吴耀华1*. Lin-Kernighan算法初始解的启发式构造策略[J]. 山东大学学报(工学版), 2012, 42(2): 30-35.

ZENG Hua1, CUI Wen2, FU Lian-ning1, WU Yao-hua1*. Heuristic construction method for the initial tour of the Lin-Kernighan algorithm[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(2): 30-35.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

[1]	易云飞,苗剑,林郭隆,殷智. 基于牛顿力学和博弈论模型的粒子网络优化算法[J]. 山东大学学报(工学版), 2017, 47(1): 28-36.
[2]	王立宏,李强. 旅行商问题的一种选择性集成求解方法[J]. 山东大学学报(工学版), 2016, 46(1): 42-48.
[3]	戴红伟, 杨玉, 仲兆满, 李存华. 改进量子交叉免疫克隆算法及其应用[J]. 山东大学学报(工学版), 2015, 45(2): 17-21.
[4]	吴克寿,陈玉明,曾志强. 基于邻域关系的决策表约简[J]. 山东大学学报(工学版), 2012, 42(2): 7-10.
[5]	付连宁1, 崔文2, 曾华1. 并行节约算法的自适应邻域选择策略[J]. 山东大学学报(工学版), 2012, 42(1): 72-80.
[6]	蔡荣英,王李进,吴超,钟一文*. 一种求解旅行商问题的迭代改进蚁群优化算法[J]. 山东大学学报(工学版), 2012, 42(1): 6-11.