The Capacitated Vehicle Routing Problem (CVRP)
The Capacitated Vehicle Routing Problem (CVRP) is a classic optimization challenge in logistics and operations research. Given a fleet of vehicles with limited capacity and a set of customers with known demands, the goal is to find the most efficient routes that minimize total distance while satisfying all constraints.
1. Problem Definition
The CVRP extends the famous Traveling Salesman Problem (TSP) by adding two key constraints:
- Multiple Vehicles: Instead of one salesman, you have a fleet of trucks.
- Capacity Constraints: Each vehicle has a maximum capacity (e.g., weight or volume).
- Customer Demands: Each customer requires a specific amount of goods to be delivered.
- Depot: All vehicles start and end at a central depot.
2. Real-World Applications
CVRP is fundamental to modern logistics:
- Last-Mile Delivery: Companies like Amazon, UPS, and Glovo optimize delivery routes daily.
- Waste Collection: Garbage trucks planning efficient collection routes.
- Supply Chain: Distributing goods from warehouses to retail stores.
- School Bus Routing: Picking up students while respecting bus capacity.
3. Algorithms Implemented
Greedy Nearest Neighbor
How it works: Each truck starts at the depot and repeatedly drives to the closest unvisited customer that fits in its remaining capacity. When full or no more customers fit, it returns to the depot and a new truck starts.
Pros: Fast, simple, intuitive to visualize.
Cons: Short-sighted. Often creates inefficient routes by leaving remote customers for last.
Polar Sweep (Geometric)
How it works: Calculates the angle of each customer relative to the depot (like a radar sweep). Sorts customers by angle and groups them into wedge-shaped sectors, assigning each sector to a truck.
Pros: Creates visually distinct, non-overlapping routes. Good for geographically clustered customers.
Cons: Ignores distance. Can group nearby and far customers together just because they're in the same direction.
Clarke-Wright Savings Algorithm
How it works: Starts with a naive solution (one truck per customer). Iteratively merges routes that produce the biggest "savings" in distance by avoiding redundant trips back to the depot.
The savings for merging customers i and j is calculated as:
s(i,j) = distance(depot,i) + distance(depot,j) - distance(i,j)
Pros: Industry-standard heuristic. Balances distance and capacity well.
Cons: More computationally intensive (O(n² log n)).
4. Complexity
CVRP is NP-hard, meaning there's no known polynomial-time algorithm to find the optimal solution for large instances. For n customers and k vehicles, the exact solution space is astronomical. Therefore, real-world applications rely on heuristics (like those shown here) or metaheuristics (Simulated Annealing, Genetic Algorithms, Ant Colony Optimization).
5. Connection to My Work
At Glovo, I built large-scale discrete event simulations for testing courier assignment and routing algorithms. CVRP variants (with time windows, multiple depots, and dynamic customer arrivals) are at the core of on-demand delivery optimization. This tool demonstrates the fundamental building blocks of those systems.
Note:
This visualization uses a simplified Euclidean distance model on a map of Barcelona. Real-world routing uses road networks, traffic data, and additional constraints like time windows and driver breaks.