OR-Tools中如何用AddMinEquality与AddMaxEquality均匀分配任务

核心逻辑 #

你要实现的任务均衡分配目标，本质是最小化各分配单元（此处为车辆）承载任务量的极差，即单车辆最大任务数减去单车辆最小任务数，用AddMinEquality和AddMaxEquality两个接口完全可以实现该需求。
两个接口的作用：

• AddMaxEquality(target_var, var_list)：自动添加约束，令target_var的取值等于var_list内所有变量的最大值，无需手动编写大M法等自定义最值约束，求解器会原生处理该逻辑。
• AddMinEquality(target_var, var_list)：自动添加约束，令target_var的取值等于var_list内所有变量的最小值。
  目标函数设置为最小化max - min后，求解器会自动搜索让所有车辆任务量尽可能接近的分配方案，实现均匀分配。

原有代码的常见坑点 #

你原有代码的核心框架逻辑成立，但存在一个接口使用错误：

AddMinEquality和AddMaxEquality的返回值是约束对象，不是代表最值的决策变量，直接将返回值做差传入目标函数会触发类型错误。使用时需要先单独创建存储全局最大值、最小值的整数变量，再将该变量作为第一个参数传入对应接口，第二个参数传入待求最值的变量列表。

修正后的实现代码 #

assignments = []
for c in cars:
    # 定义单辆车分配的任务总数变量，上下界为0到总任务量
    a = model.NewIntVar(0, total_assignments, f"assign_cnt_{c}")
    model.Add(a == sum(car_sch[(d, c)] for d in days))
    assignments.append(a)

# 单独创建存储全局最小、最大分配量的决策变量
assignment_min = model.NewIntVar(0, total_assignments, "global_min_assign")
assignment_max = model.NewIntVar(0, total_assignments, "global_max_assign")

# 添加最值约束，注意参数顺序：[目标最值变量, 待求最值的变量列表]
model.AddMinEquality(assignment_min, assignments)
model.AddMaxEquality(assignment_max, assignments)

# 最小化分配量极差，实现均衡目标
model.Minimize(assignment_max - assignment_min)

可选优化技巧 #

• 如果总任务量不能被车辆总数整除，理论最优解的极差固定为1（例如10个任务分给3辆车，最优分配为3、3、4，极差为1），可以提前添加极差上界约束model.Add(assignment_max - assignment_min <= 1)，裁剪求解搜索空间，大幅提升求解速度。
• 如果模型需要兼顾其他优化目标（例如总调度成本最低、总路径最短），可以将极差最小作为第一优先级目标，其余目标作为次级优先级，通过OR-Tools的多目标求解能力配置，避免为了追求绝对均匀牺牲过多其他收益。
• 由于你的底层决策变量car_sch均为布尔类型，单车辆的任务计数变量a天然为整数，无需额外添加整数约束，求解器会自动处理变量类型逻辑。

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