摘要
旅行商 ( TSP)问题是组合优化中最典型的 NP-Hard问题之一 ,目前关于该问题的启发式算法主要分为两类 :环路构造算法和环路改进算法 .对于第 1类算法 ,首次提出了在环路构造中成批加入顶点 ,同时在构造过程对环路进行局部优化的思想 ,由此得到了一种新的算法 :Size Scale-Construct,它的解质量极大地改进了现有的环路构造算法 .对于第 2类算法 ,在分析局部最优解与全局最优解之间关系的基础上 ,提出了另一个采用局部最优解的交集作为初始环路的新算法 :Size Scale-Improve.实验结果表明该算法在解的质量和求解速度上都较大地改进了现有最好的环路改进算法 ;另一方面 。
The Traveling Salesman Problem is one of the typical NP-hard problems in combinatorial optimization and arises in many fields such as VLSI design and vehicle routing. The main heuristic algorithms for TSP fall into two classes: tour construction algorithms and tour improvement algorithms. For tour construction algorithms, a novel idea is proposed, which adds vertices into the subtour in batches and improves the subtour during construction. Consequently a new algorithm SizeScale-Construct is presented, which considerably improves the known tour construction algorithms in the quality of solution. For tour improvement algorithms, a new algorithm SizeScale-Improve is also proposed based on the analysis of the relation between local optimum and global optimum. In the algorithm the intersection of some local optima is used as the initial subtour and then the same operations as in SizeScale-Construct are excuted. The experimental result shows that the algorithm outperforms the known best ones in quality of solution and running speed. On the other hand, the time complexities in the worst case and the average case for the two algorithms are also analysed, which shows that the algorithms are practical.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2002年第10期1294-1302,共9页
Journal of Computer Research and Development
基金
国家重点基础研究发展规划项目基金 (G19980 3 0 40 3 )
中国科学院高水平大学建设项目 (KY2 70 6)资助
