Vehicle Routing Problem (VRP)
Plan the least-cost routes for a fleet serving many stops. The vehicle routing problem finds efficient delivery routes from a depot to many customers under vehicle capacity and other constraints, minimizing total travel while meeting every demand.
Solve Vehicle Routing →What is the Vehicle Routing Problem?
The vehicle routing problem (VRP) is the challenge of designing optimal routes for a fleet of vehicles to serve a set of customers from one or more depots, minimizing total cost, usually distance or time, while satisfying constraints. It is one of the most studied and practically important problems in operations research and logistics.
VRP generalizes the classic Traveling Salesman Problem (TSP), which finds the shortest route for a single vehicle visiting all locations. VRP adds multiple vehicles and real-world constraints, most commonly vehicle capacity (the capacitated VRP), and often time windows, multiple depots, or maximum route durations. Each customer must be served, and the routes together must respect the constraints at least cost.
The VRP is computationally hard (NP-hard), so exact solutions are only practical for small instances. Real-world routing relies on heuristics and metaheuristics that find very good, though not provably optimal, routes quickly. Even modest routing improvements translate into large savings in fuel, labor and vehicles, which is why VRP optimization is so widely applied.
In plain terms: You've got a depot, a fleet of trucks, and a lot of stops to cover. The VRP figures out which truck goes where and in what order, so the total driving is minimized and no truck is overloaded. It's the delivery-fleet version of the classic 'shortest route' problem, and it's hard, so solvers use smart approximations.
Key Elements
Depot, Fleet, Customers
Vehicles start from a depot, serve a set of customers each with a demand, and return, minimizing total travel.
Capacity & Constraints
The capacitated VRP limits each vehicle's load; variants add time windows, multiple depots, or route-length limits.
Extends the TSP
VRP generalizes the Traveling Salesman Problem to multiple vehicles with capacity and other real-world constraints.
Key Formulas
Understanding the Solution
The solution is a set of routes, one per vehicle, that together cover all customers at minimum total cost while respecting capacity and any other constraints. The number of vehicles used, route lengths and loads all follow from the optimization.
Because the VRP is NP-hard, large real instances are solved with heuristics that produce excellent routes without guaranteeing the exact optimum. In practice this is entirely acceptable: the gap from optimal is usually small, and the savings over manual or naive routing, in fuel, driver hours and vehicles, are substantial.
Assumptions & Validation
Known Locations & Demands
Customer locations and demands are known.
If violated: Gather accurate location and demand data.
Defined Constraints
Vehicle capacity and any time or route constraints are specified.
If violated: State all binding constraints; missing ones give infeasible routes.
Reliable Travel Costs
Distances or travel times between points are known.
If violated: Use realistic travel-time data, especially with traffic.
⚠️ Check assumptions first
The VRP is NP-hard, so for realistic problem sizes solvers return excellent heuristic routes rather than a proven optimum, which is normally fine. The solution is only as good as its inputs, however: inaccurate demands, capacities, or travel times produce routes that fail in practice. Specify every binding constraint (capacity, time windows, route limits), since a missing constraint yields routes that look optimal but cannot actually be run.
When NOT to Use Vehicle Routing Problem (VRP)
Single Vehicle
For one vehicle visiting all stops, the Traveling Salesman Problem is the specific case.
Joint Inventory & Routing
When replenishment quantities and routing are decided together over time, use the inventory routing problem.
Point-to-Point Flow
For least-cost flow between sources and sinks without routing, use transportation or network-flow models.
Industry Applications
Delivery Fleets
Plan daily delivery routes for parcels, food, retail or field service.
Distribution Logistics
Route vehicles from depots to stores or customers at minimum cost.
Service Scheduling
Route technicians or crews to jobs under time and capacity limits.
Cost Reduction
Cut fuel, driver hours and fleet size through better routing.
Frequently Asked Questions
What is the vehicle routing problem?
The vehicle routing problem is the challenge of designing optimal routes for a fleet of vehicles to serve a set of customers from one or more depots, minimizing total travel cost while satisfying constraints such as vehicle capacity. Every customer must be served, and the routes together must respect the constraints at least cost. It is a central problem in logistics and operations research.
How is the VRP related to the Traveling Salesman Problem?
The VRP generalizes the Traveling Salesman Problem. The TSP finds the shortest route for a single vehicle visiting all locations once, while the VRP adds multiple vehicles and real-world constraints, most commonly vehicle capacity, and often time windows or multiple depots. When there is only one vehicle and no capacity limit, the VRP reduces to the TSP, making the TSP a special case.
What is the capacitated VRP?
The capacitated vehicle routing problem, or CVRP, is the most common VRP variant, in which each vehicle has a limited carrying capacity and each customer has a demand. The routes must be designed so that the total demand on any route does not exceed the vehicle's capacity, in addition to minimizing total travel. Capacity is often the binding constraint that determines how many vehicles and routes are needed.
Why is the vehicle routing problem hard to solve?
The VRP is NP-hard, meaning the number of possible route combinations grows explosively with the number of customers, so finding a provably optimal solution is only practical for small instances. Real-world problems with many stops and constraints are solved with heuristics and metaheuristics that find very good routes quickly without guaranteeing optimality, which is almost always acceptable in practice.
What constraints can a VRP include?
Beyond vehicle capacity, common VRP constraints include time windows during which each customer must be served, maximum route duration or distance, multiple depots, heterogeneous fleets with different vehicle types, and pickup-and-delivery requirements. Each added constraint reflects a real operational limit and makes the problem more realistic, though also more complex. Specifying all binding constraints is essential for routes that can actually be executed.
What savings can VRP optimization deliver?
Even modest improvements in routing translate into substantial savings, because routing drives fuel consumption, driver hours and the number of vehicles required. Optimized routes over manual or naive planning commonly reduce total distance and time significantly, lowering operating cost and sometimes allowing a smaller fleet. This high leverage is why vehicle routing optimization is one of the most widely applied techniques in logistics.
Plan Least-Cost Routes for Your Fleet
Solve the capacitated vehicle routing problem under real constraints. Free during Beta.
Solve Vehicle Routing →