Vehicle Routing Problem: Practical Guide for Data-Driven Decisions

The Vehicle Routing Problem asks how to split a set of stops among vehicles, and in what order each vehicle should visit them, so the total cost is as low as possible. This guide shows the idea on a small made-up map first, then covers the choices that matter in practice: which objective to pick, which method to use, and which constraints and data problems break real routes.

Worked Example (Simulated): Nearest Neighbour, Then 2-opt

All stops below are made-up points, not a client. We make 40 stops at random places around one depot. One van must visit every stop and return. We try two ways to plan the route. First, nearest neighbour: from where the van is, always drive to the closest stop left. It is quick, but it can leave long gaps at the end. Second, 2-opt: take that route and flip a stretch of it whenever the flip makes the trip shorter. We stop when no flip helps.

import numpy as np
rng = np.random.default_rng(5)
depot = np.array([0.0, 0.0])
stops = rng.uniform(-20, 20, size=(40, 2))  # made-up stop coordinates, in km
pts = np.vstack([depot, stops])
def length(route):
    p = pts[route + [0]]
    return np.sum(np.linalg.norm(np.diff(p, axis=0), axis=1))
def nearest_neighbour():
    left = set(range(1, len(pts)))
    route = [0]
    while left:
        last = pts[route[-1]]
        nxt = min(left, key=lambda i: np.linalg.norm(pts[i] - last))
        route.append(nxt)
        left.remove(nxt)
    return route
def two_opt(route):
    best = route[:]
    improved = True
    while improved:
        improved = False
        for i in range(1, len(best) - 1):
            for j in range(i + 1, len(best)):
                cand = best[:i] + best[i:j + 1][::-1] + best[j + 1:]
                if length(cand) < length(best) - 1e-9:
                    best = cand
                    improved = True
    return best
start = nearest_neighbour()
better = two_opt(start)
print("40 made-up stops, one depot, one van")
print(f"nearest neighbour: {length(start):.1f} km")
print(f"after 2-opt:       {length(better):.1f} km")
print(f"saved: {100 * (1 - length(better) / length(start)):.1f}%")
rand = [length([0] + list(rng.permutation(np.arange(1, len(pts)))))
        for _ in range(200)]
print(f"random order, mean of 200: {np.mean(rand):.1f} km")

Output:

40 made-up stops, one depot, one van
nearest neighbour: 243.2 km
after 2-opt:       218.3 km
saved: 10.2%
random order, mean of 200: 862.9 km

Result: The random orders averaged 862.9 km, so the nearest-neighbour route (243.2 km) is far shorter. The 2-opt step cut it to 218.3 km, which is 10.2% shorter. The lesson is the order of the work: build a quick route, then improve it. A common plan uses two steps. Quick rules make the first routes. Then small route changes make them better. The example above does this.

Limit: This is one made-up map, so the exact numbers will differ on yours. 2-opt is a heuristic: it can stop at a route that is not the best one. With real vans you also add load limits and time windows, and the improving step has to respect them.

What the Vehicle Routing Problem Asks

The Vehicle Routing Problem sounds academic, but it is practical: you have vehicles with capacity limits, customers with delivery requirements, and constraints like time windows and driver shifts. Your job is to find routes that minimize cost while meeting all constraints. The textbook makes this sound like a pure math problem. It is not. The choices below decide whether the routes work in practice.

Choosing Your VRP Approach: A Decision Framework

Let's look at this as a system, not isolated parts. Your VRP approach should match your operational reality and cost structure. Here's how to choose.

When to Minimize Total Distance

Use this approach when variable costs (fuel, maintenance, driver overtime) are your primary expense and you have operational flexibility. Best for:

• Bulk delivery operations - food distribution, beverage delivery, industrial supplies
• Recurring route structures - most stops are the same week to week
• Flexible time windows - customers accept deliveries within wide windows or no specific windows at all
• High fuel costs - when fuel is a large share of operating costs

