Version 1.0 (April 2014)

BLKH is a program for solving the Bottleneck Traveling Salesman Problem and the Maximum Scatter Traveling Salesman Problem, two variations of the classical Traveling Salesman Problem. The Bottleneck Traveling Salesman Problem (BTSP) asks for a tour in which the largest edge is as small as possible. The figure above depicts an optimal solution for a BTSP instance consisting of 1097 cities in the 49 continental US states. The Maximum Scatter Traveling Salesman Problem asks for a tour in which the smallest edge is as large as possible. The figure below depicts a near-optimal solution of the MSTSP version of the US instance.

BLKH has been described in the report

         K. Helsgaun,
         Solving the Bottleneck Traveling Salesman Problem Using the Lin-Kernighan-Helsgaun Algorithm.
         Computer Science Report #143, Roskilde University, 2014.



BLKH has been implemented in the programming language C and runs under Unix/Linux.

Source code, test instances and solution tours can be downloaded here: BLKH-1.0.tgz (gzipped tar file, approximately 1 MB).

Execute the following UNIX commands:

tar xvfz BLKH-1.0.tgz
cd BLKH-1.0
make _O

Five executable files called BLKH, BLKH_EXP, MBLKH, MBLKH_EXP, and LKH will now be available in the directory BLKH-1.0. LKH is an executable of LKH-2.0.7.

More efficient executables of BLKH and BLKH_EXP are obtained by executing the UNIX command:

make _R

BLKH is used for solving a given BSTP instance once, whereas BLKH_EXP is used for solving a BTSP instance using a specified number of independent runs, default is 10.

MBLKH and MBLKH_EXP are the corresponding executables for solving MSTSP instances.

To ease the running of BLKH and BLKH_EXP, four scripts, runBLKH, runBLKH_ASYM, runBLKH_EXP, and runBLKH_ASYM_EXP, are provided. They create suitable parameter files and execute BLKH or BLKH_EXP. Scripts with the denotation ASYM are used for asymmetric instances.

Similarly, to ease the running of MBLKH and MBLKH_EXP, four scripts, runMBLKH, runMBLKH_ASYM, runMBLKH_EXP, and runMBLKH_ASYM_EXP, are provided.

In order to ease solution of a specified set of instances, the following scripts are provided:

      runAMAT, runATSPLIB, runBALAS, runCOIN, runCRANE, runDISK, runHARD,
      runJM, runMSTSP, runNATIONAL, runRAN, runRECT, runRTILT, runSHOP,
      runSMAT, runSTILT, runSUPER, runTEST, runTMAT, runTSMAT, runTSPLIB,
      runUK66+US1097, runVERY_LARGE, runVLSI

It is recommended to run the script runTEST in order to test the installation:


The BLKH-1.0 directory contains the following subdirectories:

      TSP_INSTANCES:      Library of symmetric benchmark instances.
                                          The files (418 MB) can be downloaded from

      ATSP_INSTANCES:    Library of asymmetric benchmark instances.
                                          The files (478 MB) can be downloaded from

      SRC:                            Source code of BLKH.

      LKH-2.0.7:                   Source code of the current version of LKH.

      TMP:                           Temporary files used during the solution process.