last-mile-delivery

How it is built

Architecture overview

A last-mile delivery system turns a day's parcels into one ordered route per driver and then keeps those routes true while the day goes wrong. It has a planning side that runs in batches (geocode the addresses, group the stops into areas, assign areas to drivers, optimise each route against travel times and delivery windows) and an execution side that runs in real time (the driver's phone reports scans and positions, the dashboard shows progress, the plan is repaired when a stop fails). Everything the optimiser decides rests on two estimates: how long it takes to drive between two points, and how long the driver stands at a stop. The idea that makes it work is to keep those estimates and the search separate: a routing engine answers travel-time queries in microseconds, a learned model supplies service times, and a metaheuristic spends its time on thousands of cheap evaluations of candidate routes rather than on any exact solve. Public data on real routes is rare: the data set of the Amazon Last Mile Routing Research Challenge, 9,184 historical routes from five US metropolitan areas, was described by its authors as the first large public set built from real operational routing data (Merchán et al. 2024).

Parts:

• Address resolution — turns free-text addresses into coordinates and cells — address-geocoding (no page yet), Geospatial cell index, Geodesic distance
• Road network engine — travel times and distances between any two points, as single queries and as matrices — Contraction hierarchies, Dijkstra's algorithm, A* search
• Zoning and assignment — splits the stops into compact areas and gives each area to a driver — k-means clustering, Assignment problem
• Route optimiser — orders the stops of each route under time windows and capacity — Time-window feasibility, local-search-2opt-or-opt (no page yet), Large neighbourhood search, Mixed-integer programming
• Prediction — service time per stop, travel-time corrections, parcel volume per day — Gradient-boosted decision trees, Time-series forecasting
• Position cleaning — snaps noisy driver GPS to roads for tracking and for learning real travel times — map-matching-hmm (no page yet), Convolutional codes and the Viterbi decoder
• Event backbone and live view — records every scan and state change once, pushes it to screens — Event sourcing, Idempotency keys, WebSockets
• Operations and verification — keeps planning and live tracking running, authenticated, recoverable and tested — Process supervision, Graceful draining, Mutual TLS, Primary-backup replication, Point-in-time recovery, hdr-histogram (no page yet), Coverage-guided fuzzing, Deterministic simulation testing

 orders ─► geocode ─► cell index ─► k-means zones ─► Hungarian: zone→driver ─► route optimiser ─► manifests
              │            │                                   ▲                    ▲   │ (LNS, windows)
              ▼            ▼                                   │                    │   ▼
          coordinates   neighbours            travel-time matrix ◄─ routing engine (CH)    phones
                                                               ▲                    ▲        │ scans, GPS
                          GBDT: service time ──────────────────┘   forecast: volume │        ▼
                                                                                      │   event log ─► map-matching ─► live view
                                                 re-plan trigger ◄────────────────────┴───── (event sourcing, WebSocket)

How the parts fit together

Address resolution

An address is text; the optimiser needs a point. address-geocoding (no page yet) resolves the text to a coordinate and a confidence, and the confidence matters downstream: a rooftop match can be driven to, a street centroid cannot. Once a stop is a point, a cell index (H3, S2 or geohash) gives every stop an integer cell id, so "which stops are near this one" is a range scan in an ordinary sorted store and parcels bunch into cells without a spatial database. Geodesic distance (haversine for speed, Karney for accuracy) is the cheap pre-filter: it is a lower bound on road distance, so pairs that are too far apart are never sent to the routing engine at all. Contract: every stop leaves this part with lat, lon, cell id, match quality.

Road network engine

