The classical decision for a distributor delivering daily from a single depot to 5-30 customers: how many vehicles to dispatch, which vehicle visits which customers, in what order — capacity not exceeded, total distance minimum. Academic name: Capacitated Vehicle Routing Problem (CVRP); the canonical ancestor of the VRP family, opened by Dantzig and Ramser in 1959.
In plain words
Sound familiar?
- We deliver daily from our depot to 30-100 customers — dealer distribution, B2B spare parts, food-and-beverage distribution, single-depot operation.
- Each customer's order is known in kg or m³; the dispatcher groups customers intuitively to avoid exceeding the 2-5 tonne vehicle capacity.
- Customers have no time windows or wide ones (accept between 08:00-18:00) — they receive at any hour.
- Two adjacent customers may be split across two different vehicles — the 'which vehicle in which zone this week' decision follows the previous plan.
- How many vehicles leave the depot in the morning depends on the dispatcher — some days 3 are enough, other days 5 go out, no clear rule.
- Fuel plus driver wages are 30-50% of operating expense, but we don't know how much km saving a route change would deliver.
- When a new customer is added, 'which vehicle does this fit on' is answered by gut feel, not by calculation.
Why it matters
How it's solved
Technical depth
How it's solved
Technical depthIn one sentence: Instead of running a separate depot-to-customer trip for each, compute how many km you save when two customers ride the same truck, merge the highest-savings pairs while capacity allows — runs in seconds; layer local search on top for higher quality.
CVRP is the canonical and oldest member of the VRP family in Operations Research (the discipline that uses math and computers to solve business decisions) literature. The 1959 paper “The Truck Dispatching Problem” is the field’s opening shot. Single depot, multiple vehicles, capacity constraint, customer demands; no time windows. Solution in three stages:
1. Modeling. Input data: depot location (single coordinate), customer locations and demand quantities (kg, m³, parcels — whatever unit, total must not exceed capacity), vehicle fleet (homogeneous — all the same capacity; heterogeneous — different capacities), distance matrix depot-to-customer and customer-to-customer (symmetric — A→B = B→A; asymmetric — can differ in cities with one-way streets). Constraints: each customer visited exactly once, every tour starts and ends at the depot, total demand on a tour does not exceed vehicle capacity. Optional extras: maximum tour length (driver shift), maximum customers per tour, open VRP (vehicle ends at last customer, no return — rented-vehicle scenarios), multi-depot VRP. Objective is usually total distance minimum (or fuel); vehicle-count minimum can be added secondarily.
2. Solver-driven decision. Three main approaches:
- Classical heuristic — Clarke-Wright Savings (1964): Each customer starts on its own tour (depot → customer → depot). The “savings” from merging two tours is computed: if A and B sit on separate tours but are merged, how much distance is saved? The largest-savings pair is merged whenever capacity allows. Computable without a computer; runs in seconds for 100-200 customers; typically lands within 5-10% of optimum. Sixty years on, it remains a practical starting point for mid-size operations.
- Exact MIP — branch-and-cut-and-price (branch-cut-price — tree search strengthened with column generation): yields optimum on 50-200 customers, but solve time stretches from minutes to hours. Suitable for weekly or seasonal planning — heavy for daily dynamic planning. MIP = Mixed-Integer Linear Programming (optimisation with some 0/1 variables and some continuous).
- Metaheuristics — 2-opt, Or-opt, ALNS (Adaptive Large Neighborhood Search — intelligent search method that steps the solution forward by ripping out and re-inserting chunks): applies local-improvement operators (“swap two edges”) on top of the Clarke-Wright output. Practical for 200-1000 customers; delivers within 2-5% of optimum in minutes.
Practical preference: under 50 customers — exact MIP (optimum guarantee); 50-200 customers — Clarke-Wright + 2-opt improvement; 200+ customers — ALNS or similar metaheuristic.
3. Field integration. Output is an ordered list pushed to a driver tablet or printout: “Vehicle 1 — 08:30 leave depot → customer A (1.2 t) → customer C (0.8 t) → customer F (1.5 t) → return to depot.” The order management system (ERP or standalone dispatch software) feeds the CVRP solver: customer order list, demand quantities, fleet state, depot stock. Computed in the evening or early morning; if new orders arrive during the day, rolling-horizon re-planning (typically 5-15 minutes). Monthly operations review: actual vs planned km, actual vs planned vehicle count, savings report.
Alternatives
Manual + spreadsheet + dispatcher's judgement
FreeZero license
Who it fits: 1-3 vehicles, 15-30 daily customers, fixed territory
- + Zero software cost
- + Dispatcher's experience leads
- + Quick adjustment by phone
- − Plan quality drops above 30-50 customers
- − No optimal-capacity-utilisation guarantee
- − Long onboarding for new dispatchers
- − No historical km/vehicle records
Local routing software (TR SMB market)
Enterprise10K-40K TRY setup + 3K-10K TRY/month subscription
Who it fits: 5-15 vehicles, 50-200 daily customers, single depot
- + TR address and map data integrated
- + Turkish UI, local support
- + Driver mobile app included
- − Engine is typically a simple savings-style or nearest-neighbor method; weak under heavy constraints
- − Weak on multi-depot or mixed-capacity fleets
- − Limited algorithm transparency — 'why this route' is hard to answer
International specialised routing software
Enterprise100-500 EUR/vehicle/month subscription or 1.5M-8M TRY/year license
Who it fits: 20-100 vehicles, multi-depot, heterogeneous fleet, heavy constraints
- + Mature: capacitated routing plus extensions (mixed-capacity fleet, depot-return-free tours, multi-depot) fully supported
- + Advanced search engines for large scale
- + Strong scenario comparison and simulation
- − High licence cost + 3-6 month rollout
- − Turkish-language support may be limited
- − Wide training programme for operations
Open-source solver + in-house build
Open SourceLicense free; in-house build 8-16 weeks or 300K-1M TRY consultancy
Who it fits: Distributor with a tech team, ERP integration required
- + No licence fee
- + Capacitated routing is well supported in open-source solvers
- + Savings method + local-improvement reference implementations are widely available
- − Requires internal optimisation and software expertise
- − 6-12 months to reach field-system maturity
- − Maintenance burden stays with the operator
Recommendation
Ask in the meeting
- What is the engine — a savings-style method, a solver with optimum guarantee, an advanced search engine, or only nearest-neighbor? In a demo with 50 customers, which method produces the result?
- Same-capacity fleet only, or are mixed-capacity vehicles also supported? In a mixed-capacity fleet, is the choice of vehicle-to-customer made by the engine?
- Are tours where the vehicle ends at the last customer (rented vehicles, no depot return) and multi-depot routing supported?
- How is the distance matrix computed — straight line, real road distance, or traffic-adjusted time? How was regional accuracy validated?
- When a new order arrives during the day, is the plan re-solved? In how many seconds does the updated route reach the driver?
- Are tour-length limits (e.g. max 6 hours or 300 km) and driver-shift constraints enforced at engine level, or post-filtered?
- In an 8-12 week pilot with real operational data, what kind of savings report can be produced versus prior manual planning?
- If we end the contract, in which open format (CSV, GeoJSON or similar) can we export customer location data, order history, route history and the distance matrix?
Technical details
Editor’s note
In plain speech this problem is called “route planning”, “distribution schedule” or “dispatch order”. In academic literature its name is the Capacitated Vehicle Routing Problem (CVRP) — the oldest and canonical member of the VRP family. Dantzig and Ramser opened operations research to this sub-discipline with their 1959 definition. The question you ask every morning — “how many vehicles, which vehicle to which customers, in what order, capacity not exceeded” — is the question academia has worked on for over 60 years.
This page should not be confused with VRPTW (#002): VRPTW adds a time window for each customer (“the shop is open only 09:00-12:00”). CVRP has no time windows — the customer is available all day. The difference is vegan delivery hours versus B2B flexible-time delivery. CVRP is easier (softer); VRPTW is more realistic but mathematically harder. If your customers truly have flexible receiving hours — dealer distribution, B2B spare parts, water-and-beverage distribution — this is your page. If you have tight time windows (e-commerce home delivery, cold chain), see #002.
Most-skipped point in the sector: the practical power of the Clarke-Wright savings algorithm. Developed in 1964 to be computed with paper and pencil before computers were available, this heuristic still lands within 5-10% of optimum on mid-size operations sixty years later, running in minutes. When a software vendor pitches a “proprietary heuristic engine” or “patented optimization motor”, ask them for a benchmark comparison on 50 customers against Clarke-Wright + 2-opt improvement. If the gap is under 2%, the extra licence fee is not worth it. Second skipped point: distance-matrix quality. Many tools use Euclidean (straight-line) distance; real urban road distance is 1.3-1.8× higher. Wrong distance means wrong route — the real road matrix must be tested in the pilot.
A step-by-step path for an SMB
Stage 1 — Measure first, plan second. For at least 4 weeks keep a table: per-vehicle daily km, customer count, capacity utilisation percentage (load / max), depot-to-depot tour duration, driver hours. Without this baseline you cannot tell which software delivers what result.
Stage 2 — Build the customer-demand table. For each customer: typical order quantity (kg or m³), address, coordinates, any constraint (vehicle-size limit — “large truck can’t enter”, manual unload time). In most SMBs this table lives only in the dispatcher’s head; writing it down alone yields 5-10% efficiency.
Stage 3 — Pilot. 6-10 weeks. Start with 1-3 vehicles. Success criterion in writing, before start: “in 60 days, total km -10%, capacity utilisation +5%, daily vehicle count -1.” If the bar is missed, pilot ends — keep the exit right in the contract.
Stage 4 — Rollout. 2-4 months to the full fleet. Driver training 1-2 weeks. Assign one “champion” driver per zone. Monthly operations review: actual vs planned km, capacity utilisation, cost per customer.
Risks — what can go wrong
- Demand-forecast drift. If a customer’s daily order is 20-50% off the plan, capacity is either half-empty or exceeded. Order cut-off and route-computation times must be as close as possible; rolling-horizon re-planning is essential.
- Mid-day vehicle breakdown. If a vehicle breaks down on the road, intuitive reassignment of remaining customers to other vehicles overshoots capacity or skips a customer. The software must support mid-day re-solve, producing an updated plan within 30 minutes.
- Customer time-demand emerging later. A customer saying “actually I only receive in the morning” breaks the CVRP model — the problem becomes VRPTW. As the customer set grows, once time-window count exceeds 10-20, migration to a VRPTW solver is needed.
- Single-supplier (TMS) lock-in. Without a contract clause for “annual standard-format export of customer location, order history, route history (CSV or GeoJSON)”, leaving the system means losing the distributor’s operational memory.
Solution method — technical view
Main approaches in the CVRP literature:
| Approach | Typical scale | Solve time | Guaranteed optimum? |
|---|---|---|---|
| Heuristic (dispatcher + rule) | 1-3 vehicles, 15-30 customers | instant | No, 50-80% optimum |
| Clarke-Wright savings (1964) | 50-200 customers | seconds-minutes | No, within 5-10% |
| Clarke-Wright + 2-opt / Or-opt | 50-300 customers | minutes | No, within 3-7% |
| Exact MIP — branch-and-cut-and-price | 50-200 customers | minutes-hours | Yes (at bounded scale) |
| ALNS metaheuristic | 200-1000 customers | minutes | No, within 2-5% |
| Column generation | 100-500 customers, multi-tour | hours | Practically near-optimum |
Formulation choice:
- 2-index formulation: A decision variable per edge (i, j). Easy to understand, but heavy on large scale due to subtour elimination constraints (SEC).
- 3-index formulation: A decision variable per (i, j, vehicle k). More flexible for heterogeneous fleet or open VRP extensions; variable count multiplies.
Objective function choices:
- Total distance minimum: Most common; fuel + maintenance focus.
- Total time minimum: When driver cost outweighs fuel.
- Vehicle count plus total distance (hierarchical): Vehicle count first, then distance — for fleet-shrink decisions.
- Fuel plus driver wage combined: Direct operating-cost objective.
Extensions — practical CVRP relatives:
- Heterogeneous Fleet VRP: Fleet with different capacities — pairs with “large vehicle can’t enter city centre” constraints.
- Open VRP: Vehicle ends at last customer, no return (rented vehicle, gig-economy driver).
- Multi-Depot VRP: Multiple depots; each customer is assigned to the most convenient depot.
- Distance-Constrained VRP: Tour length limited by driver shift.
- Asymmetric CVRP: A→B differs from B→A due to urban one-way streets.
VRPTW (#002), PDPTW (#046), DARP (#047) and TSP (#068) are close cousins. CVRP is the simplest and oldest member; understanding it is the first step to the others.
Academic references
Listed in the page frontmatter under sources.
Sources
- Dantzig, G. B. and Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. The paper that founded the VRP family — first definition as ‘TSP with capacity’.
- Clarke, G. and Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581. Classical savings algorithm — still a practical benchmark.
- Toth, P. and Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM-MOS. Canonical book of the VRP field.
- Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358. Historical and methods overview.
- Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P., Reis, M., Uchoa, E. and Werneck, R. F. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming, 106(3), 491-511. Modern exact CVRP algorithm.
- YÖK Thesis Center — keyword: ‘kapasiteli araç rotalama’ or ‘CVRP’ — 30+ theses from TR academia. tez.yok.gov.tr
Glossary
- Capacitated Vehicle Routing
- Designing minimum-cost vehicle routes that start and end at a single depot, visit each customer exactly once, with total demand per route not exceeding vehicle capacity.
- Clarke-Wright Savings
- Classical 1964 heuristic for the Capacitated Vehicle Routing Problem: start with each customer on its own route, iteratively merge pairs of routes that yield the largest 'savings' in distance, until capacity blocks further merges.
- VRP
- The decision of which vehicles, leaving from one or more depots, visit which customers in which order.
- MIP
- An optimization model where some decision variables are forced to be whole numbers (e.g. number of trucks, number of shifts).
Related problems
From One Node to Another — How Do I Compute the Shortest Path on a Weighted Graph?
For SMBs that need to compute the fastest or shortest route between two points: 10-50-vehicle field-service teams (plumbing, electrical, appliance repair), urban courier/parcel operations, or dispatch centres coordinating emergency response. Every day brings hundreds of 'how do I get from A to B fastest right now' questions; the answer shifts with traffic, road closures and vehicle type. A wrong route costs the technician one or two jobs missed for the day, the courier a late delivery, and the firm a customer. Manual or by-eye routing typically leaves 20-60 wasted minutes per vehicle per day on the table compared with a network-aware route calculation.
Multiple Plants, Multiple Customers — How Much Does Each Plant Ship to Each Customer to Minimise Total Freight?
For food, packaging or textile producers shipping weekly from 3-8 plants or regional warehouses to 20-100 customers. The weekly decision is: which plant ships how much to which customer, given fixed plant capacities, stated customer demands, and a different per-unit cost (distance + vehicle + contract terms) for each plant-customer pair. The goal is the lowest total freight bill across the network. A 'nearest plant' or 'we've always done it this way' habit typically leaves 10-20% extra fuel and vehicle cost on the table compared with a systematic allocation.
One Vehicle, Many Stops — In What Order Should I Visit Them All to Minimize Total Distance?
You run a field technician visiting 8-15 customers a day (HVAC, lift servicing, white-goods repair), a single-vehicle supplier tour by a sales rep, or a PCB drilling machine sequencing 500-5,000 holes. All of them face the same core call: given N points, in what order should a single vehicle or head visit each one and return to the start. Get the order wrong and a field service vehicle burns 80-200 TRY/day extra in fuel and driver hours, a PCB line takes 15-30% longer per part, and the last customer of the day misses their delivery window. At 50 stops, a hand-built sequence runs 20-40% above the true minimum; as the number of stops grows, the gap from intuitive ordering compounds.