TSP TS_最短路

# GNN-MCTS-TSP Implementation of "A Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem" (https://ieeexplore.ieee.org/document/9109309)  # 1. Build 1. Get the source code, and install all the dependencies. ```bash git clone --recursive https://github.com/snail-ju/GNN-MCTS-TSP.git ``` 2. Build the pytorch with the instructions here, ~~~bash conda install pytorch==1.2.0 torchvision==0.4.0 cudatoolkit=10.0 -c pytorch ~~~ 3. 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,** ~~~bash 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 ~~~ 4. Build other dependencies including tqdm and tensorboardX. # 2. Experiments on synthetic data ## Generate synthetic data To generate the synthetic data for TSP, you can do with the instructions here: 1. Visit the website of the DIMACS Implementation Challenge (http://dimacs.rutgers.edu/archive/Challenges/TSP/download.html). 2. Download the instance generator in part “Benchmark Code and Instance Generation Codes” of the above website. 3. 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, ** ~~~bash cd data-generator gcc portgen.c -o prorgen -lm gcc portcgen.c -o prorgen -lm ~~~ ## Training SE-GNN on synthetic data 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, ```bash 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". ### Test the GNN-MCTS 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. ```bash 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. # Reproducing the results that reported in the paper Here is the link to the dataset that was used in the paper: https://www.dropbox.com/sh/4o0tc5aoamat7hy/AABzIz-bOgSLp9_da5GQmjKGa?dl=0 # Reference Please cite our work if you find our code/paper is useful to your work. ```markdown @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}, } ```