多约束Binpacking/装箱问题咨询：含重量、长宽高、堆叠限制适配方案

你遇到的是带堆叠限制、托盘固定尺寸、承重约束的3D托盘装载问题（3D PLP），比普通重量体积双约束装箱多了空间排布类约束，可选择两种适配方案： #

1. 启发式算法方案（推荐处理全量77000件数据） #

工业界处理大规模同场景问题普遍采用启发式算法，计算效率高，空间利用率可满足生产需求，适配步骤如下：

• 同物料预堆叠：先将同一SKU的包裹按照stack_limit堆叠成独立单元，例如物料00000001堆叠上限为11，每个单元就是11件包裹垂直堆叠，单元尺寸为30（长）30（宽）22（高=211），单元重量为6.6（=0.611）
• 托盘层排布：每个托盘水平面尺寸固定为120*80，将预堆叠好的单元按照底面积从大到小的顺序做二维排程，优先摆放大尺寸单元，避免小单元挤占空间导致大单元无法放置
• 全局约束校验：每层单元堆叠到托盘后，校验累计总高度不超过120、累计总重量不超过500，满足约束则继续堆叠下一层，不满足则新开托盘
  该方案处理77000件包裹的耗时可控制在秒级，托盘空间利用率普遍可达80%~90%。

2. CVXPY适配方案 #

CVXPY可通过混合整数线性规划（MILP）建模适配该场景，更适合小批量验证、对利用率要求极高的场景，不建议直接跑全量77000件数据，可分批处理：

核心约束建模要点 #

需要在普通双约束装箱模型基础上新增3类约束：

• 堆叠上限约束：同一托盘上单SKU的堆叠层数不能超过其stack_limit
• 托盘尺寸约束：所有放置在托盘上的包裹投影总面积不超过托盘底面积9600（=120*80），总高度不超过120
• 承重约束：单托盘总重量不超过500

简化版代码示例 #

import cvxpy as cp
import numpy as np

# 预设参数
material_count = 750  # 物料SKU总数
max_pallet = 2000     # 预估托盘数上限，可按需调整

# 变量定义
x = cp.Variable((material_count, max_pallet), boolean=True)  # x[i][j]=1代表第i类物料放在第j个托盘
pallet_height = cp.Variable(max_pallet)
pallet_weight = cp.Variable(max_pallet)

constraints = []
# 约束1：所有物料包裹全部分配
constraints.append(cp.sum(x, axis=1) == pkg_count_list)
# 约束2：托盘高度、承重上限
constraints += [pallet_height[j] <= 120 for j in range(max_pallet)]
constraints += [pallet_weight[j] <= 500 for j in range(max_pallet)]
# 约束3：堆叠上限约束
constraints += [cp.sum(x[i,j]) * pkg_height[i] <= stack_limit_list[i] * pallet_height[j] 
                for i in range(material_count) for j in range(max_pallet)]
# 约束4：托盘底面积约束
constraints += [cp.sum(x[i,j] * pkg_length[i] * pkg_width[i]) <= 120*80 
                for j in range(max_pallet)]

# 目标：最小化托盘使用数量
objective = cp.Minimize(cp.sum(cp.sum(x, axis=0) > 0))
prob = cp.Problem(objective, constraints)
# 用CBC开源求解器求解
prob.solve(solver=cp.CBC, verbose=True)

如果要更高的空间利用率，可以新增坐标变量控制包裹之间无空间重叠，但求解速度会进一步变慢，建议全量数据分批处理，每次只计算10~20类物料的装箱结果。 #

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