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 (like logistics, field service, waste collection, home care, public transport) are VRPs in disguise.
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.
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.
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.
Timefold's explicitly covers CVRP, VRPTW, SDVRP, VRPHF and DVRP. The Field Service Routing API and the Pickup & Delivery Routing API extend these into full operational problems.
Four families of approaches, and where each one fits.
The practical answer: production routing runs on metaheuristics initialized by construction heuristics. That is exactly how the Timefold Solver works. It combines construction heuristics with metaheuristics like Tabu Search, Simulated Annealing and Late Acceptance, then pairs them with an incremental score engine that evaluates every constraint in real time.
Sources: Timefold customer results; industry range per Springer / VRP literature.
Timefold's vehicle routing APIs ship with 100+ pre-configured constraints and stay extensible for the rules unique to your operation, without breaking as you scale from dozens to millions of scheduling 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 (think of a cancellation, a delay, or a new urgent order) Timefold replans in real time, resolving disruptions in under a second.
Every schedule shows trade-offs and impact, 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.
JSON in, JSON out. Stateless. Technology agnostic.
Less waste. More control. Teams that trust the plan.