Delivery Route Planning
Capacitated Vehicle Routing Problem (CVRP)
A delivery company operating from a depot must serve customers across Quebec City. Each van has limited capacity, each stop has a package demand, and the goal is to find the shortest set of routes that delivers everything. This is the Capacitated Vehicle Routing Problem — one of the most studied and practically important problems in Operations Research.
The Problem
Why route optimization matters for last-mile delivery
Consider a courier company based in Sainte-Foy, Quebec City. Every morning, a fleet of delivery vans departs from a central distribution center, each loaded with packages for customers scattered across the city — from the historic streets of Vieux-Québec to the commercial centers of Beauport and Lévis. Each van can carry at most Q kilograms, and each delivery stop requires a known quantity of packages. Every van must start and end at the depot, and every customer must be served exactly once.
The objective is to minimize total travel distance across all routes, which directly translates to reduced fuel costs, fewer driver hours, and faster deliveries. In practice, even a 5–10% reduction in total route distance can yield significant annual savings for a fleet of 20–50 vehicles making hundreds of daily stops.
This problem is NP-hard: with n delivery stops, the number of possible route configurations grows super-exponentially. For just 15 stops, there are over one trillion possible orderings — and that is before considering how to split stops across multiple vans. No known algorithm can guarantee an optimal solution in polynomial time. The CVRP was introduced by Dantzig & Ramser (1959) as a generalization of the Traveling Salesman Problem, and remains one of the most active areas of research in combinatorial optimization.
The Model
Mathematical formulation of the CVRP
subject to
Σk Σj xijk = 1 // each customer visited exactly once
Σi∈Sk qi ≤ Q // route load ≤ van capacity
// each route starts and ends at depot (node 0)
xijk ∈ {0, 1} // binary assignment of edge (i,j) to vehicle k
Where dij is the distance between stops i and j, qi is the demand at stop i, and Q is the van capacity.
See full CVRP theory and all algorithmsTry It Yourself
Plan delivery routes across Quebec City
Quebec City Route Planner
8 Stops · Capacity 60 kg · Click any cell to edit| # | Name | Latitude | Longitude | Demand (kg) |
|---|
| Algorithm | Total Distance (km) | Vans Used | Time |
|---|---|---|---|
| Configure stops and click Solve & Compare All Algorithms | |||
Ready. Edit stops above or choose a preset, then click Solve.
Real-World Complexity
What this demo does not capture
Production-Grade Challenges
- Real road distances vs. straight-line distances — actual routes follow streets, highways, and bridges, with one-way roads and turn restrictions
- Traffic patterns varying by time of day — a 5 km route through downtown at 8 AM takes far longer than at 2 PM
- Driver break regulations and shift limits — Quebec labor standards require rest periods after consecutive driving hours
- Multiple vehicle types with different capacities — small vans for narrow Old Quebec streets, larger trucks for commercial zones
- Priority customers and delivery time windows — "deliver between 9 AM and 11 AM" constraints dramatically increase complexity
- Dynamic orders arriving during the day — real-time re-optimization as new pickup requests come in
- Scale: real instances involve 500+ delivery stops per day, requiring specialized solvers and decomposition techniques
References
- (1959). "The Truck Dispatching Problem." Management Science, 6(1), 80–91.
- (1964). "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points." Operations Research, 12(4), 568–581.
- (1974). "A Heuristic Algorithm for the Vehicle-Dispatch Problem." Operations Research, 22(2), 340–349.
- Application context and algorithm implementations from this repository's CVRP module.