This repo implements paper Wu et. al., Learning Improvement Heuristics for Solving Routing Problems, IEEE Transactions on Neural Networks and Learning Systems, 2021, which solves TSP with the improvement-base Deep Reinforcement Learning method.

For more details, please see the paper Wu et. al., Learning Improvement Heuristics for Solving Routing Problems, IEEE Transactions on Neural Networks and Learning Systems, 2021.

@article{wu2021learning,
  title={Learning improvement heuristics for solving routing problem},
  author={Wu, Yaoxin and Song, Wen and Cao, Zhiguang and Zhang, Jie and Lim, Andrew},
  journal={IEEE Transactions on Neural Networks and Learning Systems},
  year={2021}
}

We provide a Jupyter notebook to help you get started and understand our code. Please open the notebook here for more details.

Note: due to the 100MB limit of Github, please download the logs folder for the pre-trained model via Google Drive and put it under './logs/pre_trained/' folder.

• Python>=3.6
• PyTorch>=1.1
• numpy
• tqdm
• cv2
• tensorboard_logger
• imageio (optional, for plots)

For the exception below from package tensorboard_logger,

AttributeError: module 'scipy.misc' has no attribute 'toimage'

Please refer to issue #27 to fix it.

CUDA_VISIBLE_DEVICES=0 python run.py --graph_size 20 --seed 1234 --n_epochs 100 --batch_size 512 --epoch_size 5120 --val_size 1000 --eval_batch_size 1000 --val_dataset './datasets/tsp_20_10000.pkl' --no_assert --run_name training

--eval_only --load_path '{add model to load here}'

Note: A pre-trained model can be found at './outputs/tsp_20/tsp_20200714T212735/epoch-99.pt'

You may also be interested in our new approaches:

• DACT (NeurIPS 2021) which is more advanced than the model implemented in this repo. DACT achieves the SOTA performance among purely learning-based improvement solvers for routing problems. Paper: Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, Jing Tang, “Learning to iteratively solve routing problems with dual-aspect collaborative transformer,” in Advances in Neural Information Processing Systems, vol. 34, 2021.
• N2S (IJCAI 2022) which makes DACT more efficient for solving pickup and delivery problems (PDPs). Paper: Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Hongliang Guo, Yuejiao Gong and Yeow Meng Chee, “Efficient Neural Neighborhood Search for Pickup and Delivery Problems,” in the 31st International Joint Conference on Artificial Intelligence (IJCAI 22), 2022.

The code is based on the repo wouterkool/attention-learn-to-route and the paper Wu et. al., Learning Improvement Heuristics for Solving Routing Problems, IEEE Transactions on Neural Networks and Learning Systems, 2021.