Amazon-scale last-mile, two ways
Last-mile delivery is capacitated vehicle routing at scale. Amazon’s 2021 Last Mile Routing Research Challenge released real operational routes — a glimpse of the size of the problem. Their data is non-commercial, so we cite it for scale and run the reproducible solve on the public CVRPLIB benchmark (Uchoa et al., 2017), whose best-known solution is the number to beat.
The MILP proves the optimum — until it can’t
On CVRPLIB’s X-n101-k25 (100 customers, best-known 27,591), the exact AMPL model proves the optimum on the first few stops in seconds — and then the branch-and-bound tree explodes. Beyond twelve customers it can no longer prove optimality inside the time budget. This is not a solver weakness; it is the combinatorics.
| customers | exact distance | proven optimal? | solve time |
|---|---|---|---|
| 8 | 3,546 | yes | 0.5s |
| 10 | 4,249 | yes | 3.4s |
| 12 | 4,830 | yes | 17.7s |
| 14 | 5,429 | no — hit the time limit | 30s |
On the 12-customer slice the two engines agree exactly: the exact optimum is 4,830, and BIS’s own HGS finds it in 0.12s versus 17.7s for the proof — the same answer, ~148× faster.
The tailored engine reaches the best-known solution
Where the exact model stalls at a dozen stops, the Hybrid Genetic Search keeps going. BIS’s in-browser engine still solves a 50-customer instance in 2.4s; and PyVRP — the reference open-source HGS — reproduces the full 100-customer best-known solution of 27,591 exactly (0.00% gap) in 8s, using 26 vehicles. That is the tradeoff in one line: exact gives a certificate but not scale; the metaheuristic gives best-known at scale, in seconds.
Routing at your scale?
We build the engine your instance size actually needs — and prove it on your data.