Awesome

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: <br> <br> Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem (AAAI 2021) <br> Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, Chu-Min Li <br> <br>

Installation

On a Unix/Linux machine execute the following commands: <br> <br>

unzip VSR-LKH-main.zip <br> cd VSR-LKH-main <br> make <br> <br>

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

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: <br> <br>

• The statement of reinforcement learning parameters and Q-value: LKH.h <br>
• 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). <br>
• The initialization of parameters: ReadParameters.c <br>
• The reinforcement learning parameters adaptation process: FindTour.c <br> <br>

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/. <br> <br>

Contact

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

Citation

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

@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}
}