Capacitated Vehicle Routing Problem: What It Is and How AI Solves It

Your route optimization just scheduled a technician for 14 hours of work in an 8-hour shift. The route looks efficient — minimal drive time, perfect geographic clustering. But the math doesn’t work. The last three jobs will never get completed.

This is the capacitated vehicle routing problem in action. Perfect routes mean nothing if your team can’t physically complete them.

The capacitated vehicle routing problem (CVRP) is a routing challenge that determines optimal routes while respecting real-world capacity limits — shift hours, job caps, certifications, equipment availability, and physical constraints like tank capacity or cargo weight. Most routing tools optimize distance first, then discover that the schedule is impossible. CVRP flips this: check capacity first, then optimize.

This guide covers what CVRP actually means for field service, the four types of capacity that matter, and how modern AI dispatching solves it without requiring a PhD in operations research.

What Is the Capacitated Vehicle Routing Problem?

The capacitated vehicle routing problem adds real-world limits to route optimization. Basic VRP (Vehicle Routing Problem) finds the shortest routes. CVRP finds the shortest routes that your team can actually complete.

“Capacitated” simply means “with capacity limits.” Those limits include shift hours (a tech can only work 8 hours, not 14), job count (6 jobs per day maximum, not 12), certifications (only EPA-certified techs can handle refrigerant), equipment (one bucket truck shared across three crews), and physical capacity (a 600-gallon tank that fills up after 8 stops).

Every CVRP scenario has four components:

Component	What It Means	Example
Starting location	Where techs begin	Home address or central depot
Customer demands	What each job requires	2-hour install, EPA cert needed, morning window
Technician constraints	What limits each tech	8-hour shift, max 6 jobs, Licensed_Plumber
Travel times	Real driving between stops	22 minutes accounting for traffic

Why it matters at scale: a 50-job routing scenario has more possible solutions than atoms in the observable universe. Manual scheduling can’t evaluate even a fraction of these combinations — let alone while respecting capacity constraints simultaneously.

This is exactly why field service optimization requires algorithmic approaches rather than manual dispatch boards.

The Four Types of Capacity in Field Service

Capacity isn’t just about how much a truck can carry. In field service, four distinct types of capacity determine whether a schedule is executable.

1. Temporal Capacity — When a Tech Can Work

Shift hours, breaks, overtime limits, and end-of-day constraints. An 8-hour shift from 7:30 AM to 5:00 PM with a 1-hour lunch means 7 productive hours — not 8. Without temporal checks, a system might schedule 12 hours of work in an 8-hour shift. The route looks efficient. The last three jobs never happen.

What to configure: shift start/end times, mandatory break periods (lunch, short breaks), overtime allowance per tech (yes/no, max minutes), end-of-day buffer for return drive, and cost multiplier for overtime hours (typically 1.5x). See overtime management for how the AI handles this automatically.

2. Workload Capacity — How Much a Tech Should Handle

Maximum jobs per day prevents burnout and quality degradation. A tech with 12 jobs rushes through every appointment. A tech with 4 sits idle half the day. Different day types need different caps — a local day might allow 6 jobs, while a travel-heavy day with 2-hour drives between zones should cap at 3–4.

What to configure: max jobs per normal day, max jobs on travel days, and max consecutive work days for multi-day operations. See workload balancing with AI and preventing technician burnout for the full picture.

3. Skill Capacity — Who Can Do the Work

When only 2 out of 5 techs hold EPA 608 certification and 15 jobs require refrigerant handling, those 2 techs become a bottleneck. Skill capacity means the system can’t just assign the closest tech — it must assign a qualified one. A non-certified tech dispatched to a refrigerant job arrives, can’t legally perform the work, and leaves. The customer waits. The company faces compliance risk.

What to configure: required skills per job type, certification tracking per tech, and skill tags for situational requirements. See certifications and qualifications in AI dispatch and skill-based technician assignment for configuration details.

4. Equipment Capacity — What’s Available to Share

Expensive equipment shared across crews creates scheduling dependencies. Three tree crews sharing one bucket truck can’t all use it simultaneously. The system must sequence jobs with handoff buffers so Crew A finishes with it before Crew B needs it.

Three handoff strategies:

• Direct — Tech A drives equipment to Tech B, best when nearby
• Depot — equipment returns to base, next tech picks up, best for overnight handoffs
• Meet halfway — both techs travel to a midpoint, best when far apart

Buffer time between handoffs (typically 20–30 minutes) prevents the second crew from standing idle waiting. See equipment-based scheduling for how to configure this in practice.

Hard Constraints vs. Soft Constraints

Not all capacity limits are equal. Understanding the difference determines whether your schedules are safe or just optimistic.

Hard constraints — cannot be violated. The system eliminates any assignment that breaks these: shift boundaries when overtime isn’t allowed, skill certifications (EPA 608, electrical licenses, gas permits), mandatory breaks for labor law compliance, and equipment availability (can’t schedule a bucket truck that’s already assigned). A tech without EPA certification assigned to refrigerant work isn’t a “preference violation” — it’s a compliance violation. Hard constraints make it impossible.

