arXiv cs.AI· Ziyu Zhang, Peilan Xu, Yuetong Sun, Yuhui Shi, Wenjian Luo·· 3 天前AI 评分18
基于可分解性引导的协同协同进化大规模行程规划方法
Decomposability-Guided Cooperative Coevolution for Large-Scale Itinerary Planning
AI 导读
针对大规模行程规划中组件依赖问题，研究者建立了弱可分解性的充分条件，并据此提出一种多目标协同协同进化算法，通过基于归一化适应度的动态分解策略和计算资源分配策略应对组件不平衡与交互挑战。在34个测试用例（含18个真实案例、8个大规模半合成案例及8个聚类定向越野基准案例）上，该算法均取得最高平均超体积，显著优于对比算法，大规模基准实例上性能提升尤为明显。
正文 · AI 翻译
摘要：大规模行程规划是旅行商问题的一个变体，旨在确定一条最优路径，在满足旅行时长约束的前提下，最大化收集到的兴趣点（POI）得分，同时最小化旅行时间和成本。本文分析大规模行程规划中的组件间依赖关系，并建立弱可分解性的充分条件，在该条件下，最优路径可以将每个簇作为连续子路径进行访问。在此弱可分解性的指导下，我们提出了一种新颖的多目标协同协同进化算法用于大规模行程规划，以应对组件不平衡和交互带来的挑战。具体而言，我们设计了一种基于各组件内归一化适应度的动态分解策略，定义了考虑组件规模和贡献的优化潜力，并开发了一种计算资源分配策略。最后，我们在 18 个真实世界测试用例、8 个大规模半合成测试用例以及 8 个改编的公开聚类定向问题基准用例上评估了所提出的算法。对比结果表明，所提出的算法在所有 34 个测试用例上取得了最高的平均超体积，并显著优于所比较的算法。消融和优化器解耦分析进一步验证了其核心机制的有效性以及所提出框架的普遍适用性，在大规模基准实例上的性能提升尤为显著。
| 主题： | 人工智能（cs.AI） |
| 引用为： | arXiv:2506.06121 [cs.AI] |
| （或 arXiv:2506.06121v3 [cs.AI] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2506.06121 arXiv 颁发的 DOI（通过 DataCite） |
提交历史
来自：Ziyu Zhang [查看电子邮件]
[v1]
2025 年 6 月 6 日星期五 14:31:57 UTC（213 KB）
[v2]
2025 年 6 月 13 日星期五 04:59:48 UTC（213 KB）
[v3]
2026 年 10 月 10 日星期六 12:40:02 UTC（1,255 KB）
来源：arXiv cs.AI · arxiv.org