The optimiser asks a travel-time question millions of times per plan, so a fresh Dijkstra per question is far too slow. Contraction hierarchies pay minutes of preprocessing on the road graph once and then answer a query with two small searches that only climb the node ranking. They are the right choice for the big many-to-many matrices a planner needs; OSRM, which implements both CH and Multi-Level Dijkstra, recommends MLD by default and keeps CH for very large distance matrices (OSRM README). The price is that the graph is static: a CH is built for one weighting, so live traffic means rebuilding it, or choosing an algorithm that can re-weight cheaply (which is one reason OSRM's MLD is its default). A* search is the fallback for one-off queries and for cases where the cost changes per query. Contract: matrix(points) -> N×N seconds + metres, with road-snapped points and a flag for unreachable pairs (one-way streets, pedestrian zones).

Zoning and assignment

Optimising one route over every stop in a city is too big and produces routes that cross each other. The common structure is cluster first, route second: k-means on stop coordinates (in a projected metric space, not raw degrees) makes compact zones sized to a driver's day, with cell ids as a fast way to seed and rebalance them. Then the zones must go to drivers: each pairing has a known cost (the driver's depot, vehicle size, how familiar the driver is with the area), and the assignment problem gives the optimal one-to-one matching in O(n³), which is trivial at the size of a depot. Contract: a zone is a list of stop ids with a total demand and an expected duration; a driver gets at most one zone per route.

Route optimiser

Inside a zone the problem is a vehicle routing problem with time windows: order the stops to minimise travel while every window and the vehicle capacity hold. Exact solving with mixed-integer programming works for tens of stops; for real routes a metaheuristic wins. A construction heuristic gives a first route, local-search-2opt-or-opt (no page yet) polishes it with small moves, and large neighbourhood search removes a chunk of stops and re-inserts them, learning which removal and insertion operators pay off; Ropke and Pisinger's adaptive version improved the best known solution on more than half of 350-plus benchmark instances of up to 500 requests (Ropke & Pisinger 2006). Hybrid genetic search is the strong alternative for plain capacitated routing and has an open-source implementation (Vidal 2022).

What makes millions of move evaluations affordable is time-window feasibility: keeping earliest and latest start and slack per route segment turns "does this insertion keep every window?" into an O(1) check instead of a walk down the route. Contract with the engine: the optimiser only ever reads the travel-time matrix and a service-time function; it never calls the road graph during search.

Prediction

Two estimates change the plan more than any algorithm choice. Service time (parking, walking to the door, handing over the parcel) varies by building type, floor, parcel size and time of day, and is a tabular regression problem: gradient-boosted trees over those features are the strong default, trained on the actual dwell times the event log produces. Volume per depot and day is a forecast: a seasonal baseline first, a richer model only if a rolling-origin backtest shows it beats the baseline. The forecast sizes the fleet the night before; the service-time model feeds the optimiser at planning time.

Position cleaning

Driver GPS is noisy and sampled sparsely to save battery. To measure real travel times and show the driver on the right street, map-matching-hmm (no page yet) uses a hidden Markov model: each road segment near a fix is a candidate state, emission probability falls with the distance between the fix and the road, transition probability prefers a route distance close to the straight-line distance between consecutive fixes, and the Viterbi decoder (Convolutional codes and the Viterbi decoder explains the dynamic programme) picks the most likely road sequence (Newson & Krumm 2009). Valhalla ships this as its Meili library. The matched traces both drive the live map and become the ground truth that corrects the routing engine's speeds.

Event backbone and live view

The phone is the system's weakest link: it goes offline in a stairwell and retries when the signal returns. Every scan, arrival and failed attempt is therefore an event appended to a log (Event sourcing), with the parcel's state derived by replay, so a delivery history can be rebuilt and audited. Because a retried upload may arrive twice, every event carries an idempotency key and the server stores the first result for it. The dashboard and the driver app subscribe to changes over WebSockets; position streams are the high-volume part and are sampled for display. Contract: events are immutable, keyed by (parcel, event id), ordered per parcel.

Operations and verification

