A Multilevel Approach to the Travelling Salesman Problem

Chris Walshaw

August 21, 2000

Abstract:

We motivate, derive and implement a multilevel approach to the travelling salesman problem. The resulting algorithm progressively coarsens the problem, initialises a tour and then employs either the Lin-Kernighan (LK) or the Chained Lin-Kernighan (CLK) algorithm to refine the solution on each of the coarsened problems in reverse order. In experiments on a well established test suite of 79 problem instances we found multilevel configurations that either improved the tour quality by over 25% as compared to the standard CLK algorithm using the same amount of execution time, or that achieved approximately the same tour quality over 7 times more rapidly. Moreover the multilevel variants seem to optimise far better the more clustered instances with which the LK & CLK algorithms have the most difficulties.

Keywords: Multilevel Refinement; Travelling Salesman; Combinatorial Optimisation.




Fri Aug 13 13:39:39 BST 2004