在OR-Tools中添加特定尺寸物品重量限制约束的方法

核心逻辑 #

先把物品按「厚度+宽度」的组合分组，然后给每个箱子添加约束：同一类型的物品在该箱子里的总重量不能超过指定上限。这种方式直接贴合需求，且能被OR-Tools求解器高效处理。

具体实现步骤 #

1. 定义类型对应的重量上限
   把需要限制的尺寸组合和对应的单箱最大总重量做成字典，方便后续引用：

   # 示例：键是(厚度, 宽度)组合，值是该类型单箱总重量上限
   type_weight_limits = {
       (0.8, 1000): 50.0,
       (0.9, 1250): 60.0,
       (1.0, 914): 45.0
       # 其他需要限制的组合按需补充
   }
   

2. 按类型给物品分组
   遍历所有物品，把同尺寸组合的物品索引归到一组，只处理有重量限制的类型：

   from collections import defaultdict
   
   # 假设thickness_list、width_list是你的厚度/宽度列表，索引对应物品
   item_groups = defaultdict(list)
   for item_idx in range(len(thickness_list)):
       current_type = (thickness_list[item_idx], width_list[item_idx])
       if current_type in type_weight_limits:
           item_groups[current_type].append(item_idx)
   

3. 给每个箱子添加约束
   假设你已经用CP-SAT创建了模型model，还有布尔变量x[item][box]（表示物品item是否放进箱子box），直接添加约束：

   # 遍历每个箱子
   for box_idx in range(len(box_capacity_list)):
       # 遍历每个需要限制的物品类型
       for item_type, item_ids in item_groups.items():
           # 计算该类型物品在当前箱子里的总重量
           total_weight = sum(x[item][box_idx] * weight_list[item] for item in item_ids)
           # 添加上限约束
           model.Add(total_weight <= type_weight_limits[item_type])
   

实用优化建议 #

• 不需要限制的尺寸组合直接跳过，减少约束数量，提升求解速度。
• 如果用浮点数存在精度问题，把所有重量值乘以100转成整数（上限同步放大），OR-Tools对整数变量的求解效率更高。
• 若问题规模极大（上万物品/箱子），可以考虑使用延迟约束（lazy constraints），但常规规模下直接添加约束就足够高效。

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