VRP 容量限制 (CVRP)

問題描述

你經營一個配送中心，有 5 輛貨車，每輛最多載重 2000 公斤。今天有 20 個客戶需要送貨，每個客戶的貨物重量不同。如何規劃路線，讓所有車輛的總行駛距離最短？

from ortools.constraint_solver import routing_enums_pb2, pywrapcp
import numpy as np

def create_data_model():
    """隨機產生客戶資料"""
    np.random.seed(42)
    num_customers = 20
    
    # 隨機產生客戶位置（座標）
    locations = np.random.rand(num_customers + 1, 2) * 100
    
    # 距離矩陣
    dist_matrix = []
    for i in range(num_customers + 1):
        row = []
        for j in range(num_customers + 1):
            dx = locations[i][0] - locations[j][0]
            dy = locations[i][1] - locations[j][1]
            row.append(int(np.sqrt(dx*dx + dy*dy)))
        dist_matrix.append(row)
    
    # 每個客戶的需求量（隨機 100-500 公斤）
    demands = [0] + [np.random.randint(100, 500) for _ in range(num_customers)]
    
    data = {
        "distance_matrix": dist_matrix,
        "demands": demands,
        "vehicle_capacities": [2000] * 5,  # 5 輛車，每輛載重 2000
        "num_vehicles": 5,
        "depot": 0,
    }
    return data

def print_solution(data, manager, routing, solution):
    """輸出結果"""
    print(f"\n=== CVRP 求解結果 ===")
    total_distance = 0
    total_load = 0
    
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"車輛 {vehicle_id} 路線:\n"
        route_distance = 0
        route_load = 0
        
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route_load += data["demands"][node_index]
            plan_output += f" {node_index} (載重:{route_load}) →"
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id
            )
        
        node_index = manager.IndexToNode(index)
        plan_output += f" {node_index}\n"
        plan_output += f"  總距離: {route_distance}, 總載重: {route_load}/{data['vehicle_capacities'][vehicle_id]}\n"
        print(plan_output)
        total_distance += route_distance
        total_load += route_load
    
    print(f"所有車輛總距離: {total_distance}")
    print(f"所有車輛總載重: {total_load}")

def solve_cvrp():
    data = create_data_model()
    
    manager = pywrapcp.RoutingIndexManager(
        len(data["distance_matrix"]), data["num_vehicles"], data["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 data["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 data["demands"][from_node]
    
    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index, 0, data["vehicle_capacities"], True, "Capacity"
    )
    
    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 = 10
    
    solution = routing.SolveWithParameters(search_parameters)
    
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print("找不到解！")

if __name__ == "__main__":
    solve_cvrp()