cs.AIJun 6, 2025
SaveDecomposability-Guided Cooperative Coevolution for Large-Scale Itinerary Planning
Organizations: School of Artificial Intelligence, Nanjing University of Information Science and Technology, Nanjing 210044, China. · Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China. · School of Computer Science and Technology, Harbin Institute of Technology (Shenzhen), Shenzhen 518055, Guangdong, China. · Guangdong Provincial Key Laboratory of Novel Security Intelligence Technologies, Shenzhen 518000, Guangdong, China.
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.
Figures & tables
Figure 1. The comparative schematic of the generalized TSP, clustered TSP, and large-scale itinerary planning. Orange backgrounds indicate different clusters, solid circles represent visited vertices, and hollow circles denote unvisited vertices. Three schematic routes contrast large-scale itinerary planning, the generalized traveling salesman problem, and the clustered traveling salesman problem. Orange regions mark clusters; filled and hollow circles distinguish visited and unvisited vertices.
Figure 2. A visual illustration of a graph structure satisfying the weak decomposability conditions. (a) A conceptual multi-cluster graph highlighting intra-cluster costs and representative inter-cluster connections for visual clarity. (b) The corresponding complete cost matrix heatmap, displaying the characteristic block-diagonal structure. Three clusters with low internal edge costs and higher inter-cluster costs, alongside their symmetric complete cost matrix satisfying the sufficient conditions in Theorem 1.
Figure 3. The schematic diagram of problem decomposition and computational resource allocation. Cities are highlighted with an orange background, while green dots within each city represent POIs, with their size indicating the quality of the corresponding POI. The upper diagram shows city components and point-of-interest scores. The middle diagram shows encoding units retained, randomized, or removed during component adjustment. The lower diagram shows the initial and subsequent allocation of computational resources, including a stagnant component.
| Cases | Country | City Index | Travel Duration |
|---|---|---|---|
| 1 | China | 5,7 | 4 |
| 2 | China | 5,7 | 6 |
| 3 | France | 9,13 | 4 |
| 4 | France | 9,13 | 6 |
| 5 | Germany | 16,18 | 4 |
| 6 | Germany | 16,18 | 6 |
Table 1. The description of the test cases
| Cases | DGCC | CCIP | LSNSGA-II | MOPSO | AONSGA-II |
|---|---|---|---|---|---|
| 1 | 6.632e+07 ± 1.231e+06 | 6.251e+07 ± 1.276e+06 (++) | 5.793e+07 ±3.090e+06 (++) | 5.151e+07 ± 3.316e+06 (++) | 4.180e+07 ± 1.645e+06 (++) |
| 2 | 1.266e+08 ± 2.896e+06 | 1.143e+08 ± 1.997e+06 (++) | 8.989e+07 ± 6.553e+06 (++) | 8.295e+07 ± 9.231e+06 (++) | 6.925e+07 ± 2.831e+06 (++) |
| 3 | 2.500e+10 ± 7.272e+08 | 1.920e+10 ± 3.089e+08 (++) | 1.906e+10 ± 1.599e+08 (++) | 1.857e+10 ± 1.044e+09 (++) | 9.125e+09 ± 8.209e+08 (++) |
| 4 | 6.279e+10 ± 8.828e+08 | 4.327e+10 ± 5.463e+08 (++) | 4.304e+10 ± 1.127e+09 (++) | 4.117e+10 ± 1.673e+09 (++) | 1.221e+10 ± 1.605e+09 (++) |
| 5 | 2.694e+10 ± 1.726e+08 | 2.398e+10 ± 1.385e+09 (++) | 2.220e+10 ± 2.172e+09 (++) | 1.908e+10 ± 2.153e+09 (++) | 1.319e+10 ± 1.567e+09 (++) |
| 6 | 1.030e+11 ± 2.161e+09 | 8.990e+10 ± 3.444e+09 (++) | 7.191e+10 ± 6.747e+09 (++) | 6.269e+10 ± 6.375e+09 (++) | 3.848e+10 ± 3.682e+09 (++) |
Table 2. The mean and standard deviation of HV obtained by DGCC and four compared algorithms on 18 test cases.
Figure 4. Four test set instance parameters Four panels show the geographical cluster configurations for the China, Japan, USA, and UK semi-synthetic test sets. Annotations report cluster attributes and the total numbers of cities and points of interest.
| Cases | Country | No. of Cities | Solution Dimension | Max FEs |
|---|---|---|---|---|
| 1 | China | 10 | 500 | 300000 |
| 2 | China | 10 | 1000 | 500000 |
| 3 | Japan | 6 | 300 | 180000 |
| 4 | Japan | 6 | 600 | 300000 |
| 5 | USA | 12 | 600 | 360000 |
| 6 | USA | 12 | 1200 | 600000 |
Table 3. Parameter settings for the semi-synthetic dataset.
| Cases | DGCC | CCIP | LSNSGA-II | MOPSO | AONSGA-II |
|---|---|---|---|---|---|
| 1 | 1.620e+12 ± 3.973e+10 | 1.536e+12 ± 1.173e+10 (++) | 4.556e+11 ± 2.433e+10 (++) | 8.136e+11 ± 2.199e+10 (++) | 5.199e+10 ± 2.963e+09 (++) |
| 2 | 5.965e+11 ± 1.657e+10 | 5.625e+11 ± 4.491e+09 (++) | 1.204e+11 ± 1.122e+10 (++) | 1.640e+11 ± 1.417e+10 (++) | 2.294e+10 ± 1.632e+09 (++) |
| 3 | 3.928e+12 ± 1.247e+11 | 3.722e+12 ± 3.648e+10 (++) | 5.161e+11 ± 3.689e+10 (++) | 6.399e+11 ± 4.917e+10 (++) | 7.653e+10 ± 4.253e+09 (++) |
| 4 | 1.543e+12 ± 4.202e+10 | 1.459e+12 ± 1.623e+10 (++) | 2.585e+11 ± 1.807e+10 (++) | 3.268e+11 ± 2.367e+10 (++) | 4.563e+10 ± 3.695e+09 (++) |
| 5 | 6.179e+12 ± 1.024e+11 | 5.793e+12 ± 3.260e+10 (++) | 6.008e+11 ± 4.019e+10 (++) | 8.017e+11 ± 7.077e+10 (++) | 8.588e+10 ± 5.160e+09 (++) |
| 6 | 2.279e+12 ± 3.002e+10 | 2.142e+12 ± 1.884e+10 (++) | 3.403e+11 ± 1.897e+10 (++) | 4.427e+11 ± 3.533e+10 (++) | 6.639e+10 ± 7.583e+09 (++) |
Table 4. The mean and standard deviation of HV obtained by DGCC and four compared algorithms on 8 test cases.
| Cases | Instance | No. of Clusters | Solution Dimension | Max FEs |
|---|---|---|---|---|
| 1 | att532s10g1q2.cop | 10 | 250 | 200000 |
| 2 | att532s10g1q3.cop | 10 | 250 | 200000 |
| 3 | att532s10g2q2.cop | 10 | 250 | 200000 |
| 4 | att532s10g2q3.cop | 10 | 250 | 200000 |
| 5 | att532s15g1q2.cop | 15 | 300 | 270000 |
| 6 | att532s15g1q3.cop | 15 | 300 | 270000 |
Table 5. Parameter settings for the COP test set.
| Cases | DGCC | CCIP | LSNSGA-II | MOPSO | AONSGA-II |
|---|---|---|---|---|---|
| 1 | 1.063e+14 ± 1.383e+11 | 1.058e+14 ± 1.568e+11 (++) | 2.793e+10 ± 9.778e+08 (++) | 3.264e+10 ± 9.388e+08 (++) | 2.149e+09 ± 2.479e+08 (++) |
| 2 | 1.065e+14 ± 1.482e+11 | 1.060e+14 ± 9.621e+10 (++) | 3.185e+10 ± 1.145e+09 (++) | 3.698e+10 ± 8.812e+08 (++) | 3.726e+09 ± 3.931e+08 (++) |
| 3 | 1.062e+14 ± 1.104e+11 | 1.057e+14 ± 1.448e+11 (++) | 2.718e+10 ± 8.937e+08 (++) | 3.166e+10 ± 9.840e+08 (++) | 1.786e+09 ± 2.405e+08 (++) |
| 4 | 1.064e+14 ± 1.325e+11 | 1.058e+14 ± 1.362e+11 (++) | 2.799e+10 ± 1.257e+09 (++) | 3.297e+10 ± 7.951e+08 (++) | 2.016e+09 ± 2.339e+08 (++) |
| 5 | 1.079e+14 ± 2.967e+11 | 1.069e+14 ± 1.947e+11 (++) | 5.763e+10 ± 1.477e+09 (++) | 6.214e+10 ± 1.472e+09 (++) | 4.453e+09 ± 5.725e+08 (++) |
| 6 | 1.080e+14 ± 2.303e+11 | 1.069e+14 ± 1.605e+11 (++) | 5.516e+10 ± 2.015e+09 (++) | 6.008e+10 ± 1.360e+09 (++) | 3.935e+09 ± 4.618e+08 (++) |
Table 6. The mean and standard deviation of HV obtained by DGCC and four compared algorithms on 8 test cases.
| Case | DGCC | w/o structure adjustment | w/o resource allocation | w/o population inheritance |
|---|---|---|---|---|
| 1 | 1.812e+06 ± 4.904e+04 | 1.761e+06 ± 4.137e+04 | 1.809e+06 ± 6.137e+04 | 1.396e+06 ± 5.886e+04 |
| 2 | 4.736e+06 ± 2.151e+05 | 4.525e+06 ± 1.824e+05 | 4.705e+06 ± 1.995e+05 | 3.040e+06 ± 2.209e+05 |
| 3 | 5.963e+09 ± 2.292e+08 | 4.537e+09 ± 3.976e+08 | 5.840e+09 ± 2.825e+08 | 4.148e+09 ± 2.450e+08 |
| 4 | 2.150e+10 ± 4.201e+08 | 1.647e+10 ± 7.287e+08 | 2.111e+10 ± 4.707e+08 | 1.420e+10 ± 4.289e+08 |
| 5 | 1.421e+09 ± 5.328e+07 | 1.411e+09 ± 7.589e+07 | 1.409e+09 ± 5.872e+07 | 1.221e+09 ± 1.083e+08 |
| 6 | 7.829e+09 ± 3.546e+08 | 7.451e+09 ± 6.230e+08 | 7.809e+09 ± 3.583e+08 | 5.612e+09 ± 7.196e+08 |
Table 7. The mean and standard deviation of HV about the ablation study of DGCC on 18 test cases.
| Test Sets | Dataset 1 (Itinerary Planning) | Dataset 2 (COP Instances) | ||||||
|---|---|---|---|---|---|---|---|---|
| Original Index | 7 | 8 | 13 | 14 | 1 | 2 | 5 | 6 |
| New Cases | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Table 8. Mapping relationship between the evaluated test cases and the original datasets.
| Cases | NSGA-II Operators | HI_MOEA Operators | MMTSP_DS Operators | |||
|---|---|---|---|---|---|---|
| with DGCC | without DGCC | with DGCC | without DGCC | with DGCC | without DGCC | |
| 1 | 3.740e+08 7.410e+06 | 1.548e+08 1.430e+07 (++) | 3.733e+08 4.586e+06 | 1.608e+08 1.864e+07 (++) | 3.656e+08 3.770e+06 | 1.224e+08 1.668e+07 (++) |
| 2 | 9.781e+08 1.955e+07 | 2.114e+08 2.273e+07 (++) | 9.664e+08 1.584e+07 | 2.185e+08 2.681e+07 (++) | 9.584e+08 1.188e+07 | 1.538e+08 2.838e+07 (++) |
| 3 | 4.163e+09 4.633e+07 | 1.688e+09 2.384e+08 (++) | 4.146e+09 5.775e+07 | 1.689e+09 2.323e+08 (++) | 4.173e+09 6.463e+07 | 1.408e+09 3.046e+08 (++) |
| 4 | 1.338e+10 1.761e+08 | 2.920e+09 3.062e+08 (++) | 1.341e+10 1.496e+08 | 3.117e+09 5.452e+08 (++) | 1.336e+10 1.619e+08 | 2.180e+09 7.039e+08 (++) |
| 5 | 1.059e+14 1.514e+11 | 1.674e+09 2.631e+08 (++) | 1.058e+14 1.166e+11 | 1.577e+09 2.960e+08 (++) | 1.058e+14 1.501e+11 | 1.587e+09 2.776e+08 (++) |
Table 9. The mean and standard deviation of HV obtained by different base operators with and without the proposed DGCC framework.
Figure 5. The variation curve of normalized HV with respect to the structure adjustment period in three test cases from China, France, and Germany. Normalized hypervolume versus structure adjustment period L for test cases from China, France, and Germany. The curves generally rise at smaller periods and decline at larger periods, with fluctuations.
Figure 6. The variation curve of normalized HV with respect to the available computational resource in three test cases from China, France, and Germany. Normalized hypervolume versus computational resources per round Q for test cases from China, France, and Germany. All three curves show an overall decrease as Q increases, with local fluctuations.
| Algorithms | Day | City | Points of Interest |
|---|---|---|---|
| DGCC | 1 | Nanjing | Laomen East Historical District Confucius Temple–Qinhuai Scenic Area Confucius Temple Zhan Garden Mochou Lake Scenic Area |
| 2 | Nanjing | Shiziqiao Food Street Jiming Temple Jiangning Imperial Silk Manufacturing Museum Xinjiekou | |
| 3 | Nanjing | Presidential Palace of Nanjing Nanjing Ming Palace Ruins Park | |
| 4 | Suzhou | Fengqiao Scenic Area Hanshan Temple Suzhou Museum Lion Grove Garden | |
| CCIP | 1 | Nanjing | Drum Tower Jiming Temple Xinjiekou Mochou Lake Scenic Area |
| 2 | Nanjing | Qinhuai River Laomen East Historical District Nanjing Ming Palace Ruins Park Nanjing Museum |
Table 10. Itineraries for DGCC, CCIP, and LSNSGA-II