用聚类思想分解大规模巡检任务，显著降低计算成本。
A K-means Inspired Solution Framework for Large-Scale Multi-Traveling Salesman Problems
- 将多旅行商问题转化为空间聚类任务，先分组后规划路径。
- 1000个智能体、5000个目标下仍保持高质量解。
- 适合无人机群、机器人等大规模协同系统部署。
多旅行商问题（MTSP）是多智能体任务分配的常用数学模型。但随着智能体和任务目标数量增加，现有基于优化的方法往往带来难以承受的计算开销，给无人系统的大规模协调带来挑战。为此，本文提出一种受K-means启发的任务分配框架，将MTSP重构为具有空间约束的分类过程。通过利用空间一致性，该方法能快速估算路径成本并高效完成任务分组，从根本上降低整体计算复杂度。大量仿真实验表明，该框架在极端大规模场景下仍可维持高解质量，例如在1000个智能体与5000个目标的任务中表现优异。结果表明，这种‘先聚类后规划’的分解策略为大规模多智能体任务分配提供了高效可靠的解决方案。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。