For prohibitively large-scale Travelling Salesman Problems (TSPs), existing
algorithms face big challenges in terms of both computational efficiency and
solution quality. To address this issue, we propose a hierarchical
destroy-and-repair (HDR) approach, which attempts to improve an initial
solution by applying a series of carefully designed destroy-and-repair
operations. A key innovative concept is the hierarchical search framework,
which recursively fixes partial edges and compresses the input instance into a
small-scale TSP under some equivalence guarantee. This neat search framework is
able to deliver highly competitive solutions within a reasonable time. Fair
comparisons based on nineteen famous large-scale instances (with 10,000 to
10,000,000 cities) show that HDR is highly competitive against existing
state-of-the-art TSP algorithms, in terms of both efficiency and solution
quality. Notably, on two large instances with 3,162,278 and 10,000,000 cities,
HDR breaks the world records (i.e., best-known results regardless of
computation time), which were previously achieved by LKH and its variants,
while HDR is completely independent of LKH. Finally, ablation studies are
performed to certify the importance and validity of the hierarchical search
framework.

对于庞大规模的旅行推销员问题（TSP），现有算法在计算效率和解决方案质量方面面临巨大挑战。为了解决这个问题，我们提出了一种分层销毁和修复（HDR）方法，通过一系列精心设计的销毁和修复操作来改进初始解。一个关键创新概念是分层搜索框架，它递归地修复部分边缘，并将输入实例压缩成小规模的 TSP，在某种等价保证下。这个巧妙的搜索框架能够在合理的时间内提供极具竞争力的解决方案。基于 19 个著名的大规模实例（城市数量从 10,000 到 10,000,000 个），公平比较显示 HDR 在计算效率和解决方案质量方面与现有最先进的 TSP 算法高度竞争。值得注意的是，在 3,162,278 个和 10,000,000 个城市的两个大型实例中，HDR 打破了 LKH 及其变体先前创下的世界纪录（即无论计算时间如何，都是最好的已知结果），而 HDR 完全独立于 LKH。最后，通过消融研究来证明分层搜索框架的重要性和有效性。