The problem
An electric delivery van leaves the depot at 08:00 with eight parcels and a battery that won’t quite last the day. Somewhere it has to stop for 35 minutes to charge. The question every morning is the same: in what order do I drop the parcels, and where do I charge?
Most route planners answer the first half and leave the second to the driver: take the shortest loop, charge when the gauge gets low. EV-aware planners do better. They plan the charging stop up front, but they usually assume a flat energy rate: so many kWh per km, whatever the van is carrying.
A loaded van doesn’t drive like an empty one. Real-world tests put the range loss of a fully loaded electric van at roughly 11–31 percentage points. In this demo a full van drains up to 30% faster than an empty one, and every drop makes it a little lighter.
Why it’s hard
- The cheapest day is not the shortest route. Driver time is paid, so a 35-minute charging stop costs about as much as 9 km of driving. A slightly longer loop that passes a charger at the right moment, or needs no charge at all, can win.
- Weight makes the energy depend on the order. The same loop driven clockwise or anticlockwise has the same length, but not the same energy. Drop the heavy parcels early and you carry less weight for the rest of the day.
- The flat-rate planner gets surprised. It plans with the wrong drain, finds out on the road that the plan doesn’t reach the next charger, and has to make an unplanned stop. Often a detour to a charger it never meant to use.
The approach
The day is solved exactly in the browser, with no solver library.
The key observation: the van’s load depends only on which parcels are already delivered, not on the order they were delivered in. So the energy cost of the next drive is fixed by the state (delivered set, current stop), which is the state of a classic Held–Karp dynamic program over subsets.
- Labels. Each state keeps a small set of labels: cost so far, and energy used since the last charge (plus the clock, when delivery windows are on). A label is dropped when another label in the same state is no worse on every field.
- Charging. Every move between two stops is either direct or goes through one of the three chargers (depot plus two public ones). A charge is a full refill and costs fixed time. Chargers that can’t help a given move are skipped.
- Streets. The van drives a real street network, river and bridges included. Between every pair of places the solver considers every street path that is Pareto-optimal on distance and energy, so the player can’t beat it with a flatter detour.
- Objective. Distance cost plus driver time (plus a penalty per missed delivery window).
With 8 stops one solve takes about 3 ms; with 12 stops about 0.1 s, or 0.2 s with delivery windows. It runs in a Web Worker, and “Run 100 days” spreads the days over a pool of workers. It’s plain TypeScript, with no WASM needed.
It is checked against a brute-force solver on 40 small worlds and against an earlier Python prototype on 55 more. Costs agree to 10-6.
Three planners
To separate the two effects, every day is planned three ways and then driven under the true energy model, with the same driver rule: follow the plan while it still works, otherwise charge at the nearest reachable charger.
| Planner | Knows about the battery | Knows about weight |
|---|---|---|
| Shortest route | no: charges when needed | no |
| Flat-rate planner | yes | no |
| Weight-aware planner | yes | yes |
Shortest → flat-rate measures what battery awareness is worth. Flat-rate → weight-aware measures what weight is worth.
Results
300 random days, 8 stops, a full van drains 30% faster than an empty one.
- 7.6%
- cheaper on a median day than the shortest route with charging when needed. On one day in ten, 14.4% or more.
- 62%
- of days the weight-aware plan saves more than 5%.
- 48%
- of days the flat-rate planner is forced into an unplanned charge.
| Days flat-rate costs more than weight-aware | 44%, by 11% on a median such day |
| Days weight-aware makes fewer charges than flat-rate | 14% |
With a milder load effect (+15%) the flat-rate planner is still surprised on 29% of days. Hills barely move any of these numbers.
The honest finding is the last row.
On 4 days in 5 both planners stop exactly once; the weight-aware one knows where it will actually run low and plans the stop there. The flat-rate one finds out on the road.
One subtlety worth stating: distance and time don’t depend on weight, so a loop and its mirror image often cost exactly the same on paper. A flat-rate planner has no reason to prefer either direction, and sometimes it picks the one that carries the heavy parcels furthest. Part of its surprise rate is that coin flip. That is realistic: it’s exactly the information it lacks.
Limitations
This is a simplified world, built to show one effect clearly:
- one van, one depot, two public chargers;
- constant speed, no traffic, no randomness during the day: energy use is known exactly;
- every charge takes 35 minutes and fills the battery (real chargers slow down as the battery fills);
- energy per km is linear in the load; hills add a fixed cost per metre climbed, with 60% back downhill;
- the morning battery is drawn at random between 70% and 102% of what the shortest loop needs.
Real fleets add uncertain consumption (which turns the reserve into a real decision), several vans, pickups that add weight back, and charger prices and queues. The exact DP grows exponentially with the number of stops (about 6× per two extra stops here); beyond that it becomes a heuristic or column-generation problem.
Further reading
- Goeke & Schneider (2015), Routing a mixed fleet of electric and conventional vehicles, EJOR. Load-dependent energy consumption in vehicle routing.
- Schneider, Stenger & Goeke (2014), The electric vehicle-routing problem with time windows and recharging stations, Transportation Science.