VRP 基礎與問題定義

從 TSP 到 VRP

旅行推銷員問題 (TSP) 是所有路徑問題的基礎：一個推銷員要拜訪 N 個城市，每個城市只能去一次，最後回到起點，如何安排順序讓總距離最短？

VRP 是 TSP 的延伸：你有多個推銷員（車輛），每個推銷員有自己的容量限制，如何分配路線讓總成本最低？

安裝 OR-Tools

pip install ortools

使用 OR-Tools Routing 求解

from ortools.constraint_solver import routing_enums_pb2, pywrapcp

def create_data_model():
    """建立距離矩陣"""
    data = {}
    # 9 個地點（0 = 倉庫，1-8 = 客戶）
    data["distance_matrix"] = [
        [0, 548, 776, 696, 582, 274, 502, 194, 308],
        [548, 0, 684, 308, 194, 502, 730, 354, 696],
        [776, 684, 0, 992, 878, 502, 274, 810, 468],
        [696, 308, 992, 0, 114, 650, 878, 502, 844],
        [582, 194, 878, 114, 0, 536, 764, 328, 674],
        [274, 502, 502, 650, 536, 0, 228, 308, 194],
        [502, 730, 274, 878, 764, 228, 0, 536, 194],
        [194, 354, 810, 502, 328, 308, 536, 0, 574],
        [308, 696, 468, 844, 674, 194, 194, 574, 0],
    ]
    data["num_vehicles"] = 3
    data["depot"] = 0
    return data

def print_solution(data, manager, routing, solution):
    """輸出結果"""
    print(f"\n=== VRP 求解結果 ===")
    max_route_distance = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"車輛 {vehicle_id} 路線:\n"
        route_distance = 0
        while not routing.IsEnd(index):
            plan_output += f" {manager.IndexToNode(index)} →"
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id
            )
        plan_output += f" {manager.IndexToNode(index)}\n"
        plan_output += f"總距離: {route_distance}\n"
        print(plan_output)
        max_route_distance = max(route_distance, max_route_distance)
    print(f"所有路線最大距離: {max_route_distance}")

def solve_vrp():
    data = create_data_model()
    
    # 建立 Routing Index Manager
    manager = pywrapcp.RoutingIndexManager(
        len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
    )
    
    # 建立 Routing Model
    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)
    
    # 設定距離限制
    dimension_name = "Distance"
    routing.AddDimension(
        transit_callback_index, 0, 3000, True, dimension_name
    )
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)
    
    # 搜尋參數
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    
    # 求解
    solution = routing.SolveWithParameters(search_parameters)
    
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print("找不到解！")

if __name__ == "__main__":
    solve_vrp()

更多章節內容持續建置中...