Distilling Charging Plans, Not Just Actions, into Fast Electric Vehicle Routing Policies

Neural routing policies plan delivery routes for electric vehicle fleets in seconds. They are also short-sighted. They drive a vehicle toward customers until its battery is nearly empty, then make a costly detour to a charger they should have visited earlier. This proposal teaches a small routing network to write a short plan before each move, much as a language model writes intermediate reasoning before answering. The plan is a few tokens long: which charging station the vehicle will use next, roughly how much charge it will have on arrival, and how many customers it will serve before then. The training signal comes from offline solutions produced by a strong but slow optimizer, which are rewritten into these plan tokens. The student learns to imitate both the optimizer's moves and its plan. A plan-consistency objective forces the student's moves to actually follow the plan it wrote. An exact battery-feasibility mask at every step means no vehicle is ever sent toward a stranding.

The idea borrows three findings from reasoning research. First, intermediate tokens act as working memory. Second, a partially written-out reasoning trace rescues distillation on search problems where fully hidden reasoning fails. Third, students tend to ignore their own rationales unless trained not to. We apply these findings to a domain where the "reasoning" can be generated exactly by a solver rather than imagined by a language model. If the idea works, a compact policy closes much of the gap to the optimizer on electric vehicle routing with time windows. It also gives dispatchers a readable, editable charging plan.

Core Claim

On the Electric Vehicle Routing Problem with Time Windows (EVRPTW), a constructive neural policy should improve over two alternatives: imitating the optimizer's actions alone, and receiving cheap battery-reachability features as inputs. The improvement should come from training it to predict and then condition on the optimizer's plan-level charging commitments. The key contrast is between quantities that need a full solve to know and quantities that are cheap to compute. The next station the optimal route will use, and the charge carried into it, are only known after solving the remaining route. A one-step check such as "can I still reach some charger from here" is cheap, and an input feature or mask handles it fine. The scaffold is only worth having for the first kind. The experiments are built to tell the two apart.

Where This Sits

The application gap comes from Deep Reinforcement Learning for the Electric Vehicle Routing Problem With Time Windows. That paper trains an attention policy with hard feasibility masking on the Schneider et al. EVRPTW benchmark. It reports an 8.5% to 11.8% optimality gap against CPLEX on small instances, and it explicitly identifies myopic charging decisions as the cause of later detours. We keep its masking and its benchmark. We change the training signal.

The distillation machinery comes from neural routing work. Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation distills several distribution-specific teachers into a smaller student using a KL loss on action probabilities. MTL-KD distills reinforcement-learning teachers into a heavy-decoder student. It reaches a 6.65% average gap on CVRPLIB Set-X, against 19.6% for MVMoE and 29.6% for POMO. Both transfer only action distributions, and neither models battery state or charger insertion. Our student is trained the same way but adds a supervised plan channel.

The reasoning ideas come from three papers. Masked Distillation shows that fully hiding the reasoning trace drops Countdown accuracy to 41.7%, while keeping a 30% explicit suffix restores 86.2%, close to the teacher's 87.3%. This is the motivating evidence that a short visible scaffold matters on search-like tasks. Implicit Chain of Thought Reasoning via Knowledge Distillation constrains the design. Hidden reasoning failed in a 12-layer model and succeeded in a 24-layer one, which suggests a compact routing decoder cannot simply absorb lookahead into its weights. SCOTT supplies the counterfactual training objective. In SCOTT, students are trained on rationales perturbed to imply a different answer and are penalized unless they follow the rationale. We reuse that objective with perturbed charging plans in place of text rationales.

We deliberately do not use a language model as teacher. A Large Language Model-Enhanced Q-learning for Capacitated Vehicle Routing Problem with Time Windows uses chain-of-thought prompting to guide exploration. Its LLM-guided variant reaches only "over 81%" constraint satisfaction even with a three-tier validator, and it models no battery at all. Talking Trails does model e-bike battery state, but it reroutes with a fixed rule that sends the bike to a swap station below 30% charge. Both results suggest that energy arithmetic should come from an exact source. LLM4Teach shows that a tiny distilled student can outperform its large teacher once imitation is annealed. We use the same annealing schedule, with an optimizer as the teacher.

Research Program

Teacher traces. We generate tens of thousands of EVRPTW instances matching the Schneider customer, station, and time-window distributions. Each instance is solved offline. Small instances are solved exactly with CPLEX. Larger instances are solved with the Hybrid Memetic Search algorithm (HMA), which combines large-neighborhood search with population-based search and inserts partial-recharge stations. Each solved route is then decomposed step by step. At every step where the vehicle leaves a node, we record three things: the next charging station on the route, its arrival state of charge rounded to one of eight levels, and the number of customers remaining before that stop.

Student. The student builds the route one move at a time. At each step it reads a graph embedding of the instance plus the current vehicle state. Before choosing the next node, it first decodes the three scaffold tokens. These tokens are fed back as inputs to the action decoder. A plan is only re-emitted when the vehicle reaches a charger or the plan becomes infeasible, so the overhead is a handful of tokens per charging leg rather than per move. The action decoder also uses the feasibility mask from the deep reinforcement learning paper. In addition, it masks any move after which no charger or depot is reachable on remaining charge. That reachability test is computed exactly from the energy model in Optimal Route Planning for Electric Vehicles in Large Networks.

Training objective. The student minimizes

$$\mathcal{L} = \mathrm{KL}(\pi_T \,\|\, \pi_S) + \lambda\, \mathrm{CE}(\hat z, z_T) + \mu\, \mathcal{L}_{\mathrm{cf}}.$$

