Antenor Blog 5 min read
Route Optimization at Scale: Solving TSP for Last-Mile Logistics
Why last-mile routing is not textbook TSP, which solver strategies survive real dispatch operations, and what it takes to serve optimized routes in seconds via API.
Last-mile route optimization is a vehicle routing problem with time windows, capacities, and constant change, not the clean traveling salesman problem from textbooks. Exact solvers cannot answer at dispatch speed for realistic instance sizes, so production systems rely on construction heuristics refined by local search and metaheuristics, engineered to return good routes in seconds. The hard part is not the algorithm on a benchmark; it is holding solution quality while couriers cancel, addresses fail to geocode, and the fleet changes mid-morning. We built a routing API on these principles that has optimized millions of shipments across seven countries.
The textbook problem is not the real problem
The traveling salesman problem asks for the shortest tour through a set of points. Real last-mile dispatch asks something messier: assign hundreds or thousands of shipments to a fleet of couriers with different vehicle types, capacities, shift lengths, and starting points, respecting delivery time windows, and produce each courier’s stop sequence. That is the capacitated vehicle routing problem with time windows (CVRPTW), and it is substantially harder than TSP.
Then reality adds the constraints the papers leave out:
- Travel times are not Euclidean. They come from a road network, vary by hour, and differ by vehicle type. A motorcycle and a van do not share a cost matrix.
- The instance is never final. Shipments arrive after routes are cut. Couriers do not show up. A recipient reschedules. The system re-optimizes all day, not once at dawn.
- Geocoding is part of the problem. In much of Latin America, where we operate, address quality is poor enough that a routing system is only as good as its address resolution layer.
- The objective is plural. Distance, on-time percentage, courier workload balance, and cost per drop all matter, and their weights differ per client.
Why exact methods lose at dispatch time
Mixed-integer programming and branch-and-cut can solve small VRP instances to proven optimality, and they are excellent for offline network design. At dispatch time they fail on two axes at once: solve time grows explosively with instance size, and the “optimal” solution is stale the moment the input changes, which is constantly. Proving optimality on data that will be wrong in twenty minutes is wasted compute.
Production routing engines therefore use a layered heuristic strategy:
- Construction. Build a feasible solution fast with savings-style or insertion heuristics. Quality is mediocre; feasibility and speed are the point.
- Local search. Improve it with well-studied move operators: 2-opt and Or-opt within routes, relocate and swap and cross-exchange between routes.
- Metaheuristic control. Escape local optima with strategies such as guided local search, tabu search, or large neighborhood search that destroys and rebuilds parts of the solution.
- Time budget, not optimality gap. The solver runs until its deadline and returns the best solution found. The deadline is a product decision: seconds for interactive dispatch, minutes for overnight planning.
What “an API that answers in seconds” actually requires
Wrapping a solver in HTTP is trivial. Meeting a seconds-level latency budget on real instances is a systems problem:
| Requirement | What it means in practice |
|---|---|
| Precomputed travel-time matrices | Distance queries answered from cached road-network data, not computed per request |
| Warm solver state | Re-optimization starts from the current plan, not from scratch, when a shipment is added or a courier drops |
| Instance decomposition | Large territories split into zones solved in parallel, with boundary repair afterward |
| Graceful degradation | If the budget expires, return the best feasible plan and keep improving in the background |
| Deterministic replay | Same input, same output, so operations teams can audit why a route looked the way it did |
| Constraint validation up front | Reject impossible inputs (overlapping windows, over-capacity loads) with clear errors instead of silently dropping stops |
The last two are the difference between a demo and a system a dispatch team trusts. When a route looks strange, someone will ask why, and “the metaheuristic did it” is not an acceptable answer. Explainability tooling around the solver matters as much as the solver.
What the scoreboard looks like in production
We built this class of system for Moova, a last-mile logistics platform. The routing engine solves courier assignment and stop sequencing with a latency of seconds, has optimized millions of shipments, and runs in seven countries: Argentina, Chile, Colombia, Guatemala, Mexico, Peru, and Uruguay. Shippers on the platform include Mercado Pago, Nestle, AT&T, Samsung, Puma, and UPS. The operational lesson from that scale is consistent: the solver is maybe a third of the engineering. The rest is data quality, re-optimization workflows, and the interfaces that let humans override the machine without destroying route quality.
This work sits inside our process optimization practice, alongside scheduling and pricing problems that share the same operations-research toolbox.
Frequently asked questions
Should we use an off-the-shelf routing API or build our own?
Start with off-the-shelf if your constraints are standard and your volume is modest; the good commercial APIs handle plain CVRPTW well. Building pays off when your constraints do not fit their model (custom courier types, unusual service rules, tight coupling with your dispatch workflow), when per-request pricing becomes material at your volume, or when routing quality is a competitive differentiator rather than a utility.
How large an instance can be solved in seconds?
With precomputed matrices, decomposition, and warm starts, thousands of stops across a metropolitan fleet are solvable within an interactive budget on commodity hardware. The honest answer for any specific case comes from benchmarking on your own geography and constraint set, which is the first thing we do in a scoping engagement.
Is machine learning replacing OR solvers for routing?
Not replacing, complementing. Learned models are excellent for travel-time prediction, demand forecasting, and warm-starting solvers, and there is active research on neural construction heuristics. But for constraint-heavy routing, hybrid systems where ML feeds an OR solver remain the production standard.