Inside VRP Solutions: Engineering a Modern Vehicle Routing Problem Solver

Why Vehicle Routing Is Still a Hard Problem

Every logistics company eventually runs into the same wall: they have N vehicles, M stops, a handful of time windows, and a fleet of drivers who need to be somewhere before lunch. On paper it looks like a scheduling exercise. In practice, it's one of the most computationally brutal problems in applied optimization.

The Vehicle Routing Problem (VRP) is a generalization of the Traveling Salesman Problem — and TSP is already NP-hard. Add multiple vehicles, capacity constraints, time windows, driver shift limits, and live traffic conditions, and the search space explodes combinatorially. For a modest fleet of 20 vehicles serving 150 stops, the number of possible route assignments outstrips brute-force computation by many orders of magnitude. There is no exact algorithm that solves this at scale in reasonable time — which is exactly why VRP has spent decades as a proving ground for operations research and, more recently, applied heuristics and metaheuristics.

VRP Solutions was built to close the gap between textbook VRP theory and the messy reality of dispatch operations: vehicles break down, customers reschedule, traffic doesn't cooperate, and dispatchers need answers in seconds, not minutes. This post walks through the core engineering decisions behind the three pillars of the product — multi-vehicle route optimization, real-time constraint solving, and the fleet scheduling engine.

1. Multi-Vehicle Route Optimization

The problem formulation

At its core, multi-vehicle routing is a constrained combinatorial optimization problem. Given a depot (or multiple depots), a set of delivery/pickup stops — each with demand, service time, and often a time window — and a fleet of vehicles with capacity, start/end location, and maximum route duration, the objective is to partition stops into vehicle routes that minimize a cost function while satisfying every hard constraint.

This is the Capacitated VRP with Time Windows (CVRPTW) — the workhorse variant that most real dispatch operations actually need, and the one VRP Solutions targets by default. It also composes into more specialized cases (pickup-and-delivery, multi-depot, heterogeneous fleets) via the same underlying constraint model.

Construction: getting to a feasible solution fast

Rather than starting from a blank slate and searching the entire space, the engine builds an initial feasible solution using a parallel savings algorithm (a variant of Clarke-Wright), which greedily merges single-stop routes based on the distance saved by combining them, subject to capacity and time-window feasibility. This gives a decent starting point in near-linear time relative to stop count — good enough to dispatch on if a plan is needed immediately, but rarely optimal.

Improvement: local search + metaheuristics

The initial solution is then refined using a layered local search strategy:

• 2-opt and Or-opt moves within a route to eliminate crossing paths and awkward detours
• Inter-route relocation and exchange — moving a stop (or a small chain of stops) from one vehicle's route to another when it reduces total cost
• Cross-exchange between route pairs, useful when two vehicles are servicing overlapping geographic zones inefficiently

To avoid getting stuck in local optima, these moves are wrapped in a Guided Local Search (GLS) framework, which penalizes frequently-traversed “expensive” edges to push the search toward unexplored configurations, combined with a Large Neighborhood Search (LNS)destroy-and-repair loop: a subset of stops is deliberately removed from the current solution (“destroy”) and reinserted using a regret-based heuristic (“repair”). This destroy/repair cycle is what allows the solver to escape plateaus that pure 2-opt gets trapped in, especially on dense urban stop clusters.

For fleets under roughly 50 vehicles and a few hundred stops, this pipeline converges to within a few percentage points of the best-known solution in well under a minute on standard compute. Larger instances are handled by partitioning the service area into geographic clusters first (using a k-means-like sweep on stop coordinates weighted by demand), solving each cluster semi-independently, and then running a final cross-cluster improvement pass to catch any obviously suboptimal boundary assignments.

Distance and time matrices

Optimization quality is bounded by the quality of the underlying distance/time data. Straight-line (haversine) distance is fine for a rough cut, but real dispatch requires actual road-network travel times, which vary by time of day. VRP Solutions precomputes an asymmetric time-distance matrix using routing engine calls (batched and cached aggressively, since matrix computation cost grows quadratically with stop count), and refreshes travel-time estimates using historical time-of-day traffic profiles rather than a single static number.

2. Real-Time Constraint Solving

