基于OR-Tools CP-SAT的带重量约束二维装箱问题求解咨询

问题的核心在于：你需要将布尔变量z_vars与箱子的坐标约束关联，让未被选中的箱子（z_i=0）的位置超出容器范围，避免被分配到容器内的有效坐标。以下是具体的修改方案：

步骤1：调整坐标变量的定义域 #

将x_vars和y_vars的上限放宽至容器的长度/宽度，允许未选中的箱子放置在容器外部：

x_vars = [
    model.NewIntVar(0, container[0], name=f"x1_{i}")
    for i, box in enumerate(boxes)
]
y_vars = [
    model.NewIntVar(0, container[1], name=f"y1_{i}")
    for i, box in enumerate(boxes)
]

步骤2：添加蕴含约束关联z_vars与坐标范围 #

对每个箱子，添加蕴含约束：当z_i=1（箱子被选中）时，强制其坐标必须落在容器内部；当z_i=0时，该约束不生效，箱子可以被放置在容器外（不会占用有效空间）：

for i, box in enumerate(boxes):
    # 选中的箱子必须在容器长度范围内
    model.Add(x_vars[i] <= container[0] - box[0]).OnlyEnforceIf(z_vars[i])
    # 选中的箱子必须在容器宽度范围内
    model.Add(y_vars[i] <= container[1] - box[1]).OnlyEnforceIf(z_vars[i])

步骤3：保留原有区间变量与无重叠约束 #

区间变量和AddNoOverlap2D约束无需修改——未选中的箱子坐标超出容器后，其对应的区间也会落在容器外，不会与容器内的选中箱子产生重叠冲突：

x_interval_vars = [
    model.NewIntervalVar(
        start=x_vars[i], size=box[0], end=x_vars[i] + box[0], name=f"x_interval_{i}"
    )
    for i, box in enumerate(boxes)
]
y_interval_vars = [
    model.NewIntervalVar(
        start=y_vars[i], size=box[1], end=y_vars[i] + box[1], name=f"y_interval_{i}"
    )
    for i, box in enumerate(boxes)
]
model.AddNoOverlap2D(x_interval_vars, y_interval_vars)

步骤4：保留重量约束与目标函数 #

你之前写的重量约束和最大化装箱面积的目标函数可以直接沿用：

z_vars = [model.NewBoolVar(f"z_{i}") for i in range(len(boxes))]
model.Add(sum(z_vars[i] * box[2] for i, box in enumerate(boxes)) <= container[2])

box_areas = [box[0]*box[1] for box in boxes]
model.Maximize(sum(z_vars[i] * box_areas[i] for i in range(len(boxes))))

原理说明 #

• 当z_i=1时，坐标被限制在容器内部，区间变量有效参与无重叠检查；
• 当z_i=0时，坐标可以超出容器，对应的区间落在容器外，不会占用有效空间，也不会与其他选中箱子产生重叠；
• 重量约束仅计算z_i=1的箱子，确保总重量不超过容器容量。

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