We propose UTSP, an unsupervised learning (UL) framework for solving the Travelling Salesman Problem (TSP). We train a Graph Neural Network (GNN) using a surrogate loss. The GNN outputs a heat map representing the probability for each edge to be part of the optimal path. We then apply local search to generate our final prediction based on the heat map. Our loss function consists of two parts: one pushes the model to find the shortest path and the other serves as a surrogate for the constraint that the route should form a Hamiltonian Cycle. Experimental results show that UTSP outperforms the existing data-driven TSP heuristics. Our approach is parameter efficient as well as data efficient: the model takes $\sim$ 10\% of the number of parameters and $\sim$ 0.2\% of training samples compared with reinforcement learning or supervised learning methods.
翻译:我们提出了UTSP,一种用于解决旅行商问题(TSP)的无监督学习(UL)框架。我们使用代理损失训练图神经网络(GNN)。GNN输出一个热图,表示每条边成为最优路径的概率。然后,我们应用局部搜索根据热图生成最终预测值。我们的损失函数由两部分组成:一部分推动模型找到最短路径,另一部分作为限制路径构成哈密顿回路的代理。实验结果表明,UTSP优于现有的数据驱动TSP启发式算法。我们的方法具有参数效率和数据效率:与强化学习或监督学习方法相比,模型使用约10%的参数和约0.2%的训练样本。