Process supervision restarts the batch planners, the route optimiser workers and the event consumers under a delay and burst limit, so a planning run that dies on one odd stop restarts without tying up the morning cut-off. Graceful draining lets an optimiser worker finish the route it is improving, and a live-view gateway tell dashboards and driver phones to reconnect elsewhere, so a deploy during the delivery day does not drop scans. Mutual TLS authenticates the calls between the planner, the road engine, the event backbone and the driver-app gateway, so only the planner can publish routes and only the gateway can append scans. Primary-backup replication keeps a standby for the route and event store that the day's execution depends on. Point-in-time recovery rebuilds routes and parcel states to the instant before a bad plan publication or a faulty bulk status update, then replays the scans that came after. hdr-histogram (no page yet) records latency percentiles of the travel-time matrix call and of re-optimisation after a delay, because a mid-day re-plan must finish while the driver is still deciding. Coverage-guided fuzzing mutates manifest files, address strings and scan payloads that arrive from shippers and driver phones, keeping inputs that reach new code. Deterministic simulation testing replays a day of orders, delays and failed deliveries under a seeded clock, so a parcel on two routes or a lost scan replays from its seed.

Data and control flow

Planning run (night before and early morning):

1. Orders arrive; each address is geocoded and given a cell id (reads address text, writes coordinates and quality).
2. Orders with a low match quality go to a correction queue; the rest are grouped into zones by k-means, with sizes from the volume forecast and the service-time model.
3. The Hungarian step assigns zones to the drivers who report for work.
4. For each route the routing engine returns the travel-time matrix (one many-to-many CH query).
5. The optimiser runs for a fixed time budget, accepting a move only if the time-window check passes; the best route becomes the driver's manifest. Time goes to the matrix and to the search; the geocoding and assignment steps are minor.

Delivery and re-plan (during the day):

1. The phone scans a parcel at the door and uploads the event with an idempotency key.
2. The server appends the event, updates the projection and pushes it to the dashboard and the customer's tracking page.
3. A failed attempt or a running delay raises a re-plan trigger for that route only.
4. The optimiser re-runs on the remaining stops with the current position as the start (map-matched) and a short budget; the new order replaces the manifest on the phone.
5. At the end of the day the stored dwell times and matched traces feed the next training run of the service-time model.

Scaling

In the order they bite:

1. Matrix computation grows with the square of the stops in a route. Levers: geodesic pre-filtering, smaller zones (more, smaller problems parallelise trivially), CH for large matrices, caching matrices across re-plans.
2. Search time per route is bounded by the O(1) feasibility check and the move evaluator. Levers: more independent routes in parallel (they share nothing), a time budget per route, warm starts from yesterday's solution on the same zone.
3. Service-time and travel-time quality limit the real result more than search does. Levers: better features, per-driver effects, correcting speeds from map-matched traces.
4. Event volume from live positions. Levers: sample for display, partition the log by route, keep the live view on a cache.
5. Geocoding errors are mostly a data problem: the lever is a correction loop where a driver's confirmed stop location overrides the geocoder next time.

Failure modes

Real implementations

No operator publishes its production stack end to end; the open pieces above are the building blocks, and the Amazon challenge data set is the public benchmark for the routing and sequencing part.

Sources

• D. Merchán et al., 2021 Amazon Last Mile Routing Research Challenge: Data Set, Transportation Science, 2024. DOI
• S. Ropke and D. Pisinger, An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows, Transportation Science, 2006. DOI
• T. Vidal, Hybrid genetic search for the CVRP: Open-source implementation and SWAP neighborhood*, Computers & Operations Research, 2022. DOI
• R. Geisberger et al., Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks, WEA 2008. DOI
• P. Newson and J. Krumm, Hidden Markov Map Matching Through Noise and Sparseness, ACM SIGSPATIAL 2009. DOI
• OSRM README (algorithms, MLD default): github.com/Project-OSRM/osrm-backend
• Valhalla README (matrix, map matching, Meili): github.com/valhalla/valhalla
• VROOM README: github.com/VROOM-Project/vroom