大規模 VRP 與啟發式演算法

VRP 是 NP-Hard 問題。當客戶數量超過 100 個時，OR-Tools 的 exact solver 可能需要數小時才能找到最佳解。實務上，我們使用啟發式演算法來找到「夠好」的解。

Clarke-Wright 節省法 (Savings Algorithm)

這是實務上最常用的 VRP 啟發式演算法，由 Clarke 與 Wright 在 1964 年提出。

import numpy as np

def clarke_wright_savings(dist_matrix, demands, capacity, depot=0):
    """
    Clarke-Wright 節省法
    
    核心概念：合併兩條路線能節省的距離 = d(0,i) + d(0,j) - d(i,j)
    """
    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  # 超過容量
        
        # 合併路線
        # 確保 i 在末端，j 在開端
        if routes[route_i][-1] == i and routes[route_j][0] == j:
            new_route = routes[route_i] + routes[route_j]
        elif routes[route_i][0] == i and routes[route_j][-1] == j:
            new_route = routes[route_j] + routes[route_i]
        elif routes[route_i][-1] == i and routes[route_j][-1] == j:
            new_route = routes[route_i] + list(reversed(routes[route_j]))
        elif routes[route_i][0] == i and routes[route_j][0] == j:
            new_route = list(reversed(routes[route_j])) + routes[route_i]
        else:
            continue
        
        # 合併
        routes[route_i] = new_route
        routes[route_j] = []
        
        # 更新映射
        for node in new_route:
            node_to_route[node] = route_i
    
    # 過濾空路線
    return [r for r in routes if r]

# 測試
np.random.seed(42)
n = 50  # 50 個客戶
locations = np.random.rand(n + 1, 2) * 100

# 距離矩陣
dist = np.zeros((n + 1, n + 1))
for i in range(n + 1):
    for j in range(n + 1):
        dist[i][j] = np.sqrt((locations[i][0]-locations[j][0])**2 +
                             (locations[i][1]-locations[j][1])**2)

demands = [0] + list(np.random.randint(50, 200, n))
capacity = 500

print(f"\n=== Clarke-Wright 節省法 ===")
print(f"客戶數: {n}, 車輛容量: {capacity}")

routes = clarke_wright_savings(dist, demands, capacity)

print(f"\n路線數量: {len(routes)}")
for idx, route in enumerate(routes):
    route_dist = sum(dist[node][route[(i+1) % len(route)]] 
                    for i, node in enumerate(route))
    route_demand = sum(demands[node] for node in route)
    print(f"路線 {idx}: {route} (距離: {route_dist:.1f}, 載重: {route_demand})")