LKH

Version 1.3 (July 2002)

LKH is an effective implementation of the Lin-Kernighan heuristic for solving the traveling salesman problem.

Computational experiments have shown that LKH is highly effective. Even though the algorithm is approximate, optimal solutions are produced with an impressively high frequency. LKH has produced optimal solutions for all solved problems we have been able to obtain; including a 15,112-city problem (at the time of writing, the largest nontrivial problem solved to optimality). Furthermore, the algorithm has improved the best known solutions for a series of large-scale problems with unknown optima, among these a 85,900-city problem and a 1,904,711-city problem.

LKH has been described in the report

K. Helsgaun,
"An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic",
DATALOGISKE SKRIFTER (Writings on Computer Science), No. 81, 1998,
Roskilde University.

and in the paper

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

See also the addendum to the paper.

Installation

LKH has been implemented in the programming language C. The software, approximately 4000 lines of code, is entirely written in ANSI C and portable across a number of computer platforms and C compilers.

The code can be downloaded in two formats

  1. LKH-1.3.tgz (gzipped tar file, 5.9 MB)
  2. LKH-1.3.sit (Stuffit archive, 4.6 MB)

If a UNIX machine is used, download the software in the first format. Next execute the following UNIX commands:

    gzip -d LKH-1.3.tgz
    tar xvf LKH-1.3.tar
    cd LKH-1.3
    make

An executable file called LKH.UNIX is now available in the directory LKH-1.3.

If a MacOS or a Windows machine is used, download the software in the second format. Next unstuff it with Stuffit Expander™ (freeware available at http://www.aladdinsys.com).

The code is distributed for research use. The author reserves all rights to the code.

CHANGES IN VERSION 1.3:

The distance type GEOM has been added (see www.math.princeton.edu/tsp/world).

Additional control information may now be given in the parameter file by means of the following keywords:

BACKTRACK_MOVE_TYPE
CANDIDATE_FILE
INITIAL_TOUR_FILE
MAX_SWAPS
MERGE_TOUR_FILE_1
MERGE_TOUR_FILE_2
RESTRICTED_SEARCH

CHANGES IN VERSION 1.2:

Execution times are measured more accurately, if the getrusage function is supported by the system.

CHANGES IN VERSION 1.1:

The code has been made more robust regarding the solution of asymmetric problems. The previous code could loose its way in some cases due to integer overflow.

[home]