CGLKH
Version 1.0 (March 2021)

 

CGLKH is a program for solving the Clustered Generalized Traveling Salesman Problem (CGTSP), an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into clusters, the clusters are further partitioned into subclusters of cities. The objective is to find the minimal route that visits exactly one city from each subcluster in such a way that all subclusters of each cluster are visited consecutively.The figure above depicts a solution for an instance with 16 cities, 3 clusters, and 4 subclusters.

CGLKH transforms a CGTSP instance into an asymmetric TSP instance and solves the latter using the TSP-solver LKH. The transformation is inspired from GLKH, CLKH, and the paper below:

P. Baniasadi, M. Foumani, K. Smith-Miles, and V. Ejov,
A transformation technique for the clustered generalized traveling salesman problem with applications to logistics.
European Journal of Operational Research, Volume 285, Issue 2, p. 444-457, 2020.

Despite that LKH is not modified in order to cater for the unusual structure of the TSP instances, CGLKH's performance is quite impressive. New best solutions could be obtained for many of the benchmark instances provided by Baniasadi et al.

Installation

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

Source code, benchmark instances and solution tours can be downloaded here: CGLKH-1.0.tgz (gzipped tar file, approximately 37 MB).

Execute the following UNIX commands:

tar xvfz CGLKH-1.0.tgz
cd CLKH-1.0
make

Four executable files called CGLKH, CGLKH_EXP, CGLKH_CHECK, and LKH will now be available in the directory CGLKH-1.0.

CGLKH is used for solving a given instance once, whereas CGLKH_EXP is used for solving an instance using a specified number of independent runs.
CGLKH_CHECK may be used to check that a solution tour is feasible (i.e., visits exactly one the city from each subcluster, visits all subclusters of each cluster consecutively, and has the correct length).
LKH is an executable of LKH-2.0.9.

To ease the running of CGLKH and CGLKH_EXP, two scripts, runCGLKH and run CGLKH_EXP, are provided. They create suitable parameter files and next execute CGLKH and CGLKH_EXP, respectively.

The scripts runRND, runASRS and run runDRONE can be used for solving the benchmark instances. It is recommended to run the script runTest in order to test the installation:

        ./runTest

Additions to the TSPLIB input format:

CLUSTERS : <integer>
Number of clusters

SUBCLUSTERS : <integer>
Number of subclusters

CGTSP_NODE_SECTION :
This section defines which nodes belong to which clusters and subclusters.
The section contains exactly N entries, where N is the number of nodes.
Each entry has the following format:
i c s, where i is the node number, c is the cluster number, and s is the subluster number within c.
Nodes, clusters and subclusters are numbered from 1.
The section is terminated by a -1.

SCALE : <integer>
Scale factor. Distances are multplied by this factor.

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

[home]