Recent years have witnessed a surge in research on machine learning for
combinatorial optimization since learning-based approaches can outperform
traditional heuristics and approximate exact solvers at a lower computation
cost. However, most existing work on supervised neural combinatorial
optimization focuses on TSP instances with a fixed number of cities and
requires large amounts of training samples to achieve a good performance,
making them less practical to be applied to realistic optimization scenarios.
This work aims to develop a data-driven graph representation learning method
for solving travelling salesman problems (TSPs) with various numbers of cities.
To this end, we propose an edge-aware graph autoencoder (EdgeGAE) model that
can learn to solve TSPs after being trained on solution data of various sizes
with an imbalanced distribution. We formulate the TSP as a link prediction task
on sparse connected graphs. A residual gated encoder is trained to learn latent
edge embeddings, followed by an edge-centered decoder to output link
predictions in an end-to-end manner. To improve the model's generalization
capability of solving large-scale problems, we introduce an active sampling
strategy into the training process. In addition, we generate a benchmark
dataset containing 50,000 TSP instances with a size from 50 to 500 cities,
following an extremely scale-imbalanced distribution, making it ideal for
investigating the model's performance for practical applications. We conduct
experiments using different amounts of training data with various scales, and
the experimental results demonstrate that the proposed data-driven approach
achieves a highly competitive performance among state-of-the-art learning-based
methods for solving TSPs.

该论文提出了一种数据驱动的图表示学习方法，用于解决具有不同数量城市的旅行推销员问题，并通过实验证明该方法在解决旅行推销员问题方面具有与最先进的基于学习的方法相媲美的性能。

基于边缘感知的图自编码器用于规模不平衡数据的旅行商问题

An Edge-Aware Graph Autoencoder Trained on Scale-Imbalanced Data for  Travelling Salesman Problems

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。最后，通过消融研究来证明分层搜索框架的重要性和有效性。