{"id":"e8065e2b-6be8-4703-a8cc-e7857b9d9d08","arxiv_id":"2506.06121","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"A cooperative coevolution algorithm for large-scale multi-city itinerary planning, with a claimed weak-decomposability guarantee, outperforms four baselines on 18 real-world test cases.","lead":"This paper presents a new algorithm for planning multi-city trips that splits the problem by city and then rebalances days and computing effort between cities. The authors claim a theoretical guarantee that splitting by city does not lose optimal routes, and report better solutions than four existing planners on real data from China, France, and Germany.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The weak-decomposability guarantee does not justify DGCC's fixed city-order search space; the paper never shows that the predefined component order preserves the Pareto front.","rationale":"The reader's weakest assumption centers on the unverified condition (2). I agree that this is a real concern, but the more decisive and theory-internal gap is the mismatch between Theorem 1's guarantee (existence of some single-visit order) and the algorithm's fixed-order encoding. This mismatch is independent of the dataset and would survive even if condition (2) were verified computationally. The proposed permutation test would settle whether the fixed order is actually harmful on the reported instances; if it is, the paper overclaims its decomposability guarantee. The reader's REJECT verdict is therefore retained, with the emphasis shifted to the order restriction. The paper's empirical study is reasonably thorough, including 50 runs, Wilcoxon tests, and ablations, and the algorithm may well be effective on the restricted problem; the problem is that the theoretical framing does not justify the restriction. The missing code and data, plus the undisclosed adjustment period L, further lower confidence, but the structural gap in the proof-to-algorithm bridge is the load-bearing issue.","tokens_in":19665,"tokens_out":6687,"duration_ms":72934,"concrete_test":"For Cases 13 and 14 (Chinese cities 1,4,5,7; travel durations 8 and 12 days), run DGCC with each of the 24 possible city orderings, keeping all other parameter settings identical to the paper and using the same 50-run protocol; compare mean HV with the Wilcoxon signed-rank test. If any alternative ordering yields a significantly higher HV, the fixed order excludes superior solutions and the weak-decomposability guarantee does not cover the implemented search space. Independently, compute for each test case the max intra-cluster and min inter-cluster edge weights for both travel time and travel cost to verify whether condition (2) holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's core theoretical warrant is Theorem 1, which establishes that when condition (2) holds, there exists an optimal path visiting each cluster exactly once. It does not say anything about which cluster order is optimal. Yet DGCC fixes a single 'optimal visiting sequence of components' at initialization (Algorithm 2, line 3) and never reorders components; the dynamic decomposition in Algorithm 1 only transfers encoding units while retaining that order. Consequently, the search space actually optimized by DGCC is a strict subset of the weakly decomposable path space. The paper supplies no proof, and the theorem's proof itself reorders clusters, that the fixed order preserves optimality or the Pareto front. Even if every test case satisfied condition (2), the reported HV improvements could reflect solving an order-restricted problem rather than the large-scale itinerary planning problem defined in Section II.A. Separately, the assertion in Section III.A that 'the test cases satisfy the conditions of Theorem 1' is not verified against the dataset, but that is a secondary gap: the fixed-order restriction would remain a gap even if condition (2) were confirmed. The paper should either prove that the chosen order is safe or restrict its claims to order-specified itinerary planning.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper addresses large-scale itinerary planning as a multi-objective TSP variant in which POIs are clustered by city. It introduces a formal notion of weak decomposability, proves a sufficient graph condition (Theorem 1) under which an optimal path visits each cluster exactly once, and proposes DGCC, a cooperative coevolutionary algorithm with dynamic component-size adjustment and computational-resource allocation. Experiments are run on 18 real-world test cases built from POIs in Chinese, French, and German cities, and the authors report statistically significant hypervolume improvements over four baseline algorithms, with larger gains for more cities.","tokens_in":19887,"tokens_out":16057,"duration_ms":147189,"significance":"If the weak-decomposability guarantee were correctly established and actually used, the paper would be a useful bridge between problem structure and cooperative coevolution for itinerary planning. The paper has concrete strengths: real-world data, 50-run averages with Wilcoxon and Friedman tests, ablations of the three main algorithmic components, and parameter studies. The central theoretical-to-algorithmic link, however, is not established: Theorem 1 is not proved as written, the assertion that all test cases satisfy condition (2) is unverified, and the algorithm optimizes over a fixed city order that the theorem does not justify. These are load-bearing gaps in the 'decomposability-guaranteed' claim.","major_comments":[{"comment":"The base-case proof of Theorem 1 is not valid as written. For the paths x=(v(1)_1, v(2)_1, v(1)_2, v(2)_2) and x'=(v(1)_2, v(1)_1, v(2)_1, v(2)_2), the true difference f(x')-f(x) contains the term -w(v(2)_{1,e}, v(1)_{2,s}) (the edge between the second and third segments of x) and does not contain the term -w(v(1)_{1,e}, v(2)_{1,s}), because that edge is present in both paths and cancels. The displayed formula therefore does not equal the actual difference, and the claimed bound w_max(V_1)+w_max(V_2)-2w_min(V_1,V_2) is not derived. The induction step is a sketch that never accounts for all edges affected by the 'extract' and 'reinsert' operations. Theorem 1 is consequently not established in the manuscript.","section":"Section III.A, Theorem 1"},{"comment":"The statement 'In this paper, the test cases satisfy the conditions of Theorem 1' is unsupported. No computation of w_max(V_i) or min_{j≠k} w_min(V_j,V_k) is reported for any of the 18 test cases, so the reader cannot verify the load-bearing premise that the experimental instances are weakly decomposable. Moreover, the experimental objectives in Eq. (7) differ from Eq. (1): they include vertex costs, a reciprocal POI score, and a k-dependent balancing factor ω in Eq. (8), while Theorem 1's condition is stated only for scalar edge weights. The paper should either report the verification for each case or explicitly extend the theorem to the actual objective vector.","section":"Section III.A, final paragraph"},{"comment":"The weak-decomposability guarantee does not justify the fixed city order used by DGCC. Theorem 1 asserts the existence of an optimal path that visits each cluster exactly once, but it says nothing about which cluster order is optimal. Algorithm 2 line 3 fixes an 'optimal visiting sequence' at initialization, and the dynamic decomposition in Algorithm 1 only transfers encoding units without changing that order; the assembly step then concatenates component blocks in this fixed order. The paper provides no proof, and no dataset-specific argument, that this order contains a Pareto-optimal solution for any test case. The search space actually optimized is therefore a strict subset of the path space covered by Theorem 1, and the reported HV gains could be solving an order-restricted problem rather than the problem defined in Section II.A.","section":"Sections III.B, III.E, Algorithm 2"}],"minor_comments":[{"comment":"The statement and proof of Lemma 1 contain an incomplete clause ('since no two path segments x^(i), we must have ...') and the condition on objective values is not stated precisely; the proof should say clearly that the argument assumes any two distinct path segments differ in objective value.","section":"Section III.A, Lemma 1"},{"comment":"The loop 'for i ← i_max to i_min' and the accompanying text assume i_max < i_min, but no justification is given; if i_max > i_min, the transfer direction is undefined. The pseudocode should specify the iteration direction for both cases.","section":"Algorithm 1, lines 11-18"},{"comment":"The qualitative case study is inconsistent with the test-set definition: Table I assigns case 1 to Wuxi and Yangzhou, yet Section IV.E describes a four-day itinerary to Nanjing and Wuxi, and many listed POIs (e.g., Wangshi Garden, Zhuozheng Garden, Hanshan Temple, Guanqian Street) are in Suzhou rather than the stated cities. This inconsistency should be corrected and the underlying city labels checked.","section":"Section IV.E, Table IV"},{"comment":"The ablation results are reported without significance tests; 'outperforms' is inferred from mean HV only. Please add statistical comparisons or state explicitly that the differences are numerical.","section":"Table III"},{"comment":"There are several presentation issues: 'German' is used as an adjective for Germany in Table I; the notation f(x^(i)) in Eq. (3) is used before being defined; and the meaning of the summary row '++/- 18/0/0' should be explained more explicitly in the text.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The manuscript's novelty over the authors' earlier CCIP paper [17] is not sharply delineated; both are cooperative-coevolution approaches to cross-city itinerary planning. More importantly, Section IV.E appears to mix POIs from different cities, and the editor may want to verify the integrity of the dataset labels before considering any further round. The fixed-order gap is a fundamental mismatch between the theorem and the algorithm, so a normal revision would require either a major redesign or a substantial narrowing of the claimed scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the theoretical framing overclaims, but the algorithmic work is real.\n\nWhat's new: the strict/weak decomposability definitions are a sensible way to think about cluster-structured TSP, and the dynamic decomposition and resource allocation mechanisms are genuinely not in the cited literature. The experiments are thorough—18 cases, 50 runs, Wilcoxon and Friedman tests, ablations for each of the three main mechanisms, and a parameter study.\n\nThe problem is the gap between Theorem 1 and what DGCC actually does. Theorem 1 says that when condition (2) holds, there exists an optimal path that visits each cluster once. It does not say that any particular cluster order works. But Algorithm 2 fixes an 'optimal visiting sequence' at initialization and never reorders components. The dynamic adjustment in Algorithm 1 only moves encoding units between neighboring components while preserving that order. So DGCC's search space is a strict subset of the weakly decomposable path space, and the paper gives no justification that this subset contains the Pareto front. That's a load-bearing mismatch: even if condition (2) holds on the test cases, the reported HV gains might come from solving an order-restricted problem.\n\nTwo secondary issues. First, the assertion that all test cases satisfy condition (2) is made in passing, with no verification. Given how strong the condition is (sum of max intra-city edge weights ≤ min inter-city edge weight), that needs a table or a computation. Second, Theorem 1's proof is hard to follow; the base case's edge-replacement terms look wrong and the induction is sketched. That would matter even if the statement is true.\n\nThe empirical study looks honestly done, and the ablations are informative. But the missing code/data and the undisclosed value of L in the main runs lower reproducibility. These are fixable; the fixed-order issue is not a minor rewording.\n\nWho this is for: people working on cooperative coevolution for clustered routing problems. I would probably not cite it until the order issue is resolved, but I'd bring it to a reading group to argue about the theorem-algorithm gap. Send it to peer review: the ideas deserve referee time, and the authors should be pushed to fix the proof, verify condition (2) on their data, and either add an order-adjustment mechanism or reframe the claims as order-specified planning.","headline":"The decomposability guarantee only proves existence of some cluster-once route, yet DGCC fixes one city order and never reorders, so the theoretical and algorithmic claims don't match; the empirical work is solid but the theory needs major revision.","tokens_in":20419,"tokens_out":4155,"would_cite":false,"duration_ms":41205,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a sufficient condition under which large-scale itinerary planning can be decomposed city by city, then builds a cooperative coevolution algorithm that reports higher hypervolume than four comparison methods on all 18…","keywords":["itinerary planning","cooperative coevolution","weak decomposability","large-scale multi-objective optimization","traveling salesman problem","orienteering problem","NSGA-II","hypervolume"],"falsifier":"For each of the 18 test cases, compute every intra-city edge weight and every inter-city edge weight from the travel data and test whether the sum of the within-city maxima is at most the minimum between-city edge; any violation breaks the weak-decomposability guarantee. Then run an unrestricted multi-objective optimizer without the city-block constraint and compare its Pareto front with DGCC's; a strictly better unrestricted front would show that the fixed city-order encoding excludes optimal solutions.","tokens_in":19391,"feed_emoji":"🗺️","tokens_out":7114,"duration_ms":66406,"temperature":0.7,"pith_summary":"Large-scale itinerary planning—choosing a route across many cities that maximizes collected point-of-interest scores while minimizing travel time and cost—can be decomposed city by city without giving up optimality, provided intercity travel links are heavy compared with links inside each city. The paper proves a sufficient condition (Theorem 1) under which some optimal route visits each city exactly once as a contiguous block, calling this weak decomposability. It then builds DGCC, a cooperative coevolution algorithm that optimizes each city as a separate component, dynamically shifts travel days between cities using hypervolume of normalized fitness, and distributes computation by an optimization-potential measure. In experiments on 18 real-world itinerary cases from China, France, and Germany, DGCC reports higher hypervolume than four comparison algorithms on every instance, with the advantage increasing as the number of cities grows.","feed_headline":"Splitting trips by city is safe when intercity links dominate","feed_subtitle":"New cooperative coevolution solver beats four baselines on 18 real-world cases, and the edge grows with scale.","key_machinery":"The load-bearing object is the inequality in Theorem 1: the sum, over all cities, of the maximum edge weight inside each city is at most the minimum edge weight between any two cities. When it holds, the exchange argument in the theorem shows any route can be reordered so that each city is visited in one contiguous block without increasing the objective, making the problem weakly decomposable. On that foundation, DGCC uses a per-day encoding with placeholder zeros, a dynamic decomposition that moves encoding units from the city with the lowest normalized-fitness hypervolume to the highest, and a computational resource allocation where each city's optimization potential is the product of its hypervolume improvement and its POI count, with stagnant cities receiving only basic evaluations.","core_discovery":"On its own terms, the paper claims that multi-city itinerary planning is weakly decomposable: under the condition that the sum of the largest travel edges inside the cities is no larger than the smallest edge between cities, there always exists an optimal route that visits each city exactly once, so the route can be rearranged into consecutive per-city blocks. Strict decomposability, in which each city's optimal subpath is independent of the others, is shown to be generically impossible. The paper then treats this guarantee as a license to decompose by city and proposes DGCC, whose components are per-city subpopulations with a travel-day encoding, whose dynamic decomposition transfers encoding units from low-contribution to high-contribution cities, and whose resource allocation uses hypervolume improvement combined with city POI count. The reported result is that DGCC significantly outperforms CCIP, LSNSGA-II, MOPSO, and AONSGA-II on all 18 test cases under the Wilcoxon test, with performance advantages that grow with problem scale.","pith_inferences":["The assertion that all 18 test cases satisfy the Theorem 1 inequality is stated but not demonstrated in the paper; checking it against the travel-time and travel-cost matrices would settle whether the decomposability guarantee actually holds for the experiments.","The theorem guarantees that a contiguous-block route exists, not that the particular city order fixed by DGCC is optimal, so the fixed order is an extra assumption beyond the theorem.","The same condition-and-exchange argument should transfer to other clustered routing problems, such as clustered TSP with profits or multi-zone delivery routing, whenever inter-zone travel dominates intra-zone travel."],"forward_implications":["When the Theorem 1 inequality holds, searching only over routes that visit each city as one contiguous block does not discard all optimal solutions.","Giving more travel days to cities with richer POI sets through dynamic decomposition directly targets the imbalance that the ablation study shows is important.","The reported superiority over CCIP, LSNSGA-II, MOPSO, and AONSGA-II on every one of the 18 cases suggests a generic advantage for decomposable multi-city itineraries.","The performance gap growing with the number of cities supports the claim that the curse of dimensionality is mitigated by city-level decomposition."],"supporting_citations":[{"why":"The cross-city itinerary planning cooperative coevolution framework that DGCC extends and the strongest baseline it must beat.","marker":"[17]"},{"why":"The original cooperative coevolution formulation on which the divide-and-conquer component structure rests.","marker":"[24]"},{"why":"The contribution-based resource allocation idea adapted into DGCC's optimization-potential measure.","marker":"[35]"},{"why":"The difficulty-and-contribution approach that informs how DGCC assesses component value and stagnation.","marker":"[37]"},{"why":"The per-day encoding with zero placeholders and the crossover and mutation operators used inside each NSGA-II component.","marker":"[39]"},{"why":"The NSGA-II multi-objective optimizer that evolves each component's subpopulation.","marker":"[40]"}],"fun_headline_variants":["City-wise splitting works when intercity edges are large","Weak decomposability makes large-scale itinerary planning tractable","New coevolution method tops four baselines on real-world trips","Guaranteed decomposability for multi-city route planning","Bigger trips, bigger edge: new solver scales past rivals"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the unverified assertion that every test case satisfies the Theorem 1 inequality—the largest within-city travel links are collectively no bigger than the smallest between-city link—and the extra assumption that the fixed city order used by DGCC contains an optimal route.","fun_headline_variants_meta":{"raw":{"variants":["City-wise splitting works when intercity edges are large","Weak decomposability makes large-scale itinerary planning tractable","New coevolution method tops four baselines on real-world trips","Guaranteed decomposability for multi-city route planning","Bigger trips, bigger edge: new solver scales past rivals"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000306,"raw_usage":{"total_tokens":1744,"prompt_tokens":928,"completion_tokens":816,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":544,"completion_tokens_details":{"reasoning_tokens":734}},"tokens_in":544,"tokens_out":816,"duration_ms":8050,"temperature":1.0,"reasoning_tokens":734,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T06:00:38.754581+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For each of the 18 test cases, compute every intra-city edge weight and every inter-city edge weight from the travel data and test whether the sum of the within-city maxima is at most the minimum between-city edge; any violation breaks the weak-decomposability guarantee. Then run an unrestricted multi-objective optimizer without the city-block constraint and compare its Pareto front with DGCC's; a strictly better unrestricted front would show that the fixed city-order encoding excludes optimal solutions.","supporting_citations":[{"cited_title":"Cooperative coevolution for cross-city itinerary planning,","cited_arxiv_id":null,"evidence_quote":"The cross-city itinerary planning cooperative coevolution framework that DGCC extends and the strongest baseline it must beat."},{"cited_title":"A cooperative coevolutionary approach to function optimization,","cited_arxiv_id":null,"evidence_quote":"The original cooperative coevolution formulation on which the divide-and-conquer component structure rests."},{"cited_title":"Smart use of computational resources based on contribution for cooperative co-evolutionary algo- rithms,","cited_arxiv_id":null,"evidence_quote":"The contribution-based resource allocation idea adapted into DGCC's optimization-potential measure."},{"cited_title":"Difficulty and contribution-based cooperative coevolution for large-scale optimization,","cited_arxiv_id":null,"evidence_quote":"The difficulty-and-contribution approach that informs how DGCC assesses component value and stagnation."},{"cited_title":"Au- tomatic planning of multiple itineraries: A niching genetic evolution approach,","cited_arxiv_id":null,"evidence_quote":"The per-day encoding with zero placeholders and the crossover and mutation operators used inside each NSGA-II component."}],"review_version":1}