Clarke-Wright Savings Algorithm

gistfile1.txt

function clarke_wright_savings():
    // Initial solution: direct routes (depot -> center -> depot)
    routes = [[i+1] for i in range(n)]  // +1 because depot is 0
    
    // Calculate savings for each pair of centers
    savings = []
    for i in range(n):
        for j in range(i+1, n):
            // Savings formula: d[0,i] + d[0,j] - d[i,j]
            saving = distance_matrix[0, i+1] + distance_matrix[0, j+1] - distance_matrix[i+1, j+1]
            savings.append((i, j, saving))
    
    // Sort savings in descending order
    sort savings by saving value (descending)
    
    // Track route membership and position
    center_to_route = {i+1: i for i in range(n)}
    position = {i+1: 'both' for i in range(n)}  // 'both' means both start and end (singleton route)
    
    // Merge routes based on savings if feasible
    for (i, j, saving) in savings:
        center_i = i + 1
        center_j = j + 1
        route_i = center_to_route[center_i]
        route_j = center_to_route[center_j]
        
        // Skip if centers already in same route
        if route_i == route_j: continue
        
        // Check if centers are at start/end of their routes
        valid_merge = false
        if position[center_i] in ['both', 'end'] and position[center_j] in ['both', 'start']:
            valid_merge = true
            merge_end_i_start_j = true
        elif position[center_j] in ['both', 'end'] and position[center_i] in ['both', 'start']:
            valid_merge = true
            merge_end_j_start_i = true
        
        if valid_merge:
            // Calculate total demand of merged route
            total_demand = sum of demands for all centers in both routes
            
            // Only merge if capacity constraint satisfied
            if total_demand <= vehicle_capacity:
                // Merge routes
                if merge_end_i_start_j:
                    new_route = routes[route_i] + routes[route_j]
                else:
                    new_route = routes[route_j] + routes[route_i]
                
                // Update route information
                routes[route_i] = new_route
                routes[route_j] = []
                
                // Update tracking information
                for c in routes[route_i]:
                    center_to_route[c] = route_i
                
                // Update positions
                position[new_route[0]] = 'start'
                position[new_route[-1]] = 'end'
                for c in new_route[1:-1]:
                    position[c] = 'middle'
    
    // Remove empty routes and convert indices to actual center values
    final_routes = []
    for route in routes:
        if route:
            final_route = [centers[c-1] for c in route]
            final_routes.append(final_route)
    
    return final_routes