求解TSP问题的并集搜索的新宏启发算法

被引：5

作者：

江贺

周智

邹鹏

陈国良

机构：

[1] 中国科学技术大学计算机系

[2] 国家高性能计算中心

[3] 国家高性能计算中心安徽合肥

来源：

中国科学技术大学学报 | 2005年 / 03期

关键词：

TSP; 启发集; 统计模型; 并集搜索;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

利用TSP问题解的概率统计模型,分析了TSP问题的局部最优解并集的性质,发现局部最优解的并集规模较小且包含了绝大多数全局最优解的边.利用该性质,将局部最优解并集作为启发集,并调用局部搜索算子在其上求解TSP问题,由此得到一种称为并集搜索的新宏启发算法.利用该算法还改进了目前广泛使用的求解TSP问题的算法ILK、LKH,在TSPLIB中典型实例上的实验结果表明,新算法在解的质量上有了较显著的提高.

引用

页码：367 / 375

页数：9