Reliability-Guided Erasure and Re-Decoding for Heterogeneous-Fleet Routing

Neural routing solvers build a delivery plan one decision at a time: pick a vehicle, pick its next customer, repeat. When the fleet is mixed (trucks with different capacities, speeds, or banned zones), many of these decisions are effectively coin flips. The solver commits to each one anyway and never revisits it. Communication engineers met the same problem in fast error-correcting decoders, and their fix was cheap. Keep the fast hard decisions, but also keep a per-decision confidence score. Then erase only the least-confident decisions and re-decode them. We propose carrying that fix over to heterogeneous vehicle routing. The constructive neural solver records how confident it was about each customer-to-vehicle assignment. Afterwards, a few repair trials erase the least reliable assignments, in growing numbers, and re-decode them, with the re-decoding softly anchored to the original plan.

The bet is specific and falsifiable. The solver's own confidence margins should predict which assignments are wrong ("miscorrections") better than the random or spatially chosen removals that classical ruin-and-recreate heuristics use. Erasing a jointly unreliable group of assignments also performs a multi-customer move, and that kind of move escapes capacity-locked plans that single swaps cannot fix. If the margins carry no signal, the idea fails at the first experiment, and we say so up front.

Core Claim

In product-code decoding, a component decoder can "miscorrect": it outputs a valid but wrong codeword, and nothing inside the decoder flags the error. Two papers by the same group fix this without abandoning cheap binary messages. Iterative Bounded Distance Decoding of Product Codes with Scaled Reliability combines each hard decision with the stored channel confidence before taking its sign. On Low-Complexity Decoding of Product Codes for High-Throughput Fiber-Optic Systems goes further with generalized-minimum-distance decoding. It runs only $t+1$ trials, each erasing more of the least reliable bits, and still recovers over half of the gap to full soft decoding, a 0.60 dB gain over plain iterative bounded-distance decoding at BER $10^{-5}$. These papers supply our method.

Our claim is that a heterogeneous-fleet routing decoder is in the same position. Its hard commitments discard a confidence signal that is cheap to keep. A few erasure-and-redecode trials driven by that signal should close a meaningful part of the gap to strong heuristics, at a small multiple of single-pass inference cost.

The fleet heterogeneity is what makes this a sharper bet than for homogeneous routing. With identical vehicles, a "wrong vehicle" decision does not exist, because the vehicles are interchangeable. With mixed fleets, a whole class of errors appears: a small or slow vehicle committed to a distant client cluster. The vehicle-selection head of a dual-decoder solver (Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem) produces exactly the kind of soft score that could flag these errors.

Research Program

We first record a reliability score for each client $c$ during a normal constructive rollout. The score is the margin between the chosen and runner-up vehicle at the step where $c$ was assigned:

$$r_c = \log p_\theta(v^\star_c \mid s_c) - \max_{v \neq v^\star_c} \log p_\theta(v \mid s_c).$$

Here $p_\theta$ is the solver's vehicle-selection distribution, $s_c$ is the partial-solution state when $c$ was inserted, and $v^\star_c$ is the vehicle chosen. This is the routing analogue of a bit's absolute log-likelihood ratio. We will also test a node-level margin, from the client-selection head, as an alternative.

A repair trial $k$ erases the $m_k$ clients with the smallest $r_c$. The schedule $m_1 < \dots < m_T$ mirrors the growing erasure sets of generalized-minimum-distance decoding, and $T$ is small (3 to 5). The trial then re-inserts those clients with the same network, conditioned on the frozen remainder of the plan. Re-insertion uses anchored logits, the analogue of scaled-reliability combining:

$$\tilde z_{c,v} = z_{c,v} + w_k \,\mathbb{1}[v = v^\star_c].$$

In this equation, $z_{c,v}$ is the solver's re-decoding logit for assigning client $c$ to vehicle $v$, and $w_k \ge 0$ is a per-trial weight that biases the solver toward the original assignment. A large $w_k$ means "trust the first pass"; $w_k = 0$ means free re-decoding. As in the coding papers, the final output is the best of the original plan and the $T$ trial outputs.

Two refinements test whether the analogy goes deeper than surface resemblance. The first replaces the static $w_k$ with a weight derived from an estimated miscorrection rate. This is the idea behind Bayesian reliability combining in the coding literature, and it directly targets the open problem that scaled-reliability weights are hand-tuned. The second compares margin-based erasure with a small learned miscorrection classifier, trained to predict whether an assignment disagrees with the heuristic solution. This is a cheap analogue of the Transformer rollback detector in Iterative Neural Rollback Chase-Pyndiah Decoding. That paper showed that suppressing predicted destructive updates beats doubling the decoder's search breadth: its $p=6$ decoder with rollback beat conventional $p=7$. Its open limitation is detector cost, so we test whether a margin, which costs nothing extra, captures most of the benefit.

The base solvers are USPR (USPR: Learning a Unified Solver for Profiled Routing) for profiled routing and the dual-decoder model for the heterogeneous capacitated vehicle routing problem (HCVRP), the variant where vehicles differ in capacity and speed. We use USPR because it is small (1.5M parameters) and its static score reshaping, which subtracts $\log(\text{dist}+\text{pref})$ from the attention scores, is precisely the kind of fixed prior that has no way to revise a commitment. We will re-implement both solvers, or use author code if available; the file lists no repository for either. The multi-task routing codebases RoyalSkye/Routing-MVMoE and LOGO-CUHKSZ/MTL-COP provide POMO-style infrastructure for the homogeneous control experiments.

