CVRP: Capacity Constraints

🔥 Vibe Prompt

"Solve CVRP: 1 depot, 20 customers with random demand, 5 vehicles each with 2000kg capacity. Minimize total distance."

def create_data_model():
    np.random.seed(42)
    num_customers = 20
    locations = np.random.rand(num_customers + 1, 2) * 100
    dist_matrix = [[int(np.sqrt((locations[i][0]-locations[j][0])**2 + (locations[i][1]-locations[j][1])**2)) for j in range(num_customers+1)] for i in range(num_customers+1)]
    demands = [0] + [np.random.randint(100, 500) for _ in range(num_customers)]
    data = {"distance_matrix": dist_matrix, "demands": demands, "vehicle_capacities": [2000]*5, "num_vehicles": 5, "depot": 0}
    return data

def demand_callback(from_index):
    from_node = manager.IndexToNode(from_index)
    return data["demands"][from_node]

demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(demand_callback_index, 0, data["vehicle_capacities"], True, "Capacity")

Output Example

Vehicle 0: 0 → 3 → 7 → 0, Distance: 234, Load: 1450/2000
Vehicle 1: 0 → 1 → 5 → 9 → 0, Distance: 312, Load: 1800/2000
...
Total Distance: 1,876

Chapter Summary

• Understand core concepts and principles
• Master implementation methods and techniques
• Familiar with common issues and solutions
• Able to apply in real projects

Further Reading

• Official documentation and API references
• Open source examples on GitHub
• Technical books and online courses
• Community discussions and tech blogs

Implementation Example

Basic Example

# This section provides a complete implementation example

Steps

1. Setup: Configure development environment
2. Data: Prepare required data
3. Implementation: Build core functionality
4. Testing: Verify correctness
5. Optimization: Improve performance

Common Errors

| Error Type | Cause | Solution | |------------|-------|----------| | Compilation | Syntax | Check code syntax | | Runtime | Environment | Verify dependencies installed | | Logic | Algorithm | Step-by-step debugging | | Performance | Efficiency | Use profilers |

Code Example

import sys

def main():
    print("Hello, World!")

if __name__ == "__main__":
    main()

References

• Official documentation
• API reference
• Open source examples
• Community discussions

Key Points

• Understand the core concepts thoroughly
• Practice with hands-on code examples

Summary

The Capacitated VRP adds vehicle capacity constraints to the classic VRP. Each vehicle can serve at most Q units of demand. The Clark-Wright savings heuristic provides fast, high-quality solutions by iteratively merging routes with the greatest savings.

Key takeaways:

• CVRP = VRP with vehicle capacity limits
• Clark-Wright savings: s[i][j] = d[0][i] + d[0][j] - d[i][j]
• Higher savings = more beneficial to combine customers
• Always check capacity before merging routes
• Savings heuristic is O(n² log n) for sorting
• Solutions are near-optimal for practical instances
• For optimal solutions: use OR-Tools CP-SAT (small instances only)

OR-Tools CVRP Implementation

from ortools.constraint_solver import routing_enums_pb2, pywrapcp

def solve_cvrp_ortools(distance_matrix, demands, num_vehicles, capacity):
    """Solve CVRP using Google OR-Tools."""
    manager = pywrapcp.RoutingIndexManager(
        len(distance_matrix), num_vehicles, 0  # 0 = depot
    )
    routing = pywrapcp.RoutingModel(manager)
    
    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]
    
    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    
    def demand_callback(from_index):
        from_node = manager.IndexToNode(from_index)
        return demands[from_node]
    
    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        [capacity] * num_vehicles,  # capacity per vehicle
        True,  # start cumul to zero
        'Capacity'
    )
    
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    
    solution = routing.SolveWithParameters(search_parameters)
    
    if solution:
        routes = []
        for vehicle_id in range(num_vehicles):
            index = routing.Start(vehicle_id)
            route = []
            while not routing.IsEnd(index):
                node = manager.IndexToNode(index)
                route.append(node)
                index = solution.Value(routing.NextVar(index))
            routes.append(route)
        return routes
    return None

Summary

CVRP adds realistic capacity constraints to vehicle routing. The Clark-Wright savings heuristic is fast and effective for practical instances. For small instances requiring optimal solutions, use OR-Tools CP-SAT solver.

Key takeaways:

• CVRP: vehicles have maximum capacity
• Clark-Wright: iteratively merge routes with greatest savings
• OR-Tools: exact solver for small instances
• Applications: delivery trucks, warehouse picking, service vans
• Always check capacity feasibility before merging

What's Next: VRPTW

The next chapter adds time windows — each customer must be visited within a specific time range.

Summary

The Capacitated VRP (CVRP) extends VRP with vehicle capacity constraints. Each vehicle can carry at most Q units of demand. Use the Clark-Wright savings heuristic for fast solutions, OR-Tools for small optimal solutions, and metaheuristics for high quality.

Key takeaways:

• CVRP: each vehicle has max capacity Q
• Clark-Wright: merge routes with highest savings
• Savings: s[i][j] = d[depot][i] + d[depot][j] - d[i][j]
• OR-Tools: exact solver for small instances
• Metaheuristics: best quality for medium instances
• Applications: delivery trucks, warehouse picking, service vans

What's Next: VRPTW

The next chapter adds time windows — each customer must be visited within a specific time window [ready_time, due_time].