Introduction
Picture a dispatcher at 6 a.m. with 40 vehicles, 600 stops, and three depots. Each customer has a delivery window. Each truck has a load limit. Then a driver calls in sick, and a highway backs up.
No spreadsheet handles that well. Last-mile services account for 41% of supply-chain costs in Capgemini's 2019 survey of 500 executives, so poor routing is expensive.
The Vehicle Routing Problem (VRP) asks how to assign stops to vehicles and sequence each route at the lowest cost. Here, VRP always means Vehicle Routing Problem, not Variable Recurring Payments. This guide covers the main variants, the algorithm families, and how to choose a solver.
Key Takeaways
- VRP assigns stops to vehicles and sequences visits to optimize an objective under constraints.
- Capacity, time windows, pickups, depots, and live changes create distinct variants.
- Exact methods prove optimality on smaller problems; heuristics trade proof for speed.
- Pick a solver that covers your real constraints, map data, and integrations.
What Is the Vehicle Routing Problem?
What a VRP model represents
Dantzig and Ramser introduced the problem in their 1959 paper, which routed gasoline trucks between a terminal and service stations. The model today has the same core pieces:
- Depots: where vehicles start and usually end
- Vehicles: with capacities and restrictions
- Customers or jobs: the stops, with demand and service time
- Matrix: travel time or distance between every pair of locations
The solver assigns stops to vehicles, then orders them to minimize (or maximize) an objective: distance, travel time, fuel, cost, on-time performance, or fleet utilization.
How VRP differs from the Traveling Salesman Problem
The Traveling Salesman Problem (TSP) sequences one vehicle through all locations. VRP generalizes this to a fleet, adding capacities, depots, and business rules. A real operation mixes both: it assigns stops to drivers, then sequences each driver's day like a TSP.
Objectives and constraints
The objective is what you optimize. Constraints define what's allowed. Hard constraints can never be violated, such as a vehicle's weight limit. Soft constraints can be broken for a penalty, such as arriving ten minutes late.
VRP is also computationally difficult. Lenstra and Rinnooy Kan's 1981 paper reviews NP-hardness results for routing problems, meaning solving effort grows explosively as stops, vehicles, and constraints increase.
What Are the Main Types of VRP?
Capacitated VRP (CVRP)
CVRP caps each vehicle's load by weight, volume, or item count. A beverage distributor with 12-pallet trucks can't just group nearby stops. Capacity decides which stops share a truck, and that changes the sequence.
VRP with Time Windows (VRPTW)
Customers accept service only in certain intervals. Hard windows forbid late arrival. Soft windows allow it at a cost. Some models allow multiple windows per stop.
A short route can still fail. If it puts the driver at a clinic 20 minutes after the appointment window closes, it's infeasible, no matter how few miles it saves. Service durations and driver shifts matter just as much.
VRP with Pickup and Delivery (VRPPD)
Each job has a paired pickup and drop-off that must share a vehicle, with pickup first. This fits:
- Couriers and ride-sharing
- Reverse logistics and returns
- Field service parts collection
- Non-emergency medical transportation (NEMT)
Multi-depot, heterogeneous-fleet, and open VRP
- Multi-depot: customers are served from several facilities
- Heterogeneous fleet: vehicles differ in capacity or restrictions
- Open VRP: vehicles don't return to a depot
These combine freely with time windows, capacity, and shift rules.
Dynamic, stochastic, periodic, and rich VRP
- Dynamic VRP: updates routes as new jobs, cancellations, or traffic arrive
- Stochastic VRP: treats demand or service times as uncertain
- Periodic VRP: plans recurring visits over multiple days
- Rich VRP: bundles many real-world constraints together
Errico and colleagues show that random service times can push planned routes past hard windows. Most businesses solve a hybrid, not a textbook variant.
Which Algorithms Are Used to Solve VRP?
Exact optimization methods
Mixed-integer linear programming, branch-and-bound, and branch-and-cut can find and prove optimal solutions. They suit smaller or tightly structured problems. Pecin et al. (2017) solved benchmark instances up to 199 customers, and some up to 360. That figure is a historical benchmark rather than a hard ceiling, and it still shows why exhaustive search breaks down at fleet scale.
Constructive heuristics
These build a feasible route fast:
- Nearest neighbor
- Insertion heuristics
- Sweep methods
- Clarke-Wright savings (1964)
They're good for baselines and warm starts. They rarely reach the best possible solution.
Metaheuristics
These methods improve a starting solution by exploring alternative assignments and sequences:
- Tabu search
- Simulated annealing
- Genetic algorithms
- Ant colony optimization
- Large neighborhood search
Tradeoffs include quality versus runtime, repeatability, and parameter tuning. Adaptive large neighborhood search handles complex constraints well. Hybrid genetic search won the 2022 DIMACS CVRP challenge through Huawei's Alkaid-X. That entry used HGS on smaller instances and iterated local search on larger ones. No single method ranks first everywhere.
Hybrid and matheuristic approaches
Production systems often embed mathematical models inside heuristics, using decomposition, local search, or column generation. That balances constraint compliance with consistently strong routes on large daily problems.
Dynamic and real-time routing
When conditions change after dispatch, solvers use rolling-horizon planning, incremental reoptimization, and traffic-aware updates. The tradeoff is stability. A marginally better plan isn't worth it if it scrambles loading plans, customer ETAs, or drivers' days. Minimal-change reoptimization addresses exactly that.
What Is a VRP Solver and How Do You Choose One?
A VRP solver is software that turns stops, fleet constraints, and travel times into optimized routes. The right choice depends on constraint coverage, map and traffic data, scale limits, and how you deploy and validate results in production.
What a solver needs as input
- Stop addresses or coordinates
- Depot locations
- Vehicle capacity and restrictions
- Service durations and time windows
- Driver shifts and skills
- Pickup-delivery pairs and priorities
- A travel-time or distance matrix
Bad inputs produce routes that are mathematically feasible but unusable: wrong addresses, optimistic service times, missing truck restrictions. In the US, for example, state height limits generally run from 13 ft 6 in to 14 ft, with exceptions on specific roads, per the FHWA.
Main categories of solvers
| Category | Examples | Tradeoff |
|---|---|---|
| In-house custom | Built on MILP engines such as Gurobi or CPLEX | Maximum flexibility, heavy modeling effort |
| Open-source libraries | OR-Tools, VROOM, jsprit, PyVRP, Timefold | Free, but you add constraints, maps, and infrastructure |
| API platforms | Hosted optimization APIs | Faster to deploy, limited by the vendor's model |
A solver built for textbook CVRP may fail a business needing truck restrictions, multiple depots, soft constraints, or dynamic updates.
Capabilities to evaluate
- Constraint coverage, including multiple depots and vehicle types
- Map and traffic quality, geocoding
- Large distance matrices (hosted APIs often cap matrix size)
- Dynamic reoptimization and route explainability
- Telematics and fleet integrations
- Latency, uptime, security, cloud or on-premise deployment
- Pricing model and scaling
How to validate solver output
- Replay historical routes and controlled scenarios.
- Check feasibility first.
- Compare distance, cost, utilization, on-time rate, and driver hours.
- Weigh planner overrides, stability, and customer experience, not one optimization score.
Example: NextBillion.ai
NextBillion.ai is an API-first routing platform for logistics, fleet, delivery, and field service. Against the criteria above, its documented capabilities include:
- 50+ hard and soft constraints, plus multi-depot dispatch and heterogeneous vehicles
- Custom map and road-attribute editing, and truck mode with vehicle dimensions
- Distance matrices up to 5,000 x 5,000 and optimization of up to 10,000 stops
- Re-optimization with minimal changes to the original itinerary
- Cloud-agnostic and on-premise deployment, with SOC 2 and ISO/IEC 27001 certifications
- Pricing per vehicle or order rather than per API call
Confirm current pricing, integrations, response times, and deployment options in its documentation before committing.
Why Does VRP Matter and How Is It Used in Practice?
Industries and use cases
Constraints shift by industry:
- Last-mile and food delivery: capacity and time windows
- Trucking: vehicle dimensions, hazmat rules, driver hours
- Field service and pest control: technician skills and appointments
- Waste collection: shift limits and depot-to-route structure
- NEMT and paratransit: wheelchair access, appointment matching, recurring trips
Healthcare adds more. A home health care review covers nurse assignment, schedules, and arrival times under regulatory constraints.
Business outcomes to measure
Tie the objective to measurable KPIs:
- Miles and fuel use
- Operating cost and vehicle utilization
- On-time rate and idle hours
- Fulfillment capacity
Treat large published savings as company-specific results, not industry benchmarks. UPS reported $320M saved by end-2015 from ORION, with a projected 100M fewer miles annually at full deployment.
Xpress Global Systems reported 13% fewer monthly miles and 35% lower operating costs with NextBillion.ai. Hawx Pest Control cut scheduling hours sharply.
A practical implementation workflow
- Pick one clearly defined planning problem.
- Clean address and stop data.
- Model your real constraints.
- Test against historical operations.
- Integrate dispatch, driver, fleet, and telematics workflows.
- Monitor after launch.
If planners or drivers keep overriding generated routes, a constraint is probably missing. Revise the model rather than blaming the users.
Conclusion
VRP isn't one formula. It's a family of problems shaped by fleet structure, customer commitments, vehicle restrictions, and changing conditions.
Start by defining your business objective. Then identify which variants you face, test algorithm and solver options on your own data, and judge results by operational KPIs as well as route quality on paper.
Frequently Asked Questions
How long does VRP last?
There's no fixed duration. A plan may cover a shift, a day, or a recurring horizon. Solve time depends on problem size, constraints, algorithm, and solver.
What is VRP for retirement?
That's a different use of the acronym in financial planning. This article uses VRP for Vehicle Routing Problem.
What is a VRP in business?
It's the process of assigning vehicles and stops and sequencing routes to optimize a business objective within operational constraints. Finance sources may use the acronym differently.
What is VRP in healthcare?
It supports home health visits, paratransit, medical deliveries, and NEMT. Models handle time windows, capacity, staff skills, recurring trips, and passenger needs.
What is the difference between VRP and TSP?
TSP sequences one tour. VRP assigns and sequences routes for several vehicles under constraints such as capacity, depots, and time windows.
Which algorithm is best for solving VRP?
None wins universally. Choose among exact, heuristic, metaheuristic, or hybrid methods based on problem size, constraint complexity, need for proven optimality, response time, and whether routes change dynamically.
