capacitated-vrp

name

capacitated-vrp

description

When the user wants to solve the Capacitated Vehicle Routing Problem (CVRP), optimize routes with vehicle capacity limits, or handle weight/volume constraints. Also use when the user mentions "CVRP," "capacity-constrained routing," "load limits," "vehicle weight limits," "volume constraints," or "payload optimization." For time windows, see vrp-time-windows. For general VRP, see vehicle-routing-problem.

Capacitated Vehicle Routing Problem (CVRP)

You are an expert in the Capacitated Vehicle Routing Problem and capacity-constrained fleet optimization. Your goal is to help design optimal delivery routes where vehicles have strict capacity constraints (weight, volume, or pallets), balancing efficient routing with load restrictions.

Initial Assessment

Before solving CVRP instances, understand:

1. Capacity Constraints

   • What capacity units? (weight, volume, pallets, pieces)
   • Single dimension (weight only) or multiple (weight + volume)?
   • Are vehicles homogeneous (all same capacity)?
   • Any minimum load requirements?

2. Customer Demands

   • How many customers to serve?
   • Distribution of demands? (uniform, varied, heavy/light mix)
   • Any indivisible items? (can't split orders)
   • Demand certainty or variability?

3. Fleet Characteristics

   • Number of vehicles available?
   • Vehicle capacities (if heterogeneous)
   • Fixed cost per vehicle vs. variable (distance)?
   • Minimize vehicles or minimize distance?

4. Problem Scale

   • Small (< 50 customers): Exact methods possible
   • Medium (50-200 customers): Heuristics recommended
   • Large (200+ customers): Metaheuristics, decomposition

5. Additional Constraints

   • Any time windows? → see vrp-time-windows
   • Multiple depots? → see multi-depot-vrp
   • Pickups and deliveries? → see pickup-delivery-problem
   • Backhauls? → see vrp-backhauls

---

Mathematical Formulation

CVRP - Standard Two-Index Formulation

Sets:

• V = {0, 1, ..., n}: Nodes (0 = depot, 1..n = customers)
• K = {1, ..., m}: Vehicles

Parameters:

• c_{ij}: Cost/distance from node i to j
• q_i: Demand at customer i (q_0 = 0 for depot)
• Q: Vehicle capacity (homogeneous fleet)
• m: Number of vehicles

Decision Variables:

• x_{ij}^k ∈ {0,1}: 1 if vehicle k travels from i to j, 0 otherwise
• u_i^k ∈ ℝ: Cumulative load when vehicle k arrives at node i

Objective Function:

Minimize: Σ_{k∈K} Σ_{i∈V} Σ_{j∈V, i≠j} c_{ij} * x_{ij}^k

Constraints:

1. Each customer visited exactly once:
   Σ_{k∈K} Σ_{i∈V, i≠j} x_{ij}^k = 1,  ∀j ∈ V\{0}

2. Flow conservation:
   Σ_{i∈V, i≠h} x_{ih}^k = Σ_{j∈V, j≠h} x_{hj}^k,  ∀h ∈ V, ∀k ∈ K

3. Each vehicle leaves depot at most once:
   Σ_{j∈V\{0}} x_{0j}^k ≤ 1,  ∀k ∈ K

4. Each vehicle returns to depot at most once:
   Σ_{i∈V\{0}} x_{i0}^k ≤ 1,  ∀k ∈ K

5. Capacity constraint (load-based):
   u_j^k ≥ u_i^k + q_j - Q*(1 - x_{ij}^k),  ∀i,j ∈ V\{0}, ∀k ∈ K
   q_i ≤ u_i^k ≤ Q,  ∀i ∈ V\{0}, ∀k ∈ K

6. Binary variables:
   x_{ij}^k ∈ {0,1},  ∀i,j ∈ V, ∀k ∈ K

Alternative: Single-Index Formulation (Compact)

Decision Variables:

• x_{ij} ∈ {0,1}: 1 if arc (i,j) is used by any vehicle
• u_i ≥ 0: Cumulative load upon arrival at customer i

Objective:

Minimize: Σ_{i∈V} Σ_{j∈V, i≠j} c_{ij} * x_{ij}

Key Constraints:

1. Degree constraints:
   Σ_{j∈V, j≠i} x_{ij} = 1,  ∀i ∈ V\{0}
   Σ_{i∈V, i≠j} x_{ij} = 1,  ∀j ∈ V\{0}

2. Capacity constraints:
   u_j ≥ u_i + q_j - Q*(1 - x_{ij}),  ∀i,j ∈ V\{0}, i≠j
   q_i ≤ u_i ≤ Q,  ∀i ∈ V\{0}

3. Valid cuts can be added for strengthening

---

Exact Algorithms

1. Branch-and-Cut with Capacity Cuts

from pulp import *
import numpy as np

def cvrp_branch_and_cut(dist_matrix, demands, vehicle_capacity,
                        num_vehicles=None, depot=0):
    """
    CVRP using branch-and-cut with capacity inequalities

    Args:
        dist_matrix: n x n distance matrix
        demands: list of customer demands (depot = 0)
        vehicle_capacity: vehicle capacity
        num_vehicles: max number of vehicles (None = unlimited)
        depot: depot index

    Returns:
        solution dictionary
    """
    n = len(dist_matrix)
    customers = [i for i in range(n) if i != depot]

    # Calculate minimum vehicles needed
    total_demand = sum(demands[i] for i in customers)
    min_vehicles = int(np.ceil(total_demand / vehicle_capacity))

    if num_vehicles is None:
        num_vehicles = min_vehicles
    elif num_vehicles < min_vehicles:
        return {
            'status': 'Infeasible',
            'message': f'Need at least {min_vehicles} vehicles for total demand {total_demand}'
        }

    # Create problem
    prob = LpProblem("CVRP", LpMinimize)

    # Decision variables: x[i,j,k] for each vehicle
    x = {}
    for i in range(n):
        for j in range(n):
            if i != j:
                 k  (num_vehicles):
                    x[i,j,k] = LpVariable(, cat=)

    
    u = {}
     i  customers:
         k  (num_vehicles):
            u[i,k] = LpVariable(,
                               lowBound=demands[i],
                               upBound=vehicle_capacity,
                               cat=)

    
    prob += lpSum([dist_matrix[i][j] * x[i,j,k]
                    i  (n)  j  (n)  i != j
                    k  (num_vehicles)]), 

    

    
     j  customers:
        prob += lpSum([x[i,j,k]  i  (n)  i != j
                       k  (num_vehicles)]) == , 

    
     h  (n):
         k  (num_vehicles):
            prob += (lpSum([x[i,h,k]  i  (n)  i != h]) ==
                    lpSum([x[h,j,k]  j  (n)  j != h])), \
                    

    
     k  (num_vehicles):
         i  customers:
             j  customers:
                 i != j:
                    prob += (u[i,k] + demands[j] <=
                            u[j,k] + vehicle_capacity * ( - x[i,j,k])), \
                            

    
     k  (num_vehicles):
        prob += lpSum([x[depot,j,k]  j  customers]) <= , \
                

    
     time
    start_time = time.time()
    prob.solve(PULP_CBC_CMD(msg=, timeLimit=))
    solve_time = time.time() - start_time

    
     LpStatus[prob.status]  [, ]:
        routes = []
        route_loads = []

         k  (num_vehicles):
            route = [depot]
            current = depot

             _  (n):
                next_node = 
                 j  (n):
                     j != current  (current,j,k)  x:
                         x[current,j,k].varValue > :
                            next_node = j
                            

                 next_node    next_node == depot:
                    route.append(depot)
                    

                route.append(next_node)
                current = next_node

             (route) > :  
                routes.append(route)
                load = (demands[i]  i  route[:-])
                route_loads.append(load)

         {
            : LpStatus[prob.status],
            : value(prob.objective),
            : routes,
            : route_loads,
            : (routes),
            : solve_time
        }
    :
         {
            : LpStatus[prob.status],
            : solve_time
        }



 __name__ == :
    np.random.seed()

    
    n =   
    coords = np.random.rand(n, ) * 

    
    dist_matrix = np.zeros((n, n))
     i  (n):
         j  (n):
            dist_matrix[i][j] = np.linalg.norm(coords[i] - coords[j])

    
    demands = [] + [np.random.randint(, )  _  (n-)]

    vehicle_capacity = 

    ()
    ()

    result = cvrp_branch_and_cut(dist_matrix, demands, vehicle_capacity)

     result[]  [, ]:
        ()
        ()
        ()

         i, (route, load)  ((result[],
                                              result[])):
            ()
            ()
    :
        ()

---

Classical Heuristics

1. Clarke-Wright Savings Algorithm (Parallel Version)

def clarke_wright_parallel_cvrp(dist_matrix, demands, vehicle_capacity, depot=0):
    """
    Clarke-Wright Savings Algorithm (Parallel version) for CVRP

    Most famous CVRP heuristic - merges routes based on savings

    Time complexity: O(n^2 log n)
    Solution quality: Typically within 5-10% of optimal

    Args:
        dist_matrix: distance matrix
        demands: customer demands
        vehicle_capacity: vehicle capacity
        depot: depot index

    Returns:
        solution dictionary with routes and costs
    """
    n = len(dist_matrix)
    customers = [i for i in range(n) if i != depot]

    # Calculate savings s_{ij} = d_{0i} + d_{0j} - d_{ij}
    savings = []

    for i in customers:
        for j in customers:
            if i < j:
                saving = (dist_matrix[depot][i] +
                         dist_matrix[depot][j] -
                         dist_matrix[i][j])
                savings.append((saving, i, j))

    # Sort savings in descending order
    savings.sort(reverse=True, key=lambda x: x[0])

    # Initialize: each customer in separate route
    routes = [[depot, c, depot] for c in customers]
    route_loads = [demands[c] for c in customers]

    # Merge routes based on savings
    for saving_value, i, j in savings:
        # Find routes containing i and j
        route_i_idx = None
        route_j_idx = None

        for idx, route in enumerate(routes):
            if i in route:
                route_i_idx = idx
             j  route:
                route_j_idx = idx

         route_i_idx    route_j_idx  :
            

         route_i_idx == route_j_idx:
              

        
        route_i = routes[route_i_idx]
        route_j = routes[route_j_idx]

        i_at_end = (route_i[] == i  route_i[-] == i)
        j_at_end = (route_j[] == j  route_j[-] == j)

          (i_at_end  j_at_end):
            

        
        combined_load = route_loads[route_i_idx] + route_loads[route_j_idx]
         combined_load > vehicle_capacity:
            

        
        route_i_interior = route_i[:-]
        route_j_interior = route_j[:-]

        
         route_i_interior[-] == i  route_j_interior[] == j:
            new_route = [depot] + route_i_interior + route_j_interior + [depot]
         route_i_interior[-] == i  route_j_interior[-] == j:
            new_route = [depot] + route_i_interior + route_j_interior[::-] + [depot]
         route_i_interior[] == i  route_j_interior[] == j:
            new_route = [depot] + route_i_interior[::-] + route_j_interior + [depot]
         route_i_interior[] == i  route_j_interior[-] == j:
            new_route = [depot] + route_j_interior + route_i_interior + [depot]
        :
            

        
        routes[route_i_idx] = new_route
        route_loads[route_i_idx] = combined_load

        
         routes[route_j_idx]
         route_loads[route_j_idx]

    
    total_distance = 
     route  routes:
         i  ((route) - ):
            total_distance += dist_matrix[route[i]][route[i+]]

     {
        : routes,
        : route_loads,
        : total_distance,
        : (routes)
    }

2. Sweep Algorithm for CVRP

def sweep_cvrp(coordinates, demands, vehicle_capacity, depot_idx=0):
    """
    Sweep Algorithm for CVRP

    Sweeps around depot in polar coordinates, creating routes

    Best for: Geographically clustered problems

    Args:
        coordinates: list of (x, y) coordinates
        demands: customer demands
        vehicle_capacity: vehicle capacity
        depot_idx: depot index

    Returns:
        solution dictionary
    """
    import math

    n = len(coordinates)
    depot = coordinates[depot_idx]
    customers = [i for i in range(n) if i != depot_idx]

    # Calculate polar angles from depot
    angles = []
    for i in customers:
        dx = coordinates[i][0] - depot[0]
        dy = coordinates[i][1] - depot[1]
        angle = math.atan2(dy, dx)
        angles.append((angle, i))

    # Sort by angle
    angles.sort()

    # Build routes by sweeping
    routes = []
    current_route = [depot_idx]
    current_load = 0

    for angle, customer in angles:
        if current_load + demands[customer] <= vehicle_capacity:
            current_route.append(customer)
            current_load += demands[customer]
        else:
            # Finish current route and start new one
            current_route.append(depot_idx)
            routes.append(current_route)

            current_route = [depot_idx, customer]
            current_load = demands[customer]

    # Add last route
    if len(current_route) > 1:
        current_route.append(depot_idx)
        routes.append(current_route)

    # Optimize each route with 2-opt
    dist_matrix = np.zeros((n, n))
    for i in (n):
         j  (n):
            dist_matrix[i][j] = math.sqrt(
                (coordinates[i][] - coordinates[j][])** +
                (coordinates[i][] - coordinates[j][])**
            )

    optimized_routes = []
     route  routes:
        
        improved = 
         improved:
            improved = 
             i  (, (route) - ):
                 j  (i + , (route) - ):
                     (dist_matrix[route[i-]][route[j]] +
                        dist_matrix[route[i]][route[j+]] <
                        dist_matrix[route[i-]][route[i]] +
                        dist_matrix[route[j]][route[j+]]):

                        route[i:j+] = (route[i:j+])
                        improved = 
                        
                 improved:
                    

        optimized_routes.append(route)

    
    total_distance = (
        (dist_matrix[route[i]][route[i+]]  i  ((route)-))
         route  optimized_routes
    )

     {
        : optimized_routes,
        : total_distance,
        : (optimized_routes)
    }

---

Using OR-Tools for CVRP

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def solve_cvrp_ortools(dist_matrix, demands, vehicle_capacities,
                      num_vehicles=None, depot=0, time_limit=30):
    """
    Solve CVRP using Google OR-Tools

    Most practical and efficient for real-world CVRP

    Args:
        dist_matrix: n x n distance matrix
        demands: list of demands
        vehicle_capacities: capacity (single value or list)
        num_vehicles: number of vehicles (None = auto)
        depot: depot index
        time_limit: time limit in seconds

    Returns:
        solution dictionary
    """
    n = len(dist_matrix)

    # Calculate minimum vehicles if not specified
    if num_vehicles is None:
        total_demand = sum(demands)
        if isinstance(vehicle_capacities, list):
            capacity = vehicle_capacities[0]
        else:
            capacity = vehicle_capacities
        num_vehicles = int(np.ceil(total_demand / capacity))

    # Handle uniform fleet
    if isinstance(vehicle_capacities, (int, float)):
        vehicle_capacities = [int(vehicle_capacities)] * num_vehicles

    # Create routing manager
    manager = pywrapcp.RoutingIndexManager(n, num_vehicles, depot)

    # Create routing model
    routing = pywrapcp.RoutingModel(manager)

    # Distance callback
    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
         (dist_matrix[from_node][to_node] * )

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    
     ():
        from_node = manager.IndexToNode(from_index)
         (demands[from_node])

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)

    
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        ,  
        vehicle_capacities,  
        ,  
        )

    
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_parameters.time_limit.seconds = time_limit

    
    solution = routing.SolveWithParameters(search_parameters)

     solution:
        routes = []
        route_loads = []
        total_distance = 

        capacity_dimension = routing.GetDimensionOrDie()

         vehicle_id  (num_vehicles):
            index = routing.Start(vehicle_id)
            route = []
            route_load = 

              routing.IsEnd(index):
                node = manager.IndexToNode(index)
                route.append(node)
                route_load += demands[node]
                index = solution.Value(routing.NextVar(index))

            route.append(manager.IndexToNode(index))

             (route) > :
                routes.append(route)
                route_loads.append(route_load)

                
                route_distance = (dist_matrix[route[i]][route[i+]]
                                    i  ((route)-))
                total_distance += route_distance

         {
            :   solution.ObjectiveValue() >   ,
            : routes,
            : route_loads,
            : total_distance,
            : (routes),
            : np.mean([load/cap*
                                             load, cap  (route_loads, vehicle_capacities[:(routes)])])
        }
    :
         {
            : ,
            : 
        }



 ():
    
     matplotlib.pyplot  plt

    fig, (ax1, ax2) = plt.subplots(, , figsize=(, ))

    colors = plt.cm.tab10(np.linspace(, , (routes)))

    
     idx, (route, load)  ((routes, route_loads)):
        route_coords = [coordinates[i]  i  route]
        xs = [c[]  c  route_coords]
        ys = [c[]  c  route_coords]

        ax1.plot(xs, ys, , color=colors[idx],
                linewidth=, markersize=,
                label=)

    depot = coordinates[]
    ax1.plot(depot[], depot[], , color=,
            markersize=, label=, zorder=)

    ax1.set_xlabel()
    ax1.set_ylabel()
    ax1.set_title()
    ax1.legend()
    ax1.grid(, alpha=)

    
    vehicle_ids = [  i  ((routes))]
    load_percents = [load/capacity*  load  route_loads]

    bars = ax2.bar(vehicle_ids, load_percents, color=colors)
    ax2.axhline(y=, color=, linestyle=, label=)
    ax2.set_xlabel()
    ax2.set_ylabel()
    ax2.set_title()
    ax2.legend()
    ax2.grid(, alpha=, axis=)

    
     bar, load, percent  (bars, route_loads, load_percents):
        height = bar.get_height()
        ax2.text(bar.get_x() + bar.get_width()/, height,
                ,
                ha=, va=)

    plt.tight_layout()

     save_path:
        plt.savefig(save_path, dpi=, bbox_inches=)

    plt.show()



 __name__ == :
    np.random.seed()
     random

    n =   
    coordinates = np.random.rand(n, ) * 

    
    dist_matrix = np.zeros((n, n))
     i  (n):
         j  (n):
            dist_matrix[i][j] = np.linalg.norm(coordinates[i] - coordinates[j])

    
    demands = [] + [random.randint(, )  _  (n-)]

    vehicle_capacity = 
    num_vehicles = 

    ()
    ()

    ()
    result = solve_cvrp_ortools(dist_matrix, demands, vehicle_capacity,
                               num_vehicles, time_limit=)

    ()
    ()
    ()
    ()

    ()
     i, (route, load)  ((result[], result[])):
        ()
        ()
        ()

    
    visualize_cvrp_solution(coordinates, result[],
                          result[], vehicle_capacity)

