arXiv：cs.AI· Ziyu Zhang, Peilan Xu, Yuetong Sun, Yuhui Shi, Wenjian Luo·· 22 小时前
基于弱可分解性的协同协同进化算法用于大规模行程规划
Decomposability-Guided Cooperative Coevolution for Large-Scale Itinerary Planning
AI 导读
针对大规模行程规划问题，该研究建立了弱可分解性的充分条件，并据此提出一种多目标协同协同进化算法，通过基于归一化适应度的动态分解策略、优化潜力定义和计算资源分配策略应对组件失衡与交互问题。在18个真实案例、8个大规模半合成案例和8个适配的公开聚类定向越野基准案例共34个测试中，该算法均取得最高平均超体积，显著优于对比算法，在大规模基准实例上性能提升尤为明显。
正文
Abstract:Large-scale itinerary planning is a variant of the traveling salesman problem, aiming to determine an optimal path that maximizes the collected point-of-interest (POI) scores while minimizing travel time and cost, subject to travel duration constraints. This paper analyzes inter-component dependence in large-scale itinerary planning and establishes sufficient conditions for weak decomposability, under which an optimal path can visit each cluster as a contiguous subpath. Guided by this weak decomposability, we propose a novel multi-objective cooperative coevolutionary algorithm for large-scale itinerary planning, addressing the challenges of component imbalance and interactions. Specifically, we design a dynamic decomposition strategy based on the normalized fitness within each component, define optimization potential considering component scale and contribution, and develop a computational resource allocation strategy. Finally, we evaluate the proposed algorithm on 18 real-world test cases, eight large-scale semi-synthetic test cases, and eight adapted public clustered orienteering problem benchmark cases. Comparative results show that the proposed algorithm achieves the highest mean hypervolume across all 34 test cases and significantly outperforms the compared algorithms. Ablation and optimizer-decoupling analyses further validate the effectiveness of its core mechanisms and the general applicability of the proposed framework, with particularly pronounced performance gains on large-scale benchmark instances.
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2506.06121 [cs.AI] |
| (or arXiv:2506.06121v3 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2506.06121 arXiv-issued DOI via DataCite |
Submission history
From: Ziyu Zhang [view email]
[v1]
Fri, 6 Jun 2025 14:31:57 UTC (213 KB)
[v2]
Fri, 13 Jun 2025 04:59:48 UTC (213 KB)
[v3]
Sat, 10 Oct 2026 12:40:02 UTC (1,255 KB)
来源：arXiv：cs.AI · arxiv.org