A Variable Strategy Reinforced Lin-Kernighan-Helsgaun Algorithm (VSR-LKH)

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

Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem (AAAI 2021)
Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, Chu-Min Li

Installation

On a Unix/Linux machine execute the following commands:

unzip VSR-LKH-main.zip
cd VSR-LKH-main
make

An executable file called LKH will now be available in the directory VSR-LKH-main.
Then enter the .par file name corresponding to the TSP instance, such as u574.par, to run the program.

File Description

VSR-LKH was achieved on top of the famous TSP heuristic, Lin-Kernighan-Helsgaun (LKH) algorithm. You can learn LKH from its open source website, http://akira.ruc.dk/~keld/research/LKH/, and understand the effect of each file and the meaning of the parameters from the PDF files in the directory DOC. The description of some files that differ between VSR-LKH and LKH is as follows:

• The statement of reinforcement learning parameters and Q-value: LKH.h
  
• The reinforcement learning process in k-opt: BestKOptMove.c (for parameters PATHING_A = 2, PATHING_C = 3), Best5OptMove.c (for parameters PATHING_A = 1, PATHING_C = 0).
  
• The initialization of parameters: ReadParameters.c
  
• The reinforcement learning parameters adaptation process: FindTour.c
  
  

Data

We give three TSP instances (u574, u1060, rl11849) as examples. All the TSPLIB Format instance (.tsp) can be calculated by VSR-LKH. The all 111 TSPLIB instances can be found in the directory TSPLIB_DATA or http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.

Contact

Questions and suggestions can be sent to [email protected].

Citation

If you find this code and data useful, please consider citing the original work by authors:

@inproceedings{zheng2021RL-TSP,
  title={Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem},
  author={Jiongzhi Zheng and Kun He and Jianrong Zhou and Yan Jin and Chu-Min Li},
  booktitle={The Thirty-Fifth AAAI Conference on Artificial Intelligence},
  pages={12445--12452},
  year={2021}
}