GCN-Pointransformer Model for Solving Traveling Salesman Problem

doi:10.3778/j.issn.1673-9418.2404030

Abstract

Abstract: Because the Transformer model is based on the fully connected attention mechanism, the computational complexity is high and the GPU memory usage is too large when solving the classic traveling salesman problem (TSP). To solve this problem, a GCN-Pointransformer model based on graph convolutional embedding layer and multi-head local self-attention mechanism is proposed. Firstly, the graph convolutional embedding method is used to learn spatial features from the input data, and the graph convolutional embedding layer contains multiple convolution kernels that can extract the local features of the input data. Secondly, the multi-head local self-attention (MHLSA) is used, which removes redundant information and extracts useful features. In addition, this paper uses a reversible residual network in the encoder to store only input and output embedding feature pairs during backpropagation. Finally, the model adds a Pointer layer in the decoder, using attention weights as probability distributions to determine the next node to be visited. Comparative experiments on the TSP random datasets show that the optimization gap is reduced by 12%, the GPU memory is reduced by about 11%, and the inference time is reduced by about 25%, and the results show that the proposed method is superior to the standard Transformer model for solving TSP.

Key words: traveling salesman problem (TSP), GCN-Pointransformer, multi-head local self-attention (MHLSA), rever-sible residual, Pointer layer

摘要： 由于Transformer模型基于全连接注意力机制，导致在求解经典旅行商问题（TSP）时，计算复杂度较高并且GPU内存使用量过大。针对此问题，提出了一种基于图卷积嵌入层和多头局部自注意力机制的GCN-Pointransformer模型。使用图卷积嵌入方式从输入数据中进行空间特征学习，图卷积嵌入层包含多个可以提取输入数据局部特征的卷积核；使用多头局部自注意力机制（MHLSA），删除冗余信息并提取有用的特征；在编码器中使用可逆残差网络，在反向传播过程中只存储输入和输出嵌入特征对；模型在解码器中增加了Pointer指针层，使用注意力权重作为概率分布，确定要访问的下一个节点。在TSP随机数据集上进行对比实验，优化间隙减少12%，GPU内存减少约11%，推理时间减少约25%，结果表明，该方法优于求解TSP的标准Transformer模型。

关键词: 旅行商问题（TSP）, GCN-Pointransformer, 多头局部自注意力机制（MHLSA）, 可逆残差, 指针层

