Vehicle Routing Problem (VRP)

Overview

VRP determines optimal routes for a fleet of vehicles to serve a set of customers from a depot, minimizing total distance or cost. NP-hard — exact solutions only feasible for small instances (< 25 nodes). Practical solutions use heuristics (Clarke-Wright savings, sweep) or metaheuristics (simulated annealing, genetic algorithm).

When to Use

Trigger conditions:

• Planning daily delivery routes for a fleet of vehicles
• Minimizing total travel distance/time under capacity constraints
• Optimizing route assignments across multiple vehicles

When NOT to use:

• For single-vehicle route optimization (use TSP solvers)
• For real-time dynamic routing with continuous order arrivals (use online algorithms)

Algorithm