acceptodds
Withdrawn from ICLR 2027

Continuation-Conditioned Credit for Composing Vehicle Routing Heuristics

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Automatic heuristic design typically ranks programs by the quality of their complete solutions. Yet a program that is weaker on its own may supply decisions that improve another policy. We study this distinction through continuation-conditioned credit and Cross-Family Residual Composition(CFRC). CFRC uses a genetic programming (GP) scaffold and searches over bounded donor deviations evaluated under the continuation actually deployed. In an independent eight-seed capacitated vehicle routing (CVRP) campaign, changing only the continuation reverses rankings in 35.24% of 2,957 supported action contrasts. Retrospective evaluations on two independent four-pool CVRP-30 cohorts compare composition with the per-instance best complete execution of all sixteen source candidates plus the scaffold. Under a common numeric execution environment, composition yields mean paired log gains of 1.758% (95% CI [0.215,3.123]) and 3.314% ([2.594,3.955]). On 144/480 and 255/480 instances, respectively, every composed deviation is supported only by donors worse than the scaffold as standalone policies, yet the composition improves it. Separately, prospective comparisons matching successful generation evaluations, selector capacity, and K=2 deployment find mixed-donor gains of 0.625% and 0.496% over GP-only donors. Deviation-budget and donor-count ablations show how additional inference computation improves solution quality. Together, these results demonstrate that action-level composition can improve on complete-program reuse from the same candidate pool on random CVRP, with transfer varying across distributions.

Primary area:
optimization
Keywords:
Automatic Heuristic Design, Program Composition, Credit Assignment, Combinatorial Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_t5QwOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes to use continuation dependence implemented by CFRC to support automated generation of heuristics via GP. The continuation-conditioned residual values measure the actions under a specified continuation.

Critical strengths

A simple method to support automated generation of GP heuristics. It presented rigorous work proving propositions. If demonstrated applicable and effective for other VRP variants, it could be adapted to improve GP heuristic generation.

Critical weaknesses

The paper proposes a new measure assisting heuristic generation based on existing techniques. It reports more analysis on the proposed new method, thus contributing to some observations rather than developing new algorithms or models.

The test CVRP instances are a relatively easy problem compared to other VRP variants with more realistic constraints. It's not clear if statistically significant results can be obtained also for the complex VRP variants, i.e. would similar observations and results be obtained for more difficult VRPs.

Questions for authors

See the above comments.

Reviewer_9f5oOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

Cross-Family Residual Composition (CFRC) is used to solve capacitated vehicle routing (CVRP) problems.

Critical strengths
  1. Many papers on Cross-Family Residual Composition (CFRC) are surveyed.
Critical weaknesses
  1. The paper’s novelty could be presented with greater clarity and emphasis. Stating the contributions and hypotheses more explicitly may further improve the manuscript.
  2. The details of the method are not given.
  3. The experimental results are not sufficient to validate the algorithm.
  4. The introduction and RELATED WORK section do not state the related study clearly. Although several papers are mentioned, the problem being addressed and the solution are not clearly stated.
Questions for authors
  1. The paper’s novelty could be presented with greater clarity and emphasis. Stating the contributions and hypotheses more explicitly may further improve the manuscript.
Reviewer_BxoKOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper notes that automatically generated routing programs are usually ranked by the length of the route they produce on their own. However, whether a proposed next customer is good depends on who finishes the remaining route, and swapping only the finisher can reverse the ranking. The authors build a mixer: fix one base program and follow it by default, but at certain points switch to the customer proposed by another program, at most twice per route. To decide whether to switch, they simulate the rest of the route for each candidate action (a rollout) and compare the total lengths, so a single instance needs many rollouts. Exact DP then picks the shortest combination among all routes with at most two switches. In the main experiments on random 30-customer CVRP instances, they compare it with "run several candidate programs separately and keep the best" and with GP-only donors, reporting positive mean gains and cases where the switched-to action is proposed by a program that is worse on its own.

Critical strengths

The reported reversal rate is substantial, and it appears across both proposal supports (EoH and MCTS-AHD), all frozen program pairs, and all tested instances, with exact replay plus feasibility and safety checks behind it, so "standalone ranking misses action value" is not a one-off artifact.

Critical weaknesses
  1. The method's gains come at the cost of much more computation, so the comparison is unfair, and the paper does not show that the gains come from the mechanism it claims. Specificcally:
  • At every decision point it evaluates several candidate actions by simulating the rest of the route, so one instance needs many rollouts and costs far more than running the base program once. Spending the same time on standard search enhancements over the original policy — destroy-and-repair, guided local search, a stronger 2-opt — or on multi-start sampling or beam search during construction would very likely yield larger gains, but the paper never tests this equal-cost alternative.
  • Meanwhile, the two arms differ only in where the programs come from, while program selection and search stay the same, and there is no control that selects programs by standalone performance. So the paper shows neither that the method is better at equal compute nor where its gain comes from.
  1. The writing is convoluted and overhyped. The paper invents many terms for a mechanism that is simple enough to describe in a short paragraph. Key limitations are buried in figure captions and appendices, while the main text states its conclusions confidently, so readers cannot tell what is new or how strong the conclusions are.
Questions for authors
  1. Please re-run best-of-17 under the same rollout budget (or the same wall-clock time, or the same number of suffix evaluations). Does the reported advantage over best-of-17 survive? And at K=1, is the mixer still better than GP-only donors?

  2. Please add a control that selects the 8 donors by average standalone cost and compare it with the current selection rule on the same instances. Only then can one tell whether the continuation-based scoring itself contributes.

  3. The weak-donor evidence is retrospective. Can you freeze instances in advance and run a prospective test: on instances where all donors are worse standalone, does the mixer still reliably help?

  4. Which operating point is intended? K=1 is much cheaper, while K=2 buys more quality at a much higher cost. Why is the main experiment run at K=2? Is the paper meant to be a usable solver, or a measurement of whether composition has value?

  5. The named-instance and clustered-distribution transfer checks both fail, and at 100 customers a single instance takes tens of minutes. For which distribution or scale is this method worth using? JSSP is used only as a diagnostic with no systematic results. Is the mechanism general?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.