Abstract: A new algorithm, called the travelling-around-the-center method, is proposed in this paper. It is a deterministic algorithm, with its time complexity the same as the nearest neighbor algorithm, that is, O(n2), where n is the number of cities. Numerical tests for plane travelling salesman problems with various sizes are carried out by using the travelling-around-the-center method and the nearest neighbor algorithm, and the performances of both algorithms are compared. The following conclusions are drawn: (1) The relative performances of the solutions of the travelling-around-the-center method and the nearest neighbor algorithm depend on the number and distribution of the cities in a specific travelling salesman problem. (2) For n=4, the travelling-around-the-center method can always obtain the best solution, while the nearest neighbor algorithm often cannot do so. (3) For a small size problem with n<20, the travelling-around-the-center method can generally obtain better solutions than the nearest neighbor algorithm. (4) For a middle size problem with 20≤n≤30, the quality of the solution obtained by the travelling-around-the-center method is similar to that obtained by the nearest neighbor algorithm. (5) For a large size problem with n>30, the quality of the solution obtained by the travelling-around-the-center method is generally not as good as that obtained by the nearest neighbor algorithm.
|
Received: 18 August 2008
|
|
|
|