首页|基于图卷积和注意力神经网络的旅行商问题新解法

基于图卷积和注意力神经网络的旅行商问题新解法

扫码查看
旅行商问题是一个经典的组合优化问题.为快速求解旅行商问题,设计了由图嵌入网络、图卷积神经网络、注意力神经网络和多层感知机组合而成的深度学习模型的学习分支规则,通过改进传统的分支定界算法提高算法性能.对15个城市的旅行商问题实例进行监督训练,并在SCIP求解器上分别测试10,15,20,25和30个城市的旅行商问题实例.发现:基于学习分支规则的分支定界算法的求解时间比基于传统分支规则的分支定界算法的求解时间分别快-0.0022s,0.0178s,1.7643s,2.3074s和2.053 8s.因此,基于图神经网络的分支变量选择对传统分支规则的改进是有效的,可以较好地泛化到训练规模更大的旅行商问题实例中.
New Solution for Traveling Salesman Problem Based on Graph Convolution and Attention Neural Network
Traveling salesman problem is a classic combinatorial optimization problem.To solve the problem quickly,a learning branch rule is designed,which is based on a deep learning model composed of graph embedding network,graph convolutional neu-ral network,attention neural network and multi-layer perceptron,and the traditional branch and bound algorithm is modified to improve the algorithm performance.Traveling salesman problem instances of 15 cities are supervised and trained,and the trave-ling salesman problem instances of 10,15,20,25 and 30 cities are tested on the SCIP solver respectively.We find that the solution time of the branch and bound algorithm based on learning branch rule is-0.002 2s,0.017 8 s,1.764 3 s,2.307 4 s,and 2.053 8 s faster than that of the algorithm based on traditional branch rules,respectively.Therefore,the selection of branch variables based on graph neural networks is effective in improving traditional branch rules and can be well normalized to traveling salesman prob-lem instances with larger training scales.

Traveling salesman problemGraph convolutional neural networkAttention neural networkBranch and bound algo-rithmSupervised learning

韦念念、韩曙光

展开 >

浙江理工大学理学院 杭州 310018

旅行商问题 图卷积神经网络 注意力网络 分支定界算法 监督学习

国家自然科学基金

12071436

2024

计算机科学
重庆西南信息有限公司(原科技部西南信息中心)

计算机科学

CSTPCD北大核心
影响因子:0.944
ISSN:1002-137X
年,卷(期):2024.51(z1)
  • 44