H-TSP

This is the implementation of our work, H-TSP: Hierarchically Solving the Large-Scale Traveling Salesman Problem (AAAI 2023)

https://www.microsoft.com/en-us/research/publication/h-tsp-hierarchically-solving-the-large-scale-traveling-salesman-problem/

Operating System

Currently only Linux system is supported.

Dependencies

Main Dependency Packages

• python >= 3.8
• pytorch == 1.10.0
• cuda == 11.3
• pytorch-lightning == 1.5.2
• pytorch_geometric
• dgl
• numba
• wandb
• hydra-core
• tensorboardX
• scikit-learn
• tensor-sensor[torch]
• LKH-3
• tsplib95
• lkh
• word2vec

Note that LKH-3 is a TSP/VRP solver written in C language, and lkh is its Python wrapper, please refer to lkh for more detail about the installation.

Using Conda (Not tested)

You can use the conda package management system to build the development environment:

conda create --name htsp --file requirements.txt

And use

conda activate htsp

to activate this environment.

Note that LKH-3 still needs to be installed manully.

Using Docker (Recommended)

Docker and nvidia-docker is required.

You can build a development environment for the H-TSP by using Docker with the Dockerfile:

docker build -t htsp .

Or use the existing docker image:

docker pull neopan97/htsp:v0.3
# add a tag for consistency
docker tag neopan97/htsp:v0.3 htsp

After the htsp docker image is built or pulled from dockerhub, start the docker container with:

docker run -it --runtime=nvidia --mount type=bind,source=/path/to/source/code,target=/workspace htsp

Code Structure

The main code of the upper-level model structure and the TSP environment locate in h_tsp.py. Details about the neural networks and other miscellaneous are in rl_models.py and rl_utils.py.

The deep reinforcement learning training is in train.py, while the code for evaluation is in evaluate.py. The experiment hyperparameters are in config_ppo.yaml.

Codes of the lower model are in the rl4cop folder. Refer to README in the folder for more details.

Basic Usage

To train a model, firstly you need to modify the config file config_ppo.yaml, then run

python train.py

To test trained model, run

python evaluate.py --help

This will show you the parameters that need to be set.

The trained model checkpoints and datasets can be downloaded from: model and data.

For more details about the parameters, please refer to the source code and our paper.

Citation

If you find this work helpful, please consider cite our paper:

@inproceedings{pan2023h-tsp,
    author = {Pan, Xuanhao and Jin, Yan and Ding, Yuandong and Feng, Mingxiao and Zhao, Li and Song, Lei and Bian, Jiang},
    title = {H-TSP: Hierarchically Solving the Large-Scale Traveling Salesman Problem},
    booktitle = {AAAI 2023},
    year = {2023},
    month = {February},
    url = {https://www.microsoft.com/en-us/research/publication/h-tsp-hierarchically-solving-the-large-scale-traveling-salesman-problem/},
}