大規模複数巡回セールスマン問題に対するK-means着想の解法フレームワーク
A K-means Inspired Solution Framework for Large-Scale Multi-Traveling Salesman Problems
複数エージェントのタスク割り当て問題(MTSP)を空間制約付きクラスタリングとして再定式化し、K-meansに着想を得た「クラスタリング後に経路決定」戦略で大規模問題を高速かつ高品質に解くフレームワークを提案した。
詳しい要約
1. どんなもの?
2. 先行研究と比べてどこがすごい?
3. 技術・手法の肝は?
4. どうやって有効だと検証した?
5. 議論はある?
6. 次に読むべき論文は?
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Xiubin Chen
分類: eess.SY, cs.RO, cs.SY
原文アブストラクト
The Multi-Traveling Salesman Problem (MTSP) is a commonly used mathematical model for multi-agent task allocation. However, as the number of agents and task targets increases, existing optimization-based methods often incur prohibitive computational costs, posing significant challenges to large-scale coordination in unmanned systems. To address this issue, this paper proposes a K-means-inspired task allocation framework that reformulates the MTSP as a spatially constrained classification process. By leveraging spatial coherence, the proposed method enables fast estimation of path costs and efficient task grouping, thereby fundamentally reducing overall computational complexity. Extensive simulation results demonstrate that the framework can maintain high solution quality even in extremely large-scale scenarios-for instance, in tasks involving 1000 agents and 5000 targets. The findings indicate that this "cluster-then-route" decomposition strategy offers an efficient and reliable solution for large-scale multi-agent task allocation.
