SizeScale:求解旅行商问题(TSP)的新算法

摘要：

旅行商(TSP)问题是组合优化中最典型的NP-Hard问题之一,目前关于该问题的启发式算法主要分为两类:环路构造算法和环路改进算法.对于第1类算法,首次提出了在环路构造中成批加入顶点,同时在构造过程对环路进行局部优化的思想,由此得到了一种新的算法:SizeScale-Construct,它的解质量极大地改进了现有的环路构造算法.对于第2类算法,在分析局部最优解与全局最优解之间关系的基础上,提出了另一个采用局部最优解的交集作为初始环路的新算法:SizeScale-Improve.实验结果表明该算法在解的质量和求解速度上都较大地改进了现有最好的环路改进算法;另一方面,理论上对于最坏情况和平均情况时间复杂度的分析表明这两个算法是实用的.

关键词：组合优化、TSP问题、NP Hard、启发式算法

所属期刊栏目：39

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家重点基础研究发展计划973计划G1998030403;中国科学院高水平大学校科研和教改项目KY2706

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1294-1302