Reinforcement Learning-Based Nonautoregressive Solver for Traveling Salesman Problems.

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• The traveling salesman problem (TSP) is a significant combinatorial optimization challenge with diverse real-world applications.
• Neural networks (NNs) are increasingly used for TSP, offering strong heuristic solutions.
• Nonautoregressive (NAR) neural networks offer faster inference than autoregressive models but typically yield lower solution quality.

Purpose of the Study:

• To develop a novel NAR model for TSP that improves solution quality while maintaining fast inference.
• To integrate reinforcement learning (RL) with NAR networks for TSP solving.
• To address the trade-off between speed and accuracy in NAR-based TSP solvers.

Main Methods:

• Proposed NAR4TSP, a novel NAR model with a specialized architecture.
• Developed an enhanced reinforcement learning (RL) strategy tailored for NAR networks.
• Integrated NAR network output decoding directly into the RL training process, using TSP-encoded information as rewards.
• Ensured consistent TSP sequence constraints throughout training and testing.

Main Results:

• NAR4TSP demonstrated superior performance against five state-of-the-art (SOTA) models.
• Achieved improvements in solution quality, inference speed, and generalization capabilities.
• Successfully combined RL and NAR networks for TSP, a novel approach.

Conclusions:

• NAR4TSP represents a breakthrough in solving the traveling salesman problem using NAR networks and RL.
• The model offers a compelling balance of speed and accuracy, outperforming existing SOTA methods.
• This work paves the way for more efficient and effective solutions to complex combinatorial optimization problems.