关键词: 图注意力网络, 旅行售货商问题, 深度强化学习, 2-opt, 组合最优化

Abstract: TSP is a classic NP-hard combinatorial optimization problem in operations research,aimed at the shortest possible cycle that visits each city exactly once from the origin point and returns back.For solving TSP,this paper presents a hybrid deep reinforcement learning approach(2+HRL) based on a pointer network,integrating graph attention mechanisms and the 2-opt heuristic.Specifically,graph attention networks(GATs) capture both local and global structural information of cities,while bidirectional LSTMs dynamically encode path dependencies for context-aware state representation.During training stage,the 2-opt strategy iteratively improves paths by local edge swaps to enhance solution quality.The policy gradient optimization via the REINFORCE algorithm is combined with an entropy reward function to avoid local optima,while a value network enhances parameter estimation accuracy.Experimental results show that 2+HRL algorithm performs better than traditional heuristics and exact algorithms,and it has faster computational speed and higher precision if limited with fewer training iterations,and its performance exceeds other deep reinforcement learning approaches as training progresses increment.

Key words: Graph attention network, Traveling salesman problem, Deep reinforcement learning, 2-opt, Combinatorial optimization