The local-minima direction enters as an analysis lens, not as a method. Plans produced by constructive decoders often sit where every single client relocation or swap is infeasible or worsening, because heterogeneous capacities lock clients in place. This is the routing counterpart of the stall patterns described in Improved decoding and error floor analysis of staircase codes. We will measure how often outputs are 1-move local optima, and whether reliability erasure escapes them more often than random erasure of the same size. Continuation-style smoothing (A Theoretical Analysis of Optimization by Gaussian Continuation) and decomposition (Recursive Decomposition for Nonconvex Optimization - IJCAI-15 Distinguished Paper) motivate this framing. We do not use either: continuation is analysed for continuous landscapes and can lose the minimum path at bifurcations, and neither method addresses discrete masked decoding.

Baselines

The do-nothing reference is the base solver's single greedy rollout, plus its standard multi-sample or augmentation inference. For profiled routing the strongest reported neural numbers are as follows. USPR reports a 4.02% gap relative to HGS-PyVRP on standard PVRP benchmarks and 14.15% on the 1,000-node out-of-distribution test, versus 23.44% for the previous best neural solver (USPR: Learning a Unified Solver for Profiled Routing). CAMP reports 5.02% on the soft-preference variant and 3.31% on the hard-constraint zone variant (CAMP: Collaborative Attention Model with Profiles for Vehicle Routing Problems). For the V3/V5 HCVRP benchmarks, no reported result was found on Lacuna for numerical gaps; the dual-decoder paper reports only competitive quality and a speed-up from minutes to seconds. Beating the do-nothing reference means a lower gap to HGS-PyVRP at matched wall-clock time, not matched sample count.

The strongest single competitor is more sampling. The base solver draws as many extra rollouts or augmentations as fit in the time our $T$ repair trials take, on the same GPU, with the same trained weights, and keeps the best rollout. If equal-time sampling matches our repair, the proposal has no value.

The second competitor is classical ruin-and-recreate and hybrid genetic search: SISR and HGS-PyVRP polishing applied to the neural output under the same time limit. This is the right comparison because ruin-and-recreate is structurally what we do; only the choice of what to ruin differs.

The ablation that isolates our key ingredient keeps everything fixed (same network, same anchored re-decoding, same erasure sizes $m_k$) and changes only the erasure rule. The rules are random clients, SISR-style spatial strings, highest-cost-detour clients, and lowest-reliability clients. We also ablate the anchoring weight ($w_k = 0$ versus tuned) and the Bayesian versus static weight. All tuning of $m_k$ and $w_k$ uses a held-out validation split, with the same search budget given to the random and spatial variants. Beating the ablation means reliability erasure reduces the gap significantly more than the best non-reliability rule, on paired instances.

Why not just…?

Why not just draw more samples from the policy? This is the most serious threat. POMO-style multi-start rollouts do help in distribution. However, Rethinking Light Decoder-based Solvers for Vehicle Routing Problems reports POMO collapsing to a 110.6% gap on CVRP1000, which suggests independent restarts repeat the same early mistakes. Sampling also re-draws every decision, including the confident ones, while erasure spends its budget only where the solver was unsure. The equal-wall-clock comparison above settles the question. If sampling wins at small sizes but loses at 1,000 nodes or under fleet-mix shift, that is still a useful and honest result.

Why not just polish with SISR, LKH3 or HGS? Given minutes of compute, these heuristics will win; we do not claim otherwise. The relevant regime is sub-second to few-second inference, where the dual-decoder paper reports SISR needing several minutes on 120 customers and CAMP reports OR-Tools needing up to 15 minutes for a worse 10.68% gap. If SISR with a 2-second limit beats our method, the proposal loses on practicality. The time-matched comparison decides this directly.

Why not just use random or spatial ruin with the same neural repair? If the solver's margins are uninformative or overconfident, reliability erasure collapses to random erasure. The coding precedent depends on channel confidence being an independent and well-calibrated signal, and a policy's own softmax may be neither. This is why the first experiment measures predictive power before any repair is built. The learned-classifier variant is the fallback if margins fail but disagreement with HGS is still learnable.

Why not just give the encoder better features, such as an LP relaxation assignment? That could reduce errors at the source. It is complementary rather than competing: better features lower the error rate, while erasure fixes the errors that remain. We will include a feature-augmented base solver as a secondary baseline only if the core result holds.

Proposed Experiments

The decisive first check is diagnostic. On the PVRP synthetic benchmark (Random, Angle, Cluster and Zone profile distributions, 60 to 100 clients, 3 to 7 vehicles) and on V3/V5 HCVRP, we label each assignment as "miscorrected" if HGS-PyVRP places that client on a different vehicle type. We then report the area under the ROC curve of $-r_c$ for predicting this label, separately for vehicle-level and node-level margins. We pre-register a stop rule: an area below 0.65 ends the margin-based line and shifts to the learned classifier. We also expect, and will test, that vehicle-level margins are more predictive under strong heterogeneity, such as large capacity and speed spreads or the Zone profiles, than in homogeneous CVRPLib controls. That difference would confirm that heterogeneity is what makes the signal useful.

The main experiment reports the gap to HGS-PyVRP against wall-clock time for every baseline and ablation above. It covers in-distribution PVRP, the 1,000-node PVRP stress test, held-out fleet mixes for HCVRP (both Min-Sum distance and Min-Max makespan), and CVRPLib as a homogeneous control. A secondary analysis measures the fraction of outputs that are 1-move local optima before and after repair, and the escape rate per erasure rule, to test the stall-pattern interpretation.

The result we would count as success has three parts. Reliability erasure beats equal-time sampling and the best non-reliability erasure rule on heterogeneous benchmarks. The advantage grows with fleet heterogeneity and instance size. The advantage largely vanishes on homogeneous CVRP. Any other pattern means the coding analogy does not transfer, and we will report it as a negative result.