A Multilevel Approach to the Travelling Salesman Problem

C. Walshaw


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 80 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:34 BST 2004