Solving the Traveling Salesman Problem Using Graph Attention and Reinforcement Learning

Combinatorial Optimization Problems (COPs) are NP-hard, and finding optimal solutions becomes increasingly difficult as problem size grows. We propose an end-to-end reinforcement learning framework based on multi-layer hybrid graph convolution and attention to solve the Euclidean TSP. The encoder combines multi-scale convolution and graph attention to capture local and global structures, while the decoder employs a probabilistic dynamic decision mechanism (ProbAttention) and improved adaptive PPO (APPO) for balanced exploration and exploitation. Experiments on TSP instances with 20, 50, and 100 nodes show that MLH-GCN outperforms most heuristic and deep RL methods in optimality gap.