QIU Yunfei, LIU Yifei, YU Zhilong, JIN Haibo. GCN-Pointransformer Model for Solving Traveling Salesman Problem[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(3): 657-666.

邱云飞, 刘一菲, 于智龙, 金海波. 求解旅行商问题的GCN-Pointransformer模型[J]. 计算机科学与探索, 2025, 19(3): 657-666.

References

[1] BELLMAN R. Dynamic programming treatment of the travelling salesman problem[J]. Journal of the ACM, 1962, 9(1): 61-63.
[2] HELD M, KARP R M. A dynamic programming approach to sequencing problems[J]. Journal of the Society for Industrial and Applied Mathematics, 1962, 10(1): 196-210.
[3] DANTZIG G, FULKERSON R, JOHNSON S. Solution of a large-scale traveling-salesman problem[J]. Journal of the Operations Research Society of America, 1954, 2(4): 393-410.
[4] KIRKPATRICK S, GELATT C D JR, VECCHI M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598): 671-680.
[5] CROES G A. A method for solving traveling-salesman problems[J]. Operations Research, 1958, 6(6): 791-812.
[6] BIXBY R, ROTHBERG E. Progress in computational mixed integer programming: a look back from the other side of the tipping point[J]. Annals of Operations Research, 2007, 149(1): 37-41.
[7] APPLEGATE D L, BIXBY R E, CHVATAL V, et al. The traveling salesman problem: a computational study[M]. Princeton: Princeton University Press, 2011.
[8] CHRISTOFIDES N. Worst-case analysis of a new heuristic for the travelling salesman problem[J]. Operations Research Forum, 2022, 3(1): 20.
[9] PERRON L, FORTUNATO V. OR-tools[EB/OL]. [2024-02-25]. https://developers.google.com/optimization/.
[10] VINYALS O, FORTUNATO M, JAITLY N. Pointer networks[C]//Advances in Neural Information Processing Systems 28, Montreal, Dec 7-12, 2015: 2692-2700.
[11] NAZARI M, OROOJLOOY A, TAKÁČ M, et al. Reinforcement learning for solving the vehicle routing problem[C]//Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018: 9861-9871.
[12] JOSHI C K, LAURENT T, BRESSON X. An efficient graph convolutional network technique for the travelling salesman problem[EB/OL]. [2024-02-25]. https://arxiv.org/abs/1906.01227.
[13] STOHY A, ABDELHAKAM H T, ALI S, et al. Hybrid pointer networks for traveling salesman problems optimization[J]. PLoS One, 2021, 16(12): e0260995.
[14] MA Q, GE S W, HE D Y, et al. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning[EB/OL]. [2024-02-25]. https://arxiv.org/abs/1911.04936.
[15] MIKI S, EBARA H. Solving traveling salesman problem with image-based classification[C]//Proceedings of the 2019 IEEE 31st International Conference on Tools with Artificial Intelligence. Piscataway: IEEE, 2019: 1118-1123.
[16] LING Z X, TAO X Y, ZHANG Y, et al. Solving optimization problems through fully convolutional networks: an application to the traveling salesman problem[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(12): 7475-7485.
[17] SULTANA N, CHAN J, SARWAR T, et al. Learning to optimise general TSP instances[J]. International Journal of Machine Learning and Cybernetics, 2022, 13(8): 2213-2228.
[18] KOOL W, VAN HOOF H, WELLING M. Attention, learn to solve routing problems![EB/OL]. [2024-02-25]. https://arxiv.org/abs/1803.08475.
[19] WU Y X, SONG W, CAO Z G, et al. Learning improvement heuristics for solving routing problems[J]. IEEE Transactions on Neural Networks and Learning Systems, 2022, 33(9): 5057-5069.
[20] BRESSON X, LAURENT T. The transformer network for the traveling salesman problem[EB/OL]. [2024-02-25]. https://arxiv.org/abs/2103.03012.
[21] GUO Q P, QIU X P, LIU P F, et al. Star-transformer[EB/OL]. [2024-02-25]. https://arxiv.org/abs/1902.09113.
[22] 程荣. 遗传算法求解旅行商问题[J]. 科技风, 2017(16): 40.
CHENG R. Genetic algorithm for solving traveling salesman problem[J]. Technology Wind, 2017(16): 40.
[23] GOMEZ A N, REN M Y, URTASUN R, et al. The reversible residual network: backpropagation without storing activations[C]//Advances in Neural Information Processing Systems 30, 2017: 2214-2224.
[24] KITAEV N, KAISER Ł, LEVSKAYA A. Reformer: the efficient transformer[EB/OL]. [2024-02-25]. https://arxiv.org/abs/2001.04451.
[25] JIN Y, DING Y D, PAN X H, et al. Pointerformer: deep reinforced multi-pointer transformer for the traveling salesman problem[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2023, 37(7): 8132-8140.
[26] BELLO I, PHAM H, LE Q V, et al. Neural combinatorial optimization with reinforcement learning[EB/OL]. [2024-01-20]. https://arxiv.org/abs/1611.09940.
[27] JUNG M, LEE J, KIM J. A lightweight CNN-transformer model for learning traveling salesman problems[EB/OL]. [2024-01-20]. https://arxiv.org/abs/2305.01883.
[28] Google. OR-tools: Google􀆳s operations research tools[EB/OL]. [2024-01-20]. https://gitcode.com/google/or-tools.
[29] HELSGAUN K. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems[R]. Roskilde: Roskilde University, 2017: 966-980.
[30] JOHNSON D S. Local optimization and the traveling salesman problem[M]//Automata, languages and programming. Berlin, Heidelberg: Springer, 2005: 446-461.
[31] DAI H J, 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 Systems, 2017: 6351-6361.
[32] DEUDON M, COURNUT P, LACOSTE A, et al. Learning heuristics for the TSP by policy gradient[M]//Integration of constraint programming, artificial intelligence, and operations research. Cham: Springer, 2018: 170-181.
[33] XIAO Y B, WANG D, LI B Y, et al. Reinforcement learning-based non-autoregressive solver for traveling salesman problems[EB/OL]. [2024-01-20]. https://arxiv.org/abs/2308.00560.
[34] DA COSTA P, RHUGGENAATH J, ZHANG Y Q, et al. Learning 2-opt heuristics for routing problems via deep reinforcement learning[J]. SN Computer Science, 2021, 2(5): 388.