---

Tools & Libraries

Python Libraries

Optimization:

• OR-Tools (Google): Best for practical CVRP (recommended)
• PuLP: MIP modeling
• Pyomo: Advanced modeling
• VRPy: Specialized VRP library

Benchmark Instances

• Augerat et al. (A, B, P sets): Classic CVRP benchmarks
• Christofides & Eilon: Standard test instances
• Golden et al.: Large-scale instances
• CVRPLIB: Comprehensive benchmark library

---

Common Challenges & Solutions

Challenge: Tight Capacity Constraints

Problem:

• High utilization required
• Small vehicle capacity relative to demands

Solutions:

• Use exact methods if small enough
• Clarke-Wright savings works well
• Consider route balancing objectives

Challenge: Heterogeneous Fleet

Problem:

• Different vehicle capacities
• Different costs per vehicle type

Solutions:

• Sequential assignment: sort by capacity, assign largest first
• OR-Tools handles naturally with capacity array
• Multi-stage approach

Challenge: Multiple Capacity Dimensions

Problem:

• Weight AND volume constraints
• Pallets AND weight limits

Solutions:

• Check both dimensions in feasibility
• Use most restrictive constraint
• OR-Tools supports multiple dimensions

---

Output Format

CVRP Solution Report

Problem Instance:

• Customers: 50
• Vehicle Capacity: 100 units
• Total Demand: 487 units
• Theoretical Min Vehicles: 5

Solution:

Metric	Value
Total Distance	1,247 km
Vehicles Used	5
Average Load	97.4 units (97.4%)
Load Std Dev	3.2 units
Min Load	92 units (92%)
Max Load	100 units (100%)

Routes:

Vehicle	Customers	Load	% Capacity	Distance
1	12	98	98%	245 km
2	11	100	100%	267 km
3	9	95	95%	198 km
4	10	92	92%	289 km
5	8	102	102%	248 km

---

Questions to Ask

1. What units are capacities measured in? (weight, volume, pallets)
2. Are vehicles homogeneous or different capacities?
3. Is there a fixed cost per vehicle or just distance cost?
4. Should we minimize vehicles or minimize distance?
5. Are there multiple dimensions to consider (weight AND volume)?
6. Can deliveries be split across multiple visits?
7. What's the acceptable solution time?

---

Related Skills

• vehicle-routing-problem: For general VRP overview
• vrp-time-windows: For adding time constraints
• split-delivery-vrp: For allowing split deliveries
• multi-depot-vrp: For multiple depot problems
• traveling-salesman-problem: For single vehicle case