This reposity is the source code for solving the Traveling Salesman Problems (TSP) using Monte Carlo tree search (MCTS) assisted by Graph Convolutional Network with attention mechanism (Att-GraphConvNet).
If you want to get more details, please see our paper "Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances" by Zhang-Hua Fu (1,2), Kai-Bin Qiu (2) and Hongyuan Zha (1,2), which is accepted by AAAI2021. In addition, our full version has been submitted in this reposity.
1 Shenzhen Institute of Artificial Intelligence and Robotics for Society, Shenzhen, China
2 The Chinese University of Hong Kong, Shenzhen, China
Duing to the limit of platform and hardware, if you fail to build the environment of GPU, you could choose the CPU version of MCTS programs. We would finish the Readme.md of MCTS-CPUver as soon as possible!!!
After install CUDA-8.0, we need to configure its environment variables, which follow the steps bellow:
First, add environment variables in .bashrc
gedit ~/.bashrcexport PATH=/usr/local/cuda-8.0/bin${PATH:+:${PATH}}export LD_LIBRARY_PATH=/usr/local/cuda-8.0/lib64${LD_LIBRARY_PATH:+:${LD_LIBRARY_PATH}}sudo gedit /etc/profileexport PATH=/usr/local/cuda/bin:$PATHsudo gedit /etc/ld.so.conf.d/cuda.conf/usr/local/cuda/lib64sudo ldconfigTrainset: Att-GraphConvNet is trained on two datasets respectively, TSP20-dataset and TSP50-dataset which could be downloaded from:
After decompressing trainsets, you can remove them into directories ./Att-GraphConvNet/data.
Testset: Our metdod is tested on some datasets respectively, TSP-20-50-100, TSP-200-500-100 and TSP-10000 which could be downloaded from:
After decompressing datasets, you can copy them into directories respectively, ./MCTS/tsp-20-50-100, ./MCTS/tsp-200-500-1000 and ./MCTS/tsp-10000. Besides, you can copy them into directories ./Att-GraphConvNet/data.
Heatmap: Our team also published heat-map files and at the same time reader can download them from:
After decompressing heat-map files, you can copy them into directories respectively, ./MCTS/tsp-20-50-100/heatmap, ./MCTS/tsp-200-500-1000/heatmap and ./MCTS/tsp-10000/heatmap.
Our method is made up of Att-GraphConvNet and MCTS. In our paper, Att-GraphConvNet is used to generate probabilistic heat maps which assist MCTS to solve TSP.
train-20.ipynb to train Att-GraphConvNet based on TSP-20-trainset. If want to train models based on your own dataset, you just need to modify the path of dataset in ./Att-GraphConvNet/configs/tsp20.json. By the way, you can run test-20-50-100.ipynb to generate heat maps for TSP20 using trained models which are released on TSP-models-downloading-link. Heat map files would be stored in directory ./Att-GraphConvNet/results/heatmap/tsp20. cd $download-dir
cp -r $testset-dir ./MCTS/tsp-20-50-100
cp -r ./Att-GraphConvNet/results/heatmap/tsp20 ./MCTS/tsp-20-50-100/heatmap
cd ./MCTS/tsp-20-50-100
bash generate_lib.sh
bash solve-20.sh[^1,2]: [^2]: