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

作     者：韦念念 韩曙光 WEI Niannian;HAN Shuguang

作者机构：浙江理工大学理学院杭州310018 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2024年第51卷第S01期

页      面：210-217页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金(12071436) 

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

摘      要：旅行商问题是一个经典的组合优化问题。为快速求解旅行商问题,设计了由图嵌入网络、图卷积神经网络、注意力神经网络和多层感知机组合而成的深度学习模型的学习分支规则,通过改进传统的分支定界算法提高算法性能。对15个城市的旅行商问题实例进行监督训练,并在SCIP求解器上分别测试10,15,20,25和30个城市的旅行商问题实例。发现:基于学习分支规则的分支定界算法的求解时间比基于传统分支规则的分支定界算法的求解时间分别快-0.0022 s,0.0178 s,1.7643 s,2.3074 s和2.0538 s。因此,基于图神经网络的分支变量选择对传统分支规则的改进是有效的,可以较好地泛化到训练规模更大的旅行商问题实例中。