Efficient Graph Sequence Reinforcement Learning for Traveling Salesman Problem

The Traveling Salesman Problem is formulated as a sequence to sequence problem, and then policy gradient, graph convolutional networks, and multi-head attention techniques are applied to generate the according sequence model. The model is trained and tested by reinforcement learning on small-scale graphs. In addition, we use the 2-optimization algorithm to improve the model’s generation performance during the testing process. The results demonstrate that the proposed method, which is called Graph Sequence Reinforcement Learning Model, can be trained on small-scale graphs effectively without supervision and can be applied to solve TSP with large-scale graphs directly. Moreover, the performance of the proposed surpasses some of the state-of-the-art heuristic algorithms with high performance, and the ablation experiment shows that each part of the model is helpful for improving performance.