Last-Mile Delivery

Route Planning, Driver App and Live Tracking

Design the system that plans each driver's stops for the day, changes routes while drivers are out, records proof of delivery from a phone with a weak signal, and shows customers where their package is.

Overview

Last mile is the final leg of a package's trip: from a local depot to the customer's door. Each morning a depot has a few thousand packages and a few dozen vans. The system must split the packages among the vans, put each van's stops in a good order, and hand the plan to drivers before they leave. For the rest of the day it records what happened at each stop and tells customers when to expect their package.

The interview has three parts. Planning is a vehicle routing problem: it cannot be solved exactly at this size, so you use heuristics with a time limit. The driver app runs on a phone that often has no signal, so it must record everything locally and sync later without creating duplicates. Tracking turns a stream of GPS pings into a position and an ETA that millions of customers can read cheaply.

Questions to ask first

Who owns the vans and drivers? — We do; each driver starts and ends at one depot
How many drivers and stops? — 100,000 drivers, about 100 stops each, 10 million packages a day
Do customers pick delivery windows? — Some do (for example 2 pm to 4 pm); most packages have no window
How fresh must live tracking be? — Driver position within about 10 seconds; ETA within a few minutes
What counts as proof of delivery? — A photo plus GPS position; a signature or code for some packages
Must the driver app work offline? — Yes, for at least the length of a rural stretch (we assume 30 minutes)

What you will be able to do

Explain why route planning uses heuristics with a time limit, and what a time window does to a route.
Add a stop to a live route in milliseconds without breaking anyone's window.
Design a driver app that records deliveries offline and syncs them exactly once.
Size the GPS, photo and tracking traffic, and serve tracking from a cache.
Handle failed deliveries and check that a delivery photo was taken at the right place.

Key concepts

Vehicle routing with time windows
Savings heuristic and 2-opt
Cheapest feasible insertion
Offline-first outbox
Idempotent delivery events
Presigned photo upload
Latest-location store
Geofenced proof of delivery
Partition by depot

Functional requirements

Plan each driver's ordered stop list before the shift, respecting van capacity and delivery windows
Add, remove or move stops on a live route, and push the change to the driver
Record each stop's outcome with proof: photo, GPS position, and a signature or code when required
Handle failed deliveries: reattempt, redirect to a locker, or return to depot
Show customers the driver's position, stops before theirs and an ETA
Keep working in the driver app without a network, then sync

Non-functional requirements

Plans for a depot are ready before the vans leave (we target 30 seconds of solver time per route)
A new stop is inserted into a live route in under a second
No delivery event is lost or counted twice, even with retries and no signal
Driver position on the tracking page is at most about 10 seconds old (a target we chose)
Tracking reads never touch the routes database on the hot path

Interview questions

How is VRP different from TSP, and how do you solve it at scale?
How do you add a package to a route the driver is already on?
How does the driver app avoid losing or duplicating deliveries?
How do you serve live tracking to millions of customers?
How do you compute the ETA for a customer's stop?
How do you detect a false delivery?
How do you partition the data?