基于OR-Tools的单容器二维装箱空间优化问题问询

首先纠正一个关键认知：所有待装箱的箱子总面积是固定值，完全不需要通过放置后的坐标回溯计算。因为你的需求是将所有给定箱子全部放入容器，总箱子面积就是所有h[i] * w[i]的和，直接预计算即可，无需依赖模型变量。

以下是完整的实现思路与代码调整方案：

1. 修正变量定义与基础约束 #

由于容器长度可任意延伸，无需预先固定上限值，建议将坐标变量的上限设为所有箱子长度之和（足够容纳所有箱子的保守值）：

# 容器固定宽度为W，高度固定为H
W = 固定容器宽度值
H = 固定容器高度值

n = len(箱子列表)
max_possible_length = sum(l[i] for i in range(n))  # l[i]是第i个箱子的长度

# 定义箱子左上角x、y坐标，以及右下角x、y坐标
x1 = [model.NewIntVar(0, max_possible_length - l[i], f'x1_{i}') for i in range(n)]
x2 = [model.NewIntVar(l[i], max_possible_length, f'x2_{i}') for i in range(n)]
y1 = [model.NewIntVar(0, H - h[i], f'y1_{i}') for i in range(n)]
y2 = [model.NewIntVar(h[i], H, f'y2_{i}') for i in range(n)]

# 定义区间变量与不重叠约束
xinv = [model.NewIntervalVar(x1[i], l[i], x2[i], f'xinv_{i}') for i in range(n)]
yinv = [model.NewIntervalVar(y1[i], h[i], y2[i], f'yinv_{i}') for i in range(n)]
model.AddNoOverlap2D(xinv, yinv)

2. 定义容器实际使用长度 #

通过AddMaxEquality获取所有箱子的最大x2值（即容器实际被占用的长度）：

used_length = model.NewIntVar(0, max_possible_length, 'used_length')
model.AddMaxEquality(used_length, [x2[i] for i in range(n)])

3. 计算空白面积并设置优化目标 #

• 预计算总箱子面积：total_box_area = sum(h[i] * w[i] for i in range(n))
• 容器使用区域面积 = 实际使用长度 × 固定宽度，需将其定义为模型变量：

used_container_area = model.NewIntVar(0, max_possible_length * W, 'used_container_area')
model.AddMultiplicationEquality(used_container_area, used_length, W)

# 定义空白面积变量
empty_area = model.NewIntVar(0, max_possible_length * W, 'empty_area')
model.Add(empty_area == used_container_area - total_box_area)

最后设置最小化空白面积为优化目标：

model.Minimize(empty_area)

简化优化目标的替代方案 #

因为容器宽度固定，最小化容器实际使用长度等价于最大化空间利用率，你可以直接将目标设为最小化used_length，省去空白面积的计算步骤：

model.Minimize(used_length)

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