论文标题
解决旅行推销员问题的生成图方法
A Generative Graph Method to Solve the Travelling Salesman Problem
论文作者
论文摘要
旅行推销员问题（TSP）是组合优化的一项具有挑战性的图形任务，需要有关本地节点社区和全局图结构的推理。在本文中，我们建议使用新颖的图表学习网络（GLN）（一种生成方法）来大致解决TSP。 GLN模型直接了解TSP实例的模式作为训练数据集，编码图形属性，并将不同的节点嵌入到输出节点到节点，直接或通过图形搜索技术来验证最终巡回演出。拟议的新方法的初步结果证明了其对这个具有挑战性的问题的适用性，与最佳解决方案相比，可节省大量计算的最佳差距。
The Travelling Salesman Problem (TSP) is a challenging graph task in combinatorial optimization that requires reasoning about both local node neighborhoods and global graph structure. In this paper, we propose to use the novel Graph Learning Network (GLN), a generative approach, to approximately solve the TSP. GLN model learns directly the pattern of TSP instances as training dataset, encodes the graph properties, and merge the different node embeddings to output node-to-node an optimal tour directly or via graph search technique that validates the final tour. The preliminary results of the proposed novel approach proves its applicability to this challenging problem providing a low optimally gap with significant computation saving compared to the optimal solution.
