在OR-Tools的VRPTW中如何为车辆分配节点权重并实现最大化？

以下是针对Python 3.6 + OR-Tools 9.3.10497环境的完整实现，解决你提出的时间窗约束下最大化节点-车辆匹配总得分问题：

1. 定义基础数据 #

先把你提供的得分矩阵、时间窗（示例值）、节点/车辆数等数据结构化：

from ortools.constraint_solver import routing_enums_pb2, pywrapcp

# 基础配置
NUM_VEHICLES = 4
DEPOT_INDEX = 0  # 仓库节点索引
# 任务节点：Node1~Node6对应索引1~6
TASK_NODES = list(range(1, 7))

# 你提供的节点-车辆得分矩阵：index对应[Node1, Node2, Node3, Node4, Node5, Node6]
score_matrix = [
    [4, 3, 2, 1],   # Node1对应Vehicle1-4的得分
    [4, 2, 1, 3],   # Node2
    [1, 2, 3, 4],   # Node3
    [3, 2, 4, 1],   # Node4
    [2, 4, 1, 3],   # Node5
    [2, 1, 4, 3]    # Node6
]

# 时间窗配置：(最早到达时间, 最晚到达时间)，示例值可根据实际需求修改
time_windows = [
    (0, 20),    # Depot
    (1, 8),     # Node1
    (2, 9),     # Node2
    (3, 10),    # Node3
    (4, 11),    # Node4
    (5, 12),    # Node5
    (6, 13)     # Node6
]

# 行驶时间矩阵：假设节点间行驶时间均为1，可替换为实际数据
distance_matrix = [[0]*7 for _ in range(7)]
for i in range(7):
    for j in range(7):
        if i != j:
            distance_matrix[i][j] = 1

2. 注册时间窗回调与维度 #

时间窗约束依赖Time维度实现，先注册行驶时间回调并添加维度：

# 初始化路由管理器与模型
manager = pywrapcp.RoutingIndexManager(len(distance_matrix), NUM_VEHICLES, DEPOT_INDEX)
routing = pywrapcp.RoutingModel(manager)

# 1. 注册时间窗回调函数：返回节点间行驶时间
def time_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return distance_matrix[from_node][to_node]

time_callback_idx = routing.RegisterTransitCallback(time_callback)

# 2. 添加时间维度，设置时间容量与松弛
TIME_DIM_NAME = 'Time'
routing.AddDimension(
    time_callback_idx,
    slack_max=0,               # 允许的等待时间，设为0表示必须按时到达
    capacity=20,               # 车辆最大可用时间（需覆盖所有节点行驶+服务时间）
    fix_start_cumul_to_zero=True,  # 仓库起始时间设为0
    name=TIME_DIM_NAME
)

# 3. 为每个节点绑定时间窗约束
time_dimension = routing.GetDimensionOrDie(TIME_DIM_NAME)
for node in TASK_NODES:
    node_idx = manager.NodeToIndex(node)
    time_dimension.CumulVar(node_idx).SetRange(time_windows[node][0], time_windows[node][1])
# 确保车辆最终返回仓库的时间在允许范围内
for vehicle_id in range(NUM_VEHICLES):
    end_idx = routing.End(vehicle_id)
    time_dimension.CumulVar(end_idx).SetRange(time_windows[DEPOT_INDEX][0], time_windows[DEPOT_INDEX][1])

3. 注册得分回调与最大化维度 #

核心部分：实现得分的回调、维度注册，并将目标设置为最大化总得分（OR-Tools默认最小化，需转换逻辑）：

# 1. 注册得分回调函数：根据车辆ID返回对应节点的得分
# 注意：该回调使用VehicleTransitCallback，支持传入车辆ID参数
def score_callback(from_index, to_index, vehicle_id):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    # 仅当目标节点是任务节点时，返回对应车辆的得分；仓库节点无得分
    if to_node == DEPOT_INDEX:
        return 0
    return score_matrix[to_node - 1][vehicle_id]

score_callback_idx = routing.RegisterVehicleTransitCallback(score_callback)

# 2. 添加得分维度：用于累积单辆车的总得分
SCORE_DIM_NAME = 'Score'
max_possible_score = sum(sum(row) for row in score_matrix)
routing.AddDimension(
    score_callback_idx,
    slack_max=0,               # 得分无松弛需求
    capacity=max_possible_score,  # 维度容量设为最大可能得分
    fix_start_cumul_to_zero=True,  # 起始得分设为0
    name=SCORE_DIM_NAME
)

# 3. 设置最大化总得分的目标
# OR-Tools仅支持最小化目标，因此通过最小化(-总得分)实现最大化
score_dimension = routing.GetDimensionOrDie(SCORE_DIM_NAME)
total_score = 0
for vehicle_id in range(NUM_VEHICLES):
    end_idx = routing.End(vehicle_id)
    # 累加每辆车的最终得分累积值
    total_score += score_dimension.CumulVar(end_idx)
# 将总得分的相反数作为目标变量，让求解器最小化它
routing.AddVariableMinimizedByFinalizer(-total_score)

4. 求解与结果输出 #

配置搜索参数并执行求解，最后输出路径与总得分：

# 配置求解参数
search_params = pywrapcp.DefaultRoutingSearchParameters()
# 初始解策略：选择成本最低的弧
search_params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
# 本地搜索策略：引导式局部搜索，提升解质量
search_params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
# 设置时间限制（可根据需求调整）
search_params.time_limit.seconds = 10

# 执行求解
solution = routing.SolveWithParameters(search_params)

# 输出结果
if solution:
    total_final_score = 0
    print("总得分：", -solution.ObjectiveValue())  # 还原为正的总得分
    for vehicle_id in range(NUM_VEHICLES):
        print(f"\n车辆 {vehicle_id+1} 的路径：")
        index = routing.Start(vehicle_id)
        route_score = 0
        while not routing.IsEnd(index):
            node_idx = manager.IndexToNode(index)
            next_index = solution.Value(routing.NextVar(index))
            next_node_idx = manager.IndexToNode(next_index)
            # 计算当前节点的得分（仅任务节点）
            if node_idx != DEPOT_INDEX:
                node_score = score_matrix[node_idx - 1][vehicle_id]
                route_score += node_score
                print(f"Node{node_idx} (得分：{node_score}) -> ", end="")
            else:
                print("Depot -> ", end="")
            index = next_index
        print("Depot")
        print(f"车辆 {vehicle_id+1} 的得分：{route_score}")
        total_final_score += route_score
    print(f"\n最终总得分：{total_final_score}")
else:
    print("未找到可行解")

关键部分解释 #

• 得分回调与维度：使用RegisterVehicleTransitCallback实现车辆-节点匹配的得分逻辑，通过Score维度累积每辆车的得分总和。
• 最大化目标转换：利用OR-Tools的最小化特性，将总得分取反后作为目标变量，通过最小化该变量等价于最大化原总得分。
• 时间窗约束：通过Time维度绑定每个节点的到达时间范围，确保所有任务在规定时间内完成。

内容的提问来源于stack exchange，提问作者Rabbids