Decomposability-Guaranteed Cooperative Coevolution for Large-Scale Itinerary Planning

--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. Itinerary planning is a class of the orienteering problem, where a traveler aims to determine an optimal route within a city under given duration constraints, selecting a subset of points of interest (POIs) to maximize the total collected score [1]. It can be seen as a variant of the traveling salesman problem (TSP) and a combination of the knapsack problem and TSP [2]. As a real-world application, itinerary planning not only seeks to maximize the overall travel experience, i.e., the total collected score, but also considers objectives such as minimizing travel time and cost. This work is partly supported by the Natural Science Foundation of Jiangsu Province (Grant No. BK20230419), the Natural Science Foundation of the Jiangsu Higher Education Institutions of China (Grant No. 23KJB520018) and the National Natural Science Foundation of China (Grant No. U23B2058). Wenjian Luo is with the School of Computer Science and Technology, Harbin Institute of Technology (Shenzhen), Shenzhen 518055, Guangdong, China.