AddWeightedVariableMinimizedByFinalizer未被OR-Tools求解器识别的VRP问题

核心问题分析 #

1. 绝对值目标的错误定义 #

你的代码中直接使用abs(objective_distance[n_vehicle] - distance_dimension.CumulVar(routing.End(n_vehicle)))作为最小化变量，这是无效的。OR-Tools的约束求解器无法直接处理变量的绝对值表达式，因为绝对值是非线性的，必须通过引入辅助变量转化为线性约束才能被求解器识别。

2. 全局跨度成本与自定义目标冲突 #

当保留distance_dimension.SetGlobalSpanCostCoefficient(10)时，该函数的作用是最小化所有车辆路径的最大长度与最小长度之差，这个目标的优先级会覆盖你的自定义目标，导致求解器倾向于让所有车辆路径长度尽可能接近，最终出现所有路径都是1552米的结果。

3. Finalizer目标优先级低于主目标 #

AddWeightedVariableMinimizedByFinalizer添加的目标属于最终器，它的优化优先级低于主目标（默认是总路径长度）。当移除全局跨度成本后，求解器会优先优化总路径长度最小，而将所有任务分配给一辆车是总距离最小的方案，此时最终器的目标被忽略。

解决方案 #

步骤1：替换绝对值目标为线性约束 #

为了实现“路径长度接近目标值”的目标，需要为每个车辆引入辅助变量来表示路径长度与目标值的偏差绝对值，然后将这些辅助变量的和作为主目标进行最小化。

步骤2：调整主目标优先级 #

移除全局跨度成本设置，同时将自定义目标设为主目标，确保求解器优先优化路径长度与目标值的偏差。

步骤3：可选约束（避免空车） #

如果需要确保每辆车都执行任务，可以添加约束限制每辆车的路径长度大于0（或最小任务数）。

修改后的完整代码 #

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

objective_distance = [2000, 1500, 1000, 1000]

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data["distance_matrix"] = [
        # fmt: off
      [0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
      [548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
      [776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
      [696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
      [582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
      [274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
      [502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
      [194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
      [308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
      [194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
      [536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
      [502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
      [388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
      [354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
      [468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
      [776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
      [662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0],
        # fmt: on
    ]
    data["num_vehicles"] = 4
    data["depot"] = 0
    return data


def print_solution(data, manager, routing, solution, deviation_vars):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    total_deviation = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"Route for vehicle {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"Distance of the route: {route_distance}m\n"
        plan_output += f"Target distance: {objective_distance[vehicle_id]}m\n"
        deviation = solution.Value(deviation_vars[vehicle_id])
        plan_output += f"Deviation: {deviation}m\n"
        total_deviation += deviation
        print(plan_output)
    print(f"Total deviation from targets: {total_deviation}m")


def main():
    """Entry point of the program."""
    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)

    # 添加距离维度
    dimension_name = "Distance"
    routing.AddDimension(
        transit_callback_index,
        0,  # 无松弛
        30000,  # 最大行驶距离
        True,  # 起点累计值为0
        dimension_name,
    )
    distance_dimension = routing.GetDimensionOrDie(dimension_name)

    # 为每个车辆创建偏差变量，并添加约束
    deviation_vars = []
    for vehicle_id in range(data["num_vehicles"]):
        target = objective_distance[vehicle_id]
        # 获取车辆终点的累计距离变量
        end_cumul_var = distance_dimension.CumulVar(routing.End(vehicle_id))
        # 创建偏差变量s_i，表示|d_i - target|的上界
        s_var = routing.NewIntVar(0, 30000, f"deviation_{vehicle_id}")
        deviation_vars.append(s_var)

        # 添加约束：d_i - target ≤ s_i
        routing.AddConstraint(routing.LessOrEqual(
            routing.Subtract(end_cumul_var, target), s_var
        ))
        # 添加约束：target - d_i ≤ s_i
        routing.AddConstraint(routing.LessOrEqual(
            routing.Subtract(target, end_cumul_var), s_var
        ))

        # 将偏差变量加入主目标，权重设为100（可根据需求调整）
        routing.AddWeightedVariable(s_var, 100)

    # 可选：约束每辆车必须至少执行一个任务（避免空车）
    # 注意：需要确保总任务数足够分配给4辆车
    for vehicle_id in range(data["num_vehicles"]):
        routing.AddConstraint(distance_dimension.CumulVar(routing.End(vehicle_id)) > 0)

    # 设置搜索参数
    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 = 15

    # 求解
    solution = routing.SolveWithParameters(search_parameters)

    if solution:
        print_solution(data, manager, routing, solution, deviation_vars)
    else:
        print("No solution found !")


if __name__ == "__main__":
    main()

修改说明 #

1. 替换绝对值目标：为每个车辆引入deviation_var辅助变量，通过两个线性约束实现对绝对值偏差的限制，确保deviation_var大于等于路径长度与目标值的差的绝对值。
2. 调整主目标：将deviation_var加入主目标并设置权重，让求解器优先优化偏差最小化。
3. 可选空车约束：添加distance_dimension.CumulVar(routing.End(vehicle_id)) > 0确保每辆车都有任务，避免空车情况。
4. 移除全局跨度成本：删除distance_dimension.SetGlobalSpanCostCoefficient(10)，避免与自定义目标冲突。

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