如何用OR-Tools CP-SAT实现同类型任务尽可能归为同一任务包

要实现"同类型任务尽量放入同一任务包"的目标，核心是计算所有任务包内任务对的距离总和，并将其与任务包数量结合作为目标函数（一起最小化）。以下是具体实现：

关键逻辑说明 #

• 遍历所有不重复的任务对，判断它们是否被分配到同一个任务包：如果是，则累加对应的距离值
• 通过权重系数调整两个目标的优先级（比如给任务包数量更高权重，确保先满足"最少任务包"的核心需求，再优化同类型归包）

修改后的完整代码 #

from ortools.sat.python import cp_model
import pandas as pd

model = cp_model.CpModel()


# 1. Data
tasks = {'Task A1', 'Task A2', 'Task B1', 'Task B2'}
packages = {'Package 1', 'Package 2', 'Package 3'}
max_package_size = 2

distances = {
    ('Task A1', 'Task A2'): 0,
    ('Task A1', 'Task B1'): 1,
    ('Task A1', 'Task B2'): 1,
    ('Task A2', 'Task B1'): 1,
    ('Task A2', 'Task B2'): 1,
    ('Task B1', 'Task B2'): 0,
}


# 2. Decision Variables
var_task_to_package_matrix = {
    (task, package): model.NewBoolVar(f"task {task} --> group {package}")
    for task in tasks
    for package in packages
}

var_package_is_formed_indicator = {
    package: model.NewBoolVar(f"package {package} is formed")
    for package in packages
}


# 3. Constraints
for package in packages:
    # 每个任务包最多包含2个任务
    model.add(
        sum(var_task_to_package_matrix[task, package] for task in tasks) <= max_package_size
    )

for task in tasks:
    # 每个任务必须且只能分配到一个任务包
    model.add(
        sum(var_task_to_package_matrix[task, package] for package in packages) == 1
    )

for package in packages:
    # 任务包有任务分配则标记为已创建
    model.AddMaxEquality(
        var_package_is_formed_indicator[package],
        [var_task_to_package_matrix[task, package] for task in tasks]
    )


# 4. Objective
# --- 新增：计算所有任务包内的距离总和 ---
total_distances = 0
task_list = list(tasks)
# 遍历所有不重复的任务对（避免重复计算同一对任务）
for i in range(len(task_list)):
    task1 = task_list[i]
    for j in range(i + 1, len(task_list)):
        task2 = task_list[j]
        # 检查每一个任务包：如果两个任务都在这个包里，累加距离
        for package in packages:
            total_distances += distances[(task1, task2)] * var_task_to_package_matrix[(task1, package)] * var_task_to_package_matrix[(task2, package)]

total_number_of_formed_packages = sum(var_package_is_formed_indicator[package] for package in packages)

# 目标函数：优先最小化任务包数量（权重10），再最小化总距离（权重1）
# 可根据实际需求调整权重系数
model.Minimize(total_number_of_formed_packages * 10 + total_distances)


# 5. Solve
solver = cp_model.CpSolver()
status = solver.Solve(model=model)

L = []
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    for task in tasks:
        for package in packages:
            tmp = {'task': task, 'package': package, 'indicator': solver.value(var_task_to_package_matrix[task, package])}
            L.append(tmp)
    df = pd.DataFrame(L)
    df = df[df['indicator'] == 1]
    print(df)
else:
    print('模型不可行或无效')

代码说明 #

1. 距离总和计算：通过三重循环实现：遍历所有任务对 → 遍历所有任务包 → 判断任务对是否同包，若是则累加距离
2. 目标权重调整：total_number_of_formed_packages * 10 确保最小化任务包数量是优先级更高的目标，total_distances 则负责优化同类型任务归包。如果需要更侧重同类型归包，可以降低任务包数量的权重。

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