LKH

Keld Helsgaun
Department of Computer Science
Roskilde University
DK-4000 Roskilde, Denmark
E-mail: keld@ruc.dk


LKH is an implementation of a modified version of the
Lin-Kernighan algorithm. 

The new algorithm differs in many details from the original one.
The most notable difference is found in the search strategy.
The new algorithm uses larger (and more complex) search steps
than the original one. Also new is the use of sensitivity 
analysis to direct and restrict the search.

In the development of the algorithm great emphasis was put on
achieving high quality solutions, preferably optimal solutions
in a reasonable short time. 

Computational tests show that the implementation is highly
effective.  It has found optimal solutions for all solved problem
instances we have been able to obtain, including a 13509-city
problem (the largest nontrivial problem instance solved to 
optimality today). This is remarkable, considering that the
modified algorithm does not employ backtracking.
 
The effectiveness of the algorithm is primarily achieved through
an efficient search strategy. The search is based on 5-opt moves
restricted by carefully chosen candidate sets.  Minimum spanning
trees is used to define candidate sets that are small, but large 
enough to allow excellent solutions to be found (usually the
optimal solutions).

The algorithm and its implementation is described in

  K. Helsgaun, ``An Effective Implementation of the Lin-Kernighan
  Traveling Salesman Heuristic,'' European Journal of Operational
  Research 126 (1), 106-130 (2000).

The LKH-software is available from www.dat.ruc.dk/~keld/research/LKH.