The data isn't for blame - it's for learning. Track your actual vs. planned distance weekly. If the gap is large, you have either data quality issues (wrong travel times) or compliance issues (drivers aren't following routes).

When to Minimize Fleet Size

Use this when fixed costs (vehicle leases, salaries, insurance) dominate and you need to maximize asset utilization. Best for:

• Service operations - field technicians, home healthcare, meter reading
• Tight time windows - customer commitments require narrow appointment slots
• High per-vehicle costs - specialized vehicles or skilled labor where each unit is expensive to run
• Capacity constraints - you can handle more volume but are vehicle-limited

Variation is the enemy of quality. Let's measure it. Track your daily utilization by vehicle. If you see consistent patterns (some vehicles at 90% utilization, others at 50%), your territory assignment needs work before you optimize routes.

When to Minimize Maximum Route Duration

A third approach that doesn't get enough attention: minimize the longest route, not the total. This creates more balanced workloads. Best for:

• Driver retention issues - when unfair workload distribution causes turnover
• Compliance operations - where all routes must finish within shift limits (no overtime allowed)
• Time-sensitive goods - fresh food, medical supplies where delivery time matters
• Union environments - where workload equity is contractually important

This objective sacrifices total efficiency for fairness. You may drive more total miles than with pure distance minimization, but you avoid the very long route that creates driver burnout.

The Algorithm Decision: Exact vs. Heuristic vs. Hybrid

Once you've chosen your objective, you need to pick a solution method. This is where most guides get too academic. Let's focus on operational impact.

Exact Algorithms: When You Need Guaranteed Optimal

Exact methods (branch-and-bound, cutting plane algorithms, integer programming) can prove the mathematically best solution when the solver runs to completion. With a time limit they may stop with a gap between the best route found and the best bound. They're valuable when:

• Small problem size - few enough stops that the solver finishes in a useful time
• High stakes - the cost difference between good and optimal is significant (thousands of dollars per day)
• Legal requirements - regulatory fairness requirements demand provably optimal solutions
• Benchmark establishment - you want to know the theoretical best to compare heuristics against

The limitation is computational time. Exact algorithms scale poorly - run time grows quickly as stops are added, so a problem that solves in seconds can take hours when it is much larger. The reason is that each added stop multiplies the number of possible routes, so an exact solve can take much longer.

Heuristic Algorithms: Fast, Good-Enough Solutions

Heuristics (Clarke-Wright savings, sweep algorithm, genetic algorithms, simulated annealing) don't guarantee optimal solutions but find very good solutions quickly. They're the right choice for:

• Large-scale operations - many stops daily
• Dynamic routing - when new orders arrive throughout the day requiring re-optimization
• Time pressure - you need routes generated in minutes, not hours
• Good-enough economics - a good solution is fine if it is available much faster

The Clarke-Wright savings heuristic is a classic example. The algorithm works by calculating the "savings" from combining two routes into one. Start with each customer on their own route (obviously inefficient). Then iteratively merge routes where the savings is highest.

For customers i and j, the savings from combining their routes is:
s(i,j) = distance(depot, i) + distance(depot, j) - distance(i, j)

Say customer A is 20 miles from the depot and customer B is 22 miles from the depot, but they are only 5 miles from each other. Combining them saves 37 miles (20 + 22 - 5). The algorithm sorts all possible pairs by savings and merges greedily while respecting capacity and time constraints.

Hybrid Approaches

A hybrid uses a heuristic for initial route construction, then local search for improvement. This two-phase approach combines speed with quality. The worked example above is a small hybrid.

Phase 1 - Route Construction: Use a fast heuristic (nearest neighbor, sweep algorithm) to create feasible routes quickly. This is fast, even for many stops.

Phase 2 - Route Improvement: Apply local search operators to improve the initial solution:

• 2-opt: Remove two edges from a route and reconnect in a different way (eliminates crossing paths)
• Relocate: Move a single stop from one route to another if it improves the objective
• Exchange: Swap stops between routes to reduce total cost
• Or-opt: Relocate a sequence of 2-3 consecutive stops to a different position

These operators run iteratively until no further improvement is found. Small, consistent improvements compound over time.

The Constraints That Make or Break Real-World VRP

Academic VRP has simple constraints: vehicle capacity, maybe time windows. Real operations have messy constraints that dramatically affect solution quality. Let's measure them.

Time Windows Cost Efficiency

Adding time windows can increase total distance, because the windows limit which stop can come next. Tighter windows usually leave less room to shorten the route. Why? Time windows limit the sequence flexibility the algorithm needs to find efficient routes.

This is a business decision, not just an operational one. Are narrow windows worth the extra driving? It depends on your customer value. For some services, yes. For others, wider windows may be enough.

Here's the operational insight: if you must offer narrow windows, cluster them geographically. Don't promise narrow windows scattered across your service area. Offer them only in zones where you have dense demand. This gives the algorithm room to sequence efficiently within the cluster.

Heterogeneous Fleet: The Hidden Complexity

Most VRP implementations assume identical vehicles. Real fleets are mixed: different capacities, different costs, different capabilities. This adds a vehicle-type assignment problem on top of routing.

Fleets often mix large trucks, medium trucks and small vans, each with its own capacity, cost per mile and access limits. The naive approach: assign customers to the cheapest vehicle that fits their demand. This fails because it ignores routing synergies. Sometimes using a more expensive vehicle enables a better overall route structure.

A common answer is a two-stage approach: first assign customers to vehicle types based on capacity and access constraints, then optimize routes within each fleet type. This is not globally optimal, but it is tractable.

Driver Skills and Preferences: The Human Factor

Here's where pure optimization meets operational reality. Drivers aren't interchangeable. Some have special certifications (hazmat, forklift). Some have customer relationships that matter. Some know shortcuts the algorithm doesn't.

If a model ignores this, drivers may reject routes that violate their domain knowledge. One fix is to add driver-customer affinity scores to the model. Customers who specifically requested a driver got assigned to them with a preference weight. The algorithm could override for efficiency, but it paid a penalty.

This is systems thinking: the people executing the routes are part of the system. Optimize around them, not over them. Small, consistent improvements compound over time when drivers trust the system.

Data Quality: The Problem You Can't Algorithm Away

You can have the world's best VRP algorithm and still get terrible routes if your data is wrong. Let's look at the critical data elements and their failure modes.

Geocoding Accuracy

Every address must be converted to coordinates (latitude/longitude). If those coordinates are wrong, the algorithm makes wrong decisions. Where's the bottleneck in this process? It's addresses that geocode to the center of a zip code instead of the actual building.

A simple check is to plot a sample of customers on a map and look for errors, such as customers marked in the middle of a lake, in the wrong city, or at zip code centroids. A high error rate makes routes nonsense.

The fix: use a professional geocoding service (Google Maps API, Here Maps) and manually check any low-confidence matches. It's boring data work, but it matters more than your algorithm choice.

Service Time Estimates: The Compounding Error

How long do you spend at each stop? This seems simple but varies wildly. A residential delivery might take 2 minutes (drop at door). A commercial delivery might take 25 minutes (unload, get signature, restock, paperwork).

If you underestimate service time by 5 minutes per stop, and your route has 20 stops, you're off by 100 minutes - nearly two hours. The algorithm thinks a route fits in an 8-hour shift, but it actually takes 10 hours.

The lesson: segment your service times by customer or task type, and build in buffer for variance. For critical time-window operations, plan on a high percentile of the time, not the average. Variation is the enemy of quality.

Travel Time Matrices: The Real-World Routing Challenge

You need to know how long it takes to drive from every location to every other location. For 200 customers, that is 40,000 ordered pairs. You can't use straight-line distance - real roads don't work that way.

Three approaches:

• Euclidean distance: Straight-line distance times a circuity factor. Fast, but inaccurate in complex road networks or urban areas.
• API-based routing: Query Google Maps or similar for actual driving times. Accurate, but expensive (costs add up for large matrices) and slow (API rate limits).
• OSRM or local routing engine: Self-hosted routing using OpenStreetMap data. Accurate, fast, free, but requires technical setup.

A common compromise is API routing for the initial matrix, then caching it and updating it on a schedule. For daily re-optimization, use the cached matrix. This balances accuracy with cost.

The critical detail: time-of-day matters. Travel time from A to B at 6 AM is not the same as 4 PM. If your operations span rush hour, you need time-dependent travel times. This makes the problem significantly harder (now you're optimizing route sequence AND departure times), but ignoring it leads to late deliveries.

Implementation: How to Actually Deploy VRP in Your Operation

Let's look at this as a system, not isolated parts. You have an algorithm that generates good routes on paper. Making them work in practice requires process design.

Phase 1: Check Against History (Weeks 1-4)

Don't optimize live operations immediately. Start by running the algorithm on historical data and comparing against what actually happened.

1. Week 1: Pull 4 weeks of historical delivery data (stops, times, vehicle assignments)
2. Week 2: Run your VRP algorithm on that historical demand and compare recommended routes vs. actual routes
3. Week 3: Identify the gap - where does the algorithm save distance/time/vehicles? Where does it fail to match reality?
4. Week 4: Adjust constraints (add service time buffers, tighten time windows, add driver preferences) until the algorithm produces operable routes

A typical finding is a constraint you had not encoded, such as an informal limit on stops per route. Add it as a hard constraint and re-run. Small, consistent improvements compound over time.

Phase 2: Pilot (Weeks 5-8)

Choose 2-4 routes to optimize while leaving others on the existing system. This creates a controlled experiment.

• Select routes that represent typical operations (not outliers)
• Get driver buy-in by explaining the test and asking for feedback
• Track metrics daily: distance driven, time to complete, stops served, late deliveries, driver satisfaction
• Compare pilot routes against control routes

A pilot often exposes wrong inputs, such as drive times that are too short for rural roads. Adjust the travel time matrix and re-run.

Phase 3: Rollout (Weeks 9-20)

Add 5-10 new routes every week to the optimized system. This gradual rollout lets you catch issues before they affect the entire fleet.

Monitor compliance: what percentage of drivers are following the recommended routes? If compliance is low, you have a problem:

• Routes are infeasible - something is wrong with your data or constraints
• Routes are unfair - some drivers got much harder assignments than others
• Routes ignore driver knowledge - the algorithm misses practical realities drivers know
• Change management failed - drivers don't understand why changes are happening

Where's the bottleneck in this process? Usually it's feedback loops. You need a way for drivers to flag route issues same-day, and you need to respond within 24 hours. A simple form works: "Route X has a problem at stop Y" with a dropdown of issue types (time window impossible, customer access problem, traffic always backed up here). Review it daily and adjust.

When VRP Alone Isn't Enough: Dynamic and Stochastic Extensions

The classic VRP assumes perfect information: you know all customers, all demands, all constraints before you plan. Real operations are messier.

Dynamic VRP: When Orders Arrive Throughout the Day

Same-day delivery, on-demand services, emergency repairs - demand arrives dynamically. You can't plan all routes at 6 AM because you don't know who needs service at 2 PM.

Dynamic VRP requires re-optimization as new orders arrive. The approach:

1. Initial routing: Generate routes for all known demand at start of day
2. Insertion heuristics: When a new order arrives, try to insert it into an existing route with minimal distance increase
3. Re-optimization threshold: When accumulated new orders reach a threshold (e.g., 10% of daily volume), re-optimize all remaining stops
4. Slack management: Build buffer time into initial routes so new orders can be accommodated without exceeding shift length

One way to do this is to plan most routes at the start of the day from orders already placed, reserve one or two vehicles with no initial route to take new orders, and re-optimize the remaining stops across all incomplete routes on a regular schedule.

Stochastic VRP: Planning Under Uncertainty

You know you'll serve roughly 200 customers tomorrow, but you're not sure exactly which 200. Customer demand is probabilistic. This is common in field service (equipment failures are random), retail (delivery orders fluctuate), and healthcare (patient needs vary).

Stochastic VRP builds routes that perform well across multiple demand scenarios. Instead of optimizing for one specific customer set, you optimize for expected performance across a distribution of possible customer sets.

When only some of your regular customers are served each day, and which ones varies, a two-stage approach can help:

1. Strategic routes: Define high-level route territories that work well regardless of specific daily demand
2. Tactical optimization: Once actual demand is known (by 10 AM), optimize exact sequences within each territory

This hybrid planning can reduce the reactive chaos of daily route building while avoiding the fragility of static routes that break when demand shifts.

The Metrics That Matter: Measuring VRP Success

The data isn't for blame - it's for learning. Track these metrics to know if your VRP implementation is working.

Primary Efficiency Metrics

• Total distance per day/week: The most direct measure of routing efficiency. Track trend over time, not just absolute value.
• Distance per stop: Normalizes for demand variation. Should be stable even as daily stop count fluctuates.
• Fleet utilization: Average stops per vehicle, average hours per vehicle. Detects underutilized capacity.
• On-time performance: Percentage of deliveries within promised time windows. The constraint you optimized around.

Operational Health Metrics

• Route compliance: Percentage of drivers following recommended routes. Low compliance indicates problems.
• Plan vs. actual gap: Difference between algorithm's predicted route time/distance and actual results. Should be small.
• Failed deliveries: Stops that couldn't be completed due to route infeasibility. Should be near zero.
• Driver overtime: Hours worked beyond planned shift. Suggests service time underestimates or unrealistic routes.

Financial Impact Metrics

• Cost per delivery: Total route cost divided by stops served. Captures efficiency in dollar terms.
• Vehicle cost savings: If you reduced fleet size, multiply eliminated vehicles by annual operating cost.
• Fuel cost reduction: Distance savings times fuel price per mile.
• Labor productivity: Stops per driver hour. Detects whether efficiency gains come from routing or faster service.

Publishing these metrics weekly in a dashboard visible to all drivers can build trust, especially when drivers see the savings they helped create.