The staff scheduler I wrote about a few weeks ago was a MILP — a Mixed Integer Linear Program. You define variables, constraints, and an objective function. Hand it to a solver, get an answer. Clean, relatively tractable, runs in seconds on a laptop.
The vehicle routing problem is something else entirely.
VRP belongs to a class of problems that are technically NP-hard. That doesn’t mean unsolvable — it means that as the problem grows, the time to find an exact optimal solution grows exponentially. With 10 stops and 2 trucks you can probably brute-force it. With 113 stops and 10 trucks — which is roughly what this model handles — you cannot. Not in any reasonable amount of time.
So instead of searching for the provably optimal solution, you use a metaheuristic: an algorithm that explores the solution space intelligently, improves what it finds, and stops when time runs out or improvement stalls. You don’t get a guarantee. You get a very good answer, fast.
Why not PuLP?
The staff scheduler used PuLP with the CBC solver. CBC is excellent for MILP problems — it finds proven-optimal solutions to problems with hundreds of binary variables in seconds. I’ve used it for years.
For VRP at any real scale, CBC is the wrong tool. You could technically formulate VRP as a MILP — people have published papers on it — but the formulations are large and fragile and slow. The combinatorial explosion that makes VRP hard also makes the LP relaxation at the root of the branch-and-bound tree weak. CBC would spend hours searching a solution space that a dedicated VRP solver navigates in minutes.
Google OR-Tools has a routing library built specifically for this. It handles the distance matrix, time windows, capacity constraints, pickup-delivery pairs — all the structural pieces of VRP — natively. Under the hood it uses a combination of construction heuristics (to get an initial solution fast) and local search metaheuristics (to improve it). The parameters you choose — which operators, how long to search, which first-solution strategy — matter a lot to solution quality.
The time window constraint
This particular model is a VRP-TW: Vehicle Routing Problem with Time Windows. Each delivery stop has an earliest and latest arrival time. Arrive early, you wait. Arrive late, you pay a penalty. Arrive very late, the order might get dropped entirely.
Time windows make the problem significantly harder because they constrain the order in which stops can be visited. You can’t just build the shortest route geometrically — the sequence has to respect when each customer is available. A stop that’s geographically close might need to be visited early in the route, or late, depending on its window.
The model also has a capacity dimension — each truck can only carry so much weight. And a route time limit — no truck drives more than 14 hours in a day.
The dummy warehouse trick
One of the more interesting structural choices in this model is how it handles the fact that trucks have to be “loaded” before they can deliver. Each delivery stop gets a phantom twin — a dummy copy of the depot that represents the moment the truck picks up that specific load. A pickup-delivery constraint forces the truck to visit the phantom depot before visiting the real stop.
This doubles the node count (roughly), but it solves an important modeling problem: it ensures that capacity tracking works correctly, that trucks don’t deliver more than they can carry, and that the sequence of pickups and deliveries is physically coherent.
It’s a standard trick in the VRP literature. I didn’t invent it. But it’s one of those things that’s obvious in retrospect and completely non-obvious the first time you encounter it.
The distance matrix
OR-Tools needs a matrix of travel times between every pair of stops. For n stops that’s n² entries — for 113 stops that’s about 12,000 numbers, and for the model’s expanded node count (with dummy depots) it’s closer to 50,000.
We pull these from OSRM — an open-source routing engine with a free public API. It returns real drive times based on actual road networks, not straight-line distances. The results get cached to disk so you don’t make the same API call twice for the same set of stops.
The original production system used a paid distance API due to volume. For a demo app with occasional use, the free OSRM endpoint is more than enough.
Why this is worth understanding
Route optimization shows up everywhere. Food delivery. Field service scheduling. School bus routing. Medical supply chains. Any business that moves physical things between physical places has a routing problem, and most of them are solving it with gut instinct or basic rules of thumb. A VRP model doesn’t have to be a $2M system — it can be a Flask app and a spreadsheet.
Next post: what it actually took to port 1,500 lines of C# to Python, including the parts that didn’t work the first time.
Things that I use, like, and am affiliated with:
Mint Mobile offers great cell phone service for $15 flat, get $15 off using the link. Get discounted phones with service activation and no contract.
I never spend money before I check Mr Rebates or Rakuten to get cashbacks, rebates, discounts, coupons or cheaper gift cards.