[2S5-GS-2] Machine learning:

[2S5-GS-2-01] Solving Large-Scale Traveling Salesman Problems with Node Distribution-Aware Hierarchical Reinforcement Learning

〇Haruya Suwa¹, Ryosuke Saraya¹, Ayako Yamagiwa¹, Masayuki Goto¹ (1. Waseda University)

Keywords:Large-scale Traveling Salesman Problem, Hierarchical Reinforcement Learning, Real-time Route Planning, Cluster Structure, k-Nearest Neighbor Graph

The Traveling Salesman Problem (TSP) is a combinatorial optimization problem that seeks the shortest route visiting each given city exactly once. As an NP-hard problem, finding the optimal solution becomes infeasible for large instances within a reasonable time. Heuristic approaches are widely used to search for an approximate solution, but computational time remains a challenge, especially in real-time applications. Recently, deep reinforcement learning (DRL) has gained attention for solving large-scale TSP efficiently. H-TSP, a DRL-based method, improves both search time and accuracy by dividing large TSP instances into smaller subproblems. However, H-TSP assumes a uniform node distribution, limiting its applicability to real-world problems with clustered structures, such as logistics and store networks. This study proposes an improved DRL-based approach incorporating an enhanced k-NN graph and a partial initial path strategy to address clustered TSP instances. Comparative experiments with H-TSP demonstrate the effectiveness of the proposed method.