Implementation of "A Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem" (https://ieeexplore.ieee.org/document/9109309)
- Get the source code, and install all the dependencies.
git clone --recursive https://github.com/snail-ju/GNN-MCTS-TSP.git
- Build the pytorch with the instructions here,
conda install pytorch==1.2.0 torchvision==0.4.0 cudatoolkit=10.0 -c pytorch
-
Build the pytorch geometric with the instructions here, https://pytorch-geometric.readthedocs.io/en/latest/notes/installation.html
When installing the pytorch geometric, please follow the instructions below,
pip install torch-scatter==1.3.1
pip install torch-sparse==0.4.0
pip install torch-cluster==1.4.4
pip install torch-spline-conv==1.1.0
pip install torch-geometric==1.3.2
- Build other dependencies including tqdm and tensorboardX.
To generate the synthetic data for TSP, you can do with the instructions here:
- Visit the website of the DIMACS Implementation Challenge (http://dimacs.rutgers.edu/archive/Challenges/TSP/download.html).
- Download the instance generator in part “Benchmark Code and Instance Generation Codes” of the above website.
- Execute the corresponding program to generate different types of instances. Note that the program will generate the data on the fly.
**We also provide codes in the “data-generator” director to generate instances, and the file format generated by codes is adapted to our program. Compile the code with the following instructions, **
cd data-generator
gcc portgen.c -o prorgen -lm
gcc portcgen.c -o prorgen -lm
Please modify the corresponding options in the "segnn/config.json" file.
Navigate to the segnn folder and train the SE-GNN with the following instructions,
cd segnn
python train.py -c config.json
By default it will save all the model files in "saved/models/SE-GNN", the logs under "saved/log/SE-GNN".
Navigate to the gnn-mcts folder and run the evaluation script. Modify the script to change the parameters. Make sure the parameters are consistent with your training script.
cd gnn-mcts
./run.sh
The above script will load the 1000 test instances you generated before, and output the solution in some text files under the result folder.
Here is the link to the dataset that was used in the paper:
https://www.dropbox.com/sh/4o0tc5aoamat7hy/AABzIz-bOgSLp9_da5GQmjKGa?dl=0
Please cite our work if you find our code/paper is useful to your work.
@ARTICLE{9109309,
author={Z. {Xing} and S. {Tu}},
journal={IEEE Access},
title={A Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem},
year={2020},
volume={8},
number={},
pages={108418-108428},
}