VRP 時間窗 (VRPTW)

問題描述

每個客戶指定了「希望送達時間區間」。早到要等，晚到會被客訴。如何規劃路線讓所有客戶都在時間窗內收到貨？

這正是 UberEats、Foodpanda 每日面對的核心問題。

實作 OR-Tools VRPTW

from ortools.constraint_solver import routing_enums_pb2, pywrapcp

def create_data_model():
    """建立含時間窗的資料"""
    data = {}
    # 地點 0 = 餐廳，1-9 = 客戶
    data["time_matrix"] = [
        [0, 6, 9, 8, 7, 3, 6, 2, 3, 4],
        [6, 0, 8, 3, 2, 6, 8, 4, 8, 8],
        [9, 8, 0, 11, 10, 6, 3, 9, 5, 7],
        [8, 3, 11, 0, 1, 7, 10, 6, 10, 9],
        [7, 2, 10, 1, 0, 6, 9, 4, 8, 7],
        [3, 6, 6, 7, 6, 0, 2, 3, 2, 2],
        [6, 8, 3, 10, 9, 2, 0, 6, 2, 3],
        [2, 4, 9, 6, 4, 3, 6, 0, 4, 5],
        [3, 8, 5, 10, 8, 2, 2, 4, 0, 2],
        [4, 8, 7, 9, 7, 2, 3, 5, 2, 0],
    ]
    # 時間窗 [(最早, 最晚), ...] (分鐘)
    data["time_windows"] = [
        (0, 60),    # 餐廳（不須時間窗）
        (5, 20),    # 客戶 1
        (10, 30),   # 客戶 2
        (0, 15),    # 客戶 3
        (20, 40),   # 客戶 4
        (15, 35),   # 客戶 5
        (30, 50),   # 客戶 6
        (0, 25),    # 客戶 7
        (25, 45),   # 客戶 8
        (35, 55),   # 客戶 9
    ]
    data["num_vehicles"] = 3
    data["depot"] = 0
    return data

def print_solution(data, manager, routing, solution):
    print(f"\n=== VRPTW 求解結果 ===")
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        print(f"\n外送員 {vehicle_id} 配送路線:")
        route = []
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            time_var = time_dimension.CumulVar(index)
            time_min = solution.Min(time_var)
            time_max = solution.Max(time_var)
            route.append((node_index, time_min, time_max))
            index = solution.Value(routing.NextVar(index))
        
        node_index = manager.IndexToNode(index)
        time_var = time_dimension.CumulVar(index)
        time_min = solution.Min(time_var)
        time_max = solution.Max(time_var)
        route.append((node_index, time_min, time_max))
        
        for node, tmin, tmax in route:
            if node == 0:
                print(f"  餐廳 (回到) [{tmin}-{tmax}]")
            else:
                print(f"  客戶 {node} [{tmin}-{tmax}] (時間窗: {data['time_windows'][node]})")

manager = pywrapcp.RoutingIndexManager(
    len(data["time_matrix"]), data["num_vehicles"], data["depot"]
)
routing = pywrapcp.RoutingModel(manager)

def time_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data["time_matrix"][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(time_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# 加入時間維度
routing.AddDimension(
    transit_callback_index, 30, 60, False, "Time"
)
time_dimension = routing.GetDimensionOrDie("Time")

# 設定時間窗
for location_idx, (early, late) in enumerate(data["time_windows"]):
    if location_idx == data["depot"]:
        continue
    index = manager.NodeToIndex(location_idx)
    time_dimension.CumulVar(index).SetRange(early, late)

# 設定搜尋參數
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("找不到解！")