CLKH
Version 1.1 (March 2021)
CLKH is a program for solving the Clustered Traveling Salesman Problem (CTSP), an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into clusters, and the salesman has to visit the cities of each cluster consecutively. The figure above depicts a solution for an instance consisting of 1097 cities in the 49 continental US states (each state forms a cluster).
CLKH transforms a CTSP instance into a TSP instance and solves the latter using the TSP-solver LKH. Despite that LKH is not modified in order to cater for the unusual structure of the TSP instances, CLKH's performance is quite impressive. All instances in a well-known library of benchmark instances, GTSPLIB, could be solved in a reasonable time, and it was possible to find high-quality solutions for a series of new large-scale instances with up to 17,180 clusters and 85,900 vertices.
CLKH has been described in the report
K. Helsgaun,
Solving the Clustered Traveling Salesman Problem Using the Lin-Kernighan-Helsgaun Algorithm.
Computer Science Report #142, Roskilde University, 2014.
Installation
CLKH has been implemented in the programming language C and runs under Unix/Linux.
Source code, test instances and solution tours can be downloaded here: CLKH-1.1.tgz (gzipped tar file, approximately 10 MB).
Execute the following UNIX commands:
tar xvfz CLKH-1.0.tgz
cd CLKH-1.0
make
Four executable files called CLKH, CLKH_EXP, CLKH_CHECK, and LKH will now be available in the directory CLKH-1.1.
CLKH is used for solving a given instance once, whereas CLKH_EXP is used for solving an instance using a specified number of independent runs.
CLKH_CHECK may be used to check that a solution tour is feasible (i.e., visits the cities of each cluster consecutively and has the correct length).
LKH is an executable of LKH-2.0.9.
To ease the running of CLKH and CLKH_EXP, two scripts, runCLKH and runCLKH_EXP, are provided. They create suitable parameter files and next execute CLKH and CLKH_EXP, respectively.
The scripts runSmall, runLarge and runVeryLarge can be used for solving the GTSPLIB instances. It is recommended to run the script runSmall in order to test the installation:
./runSmall
The software is distributed for research use. The author reserves all rights to the code.
BAF instances
In his PhD thesis, “Techniques hybrides de recherche exacte et approchée: application à des problèmes de transport” (2008), Boris Bontoux defined a series of GTSP instances, where the groups (clusters) are not formed by a clustering method (as is the case for GTSPLIB), but are formed pseudorandomly. The current best tour costs found by CLKH are reported here. The instances and the tours can be downloaded here in tgz format.
MOM instances
The paper "M. Mestria, L. S. Ochi, and S. de Lima Martins: GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem. Computers & Operations Research, Vol. 40, Issue 12, pp. 3218–3229 (2013)" provides a suite of test instances for the Euclidean CTSP. The current best tour costs found by CLKH are reported here. The instances (in GTSPLIB format) and the tours can be downloaded here in tgz format.
A 115,475-city instance
Professor William J. Cook has proposed a 115,475-city challenge through (nearly) all cities, towns, and villages in the contiguous 48 states, plus the District of Columbia. A CTSP version of the challenge is provided here. The current best tour for this version was found by CLKH and has a length of 6,306,372.
CHANGES IN VERSION 1.1:
LKH-2.0.9 is used instead of LKH-2.0.7. This makes POPMUSIC candidate edge generation and GPX2 recombination available.
VERSION 1.0:
Created December 2013.