Inspiration
Route optimizers promise double-digit savings, and drivers ignore them. On Amazon's held-out routes a shortest-path plan is 11.3% shorter than what the driver drove, but it drives back into a zone it has already finished 15.7 times per route, where drivers do it 1.4 times. A plan like that asks a driver to throw away how they know their area, so the saving on paper rarely reaches the road.
Mail carriers solved this long ago. Every morning a letter carrier sorts the day's mail into a case of pigeonholes, one slot per stop, in the order they walk, and the US Postal Service records that order for every carrier route as its Line of Travel. Amazon drivers have a line of travel too. Nobody wrote it down, so we learned it.
What it does
Line of Travel learns the order drivers work their zones from 6,112 real Amazon routes, then re-sequences a route to remove the detours without breaking that order. On 3,052 held-out routes the model never saw, at the default setting:
- 5.9% less drive time than the driver's own route (95% bootstrap interval 5.8 to 6.1%), 592 driver-hours in all
- 0.01 zone re-entries per route, against 1.4 for drivers and 15.7 for the shortest path
- late stops down from 469 to 1, of 28,354 stops with a delivery window
For a station of 100 vans that is about 19 driver-hours a day.
The website runs the solver in your browser. Load a real route and watch it re-sequence; compare the driver's order, the shortest path and Line of Travel on the same stops; see the route laid out as a carrier's case, one slot per zone, with the changed slots marked. A dispatch desk lets you pick a real route from five cities, turn a "trust the driver" dial from pure shortest path to the driver's habits, and test a van leaving 45 minutes late or 8 same-day orders added.
How we built it
- Data: Amazon Last Mile Routing Research Challenge 2021 (public, CC BY-NC 4.0): 9,164 routes, 1,337,758 stops, Amazon's travel-time matrices and the order each driver actually delivered in.
- Habit model: a LightGBM ranker predicts the driver's next zone 68% of the time from about 21 candidates. Picking the nearest zone gets 35%.
- Cost: inside a zone an edge costs its travel time. Leaving a zone adds a fixed charge and a habit cost that is high for moves drivers rarely make, and every second late costs 20:
$$c_{ij} = t_{ij} + \mathbf{1}[z_i \ne z_j]\,\bigl(300 + 30 \cdot (-\log p(z_j \mid z_i))\bigr)$$
- Engine: iterated local search (asymmetric 2-opt with O(1) deltas, or-opt, whole-zone moves, double-bridge kicks cut at zone boundaries), with lateness counted when a round is accepted and a time-window repair that moves whole zones first. Plain JavaScript with no dependencies: the same file runs the benchmark in Node (0.3 s per route) and the demo in a Web Worker in your browser.
- Validation: held-out routes only; Amazon's official route score (our port is tested equal to the original); bootstrap intervals; an OR-Tools comparison; a scenario analysis; station-history features that only count other days.
- Site and film: Vite and MapLibre GL on OpenFreeMap tiles, deployed with GitHub Pages. The demo film is built in Remotion, narrated with Deepgram Aura-2, and its footage is a Playwright recording of the live site.
Challenges we ran into
Our first engine lost to the driver on 18% of routes. Instead of tuning around it, we diagnosed it route by route: the search was breaking zones apart to fix late deliveries at the very end. Moving whole zones and counting lateness during the search fixed it, and the default's saving went from 3.3% to 5.9%.
Making it fast enough for a phone was the other one. Amazon's matrices are asymmetric, so reversing a segment changes its cost; prefix sums over both directions keep each 2-opt move O(1), and a 154-stop route solves in under half a second in the browser.
Accomplishments that we're proud of
- A saving a driver could accept: real minutes saved with zones kept whole, measured on routes the model never saw. It drives longer than the driver on only 2.4% of routes.
- A fast engine: on 200 held-out routes our travel-time-only tour is 2.26% shorter than Google OR-Tools given 5 s per route, and as good or better on 96% of them, in about 0.3 s.
- No server: the solver runs in the browser, so the demo works on a phone.
- One source of numbers: the website, README, report, deck and this page are all generated from the same benchmark output.
What we learned
The constraint that matters in last-mile routing is trust, not distance. Measuring closeness to the driver with Amazon's own route score turned that trade-off into a dial a dispatcher can set, instead of an argument. And the routes we lost on taught us more than the averages did.
What's next for Line of Travel
A pilot on one station's live routes with the dial set per driver, GPS traces to confirm that planned savings show up on the road, and, with driver IDs, habits learned per driver instead of per station. Travel times here are Amazon's planned estimates, not GPS, so every saving above is measured in Amazon's own matrix.