2025/06/06 by Ziyu Zhang, Peilan Xu, Zhang, Ziyu +7
Computer Science · Engineering · #Advanced Multi-Objective Optimization Algorithms #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Robotic Path Planning Algorithms #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2506.06121
openalex publication_date 2025/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Large-scale itinerary planning is a variant of the traveling salesman problem, aiming to determine an optimal path that maximizes the collected points of interest (POIs) scores while minimizing travel time and cost, subject to travel duration constraints. This paper analyzes the decomposability of large-scale itinerary planning, proving that strict decomposability is difficult to satisfy, and introduces a weak decomposability definition based on a necessary condition, deriving the corresponding graph structures that fulfill this property. With decomposability guaranteed, 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 a set of real-world datasets. Comparative experiments with state-of-the-art multi-objective itinerary planning algorithms demonstrate the superiority of our approach, with performance advantages increasing as the problem scale grows.