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.