Continuation-Conditioned Credit for Composing Vehicle Routing Heuristics

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.