Soft constraints — can flex with penalties. The system tries to honor these but can bend when necessary: preferred max jobs per day, preferred technician assignments, drive time preferences, and workload balance targets. A tech getting a 7th job when the preferred max is 6 isn’t ideal — but it’s not illegal. The optimizer adds a penalty score and tries to avoid it, but the schedule remains feasible.

If violating it would…	Constraint type
Break the law or void insurance	Hard
Create a safety risk	Hard
Violate a customer SLA	Hard (usually)
Annoy a technician	Soft
Increase costs slightly	Soft
Reduce customer satisfaction	Soft

For a complete breakdown of how the AI classifies and resolves constraint conflicts, see the guide on how AI dispatching algorithms work. For SLA-specific constraint handling, see SLA-aware scheduling.

The Capacity-First Approach

Most routing tools work backwards. They optimize first, then discover capacity violations. This creates a frustrating loop: the system generates an “optimal” route, the dispatcher notices impossible assignments, manual fixes are required, the route is no longer optimal, and the cycle repeats every morning.

The right way reverses this. A capacity-first architecture runs a rapid feasibility check that eliminates capacity-violating assignments in milliseconds, builds a constraint-based skeleton that respects all hard constraints, runs deep optimization to improve routes while maintaining compliance, and applies continuous monitoring that reshuffles throughout the day without violating limits.

The key difference: impossible assignments are eliminated before optimization begins. Every generated schedule is both efficient and executable. No more generating beautiful routes that fall apart by 10 AM.

This is the foundation of AI-powered scheduling — and it’s how real-time schedule adjustments stay compliant even as the day changes. For a full walkthrough of this pipeline, see AI route optimization explained.

Multi-Day CVRP: When One Day Isn’t Enough

What happens when job volume exceeds your team’s daily capacity? Traditional CVRP assumes single-day operations. Field service often doesn’t work that way.

Automatic overflow handling. When daily capacity is exceeded, the system creates multi-day assignments automatically. With 2 technicians, a max of 2 jobs each per day, and 28 jobs to schedule: day capacity is 4 jobs/day, 24 jobs overflow, and the system extends to 7 days automatically with each tech getting daily assignments across the full period. No manual intervention. No spreadsheet planning. See multi-day job scheduling for how this works inside FieldCamp.

Day-chaining for geographic continuity. Each subsequent day starts where the previous day ended — preventing techs from backtracking across service areas.

• Day 0: tech starts in Dallas, works Dallas jobs, ends in Fort Worth
• Day 1: starts in Fort Worth, works toward Austin, ends in Austin
• Day 2: starts in Austin, works San Antonio, heads back toward Dallas

Strategy	Avg Daily Drive	Weekly Total
Single-day (return home daily)	2.8 hours	14 hours
Multi-day chaining	2.1 hours	10.5 hours
Savings	0.7 hrs/day	3.5 hrs/week

Day-chaining supports extended operations up to 14 consecutive days — enabling regional deployments where techs work across territories without daily home returns. For planning these longer horizons, see long-range scheduling and multi-day scheduling.

Real-World CVRP Scenarios

Equipment bottleneck: tree service with shared bucket truck. 3 crews, 1 bucket truck, 8 jobs requiring it.

• Without CVRP: all 3 crews get assigned bucket truck jobs simultaneously — two crews arrive on site unable to work, failed jobs, wasted drive time, angry customers.
• With CVRP: jobs sequenced across crews with handoff buffers. Crew A takes jobs 1–3, 30-minute handoff, Crew B takes jobs 4–5, handoff, Crew C takes jobs 6–8. Zero conflicts.

Skill bottleneck: HVAC with limited certifications. 5 techs, 40 jobs, 15 require EPA 608 certification, only 2 techs certified.

• Without CVRP, non-certified techs get assigned refrigerant jobs because they’re closer to compliance violations and failed appointments.
• With CVRP, the feasibility check eliminates every non-certified assignment instantly. 15 refrigerant jobs go to 2 certified techs. The remaining 25 are spread across all 5 by location. If 2 certified techs can’t handle all 15 in one day, the system creates multi-day assignments automatically.

This is a common scenario in HVAC dispatching — where certification requirements and geographic spread create exactly the kind of constraint conflict CVRP is built to resolve.

Temporal violation: plumber with an impossible schedule. 1 plumber, 6 jobs, 14 hours of service time, 8-hour shift, no overtime.

• Without CVRP: route looks perfect — minimal drive time, great clustering — but 14 hours doesn’t fit in 8. The last 3 jobs get missed. The dispatcher apologizes all afternoon.
• With CVRP, the feasibility check catches it immediately. Total time needed: 14 hrs service + 2 hrs travel + 1 hr lunch = 17 hours. The system redistributes excess jobs to other plumbers or creates multi-day assignments. No impossible schedules reach the dispatch board.

For how the system handles mid-day disruptions like this in real time, see mid-day job insertions and dynamic rerouting.