Reproduce “Reinforcement Learning-based Non-Autoregressive Solver for Traveling Salesman Problems” on OpenResearch

About this paper

Yubin Xiao, Di Wang, Boyang Li, Huanhuan Chen, Wei Pang, Xuan Wu, Hao Li, Dong Xu and 2 more

NAR4TSP, a Reinforcement Learning-based Non-Autoregressive Solver, tackles Traveling Salesman Problems by combining an enhanced Graph Neural Network architecture with a tailored self-critical RL strategy. The model achieves competitive solution quality, significantly faster inference speeds (up to 94 times faster than leading autoregressive models), and superior generalization capabilities across diverse synthetic and real-world TSP instances.

Key insights

• Successfully integrating Reinforcement Learning with a Non-Autoregressive architecture can overcome the limitations of prior NAR models (reliance on expensive labels, poor generalization) while preserving their inherent speed advantage.
• A learnable starting-node pointer within the GNN architecture significantly contributes to solution quality and robustness by allowing the model to intelligently identify the most promising starting point for tour construction.
• The proposed enhanced RL strategy substantially reduces GPU memory usage (by 9.89%) and training time (by 26.36%) compared to conventional self-critical RL, making the training process more resource-efficient without sacrificing solution quality.

Summary by alphaXiv.