基于OR-Tools的多任务-多工人分配问题求解（含规模约束）

1. OR-Tools CP-SAT求解器适用性确认 #

你的问题属于多目标整数规划问题：先最大化亲和度总和，在满足该目标的前提下最小化规模误差总和。CP-SAT求解器完全适用于这类场景：

• 支持布尔分配变量的建模（任务-工人分配逻辑）
• 支持线性约束（任务分配规则、规模计算）
• 内置绝对误差的建模方法
• 支持多目标优先级优化

2. 最小化绝对误差的实现步骤 #

要实现规模误差最小化，需分三步完成建模：

• 计算每个工人的实际总规模
• 建模实际规模与理想规模的绝对误差
• 将误差总和作为第二优先级目标进行最小化

修改后的完整代码 #

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# 亲和度数据
data = [
    [90, 76, 75], 
    [35, 85, 55], 
    [125, 95, 90], 
    [45, 110, 95], 
    [60, 105, 80]
]
# 任务规模与工人理想规模
sizes = [10, 8, 14, 18, 13]
ideal_size_per_worker = [15, 20, 18]

n_tasks = len(data)
n_workers = len(data[0])

# 1. 定义分配变量：x[task, worker] = 1表示任务task分配给工人worker
x = {}
for task in range(n_tasks):
    for worker in range(n_workers):
        x[task, worker] = model.NewBoolVar(f'x[{task},{worker}]')

# 基础约束：每个任务仅分配给一名工人
for task in range(n_tasks):
    model.AddExactlyOne(x[task, worker] for worker in range(n_workers))

# 基础约束：每名工人至少分配一个任务
for worker in range(n_workers):
    model.AddAtLeastOne(x[task, worker] for task in range(n_tasks))

# 2. 计算每个工人的实际总规模
actual_size = []
for worker in range(n_workers):
    size_expr = sum(sizes[task] * x[task, worker] for task in range(n_tasks))
    actual_size.append(model.NewIntVar(0, sum(sizes), f'actual_size_worker_{worker}'))
    model.Add(actual_size[worker] == size_expr)

# 3. 建模绝对误差：|实际规模 - 理想规模| = 误差变量
total_error = model.NewIntVar(0, sum(sizes) * n_workers, 'total_error')
error_terms = []
for worker in range(n_workers):
    error = model.NewIntVar(0, sum(sizes), f'error_worker_{worker}')
    # 使用CP-SAT内置的绝对等式约束
    model.AddAbsEquality(error, actual_size[worker] - ideal_size_per_worker[worker])
    error_terms.append(error)
model.Add(total_error == sum(error_terms))

# 4. 设置多目标优化：先最大化亲和度总和，再最小化总误差
# 第一目标：最大化亲和度总和
objective_score = sum(data[task][worker] * x[task, worker] for task in range(n_tasks) for worker in range(n_workers))
model.Maximize(objective_score)

# 第二目标：最小化总误差（CP-SAT会在第一目标最优的前提下，优化第二目标）
model.Minimize(total_error)

# 求解
solver = cp_model.CpSolver()
# 启用搜索进度日志（可选）
solver.parameters.log_search_progress = True
status = solver.Solve(model)

# 输出结果
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f'总亲和度得分 = {solver.ObjectiveValue()}\n')
    print(f'总规模误差 = {solver.Value(total_error)}\n')
    for worker in range(n_workers):
        assigned_tasks = [task for task in range(n_tasks) if solver.BooleanValue(x[task, worker])]
        assigned_size = sum(sizes[t] for t in assigned_tasks)
        print(f'工人 {worker} 分配任务：{assigned_tasks}')
        print(f'实际总规模：{assigned_size}，理想规模：{ideal_size_per_worker[worker]}，误差：{abs(assigned_size - ideal_size_per_worker[worker])}\n')
else:
    print('未找到可行解。')

关键说明 #

• 绝对误差建模：使用model.AddAbsEquality(error, expr)直接实现error = |expr|，这是CP-SAT专为绝对误差提供的高效约束，比手动拆分正负情况更简洁高效。
• 多目标处理：CP-SAT会优先完成第一目标（最大化亲和度）的优化，在找到所有第一目标最优的解后，再从中筛选出第二目标（最小化误差）最优的解。
• 变量范围设置：为actual_size和error变量设置合理的上下界，能帮助求解器缩小搜索范围，提升收敛速度。

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