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.

CARSS 是一种利用合作的多智能体强化学习方法，通过分解 TSP 求解过程为 “子路径生成” 和 “子路径合并” 两个步骤，采用关注机制来提高效率和可扩展性，证明了它在减少资源消耗、测试时间以及优化空间方面的优越性。