Design Route Optimization

Problem Statement: Fleet Route Optimization

At its core, fleet route optimization is the Vehicle Routing Problem (VRP): assign thousands of delivery stops to hundreds of vehicles each day so that every vehicle follows an ordered sequence of stops that respects capacity, service time, and customer time windows, all while minimizing total drive time and fuel. This is not the textbook Traveling Salesman Problem — TSP threads one vehicle through every stop, whereas the real system juggles a heterogeneous fleet, a mix of hard and soft constraints, and an objective that trades drive time against lateness. The decisive architectural split is between offline batch planning (solve the whole day's routes before the shift starts) and online re-optimization (cheaply repair the live plan when new stops, traffic, or cancellations land mid-shift). Conflating the two is the classic failure: a batch solver runs for minutes over the full problem, but a mid-shift change needs a bounded, incremental repair that never strands a driver with a blank map.

Track plan_solve_p99_sec, matrix_build_minutes, stops_per_vehicle_p95, and replan_events_per_hour. Page when matrix age exceeds 15 minutes in peak lunch corridors.

Edge cases: Solver timeout returns last feasible plan; never blank-map drivers. Duplicate plan tokens must not spawn twin routes.

Why interviewers care

A strong answer frames this as a constrained optimization problem with an explicit objective, not a CRUD service: name the cost function, separate batch planning from incremental repair, and state exactly what the solver returns when it runs out of time. That vocabulary — feasibility, time windows, soft penalties, last-feasible-plan — is what an interviewer listens for.

Interview checkpoint

Keep one concrete outage ready: the solver blows its time budget on a 900-stop region at lunch peak, so rather than blank the drivers' maps you publish the last feasible plan and flag the unassigned stops explicitly — degrade, never disappear.