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

doi:10.11896/jsjkx.230700222

摘要/Abstract

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

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

Abstract: 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 neural 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 traveling 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.0022s,0.0178s,1.7643s,2.3074s,and 2.0538s 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 problem instances with larger training scales.

Key words: Traveling salesman problem, Graph convolutional neural network, Attention neural network, Branch and bound algorithm, Supervised learning

中图分类号:

TP183

韦念念, 韩曙光. 基于图卷积和注意力神经网络的旅行商问题新解法[J]. 计算机科学, 2024, 51(6A): 230700222-8. https://doi.org/10.11896/jsjkx.230700222

WEI Niannian, HAN Shuguang. New Solution for Traveling Salesman Problem Based on Graph Convolution and AttentionNeural Network[J]. Computer Science, 2024, 51(6A): 230700222-8. https://doi.org/10.11896/jsjkx.230700222

参考文献

[1]PAPADIMITRIOU C H.The Euclidean travelling salesmanproblem is NP-complete[J].Theoretical Computer Science,1977,4(3):237-244.
[2]NOGAREDA A M,SER D J,OSABA E,et al.On the design of hybrid bio-inspired meta-heuristics for complex misattribute vehicle routing problems[J].Expert Systems,2020,37(6):e12528.
[3]NOVELLANI S.Models and algorithms for the optimization of real-world routing and logistics problems[J].A Quarterly Journal of Operations Research,2016,14:331-332.
[4]DANTZIG G,FULKERSON R,JOHNSON S.Solution of aLange-Scale Traveling Salesman Problem[J].Operations Research,1954,2(4):365-462.
[5]FISCHETTI M,GONZÁLEZ J J S,TOTH P.A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem[J].Operations Research,1997,45(3):327-494.
[6]BELLMAN R.Dynamic Programming Treatment of the Traveling Salesman Problem[J].Journal of the ACM,1962,9(1):61-63.
[7]TASSIULAS L.Worst Case Length of Nearest Neighbor Tours for the Euclidean Traveling Salesman Problem[J].SIAM Journal on Discrete Mathematics,1997,10(2):171-179.
[8]CLARKE G,WRIGHT J W.Scheduling of vehicles from a central depot to a number of delivery points[J].Operations Research,1964,12(4):519-643.
[9]CHRISTOFIDES N.Worst-case analysis of a new heuristic for the travelling salesman problem[J].Operations Research Forum,2022,3(1):20.
[10]DORIGO M,GAMBARDELLA L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.
[11]CHEN Y,ZHANG Y D,JING L,et al.An integer-coded chaotic particle swarm optimization for traveling salesman problem[M]//Progress in Robotics.Berlin:Springer,2009:372-379.
[12]ZHU M W,SHE X Y.Improved artificial fish swarm algorithm for solving traveling salesman problems[J].Computer Application Research,2010,27(10):3734-3736.
[13]LI Z F,WANG Y H.An improved shuffled frog leaping algorithm for TSP[M]//Advances in Multimedia,Software Engineering and Computing Vol.2.Berlin:Springer,2012:139-144.
[14]KARABOGA D,GORKEMLI B.A combinational artificial bee colony algorithm for traveling salesman problem[C]//International Symposium on Innovations in Intelligent Systems and Applications.2011:50-53.
[15]CARPANETO G,DELL′AMICO M,TOTH P.Exact solutionof large-scale,asymmetric traveling salesman problems[J].ACM Transactions on Mathematical Software,1995,21(4):394-409.
[16]GOETSCHALCKX M,JACOBS-BLECHA C.The vehicle routing problem with backhauls[J].European Journal of Operational Research,1989,42(1):39-51.
[17]XUE M H,WANG T Z,MAO S.Double evolutional artificial bee colony algorithm for multiple traveling salesman problem[J].MATEC Web of Conferences,2016,44:02025.
[18]BOUZOUBÍA S,LAYEB A,CHIKHI S.Enhanced ChemicalReaction Optimization for Multi-objective Traveling Salesman Problem[M]//Modelling and Implementation of Complex Systems.Springer,2016:91-106.
[19]MAUTOR T,NAUDIN E.Arcs-states models for the vehiclerouting problem with time windows and related problems[J].Computers & Operations Research,2007,34(4):1061-1084.
[20]LI J,ZHOU M C,SUN Q R,et al.Colored traveling salesman problem[J].IEEE Transactions on Cybernetics,2015,45(11):2390-2401.
[21]VINYALS O,FORTUNATO M,JAITLY N.Pointer networks[C]//Proceedings of the 28th Intermational Conference on Neural Information Processing Systems(NIPS’15).2015:2692-2700.
[22]BELLO I,PHAM H,QUOC V L,et al.Neural combinatorialoptimization with reinforcement learning[J].arXiv:1611.09940,2016.
[23]KOOL W,HOOF H V,WELLING M.Attention,learn to solve routing problems[J].arXiv:1803.08475,2018.
[24]NOWAK A,VILLAR S,BANDEIRA A S,et al.Revised note on learning algorithms for quadratic assignment with graph neural networks[J].arXiv:1706.07450,2018.
[25]JOSHI C K,LAURENT T,BRESSON X.An efficient graph convolutional network technique for the travelling salesman problem[J].arXiv:1906.01227,2019.
[26]KOOL W,HOOF H V,GROMICHO J,et al.Deep policy dynamic programming for vehicle routing problems[M]//Integration of Constraint Programming,Artificial Intelligence,and Operations Research.Springer,2022:190-213.
[27]FU Z H,QIU K B,ZHA H Y.Generalize a small pre-trained model to arbitrarily large tsp instances[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2021:7474-7482.
[28]DEUDON M,COURNUT P,LACOSTE A,et al.Learning heuristics for the TSP by policy gradient[C]//Integration of Constraint Programming.Artificial Intelligence,and Operations Research,2018:170-181.
[29]DAI H,KHALIL E B,ZHANG Y Y,et al.Learning combinatorial optimization algorithms over graphs[C]//Proceedings of the 31st International Conference on Neural Information Processing(NIPS’17).2017:6348-6358.
[30]WU Y,SONG W,CAO Z,et al.Learning improvement heuristics for solving routing problems[J].IEEE Transactions on Neural Networks and Learning Systems,2022,33(9):5057-5069.
[31]DACOSTA P,RHUGGENAATH J,ZHANG Y Q,et al.Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning[J].arXiv:2004.01608,2020.
[32]HUANG L Y,CHEN X M,WEI H,et al.Branch and Bound in Mixed Integer Linear Programming Problems:A Survey of Techniques and Trends[J].arXiv:2111.06257,2021.
[33]LAWLER E L,LENSTRA J K,RINNOOY K A H,et al.The Travelling Salesman:A Guided Tour of Combinatorial Optimization[J].Journal of the Operational Research Society,1986,37(5):535-536.
[34]LOMNICKI Z A.A Branch-and-Bound Algorithm for the Exact Solution of the Three-Machine Scheduling Problem[J].Journal of the Operations Research Society,1965,16:89-100.
[35]CLAUSEN J,TRAFF J L.Implementation of parallel Branch-and-Bound algorithms experiences with the graph partitioning problem[J].Annals of Operations Research,1991,33:331-349.
[36]MAUTOR T,ROUCAIROL C.A new exact algorithm for the solution of quadratic assignment problems[J].Discrete Applied Mathematics,1994,55(3):281-293.
[37]LAND A H,DOIG A G.An automatic method for solving discrete programming problems[J].Econometrica,1960,28(3):497-520.
[38]CLAUSEN J.Branch and bound algorithms-principles and examples[J/OL].https://janders.eecg.toronto.edu/1387/readings/b_and_b.pdf.
[39]ACHTERBERG T,KOCH T,MARTIN A.Branching rules revisited[J].Operations Research Letter,2005,33:42-54.
[40]GAMRATH G.Improving Strong Branching by Domain Propagation[J].EURO Journal on Computational Optimization,2014,2:99-122.
[41]KILINÇ,MUSTAFA R L.Strong-branching inequalities forconvex mixed integer nonlinear programs[J].Computational Optimization and Applications,2014,59:639-665.
[42]SANTANU S D,YATHARTH D,MARCO M,et al.A Theoretical and Computational Analysis of FullStrong-Branching[J].arXiv:2110.10754,2021.
[43]MILLER C E,TUCKER A W,ZEMLIN R A.Integer programming formulation of traveling salesman problems[J].Journal of the ACM,1960,7(4):326-329.
[44]TOBIAS A,TIMO B.Hybrid branching[M]//Integration of AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems.Berlin:Springer,2009:309-311.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed