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.