August 21, 2000
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.