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

• 作者: 付连宁 吴耀华 崔文 曾华
• 来源期刊: 山东大学学报：工学版
• 学科: 工学
• 关键词: Lin-Kernighan算法 初始解 启发式算法 旅行商问题 性能评价
• 年，卷（期）: 2012,（2）
• 所属期刊栏目: 控制科学与工程
• 页码范围: 30-35
• 分类号: TP18
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴耀华	山东大学控制科学与工程学院	103	1223	20.0	28.0
2	曾华	山东大学控制科学与工程学院	4	23	3.0	4.0
3	付连宁	山东大学控制科学与工程学院	3	12	2.0	3.0
4	崔文	山东大学现代物流研究中心	4	15	3.0	3.0