CARSS: Cooperative Attention-guided Reinforcement Subpath Synthesis for
  Solving Traveling Salesman Problem
Yuchen Shi Congying Han Tiande Guo
This paper introduces CARSS (Cooperative Attention-guided Reinforcement
Subpath Synthesis), a novel approach to address the Traveling Salesman Problem
(TSP) by leveraging cooperative Multi-Agent Reinforcement Learning (MARL).
CARSS decomposes the TSP solving process into two distinct yet synergistic
steps: "subpath generation" and "subpath merging." In the former, a cooperative
MARL framework is employed to iteratively generate subpaths using multiple
agents. In the latter, these subpaths are progressively merged to form a
complete cycle. The algorithm's primary objective is to enhance efficiency in
terms of training memory consumption, testing time, and scalability, through
the adoption of a multi-agent divide and conquer paradigm. Notably, attention
mechanisms play a pivotal role in feature embedding and parameterization
strategies within CARSS. The training of the model is facilitated by the
independent REINFORCE algorithm. Empirical experiments reveal CARSS's
superiority compared to single-agent alternatives: it demonstrates reduced GPU
memory utilization, accommodates training graphs nearly 2.5 times larger, and
exhibits the potential for scaling to even more extensive problem sizes.
Furthermore, CARSS substantially reduces testing time and optimization gaps by
approximately 50% for TSP instances of up to 1000 vertices, when compared to
standard decoding methods.