H-TSP: Hierarchically Solving the Large-Scale Traveling Salesman Problem


  • Xuanhao Pan Huazhong University of Science and Technology
  • Yan Jin Huazhong University of Science and Technology
  • Yuandong Ding Huazhong University of Science and Technology
  • Mingxiao Feng University of Science and Technology of China
  • Li Zhao Microsoft Research
  • Lei Song Microsoft Research
  • Jiang Bian Microsoft Research




ML: Reinforcement Learning Algorithms


We propose an end-to-end learning framework based on hierarchical reinforcement learning, called H-TSP, for addressing the large-scale Traveling Salesman Problem (TSP). The proposed H-TSP constructs a solution of a TSP instance starting from the scratch relying on two components: the upper-level policy chooses a small subset of nodes (up to 200 in our experiment) from all nodes that are to be traversed, while the lower-level policy takes the chosen nodes as input and outputs a tour connecting them to the existing partial route (initially only containing the depot). After jointly training the upper-level and lower-level policies, our approach can directly generate solutions for the given TSP instances without relying on any time-consuming search procedures. To demonstrate effectiveness of the proposed approach, we have conducted extensive experiments on randomly generated TSP instances with different numbers of nodes. We show that H-TSP can achieve comparable results (gap 3.42% vs. 7.32%) as SOTA search-based approaches, and more importantly, we reduce the time consumption up to two orders of magnitude (3.32s vs. 395.85s). To the best of our knowledge, H-TSP is the first end-to-end deep reinforcement learning approach that can scale to TSP instances of up to 10000 nodes. Although there are still gaps to SOTA results with respect to solution quality, we believe that H-TSP will be useful for practical applications, particularly those that are time-sensitive e.g., on-call routing and ride hailing service.




How to Cite

Pan, X., Jin, Y., Ding, Y., Feng, M., Zhao, L., Song, L., & Bian, J. (2023). H-TSP: Hierarchically Solving the Large-Scale Traveling Salesman Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 37(8), 9345-9353. https://doi.org/10.1609/aaai.v37i8.26120



AAAI Technical Track on Machine Learning III