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

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

SIZESCALE: NEW ALGORITHMS FOR THE TRAVELING SALESMAN PROBLEM

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.