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

作者：邹鹏; 周智; 江贺; 陈国良; 顾钧

来源：计算机学报, 2006, (01): 92-99.

• 旅行商
• 循环LK算法
• 运行时间分布
• 解的性能分布
• Weibull分布 TSP
• iterated Lin-Kernighan algorithm
• RTDs
• SPDs
• Weibull distribution

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

• 单位
  中国科学技术大学; 香港科技大学