VSR-LKH(-3)

---

This repository contains the code to the VSR-LKH algorithm for the TSP proposed in our paper:

Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problems
Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, Chu-Min Li

VSR-LKH

On a Unix/Linux machine execute the following commands:

unzip VSR-LKH-V2-main.zip
cd VSR-LKH-V2-main
chmod +777 -R VSR-LKH-Final
cd VSR-LKH-Final
make

An executable file called LKH will now be available in the directory VSR-LKH-Final. Then execute ./run_NAME_ALPHA (./run_NAME_POPMUSIC) to calculate the instance NAME.tsp by VSR-LKH with the α-measure (POPMUSIC) method.

VSR-LKH-3

On a Unix/Linux machine execute the following commands:

unzip VSR-LKH-V2-main.zip
cd VSR-LKH-V2-main
chmod +777 -R VSR-LKH-3-Final
cd VSR-LKH-3-Final
make

An executable file called LKH will now be available in the directory VSR-LKH-3-Final. Then place the instances in VSR-LKH-3-Final/Instances to the directory VSR-LKH-3-Final, and execute the following commands:

./run_TSPTW III NAME 10000 10 0

or

./run_CTSP III NAME 10000 10 0

to calculate the instance NAME.tsptw or NAME.ctsp by VSR-LKH-3 with the default settings in the paper.

Execute commands ./runAll_TSPTW or ./runAll_CTSP to calculate all the TSPTW or CTSP instances.

The default version of VSR-LKH-3 uses the α-measure to decide the candidate sets. Set the parameter CandidateSetType = POPMUSIC in ReadParameters.c to get the VSR-LKH-3 with the POPMUSIC method.

Data

All the 236 tested TSP instances from TSPLIB, National TSP, VLSI TSP benchmarks are available in Instances. The parameter files for 236 TSP instances are available in ParFiles. All the 425 tested TSPTW instances and 65 tested CTSP instances are available in VSR-LKH-3-Final/Instances.

Contact

Questions and suggestions can be sent to jzzheng@hust.edu.cn.