Abstract: Recently, learned heuristics have been widely applied to solve combinatorial optimization problems (e.g., traveling salesman problem (TSP)). However, the scalability of these learning-based methods hinders the applications in practical scenarios. Specifically, models pre-trained on the small-scale data generalize poorly to large-scale problems. Moreover, learning the heuristics directly for large-scale problems costs tremendous time and space. To extend the scalability of learned heuristics on TSP, we propose a Hierarchical neural framework for solving large-scale traveling salesman problems (HiTSPs) based on a divide-and-conquer strategy. In particular, the HiTSP framework first divides the large-scale problem into small-scale subproblems by node clustering. Each subproblem is conquered by a modified pointer network learned from reinforcement learning. The tour of the original TSP is constructed by linking solutions of subproblems and optimized by a novel segmented local search algorithm. Notably, the segmented local search algorithm leverages the node clustering information to prune many unnecessary operations and significantly reduces the complexity in theory. Extensive experiments show that HiTSP outperforms state-of-the-art learning-based methods and Google OR-Tools in large-scale cases. Moreover, compared to the best heuristic algorithms, HiTSP has a significant advantage in efficiency for large-scale TSP problems.

Key words: Hierarchical neural framework, Divide-and-conquer, Modified pointer network, Segmented local search algorithm