Static optimization solves the plan you had at 6 a.m. It says nothing about the vehicle that got a flat tire at 10:15, or the customer who just called to push their window back two hours. This is where most naive routing tools fall down — they require a full re-optimization from scratch, which is too slow and too disruptive (drivers don't want their entire route reshuffled because of one change three stops away).

Constraint model

Every hard and soft constraint in the system — vehicle capacity, time windows, driver shift caps, skill/equipment matching (e.g., refrigerated trucks for cold-chain stops), precedence (pickup before delivery), and depot return deadlines — is modeled explicitly as a constraint object rather than baked into the cost function. This separation is what makes real-time re-solving tractable: when a new event arrives, the engine doesn't need to reconstruct the objective, it just needs to check which routes now violate which constraints.

Incremental re-optimization

Instead of full re-optimization, the real-time layer uses a repair-based incremental approach:

1. Localize the disruption. When an event fires (vehicle breakdown, new order, cancellation, traffic incident, late arrival), the engine identifies only the routes and stops causally affected — typically the current route and any routes with slack capacity nearby.
2. Constraint propagation. Affected stops are checked against the constraint set to flag violations (e.g., a delayed vehicle now blows through a downstream customer's time window).
3. Targeted repair. A bounded LNS pass runs only on the affected neighborhood — removing and reinserting the impacted stops among nearby vehicles — rather than touching the whole solution. This keeps re-solve latency in the range of hundreds of milliseconds to a couple of seconds for typical fleet sizes.
4. Driver-disruption minimization. A penalty term discourages reassigning stops away from a driver who's already en route unless the gain clears a threshold — dispatchers don't want the system thrashing a driver's route for marginal gains.

Handling live signals

The constraint solver consumes a stream of events rather than polling:

• GPS/telematics pings update actual vs. planned position, feeding an ETA recalculation for every downstream stop on that route
• Traffic incident feeds trigger a re-check of time-window feasibility for routes crossing the affected segment
• Order-management webhooks (new orders, cancellations, address changes) enter the same event queue as breakdowns and delays, so they're handled by the identical repair pipeline

This event-driven design means the “real-time” claim isn't just about the solve being fast — it's that the whole system is architected around continuous small updates rather than periodic full recomputation.

3. Fleet Scheduling Engine

Routing tells you the sequence of stops. Scheduling tells you who drives which route, when, with whatvehicle — and that's a genuinely different optimization layer, sitting on top of routing rather than being solved by it.

Resource assignment

The scheduling engine treats drivers and vehicles as separate resource pools with their own constraint sets. Driver constraints include shift length, mandated breaks, certifications (HAZMAT, CDL class), home-base depot, and availability/PTO. Vehicle constraints include capacity, fuel type/range (relevant for EV fleets — state-of-charge becomes a routing constraint, not just a scheduling one), maintenance windows, and equipment (lift gates, refrigeration).

Assignment is solved as a bipartite matching problem layered on top of the route plan: given a fixed set of optimized routes, find the driver-vehicle pairing that minimizes cost (overtime, deadheading back to depot, certification mismatches) while respecting hard constraints. When the route plan itself is flexible, scheduling and routing are solved jointly in an outer loop — the router proposes a route set, the scheduler checks resource feasibility, and infeasibilities get fed back as additional constraints for the next routing pass.

Multi-day and recurring optimization

For operations with standing routes (e.g., recurring weekly deliveries to the same customer set), the engine separates template generation from daily variance handling. A base schedule is optimized less frequently (weekly/monthly) as a stable reference plan, and daily dispatch applies the real-time repair layer on top of that template rather than re-deriving the whole schedule from scratch each morning. This mirrors how experienced dispatchers actually work — they have a mental “normal” route and adjust from it, rather than reinventing the plan daily.

Fairness and driver experience

A scheduling engine optimized purely for cost tends to produce brittle, inequitable schedules — the same driver always gets the worst zone, or overtime concentrates on a handful of people. VRP Solutions incorporates a configurable fairness penalty (variance in route difficulty, hours, or overtime across drivers) directly into the scheduling objective, so operators can trade a small amount of theoretical cost optimality for materially better driver retention — a lever that matters more in practice than most routing literature accounts for.

Architecture Summary

What's Next

The current roadmap focuses on tightening the loop between the real-time solver and predictive ETAs — using historical route performance to anticipate delays before they trigger a constraint violation, rather than reacting after the fact. We're also extending the vehicle constraint model to handle mixed EV/ICE fleets more natively, since range anxiety and charging-window constraints behave less like vehicle capacity and more like a second, parallel time-window problem.

VRP is a problem that never gets “solved” in the permanent sense — every improvement in solve quality or latency just raises the bar for what dispatchers expect next. That's the fun of building in this space.