Route optimization: TSP, VRP and why spreadsheets don't solve real delivery
Delivery route optimization is one of the classic operations research problems and remains the single highest operating leverage for any carrier moving more than 30 stops per vehicle per day. The mathematical foundation is the Traveling Salesman Problem (TSP) — finding the shortest sequence that visits every stop and returns to origin — extended to the Vehicle Routing Problem (VRP) once you add multiple vehicles, varied capacities, customer time windows, and operational constraints. Pure TSP on 30 nodes has 2.65 × 10^32 possible routes; exhaustive enumeration is impossible even on a modern cluster. That's why the industry relies on heuristics (Clarke-Wright savings, 2-opt, Lin-Kernighan) and solvers like Google's OR-Tools, which resolve real 200-500 stop instances in seconds with a 2-5% gap to theoretical optimum.
Formulas and operating KPIs
Cost per stop = (Fuel + Driver wages + Vehicle depreciation + Maintenance) ÷ Stops delivered
Route density = Stops per route ÷ Kilometers driven. The higher the density, the lower the marginal cost per delivery. UPS ORION route optimization in Manhattan averages 6-8 stops/km; UPS suburban runs 2-3 stops/km. FedEx Ground and Amazon Logistics sit in the same corridor.
Stops per hour (SPH) = Stops delivered ÷ Route hours. UPS ORION benchmark: 18-22 SPH dense urban, 12-16 suburban. Amazon Logistics reports 15-20 SPH on its Delivery Service Partners.
Backhaul optimization — filling the empty return leg of the vehicle with pickups or return cargo. A truck that runs empty 30% of the time has cost efficiency 40-60% worse than one with scheduled backhaul.
Worked example: US mid-market last-mile carrier
A carrier with 20 vans delivers 1,400 daily parcels across a Phoenix metro zone. With manual dispatcher planning they average 70 stops/vehicle, 138 km per route, 10.8-hour shifts — SPH of 6.5 and route density 0.51 stops/km. Cost per stop: USD 3.85.
With OR-Tools calibrated for time windows (B2B 9-1pm, B2C 10-8pm), 450-lb capacity, and 9-hour shift cap:
- Stops per vehicle: 70 → 78 (+11%)
- Kilometers per route: 138 → 104 (−25%)
- SPH: 6.5 → 8.6 (+32%)
- Route density: 0.51 → 0.75 stops/km
- Cost per stop: USD 3.85 → USD 2.72 (−29%)
Monthly savings on 31,000 stops: USD 35,000. Payback on OR-Tools integration (open-source + 2 weeks of an engineer): recovered in month one.
Time windows: the constraint that breaks pure TSP
The customer's time window is the variable that separates academic VRP from real delivery. A B2B account that only receives from 9:00-11:00 turns its stop into a hard constraint — if you miss the window, you have a failed delivery and a reattempt (1.5-3x the original shipment cost). The solver weighs penalty for window violation against marginal detour cost. US retail windows typically front-load the morning (7-11am store opening) and commercial deliveries concentrate 9-13h, creating peaks that force more vehicles for the same stop volume.
Backhaul, milk runs and dense zones
The LatAm and US carriers with best cost per stop — UPS, FedEx, Amazon Logistics, OSM, Rappi, 99minutos — run three plays: (1) milk runs: pre-programmed routes with B2B pickup after B2C delivery, using the vehicle already in-zone; (2) zone density: assigning routes by fixed polygon lets the driver learn the zone — Amazon Logistics documents 8-12% SPH improvement after 90 days in the same zone; (3) B2B-B2C backhaul: leaving DC with B2C morning cargo and returning with B2B or return pickups in the afternoon, cutting idle time below 10% of shift.
Electric vehicle constraints: range planning and charging stops
The EV transition is already reshaping route design. An ICE van on a 280-km route is range-unlimited within a working day. A 100 kWh LFP urban delivery van (BYD T3, Rivian EDV, Mercedes eSprinter) carries 200-280 km usable range at 30-50% urban payload. Routes must now account for: (1) range buffer — no dispatch below 15-20% reserve given temperature degradation in winter; (2) charging stops — DC fast chargers (150+ kW) recharge 20-80% in 30-40 minutes, imposing a driver-rest equivalence that can fit within regulatory breaks; (3) depot charging capacity — a 40-van EV fleet needs 40 × 11 kW overnight chargers plus 2-4 DC fast chargers for partial topping, representing a one-time CAPEX of USD 180K-400K that the routing economics must absorb. The VRP solver handles EVs as vehicles with dynamic range state, charging nodes, and forced recharge time windows. This is more complex than adding a constraint to the classic VRP — it requires a variant called EVRPTW (Electric VRP with Time Windows) that solvers like OR-Tools and OptimoRoute now support natively.
Pharma rep and field-service routing: the B2B variant
Not all routing is parcel delivery. Pharmaceutical sales reps visiting 10-15 clinics, hospitals, or pharmacies per day face a VRP variant with: soft time windows (preferred appointment times), visit frequency requirements (some accounts need weekly coverage, others monthly), and territory equity constraints (sales manager wants similar coverage across reps). OptimoRoute and Salesforce Maps (formerly MapAnything) are the dominant platforms here. The simulator models territory design and call-frequency scenarios to quantify the cost of each additional rep hire against the coverage gap it fills — a decision that typically involves USD 80-120K in fully-loaded rep cost.
Sector benchmarks: US vs LatAm
US leading last-mile operators — UPS ORION, FedEx Ground, Amazon Logistics DSPs — run in the 15-22 SPH corridor with route density 2-5 stops/km in dense urban. LatAm leaders like Rappi Turbo, 99minutos and OSM Colombia sit at 6-9 SPH with 3-5 stops/km. The gap isn't from solver quality (both use modern VRP) but from urban traffic (2-3x worse in CDMX, São Paulo, Bogotá vs Nashville or Dallas), informal addressing density (missing visible numbers forces a customer call), and in-building delivery time (doorman, elevator, signature). Understanding the benchmark appropriate to your geography is step one before rolling out optimization — importing UPS SPH targets to a Bogotá operation sets up failure.
Common mistakes in route optimization projects
- Running the solver on stale address data. A 5% geocoding error rate means 5% of stops are placed at the wrong coordinate — the solver optimizes a fiction. Geocode validation is the highest-impact pre-processing step.
- Optimizing for distance without cost-weighting. Minimizing kilometers is not the same as minimizing cost — toll roads, fuel surcharges, and time-of-day traffic can make the shortest route the most expensive.
- Ignoring driver behavior after deployment. A perfectly optimized route degrades quickly when drivers deviate. Without GPS trace comparison against the planned route, you have no feedback loop.
Differentiation vs Excel and Google Maps
Excel doesn't solve TSP or VRP — the Solver add-in hits its variable ceiling around 15 stops. Google Maps optimizes waypoint sequence but ignores time windows, vehicle capacity and multi-vehicle routing. OR-Tools, Onfleet, Routific and Circuit for Teams close that gap; the web simulator is the bridge for carriers still planning manually and needing to quantify the value before investing in a TMS (Transportation Management System).
Conclusion
For carriers, e-commerce, FMCG distributors, and last-mile operators, route optimization is the number-one operating lever: 15-30% reduction in transport cost with marginal investment. The simulator lets you run TSP/VRP on your actual stops, compare scenarios with different fleet configurations, windows, and density, and quantify the savings before committing capital to software or additional fleet.