H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problem
This addresses time-sensitive routing problems like on-call services, offering a scalable solution for up to 10,000 nodes, though it is incremental as it builds on existing reinforcement learning approaches.
The paper tackles the large-scale Travelling Salesman Problem by proposing H-TSP, an end-to-end hierarchical reinforcement learning framework that achieves comparable solution quality (3.42% gap vs. 7.32%) to state-of-the-art methods while reducing time consumption by up to two orders of magnitude (3.32s vs. 395.85s).
We propose an end-to-end learning framework based on hierarchical reinforcement learning, called H-TSP, for addressing the large-scale Travelling 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.