Nam Le

Travelling Salesman Problem (TSP)

Nam Le
Table of Contents

Travelling Salesman Problem (TSP) #

The Travelling Salesman Problem is one of the most famous NP-hard optimization problems, with extensive research on neural and ML-based approaches.

Recent Literature #

  1. Learning Combinatorial Optimization Algorithms over Graphs. NeurIPS, 2017. paper

    Dai, Hanjun and Khalil, Elias B and Zhang, Yuyu and Dilkina, Bistra and Song, Le

  2. Learning Heuristics for the TSP by Policy Gradient CPAIOR, 2018. paper, code

    Michel DeudonPierre CournutAlexandre Lacoste

  3. Attention, Learn to Solve Routing Problems! ICLR, 2019. paper

    Kool, Wouter and Van Hoof, Herke and Welling, Max.

  4. Learning to Solve NP-Complete Problems: A Graph Neural Network for Decision TSP. AAAI, 2019. paper

    Prates, Marcelo and Avelar, Pedro HC and Lemos, Henrique and Lamb, Luis C and Vardi, Moshe Y.

  5. An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem Arxiv, 2019. paper, code

    Chaitanya K. Joshi, Thomas Laurent, Xavier Bresson

  6. POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. NeurIPS, 2020. paper, code

    Kwon, Yeong-Dae and Choo, Jinho and Kim, Byoungjip and Yoon, Iljoo and Min, Seungjai and Gwon, Youngjune.

  7. Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances. Arxiv, 2020. paper

    Fu, Zhang-Hua and Qiu, Kai-Bin and Zha, Hongyuan.

  8. A Reinforcement Learning Approach for Optimizing Multiple Traveling Salesman Problems over Graphs KBS, 2020. journal

    Hu, Yujiao and Yao, Yuan and Lee, Wee Sun

  9. Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning ACML, 2020. paper, code

    d O Costa, Paulo R and Rhuggenaath, Jason and Zhang, Yingqian and Akcay, Alp

  10. Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems. IEEE Trans Cybern, 2021. journal

    Kaiwen Li, Tao Zhang, Rui Wang Yuheng Wang, and Yi Han

  11. The Transformer Network for the Traveling Salesman Problem IPAM, 2021. paper

    Xavier Bresson，Thomas Laurent

  12. Learning Improvement Heuristics for Solving Routing Problems TNNLS, 2021. journal

    Wu, Yaoxin and Song, Wen and Cao, Zhiguang and Zhang, Jie and Lim, Andrew

  13. Reversible Action Design for Combinatorial Optimization with Reinforcement Learning Arxiv, 2021. paper

    Yao, Fan and Cai, Renqin and Wang, Hongning

  14. Solving Dynamic Traveling Salesman Problems with Deep Reinforcement Learning. TNNLS, 2021. journal

    Zizhen Zhang, Hong Liu, Meng Chu Zhou, Jiahai Wang

  15. ScheduleNet: Learn to Solve Multi-agent Scheduling Problems with Reinforcement Learning Arxiv, 2021. paper

    Junyoung Park, Sanjar Bakhtiyar, Jinkyoo Park

  16. DAN: Decentralized Attention-based Neural Network to Solve the MinMax Multiple Traveling Salesman Problem Arxiv, 2021. paper

    Cao, Yuhong and Sun, Zhanhong and Sartoretti, Guillaume

  17. Reinforcement Learning for Route Optimization with Robustness Guarantees IJCAI, 2021. paper

    Jacobs, Tobias and Alesiani, Francesco and Ermis, Gulcin

  18. Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem AAAI, 2021. paper, code

    Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, Chu-Min Li

  19. Learning to Sparsify Travelling Salesman Problem Instances CPAIOR, 2021. paper

    James Fitzpatrick, Deepak Ajwani, Paula Carroll

  20. Learning TSP Requires Rethinking Generalization CP, 2021. paper, code

    Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau and Thomas Laurent

  21. The First AI4TSP Competition: Learning to Solve Stochastic Routing Problems Arxiv, 2022. paper, code

    Bliek, Laurens and da Costa, Paulo and Afshar, Reza Refaei and Zhang, Yingqian and Catshoek, Tom and Vos, Daniel and Verwer, Sicco and Schmitt-Ulms, Fynn and Hottung, Andre and Shah, Tapan and others

  22. Graph Neural Network Guided Local Search for the Traveling Salesperson Problem ICLR, 2022. paper

    Hudson, Benjamin and Li, Qingbiao and Malencia, Matthew and Prorok, Amanda

  23. Preference Conditioned Neural Multi-objective Combinatorial Optimization ICLR, 2022. paper

    Lin, Xi and Yang, Zhiyuan and Zhang, Qingfu

  24. Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation NeurIPS, 2022. paper, code

    Bi, Jieyi and Ma, Yining and Wang, Jiahai and Cao, Zhiguang and Chen, Jinbiao and Sun, Yuan and Chee, Yeow Meng

  25. DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems NeurIPS, 2022. paper

    Qiu, Ruizhong and Sun, Zhiqing and Yang, Yiming

  26. Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization NeurIPS, 2022. paper, code

    Kim, Minsu and Park, Junyoung and Park, Jinkyoo

  27. Simulation-guided Beam Search for Neural Combinatorial Optimization NeurIPS, 2022. paper, code

    Choo, Jinho and Kwon, Yeong-Dae and Kim, Jihoon and Jae, Jeongwoo and Hottung, Andr{'e} and Tierney, Kevin and Gwon, Youngjune

  28. Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness ICLR, 2022. paper

    Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski and Stephan Günnemann

  29. ⭐LinSATNet: The Positive Linear Satisfiability Neural Networks ICML, 2023. paper, code

    Runzhong Wang and Yunhao Zhang and Ziao Guo and Tianyi Chen and Xiaokang Yang and Junchi Yan

  30. Learning to CROSS exchange to solve min-max vehicle routing problems ICLR, 2023. paper

    Kim, Minjun and Park, Junyoung and Park, Jinkyoo

  31. Generalize Learned Heuristics to Solve Large-scale Vehicle Routing Problems in Real-time ICLR, 2023. paper

    Hou, Qingchun and Yang, Jingwei and Su, Yiqiang and Wang, Xiaoqing and Deng, Yuming

  32. ⭐ROCO: A General Framework for Evaluating Robustness of Combinatorial Optimization Solvers on Graphs ICLR, 2023. paper, code

    Lu, Han and Li, Zenan and Wang, Runzhong and Ren, Qibing and Li, Xijun and Yuan, Mingxuan and Zeng, Jia and Yang, Xiaokang and Yan, Junchi

  33. Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem Arxiv, 2023. paper, code

    Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, Jiang Bian

  34. H-tsp: Hierarchically solving the large-scale traveling salesman problem AAAI, 2023. paper, code

    Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng, Li Zhao, Lei Song, Jiang Bian

  35. Select and Optimize: Learning to solve large-scale TSP instances AISTATS, 2023. paper

    Hanni Cheng, Haosi Zheng, Ya Cong, Weihao Jiang, Shiliang Pu

  36. Multi-View Graph Contrastive Learning for Solving Vehicle Routing Problems UAI, 2023. paper

    Yuan Jiang, Zhiguang Cao, Yaoxin Wu, Jie Zhang

  37. Revisiting Sampling for Combinatorial Optimization ICML, 2023. paper

    Sun, Haoran, Goshvadi Katayoon,Nova Azade,Schuurmans Dale and Dai Hanjun.

  38. Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimization ICML, 2023. paper

    Son, Jiwoo and Kim, Minsu and Kim, Hyeonah and Park, Jinkyoo

  39. Towards Omni-generalizable Neural Methods for Vehicle Routing Problems ICML, 2023. paper, code

    Zhou Jianan, Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang

  40. DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization NeurIPS, 2023. paper, code

    Zhiqing Sun, Yiming Yang

  41. DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization NeurIPS, 2023. paper, code

    Ye, Haoran and Wang, Jiarui and Cao, Zhiguang and Liang, Helan and Li, Yong

  42. Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization NeurIPS, 2023. paper

    Grinsztajn, Nathan and Furelos-Blanco, Daniel and Surana, Shikha and Bonnet, Cl{'e}ment and Barrett, Thomas D

  43. Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods NeurIPS, 2023. paper, code

    Caramanis, Constantine and Fotakis, Dimitris and Kalavasis, Alkis and Kontonis, Vasilis and Tzamos, Christos

  44. Combinatorial Optimization with Policy Adaptation using Latent Space Search NeurIPS, 2023. paper

    Chalumeau, Felix and Surana, Shikha and Bonnet, Cl{'e}ment and Grinsztajn, Nathan and Pretorius, Arnu and Laterre, Alexandre and Barrett, Thomas D

  45. Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimization NeurIPS, 2023. paper, code

    Chen, Jinbiao and Wang, Jiahai and Zhang, Zizhen and Cao, Zhiguang and Ye, Te and Chen, Siyuan

  46. BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization NeurIPS, 2023. paper, code

    Drakulic, Darko and Michel, Sofia and Mai, Florian and Sors, Arnaud and Andreoli, Jean-Marc

  47. Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization NeurIPS, 2023. paper, code

    Luo, Fu and Lin, Xi and Liu, Fei and Zhang, Qingfu and Wang, Zhenkun

  48. Neural Multi-Objective Combinatorial Optimization with Diversity Enhancement NeurIPS, 2023. paper, code

    Chen, Jinbiao and Zhang, Zizhen and Cao, Zhiguang and Wu, Yaoxin and Ma, Yining and Ye, Te and Wang, Jiahai

  49. Unsupervised Learning for Solving the Travelling Salesman Problem NeurIPS, 2023. paper

    Min, Yimeng and Bai, Yiwei and Gomes, Carla P

  50. Ensemble-based Deep Reinforcement Learning for Vehicle Routing Problems under Distribution Shift NeurIPS, 2023. paper

    Jiang, Yuan and Cao, Zhiguang and Wu, Yaoxin and Song, Wen and Zhang, Jie

  51. Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt NeurIPS, 2023. paper, code

    Ma, Yining and Cao, Zhiguang and Chee, Yeow Meng

  52. ⭐T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization NeurIPS, 2023. paper, code

    Yang Li, Jinpei Guo, Runzhong Wang, Junchi Yan

  53. Reinforced Lin–Kernighan–Helsgaun Algorithms for the Traveling Salesman Problems Knowledge-Based Systems, 2023. journal, code

    Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, Chu-Min Li

  54. Neural Improvement Heuristics for Graph Combinatorial Optimization Problems TNNLS, 2023. journal, code

    Andoni I. Garmendia, Josu Ceberio, Alexander Mendiburu

  55. GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time AAAI, 2024. paper, code

    Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, Fanzhang Li

  56. Distilling Autoregressive Models to Obtain High-Performance Non-autoregressive Solvers for Vehicle Routing Problems with Faster Inference Speed AAAI, 2024. paper, code

    Yubin Xiao, Di Wang, Boyang Li, Mingzhao Wang, Xuan Wu, Changliang Zhou, You Zhou

  57. Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems ICML, 2024. paper, code

    Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, Jiang Bian

  58. MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimization IJCAI, 2024. paper, code

    Andoni I. Garmendia, Quentin Cappart, Josu Ceberio, Alexander Mendiburu

  59. Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times NeurIPS, 2024. paper

    Pei Xiao, Zizhen Zhang, Jinbiao Chen, Jiahai Wang, Zhenzhen Zhang

  60. Collaboration! Towards Robust Neural Methods for Routing Problems NeurIPS, 2024. paper, code

    Jianan Zhou, Yaoxin Wu, Zhiguang Cao, Wen Song, Jie Zhang, Zhiqi Shen

  61. UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems NeurIPS, 2024. paper, code

    Zhi Zheng, Changliang Zhou, Tong Xialiang, Mingxuan Yuan, Zhenkun Wang

  62. Learning to Handle Complex Constraints for Vehicle Routing Problems NeurIPS, 2024. paper

    Jieyi Bi, Yining Ma, Jianan Zhou, Wen Song, Zhiguang Cao, Yaoxin Wu, Jie Zhang

  63. ⭐Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization NeurIPS, 2024. paper, code

    Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, Junchi Yan

  64. ⭐UniCO: On Unified Combinatorial Optimization via Problem Reduction to Matrix-Encoded General TSP ICLR, 2025. paper, code

    Wenzheng Pan, Hao Xiong, Jiale Ma, Wentao Zhao, Yang Li, Junchi Yan

  65. Efficient and Robust Neural Combinatorial Optimization via Wasserstein-Based Coresets ICLR, 2025. paper

    Xu Wang, Fuyou Miao, Wenjie Liu, Yan Xiong

  66. ⭐Unify ML4TSP: Drawing Methodological Principles for TSP and Beyond from Streamlined Design Space of Learning and Search ICLR, 2025. paper, code

    Yang Li, Jiale Ma, Wenzheng Pan, Runzhong Wang, Haoyu Geng, Nianzu Yang, Junchi Yan

  67. ⭐COExpander: Adaptive Solution Expansion for Combinatorial Optimization ICML, 2025. paper, code

    Jiale Ma and Wenzheng Pan and Yang Li and Junchi Yan

  68. ⭐ML4CO-Bench-101: Benchmark Machine Learning for Classic Combinatorial Problems on Graphs NeurIPS, 2025. paper, code

    Jiale Ma and Wenzheng Pan and Yang Li and Junchi Yan

Tags:
Categories: