Large-Scale VRP

🔥 Vibe Prompt

"Implement Clarke-Wright Savings Algorithm for 50 customers. Merge routes based on savings value."

def clarke_wright_savings(dist_matrix, demands, capacity, depot=0):
    num_nodes = len(dist_matrix)
    routes = [[i] for i in range(num_nodes) if i != depot]
    
    savings = []
    for i in range(1, num_nodes):
        for j in range(i + 1, num_nodes):
            saving = dist_matrix[depot][i] + dist_matrix[depot][j] - dist_matrix[i][j]
            if saving > 0:
                savings.append((saving, i, j))
    
    savings.sort(reverse=True, key=lambda x: x[0])
    
    node_to_route = {}
    for idx, route in enumerate(routes):
        for node in route:
            node_to_route[node] = idx
    
    for saving, i, j in savings:
        route_i = node_to_route[i]
        route_j = node_to_route[j]
        if route_i == route_j:
            continue
        merged_demand = sum(demands[node] for node in routes[route_i] + routes[route_j])
        if merged_demand > capacity:
            continue
        # Merge logic...
        routes[route_i] = routes[route_i] + routes[route_j]
        routes[route_j] = []
        for node in routes[route_i]:
            node_to_route[node] = route_i
    
    return [r for r in routes if r]

For 50 customers, Clarke-Wright finds a near-optimal solution in milliseconds!

Chapter Summary

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

Implementation Example

Basic Example

# This section provides a complete implementation example

Steps

Setup: Configure development environment
Data: Prepare required data
Implementation: Build core functionality
Testing: Verify correctness
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

Large-Scale VRP Challenges

As the number of customers grows, VRP becomes exponentially harder to solve optimally:

| Customers | Possible Routes | Solution Approach | |-----------|----------------|-------------------| | 10 | ~10! = 3.6M | Exact (OR-Tools CP-SAT) | | 50 | ~50! impossible | Heuristics (Savings) | | 100 | ~100! impossible | Metaheuristics (GA, SA) | | 500 | 500! impossible | Decomposition + metaheuristics | | 1000+ | Out of reach | Large Neighborhood Search |

Decomposition Strategies

Cluster-First, Route-Second

Cluster customers into groups (K-Means, DBSCAN)
Route each cluster with TSP solver
Assign clusters to vehicles

from sklearn.cluster import KMeans

def cluster_first_route_second(customers, num_vehicles):
    """
    Large-scale VRP heuristic:
    1. Cluster customers into groups
    2. Route each group with nearest neighbor
    """
    coords = [[c.x, c.y] for c in customers]
    kmeans = KMeans(n_clusters=num_vehicles, random_state=42)
    clusters = kmeans.fit_predict(coords)
    
    routes = []
    for v in range(num_vehicles):
        cluster_customers = [i for i, c in enumerate(clusters) if c == v]
        if not cluster_customers:
            continue
        # Simple TSP: nearest neighbor within cluster
        route = nearest_neighbor_tsp(cluster_customers, customers)
        routes.append(route)
    return routes

Sweep Algorithm

def sweep_algorithm(depot, customers, capacity):
    """
    Sweep algorithm for large-scale CVRP:
    1. Calculate polar angle of each customer from depot
    2. Sort by angle
    3. Sweep around, adding customers until capacity reached
    4. Start new route when capacity exceeded
    """
    import math
    
    # Calculate angles
    customer_data = []
    for i, c in enumerate(customers):
        angle = math.atan2(c.y - depot.y, c.x - depot.x)
        customer_data.append((angle, i, c.demand))
    customer_data.sort(key=lambda x: x[0])  # Sort by angle
    
    routes = []
    current_route = []
    current_load = 0
    
    for angle, idx, demand in customer_data:
        if current_load + demand <= capacity:
            current_route.append(idx)
            current_load += demand
        else:
            if current_route:
                routes.append(current_route)
            current_route = [idx]
            current_load = demand
    
    if current_route:
        routes.append(current_route)
    return routes


# Example
depot = Customer(id=0, demand=0, x=0, y=0)
customers = [
    Customer(id=1, demand=10, x=5, y=5),
    Customer(id=2, demand=15, x=-3, y=8),
    Customer(id=3, demand=12, x=-5, y=-4),
    Customer(id=4, demand=8, x=6, y=-3),
    Customer(id=5, demand=20, x=2, y=10),
    Customer(id=6, demand=5, x=-2, y=-6),
    Customer(id=7, demand=18, x=8, y=4),
    Customer(id=8, demand=6, x=-8, y=2),
    Customer(id=9, demand=14, x=4, y=-7),
    Customer(id=10, demand=10, x=-6, y=-2),
]

routes = sweep_algorithm(depot, customers, capacity=40)
for i, route in enumerate(routes):
    print(f"Route {i+1}: customers {route}, "
          f"load {sum(customers[c].demand for c in route)}")

Metaheuristics for Large-Scale VRP

| Metaheuristic | Quality | Speed | Implementation | |--------------|---------|-------|---------------| | Genetic Algorithm | Very good | Medium | Complex | | Simulated Annealing | Good | Medium | Moderate | | Tabu Search | Very good | Medium | Complex | | Large Neighborhood Search | Excellent | Slow | Very complex | | Ant Colony Optimization | Very good | Slow | Complex | | Adaptive LNS | Excellent | Medium | Very complex |

Summary

Large-scale VRP requires specialized approaches. Use cluster-first-route-second for very large instances, the sweep algorithm for medium-large instances, and metaheuristics for the best quality on moderately-sized problems.

Key takeaways:

Exact solvers work only for < 50 customers
Sweep algorithm: sort by angle from depot, scoop up customers
Cluster-first-route-second: K-Means + TSP per cluster
Metaheuristics (GA, SA, LNS) give best quality for medium instances
Large Neighborhood Search is state-of-the-art for VRP
Decompose large problems into smaller subproblems
The sweep algorithm is fast and gives reasonable routs

What's Next: VRPTW

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