Capacity-Aware Completion Bounds for Exact Fixed-Permutation Electric Vehicle Routing Decoding

We study exact decoding of a fixed customer permutation in electric vehicle routing under the recently introduced Fixed-Permutation Splitting and Charging Problem (FPSCP) and its exact forward-labeling decoder FP-FLA. The contribution is deliberately narrow. Completion bounds and lower-bound pruning are established techniques in labeling algorithms; this work develops a state-compatible cargo-capacity completion bound specialized to FPSCP/FP-FLA. The bound preserves the remaining customer order and residual cargo capacity while relaxing battery feasibility, and it depends only on the FP-FLA stage, current cargo resource, and precomputed permutation data. On 240 public benchmark/permutation cases, the capacity-aware decoder matched the unbounded source-matched FP-FLA reference objective in all cases and achieved a median preprocessing-inclusive speedup of 14.41x (bootstrap 95% CI: 12.62–16.00x), with a median 73.2% reduction in charging/reset-node pair enumeration. A further 996 feasible synthetic stress cases produced no objective mismatch. Separately, a direct-upstream compatibility gate against the pinned public FPSCP implementation produced 340/340 objective matches across 17 public EVRP instances, with 34/34 retained clean-room checks. This direct-upstream gate is compatibility evidence and not an independent MIP/CP certificate, and its timing measurements are not pooled with the primary capacity-bound benchmark. This record is a preprint and has not been peer reviewed.