求解旅行商问题的循环局部搜索算法的运行时间和性能分布分析

摘要：

旅行商问题(Traveling Sa1esman Problem,TSP)是组合优化中最典型的NP难问题之一,长期以来人们都在寻求快速高效的近似算法以在合理的计算时间内准确地解决大规模问题,并设计出许多高效实用的启发式和宏启发式算法,其中循环LK算法是性能最好和最具代表性的算法之一.作者研究了该算法的运行时间分布:通过对TSPLIB中大量不同规模的TSP实例的运行时间分布的统计分析和拟合,发现求解TSP问题的循环LK算法的运行时间分布很好地服从Weibull分布,并进一步给出了该分布对求解TSP问题的物理意义.作者同时首次给出了循环LK算法求解TSP问题得到的解的性能分布以及由此得到的一些有实际指导意义的结论.

关键词：旅行商、循环LK算法、运行时间分布、解的性能分布、weibull分布

所属期刊栏目：29

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

资助基金：科技部科研项目G1998030403

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

页数：共8页

页码：92-99