The vehicle routing problem (VRP) asks a deceptively simple question: what is the cheapest set of routes for a fleet of vehicles to serve every customer? Answering it well is worth millions in fuel, time, and service quality, and it's one of the hardest problems in computer science. This page covers what the VRP is, why it's so hard, and how modern solvers crack it at scale
The vehicle routing problem (VRP) is a combinatorial optimization problem that asks: what is the optimal set of routes for a fleet of vehicles to travel in order to serve a given set of customers at the lowest possible cost? Typically, goods sit at one or more depots and must be delivered to customers who have placed orders, and each vehicle's route must start and end at its depot while every customer is served exactly once.
That single sentence hides enormous operational reality. "Cost" might mean distance, drive time, fuel, driver hours, or a blend of all of them. "Serve" might mean a delivery, a pickup, a repair visit, or a passenger transfer. And the "fleet" almost never behaves like a textbook: vehicles have different capacities, drivers have shifts and skills, and customers expect service inside narrow time windows.
The standard objective of the VRP is to minimize total route cost. In practice, most operations optimize for one or more of the following, often at the same time:
Real fleets rarely optimize for one number. The art of solving the VRP well is trading these goals off against each other in a way that reflects how the business actually makes money.
A VRP is defined as much by its constraints as by its objective. The most common ones:
Add a few of these together and the number of feasible plans explodes, which is exactly why the VRP is hard.
The VRP was introduced in 1959 by George Dantzig and John Ramser in their paper "The Truck Dispatching Problem," which applied it to petrol deliveries from a bulk terminal to service stations. It generalized the earlier Traveling Salesman Problem (TSP) from a single traveller to a fleet. More than six decades later it remains one of the most studied problems in operations research, precisely because so many real industries (logistics, field service, waste collection, home care, public transport) are VRPs in disguise. (Link "The Truck Dispatching Problem" to the Dantzig & Ramser 1959 paper.)
The VRP is a generalization of the traveling salesman problem. The TSP asks for the shortest single route that visits every location once and returns to the start: one traveller, no capacity, no time windows. The VRP keeps that sequencing challenge but layers on a whole fleet plus real-world constraints, namely which vehicle serves which customers, in what order, without breaking capacity, shift, or time-window rules. Put simply, a VRP is many interacting TSPs solved together under shared constraints, which is what makes it dramatically harder. (Link "traveling salesman problem" to the Timefold TSP page.)
The VRP is NP-hard: as you add stops, the number of possible route combinations grows factorially, far faster than any computer can enumerate. A route with just 10 stops already has over 3.6 million possible orderings. Push that to a few dozen stops across a fleet and the number of feasible plans exceeds the number of atoms in the observable universe. You cannot check every option, not today and not ever.
That is why brute force is off the table for anything but toy problems, and why real fleets rely on optimization algorithms (heuristics and metaheuristics) that find near-optimal routes in seconds rather than perfect routes in geological time. The best modern solvers reach solutions within roughly 0.5–1% of the theoretical optimum on problems with hundreds or thousands of stops, and vendors of routing tools routinely report 5–30% cost savings versus manual planning. (Link the 5–30% figure to a citable source such as the Toth & Vigo VRP reference.)
Real operations rarely match the textbook. These are the VRP variants you'll actually encounter, and Timefold's routing APIs are built to solve them all.
What it adds
Typical use case
Solvable with Timefold
CVRP - Capacitated VRP
Vehicles have a maximum load
Parcel and grocery distribution
Yes
VRPTW - VRP with Time Windows
Each stop must be served within a set interval
Appointment-based delivery, field service
Yes
VRPVRPPD / PDP Pickup & Delivery
Items collected at one stop, delivered to another, same vehicle
Courier, freight, waste, moving
Yes
MDVRP - Multi-Depot VRP
Multiple start/end depots
Regional distribution networks
Yes
HVRP / VRPHF - Heterogeneous Fleet
Mixed vehicle types and capacities
Mixed van/truck fleets
Yes
OVRP - Open VRP
Vehicles don't return to the depot
Contracted / third-party drivers
Yes
SDVRP - Split Delivery VRP
A customer's demand can be split across vehicles
Bulk / high-volume delivery
Yes
DVRP - Dynamic VRP
New orders arrive mid-route; routes replan live
On-demand delivery, dispatch
Yes
EVRP - Electric VRP
Battery range and charging stops
EV fleets
Yes (range / charging as constraints)
Four families of approaches, and where each one fits.
Hopw it works
Best for
Trade-off
Exact methods (branch-and-cut, column generation, MILP)
Mathematically guarantee the optimal solution
Small, well-defined problems (tens of stops)
Does not scale; impractical for real fleets
Construction heuristics (nearest neighbour, savings / Clarke-Wright, insertion)
Build a decent route quickly, step by step
Fast first solution / initialization
Result is good but not optimal
Metaheuristics (tabu search, simulated annealing, late acceptance, genetic algorithms, Large Neighbourhood Search)
Iteratively improve a solution, escaping local optima
Real-world VRPs at scale with many constraints
Near-optimal rather than provably optimal, which is what production needs
AI / learning-based (reinforcement learning, graph neural networks)
Learn routing policies from data
Emerging, very large or highly repetitive problems
Early-stage; hard to constrain and explain
for Timefold customers
vs. manual planning
To replan around a real-time disruption
per day
The Timefold Solver is a lightweight, embeddable constraint-satisfaction engine, the commercial successor to OptaPlanner with 20+ years of constraint-solving heritage and a proven track record on NP-hard problems. On the Timefold Platform, it's productized into REST APIs you can call without any solver expertise. Here's what that means in practice.
Timefold ships with 50+ pre-configured routing constraints and stays extensible for the rules unique to your operation, without breaking as you scale from dozens to millions of planning decisions. Capacity, time windows, skills, dependencies, SLAs, priorities: combine any of them and the solver optimizes around all of them at once.
Assign jobs first and plan routes second, and you lock in a schedule that ignores travel. Timefold solves both together, matching the right jobs to the right vehicles on the most efficient routes in a single optimization pass.
Plan the week, month, or year ahead, then continuously roll the horizon forward and optimize only what's new. When reality disrupts the plan, whether a cancellation, a delay, or a new urgent order, Timefold replans in real time, resolving disruptions in under a second.
Every plan shows the trade-offs it made and why, with real-world metrics. Planners and dispatchers see the reason behind each routing decision and can adjust constraint weights with confidence, instead of fighting a black box.
JSON in, JSON out. Stateless. Technology agnostic. Timefold slots into your existing systems over a stable REST API, and it never locks you to one map provider. Point it at any source of distance and travel-time data and the Platform handles pre-calculation, updates, throttling, and concurrency.
A sample of the routing constraints Timefold optimizes out of the box. All are configurable as hard, medium, or soft, with adjustable weights.
minimize travel time, mileage, and waiting.
respect load, weight, and volume on every route.
serve every stop when it's allowed.
match certifications, equipment, and customer preferences.
same vehicle, right order, every time.
prerequisites, mutual exclusions, same-vehicle rules.
honour contractual response times; make optional stops truly optional.
legal hours, start/end locations, rest and lunch.
several vehicles or people on the same visit.
A complete toolbox to make sscheduling and routing optimization succeed in production.
JSON in, JSON out. Stateless. Technology agnostic.
Timefold consumes the data you already have (stops, vehicles, constraints) as structured JSON over a REST API.
/ Fit Timefold into the way you work
/ Start with sample data or your own
Your routing challenge is sent through the API to the stateless constraint solver, which optimizes every constraint at once.
/ Stateless constraint solver
/ No solver expertise required
A fully optimized set of routes comes back as structured JSON, ready to render as-is or adjust as things change.
/ Replan in real time
/ Explainable, metric-backed results
The vehicle routing problem (VRP) is the challenge of finding the cheapest set of routes for a fleet of vehicles to serve a group of customers, while respecting real-world limits like vehicle capacity, delivery time windows, and driver shifts.
Yes. The VRP is NP-hard, meaning the number of possible solutions grows factorially with the number of stops, so no algorithm can guarantee the optimal answer quickly for realistic problem sizes. This is why production systems use heuristics and metaheuristics rather than exact methods.
The traveling salesman problem finds the shortest route for one vehicle visiting every location once. The VRP generalizes this to a whole fleet and adds constraints like capacity and time windows. A VRP is effectively many interacting TSPs solved together.
The most common variants are the Capacitated VRP (CVRP), VRP with Time Windows (VRPTW), Pickup & Delivery Problem (PDP/VRPPD), Multi-Depot VRP (MDVRP), Heterogeneous Fleet VRP (HVRP), Open VRP (OVRP), Split Delivery VRP (SDVRP), Dynamic VRP (DVRP), and Electric VRP (EVRP).
There are four families of methods: exact algorithms (optimal but don't scale), construction heuristics (fast, approximate), metaheuristics (near-optimal at scale, and the production standard), and emerging AI/learning methods. Most real systems combine construction heuristics with metaheuristics.
Routing tools typically report 5–30% cost savings versus manual planning. Timefold customers see an average 25% reduction in travel time after implementation.
Options range from open-source libraries (Google OR-Tools, VROOM) and commercial solvers (Hexaly, Timefold Solver) to full routing APIs. Timefold offers production-ready routing APIs, including Field Service Routing and Pickup & Delivery Routing (in preview), powered by the Timefold Solver.
Yes, this is the Dynamic VRP. Timefold supports continuous and real-time planning, replanning around disruptions like cancellations, delays, and new orders in under a second.
George Dantzig and John Ramser introduced it in 1959 in their paper "The Truck Dispatching Problem," applied to petrol deliveries.
Timefold solves routing and scheduling together, handles any combination of constraints at any scale, explains every decision, replans in real time, and integrates over a stateless REST API (JSON in, JSON out) without requiring any solver expertise.
Less travel. Lower cost. Routes your team can trust.