The Vehicle Routing Problem, Explained
What the VRP is, why it's one of the hardest problems in logistics — and how modern fleet optimisation software solves it in seconds.
In This Guide
1. What Is the Vehicle Routing Problem?
The Vehicle Routing Problem (VRP) asks a deceptively simple question: given a fleet of vehicles and a set of stops to serve, what is the cheapest set of routes that visits every stop? "Cheapest" usually means least total distance or time. It's a generalisation of the classic Travelling Salesman Problem — but instead of one traveller, you have many vehicles, each with limits.
For a transport operator, the VRP is the daily reality of dispatch: which driver takes which jobs, and in what order, so the whole operation drives the fewest kilometres.
2. Why It's So Hard
The VRP is NP-hard. The number of possible route combinations grows factorially — add a few stops or another vehicle and the possibilities explode past anything a person, or even a brute-force computer, could check. That's why manual planning tops out quickly: a dispatcher can hold maybe a dozen jobs in their head, but the truly optimal plan is usually invisible to intuition.
3. The Main Variants
- Capacitated VRP (CVRP) — each vehicle has a limited capacity (seats, wheelchair spaces, weight).
- VRP with Time Windows (VRPTW) — each stop must be served within an appointment window.
- Pickup & Delivery (PDPTW) — jobs pair a pickup with a matching dropoff, which must happen in order on the same vehicle.
- Multi-depot & driver-shift variants — vehicles start from different locations and drivers have shift and fatigue limits.
Real passenger transport is usually a blend of all of these at once.
4. How Software Solves It
Because exact optimal solutions are impractical at scale, solvers use a pipeline of techniques: construction heuristics build a reasonable initial plan, local search improves it by swapping and reordering stops, and metaheuristics (simulated annealing, large neighbourhood search, genetic algorithms) escape dead-ends to find much better global solutions. Accurate road-network travel times — not straight-line distance — make the results usable in the real world.
5. From Theory to Your Fleet
You don't need a maths degree to benefit from decades of VRP research — it's built into modern dispatch tools. Waybill's fleet optimisation software solves the VRP for your jobs in one click, and its route optimisation explainer shows what's happening under the hood. For the bigger picture, see the smart transport optimisation guide.
The VRP has been studied since 1959. The good news for operators: you get the benefit of that research automatically — the algorithm handles the maths, you handle the exceptions.
Vehicle Routing Problem FAQs
The Vehicle Routing Problem (VRP) is the challenge of deciding the optimal set of routes for a fleet of vehicles to serve a set of stops at lowest total cost — usually distance or time. It generalises the Travelling Salesman Problem to multiple vehicles and adds real-world constraints like capacity and time windows.
The number of possible route combinations grows factorially with the number of stops and vehicles, so even a modest fleet has more possible plans than could ever be checked manually. Software uses heuristics and metaheuristics to find near-optimal solutions in seconds.
A practical solver handles vehicle capacity (CVRP), delivery or appointment time windows (VRPTW), pickup-and-delivery pairs, driver working hours, and vehicle-type matching such as wheelchair-accessible vehicles.
Fleet optimisation software is applied VRP: it takes your jobs, drivers, and constraints and solves the routing problem automatically, then lets you preview and apply the plan. Waybill's fleet optimisation does exactly this in one click.
Let the Algorithm Solve Your Routes
Waybill solves the Vehicle Routing Problem for your fleet in one click. Pay only for completed jobs — from $0.45.