Vehicle Routing Problem (VRP)
Also known as: Capacitated Vehicle Routing Problem, Fleet Routing Problem, Multi-Vehicle Routing Problem, Araç Rotalama Problemi
The Vehicle Routing Problem (VRP) seeks the minimum-cost set of routes for a fleet of vehicles to serve a collection of geographically dispersed customers, each with a known demand, departing from and returning to a central depot. Originally formulated as the Truck Dispatching Problem by Dantzig and Ramser in 1959, VRP is a foundational model in logistics, supply chain management, and operations research, applicable whenever goods or services must be delivered efficiently across multiple stops.
Key highlights
- Provides provably optimal or near-optimal routes that reduce operational cost and fuel consumption.
- Highly generalizable: dozens of variant formulations address time windows, multiple depots, heterogeneous fleets, and split deliveries.
- Well-supported by mature solvers (CPLEX, Gurobi) and open-source libraries (OR-Tools, VRPy).
- Scales to real logistics networks through effective metaheuristic and column-generation algorithms.
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
When to use it
Use VRP when a fleet must serve multiple demand points from a shared depot and vehicle capacity is a binding constraint. Core assumptions include known customer locations and demands, homogeneous or heterogeneous fleet with known capacities, and a symmetric or asymmetric cost matrix. The model extends naturally to time-window VRP, split-delivery VRP, and stochastic VRP variants. It is less appropriate when customer demand is highly uncertain, routes are fixed by contract, or only a single vehicle is involved (reducing to the Traveling Salesman Problem).
Strengths & limitations
- Provides provably optimal or near-optimal routes that reduce operational cost and fuel consumption.
- Highly generalizable: dozens of variant formulations address time windows, multiple depots, heterogeneous fleets, and split deliveries.
- Well-supported by mature solvers (CPLEX, Gurobi) and open-source libraries (OR-Tools, VRPy).
- Scales to real logistics networks through effective metaheuristic and column-generation algorithms.
- Exact solution is NP-hard; optimal solutions for instances with more than a few hundred customers are computationally intractable without decomposition.
- Model quality depends critically on accurate cost matrices and demand estimates; errors propagate directly into route quality.
- Static formulation does not naturally accommodate real-time events such as traffic disruptions or last-minute orders.
- Setting up and solving large integer programs requires specialized software and expertise beyond basic spreadsheet tools.
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
How does VRP differ from the Traveling Salesman Problem?
TSP finds a single minimum-cost tour visiting all customers once. VRP generalizes TSP to multiple vehicles, each with a capacity limit, so the problem also decides how to partition customers across vehicles. TSP is a special case of VRP with one vehicle of unlimited capacity; in practice VRP is significantly harder because the partitioning and sequencing decisions interact.
Can VRP handle time windows and real-time updates?
Yes, through the Vehicle Routing Problem with Time Windows (VRPTW) variant, each customer is given an earliest and latest service time and the model adds temporal feasibility constraints. Dynamic VRP extensions re-optimize routes as new orders or disruptions arrive during the day, typically using rolling-horizon heuristics that re-solve a reduced problem at each decision epoch.
What solver or library should I use to implement VRP?
For prototyping, Google OR-Tools offers a free, well-documented VRP solver in Python and C++ that handles most standard variants. For production-scale exact optimization, CPLEX or Gurobi with column-generation or branch-and-price frameworks are preferred. The open-source library VRPy provides Python wrappers for labeling algorithms suited to VRPTW and related variants.
Sources
- 1.Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80–91.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 2). Vehicle Routing Problem. ScholarGate. https://scholargate.app/optimization/vehicle-routing