# H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problem

**Authors:** Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng, Li Zhao, Lei Song, Jiang Bian  
**arXiv:** [2304.09395](https://arxiv.org/abs/2304.09395)  
**Date:** 2023-04-19  
**Summary page:** https://www.summarizepaper.com/en/paper/2304.09395v1/

## Key points

- Authors propose H-TSP framework for Large-Scale Travelling Salesman Problem (TSP)
- H-TSP utilizes hierarchical reinforcement learning with upper-level and lower-level policies
- Approach directly produces solutions without time-consuming search procedures
- Extensive experiments show H-TSP achieves comparable solution quality with significant time reduction
- First end-to-end deep reinforcement learning approach scaling to TSP instances up to 10,000 nodes
- Holds promise for practical applications like on-call routing and ride-hailing services

## Summary

In their paper titled "H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problem," authors Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng, Li Zhao, Lei Song, and Jiang Bian propose an innovative end-to-end learning framework based on hierarchical reinforcement learning to tackle the challenging large-scale Travelling Salesman Problem (TSP). The H-TSP framework is designed to efficiently construct solutions for TSP instances by utilizing two key components: an upper-level policy that selects a small subset of nodes from the total set to be traversed (up to 200 nodes in experiments), and a lower-level policy that generates a tour connecting these chosen nodes to the existing partial route. By training these policies jointly, the approach can directly produce solutions for TSP instances without resorting to time-consuming search procedures. To validate the effectiveness of their proposed approach, the authors conducted extensive experiments on randomly generated TSP instances with varying numbers of nodes. The results demonstrate that H-TSP achieves comparable solution quality (with only a 3.42% performance gap compared to state-of-the-art search-based methods) while significantly reducing time consumption by up to two orders of magnitude (3.32 seconds versus 395.85 seconds). Notably, H-TSP stands out as the first end-to-end deep reinforcement learning approach capable of scaling to TSP instances containing up to 10,000 nodes. Despite some remaining gaps in solution quality compared to existing approaches, the authors believe that H-TSP holds promise for practical applications where time sensitivity is crucial—such as on-call routing and ride-hailing services. Accepted for presentation at AAAI 2023 in February 2023, this research represents a significant advancement in addressing large-scale TSPs through innovative hierarchical reinforcement learning techniques.