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.
1 Shenzhen Institute of Artificial Intelligence and Robotics for Society, Shenzhen, China
2 The Chinese University of Hong Kong, Shenzhen, China
- Needed libraries for the Python programming language:
- pytorch == 1.0.1.post2
- tensorboardX
- tensorboard
- numpy
- pandas
- scikit-learn
- multiprocessing
- matplotlib
- seaborn
- scipy
- pyconcorde
- gcc >= 4.8.5
- CUDA = 8.0
- Computing platform : Linux
-
If you want to run our MCTS programs, you need to install CUDA-8.0.
-
After install CUDA-8.0, we need to configure its environment variables, which follow the steps bellow:
-
First, add environment variables in .bashrc
gedit ~/.bashrc
-
then add the following two lines of statements at the end of the file which is opened above:
export 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}}
-
Secondly, set environment variables and dynamic link library
sudo gedit /etc/profile
-
then add the following statement at the end:
export PATH=/usr/local/cuda/bin:$PATH
-
After that, create link file
sudo gedit /etc/ld.so.conf.d/cuda.conf
-
then add the following statement:
/usr/local/cuda/lib64
-
Finally, run the command to make the file work:
sudo ldconfig
-
-
Trainset: 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:
- TSP-20-50-100-testset-downloading-link
- TSP-200-500-1000-testset-downloading-link
- TSP-10000-testset-downloading-link
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:
- TSP-20-50-100-heatmap-downloading-link
- TSP-200-500-1000-heatmap-downloading-link
- TSP-10000-heatmap-downloading-link
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.
- First, you can run
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 runtest-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
. - After generating heat maps, you can solve TSP instances with 20 nodes using MCTS with single GPU:
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
- Models: Our team also released Att-GraphConvNet models which are downloaded from: TSP-models-downloading-link
- Taillard & Helsgaun, 2019 : LKH3
- Concorde : pyconcorde
- Gurobi : gurobi
- Kool et al., 2019 : Attention learn to route
- Joshi et al., 2019 : Graph Convolutional Network
- Deudon et al., 2018 : Encode attend naviagte