Here $\pi_T$ is the teacher's action distribution, taken as one-hot on the solver's move. $\pi_S$ is the student's action distribution. $\hat z$ and $z_T$ are the student's and the teacher's scaffold tokens, and $\mathrm{CE}$ is cross-entropy. $\mathcal{L}_{\mathrm{cf}}$ is the counterfactual term: we replace $z_T$ with a different feasible station plan and train the student to take the move that the perturbed plan implies. The weights $\lambda$ and $\mu$ balance the terms. After imitation, the student is fine-tuned with REINFORCE using a greedy-rollout baseline. During this phase the imitation weight is annealed as in LLM4Teach, so the student can surpass imperfect HMA plans.

Analysis. We measure four things. The first is how often the student's moves follow its own emitted plan. The second is whether editing a plan token changes behavior as intended, which is the property that makes the plan useful to a human dispatcher. The third is where in the route the gap to the optimizer is concentrated: before or after the first charging stop. The fourth is how often the reachability mask has to intervene.

Baselines

The naive reference point is a nearest-feasible-customer greedy heuristic under the same masking. It charges to full at the nearest station whenever the reachability test would otherwise fail. Every learned method must beat it, and it shows how much of any improvement comes from the mask rather than from learning.

The strongest learned competitor is the attention policy from Deep Reinforcement Learning for the Electric Vehicle Routing Problem With Time Windows. On small Schneider instances it reports an 8.5% to 11.8% optimality gap against CPLEX. On C100-S12-EV12 it takes about 6.7 minutes with stochastic sampling, while VNS/TS often finds no solution within two hours. It is the strongest competitor because it is the only published neural EVRPTW solver in the file and it shares our masking. We will retrain it on our instance generator with the same encoder size, number of training instances, sampling budget at test time, and hyperparameter search budget as the student. Beating it means a lower gap on the same Schneider instances at equal or lower wall-clock time.

The second strong competitor is action-only distillation from the same HMA and CPLEX traces. This is the AMDKD or MTL-KD recipe adapted to EVRPTW: identical architecture and data, but the $\lambda$ and $\mu$ terms are removed. This is the ablation that isolates the scaffold. The scaffold must win here, or the proposal reduces to "imitate a better teacher."

The third is a feature-augmented student. It receives cheap reachability features as inputs: the energy needed to reach the nearest station, the number of reachable stations, and the slack in time windows. It is trained with action-only distillation. This tests whether the plan tokens carry information beyond what is cheap to compute.

We also run a scaffold-without-counterfactual variant ($\mu = 0$) to measure the SCOTT-style term's effect on faithfulness. HMA itself is reported as an upper reference at matched and unmatched time budgets. On the jd and akb sets the file reports only that HMA beat Adapt-CMSA baselines, so no reported result was found on Lacuna for HMA's numerical gap. We will measure it ourselves.

Why not just…?

Why not just run the optimizer at dispatch time? For static instances with minutes to spare, HMA or CPLEX may well win, and we will report that honestly. The case for a fast policy rests on settings that need near-instant re-planning. The Schneider results show the pressure: VNS/TS often finds no feasible solution in two hours on 100 customers. We will report quality against time budget, so the reader can see the crossover point instead of taking our word for it.

Why not just feed lookahead features as inputs instead of predicting a plan? This is the most serious threat. If cheap reachability features close the gap, then the scaffold adds nothing. The feature-augmented baseline is designed to settle this. Our hypothesis is that features can encode only what is cheaply computable, while the plan encodes a commitment that only a full solve reveals. A further check makes this testable. Swapping in oracle plan tokens computed from the teacher should help far more than any feature set. If it does not, the plan is carrying no extra information.

Why not just imitate the teacher's actions, as AMDKD and MTL-KD do? Action imitation already transfers the teacher's charging choices indirectly. But the evidence from Masked Distillation and Implicit Chain of Thought suggests that small models given only final outputs fail to reconstruct the search behind them. The action-only ablation tests this directly. We expect its errors to cluster before the first charging stop, and the scaffold to reduce exactly those errors.

Why not use a language-model teacher with chain-of-thought, as in LLM-enhanced Q-learning? That work tops out at "over 81%" constraint satisfaction with external validation. Its reasoning also never handles battery limits. An exact solver gives correct energy arithmetic at lower cost. On 30 small instances we will run a prompted LLM teacher and report its plan-error rate as a sanity check.

Proposed Experiments

The primary benchmark is the Schneider et al. EVRPTW set, from 5 to 100 customers. We report the optimality gap against CPLEX on small instances, the gap against HMA on 100-customer instances, solve time, and detour distance attributable to charging. Generalization is tested on the akb set and the real Beijing jd set, which has up to 1,000 customers, 100 charging stations, and non-Euclidean distances. These sets add pickup-and-delivery and partial recharging. We extend the scaffold with a charge-amount token for this setting and use barycenter decomposition at the largest sizes. Faithfulness is measured by plan-following rate and by intervention success: whether the student changes its route as intended after a plan token is edited.

The decisive checks are three. The scaffold student must beat both action-only distillation and the feature-augmented student on the Schneider gap at matched compute. Its improvement must concentrate in the charging-related portion of the route. Its counterfactual edits must change behavior more than 90% of the time when $\mu > 0$ and noticeably less when $\mu = 0$. If the feature-augmented student matches the scaffold, we will conclude that the short-sightedness problem is a missing-input problem rather than a missing-reasoning problem, and report it as such.