1.摘要

物流中袋装箱具有柔性、便于压缩和成本低等优点，但袋体会随装入物品而改变形状，传统刚性箱体装箱模型难以直接适用。论文提出三维袋装箱问题（3D-BGPP）：给定不同尺寸和成本的柔性袋，将可旋转长方体物品装入部分袋子，在满足不重叠和袋体重塑约束的前提下最小化袋子总成本。论文设计组合 Benders 分解—束搜索混合算法（CBD-BS）：主问题选择袋子和物品归属，子问题由 MILP 或新的极点束搜索（EP-BS）判定单袋装箱可行性；有效不等式、变量固定、可行性测试和增强 Benders 割进一步加速求解。基于电商真实订单和生成实例的实验表明，CBD-BS 在小、中规模实例上可在秒级得到高质量解，在大规模实例上约一分钟内获得比 CPLEX 更好方案。

2.研究背景与问题定义

电商物流中，袋子相较纸箱更易压缩和储运，但实际装袋长期依赖工人经验。3D-BGPP 与经典三维箱装箱问题的差异在于：容器由刚性箱体变为可变形袋体；袋子的长度、宽度和厚度相互耦合而非独立变化；目标从最小化箱子数量转为最小化异质袋子的总成本；袋体柔性产生大量不规则形状，传统固定容器算法无法充分表达。

论文考虑长方体物品集合I II和J JJ类袋子集合，每类袋子具有固定的未打开长度X j X_jXj​、宽度Y j Y_jYj​和单位成本c j c_jcj​，物品允许六种正交旋转。目标是选择足够的袋子、分配并放置所有物品，使总成本最小。

3.袋体重塑规则与柔性容量

未打开的袋子可视为厚度近似为零、长为X XX、宽为Y YY的二维矩形。装入物品后，袋子厚度增加，原来的长度和宽度缩短；底部折角使四个角不能放置物品。论文用装袋后的三维矩形( L , W , H ) (L,W,H)(L,W,H)近似袋体，其中H HH是深度，规则为

X = L + H , Y = W + H . X=L+H,\qquad Y=W+H.X=L+H,Y=W+H.

其中，X , Y X,YX,Y是袋型固定参数，L , W , H L,W,HL,W,H是由装箱方案决定的变量。袋体可容纳的矩形体积为

V ( H ) = ( X − H ) ( Y − H ) H . V(H)=(X-H)(Y-H)H.V(H)=(X−H)(Y−H)H.

当H HH过小或过大时，可用体积都会下降；令导数为零可得最大容量对应的深度

H ∗ = X + Y − ( X − Y ) 2 + X Y 3 . H^*=\frac{X+Y-\sqrt{(X-Y)^2+XY}}{3}.H∗=3X+Y−(X−Y)2+XY​​.

该规则把难以直接建模的连续不规则形变压缩为一族可计算的三维矩形，同时保留不同深度、长度和宽度之间的联动。

4.3D-BGPP 混合整数模型

二进制变量n b j n_{bj}nbj​表示是否使用第j jj类的袋b bb，s i b j s_{ibj}sibj​表示物品i ii是否分配给该袋；连续变量L b j , W b j , H b j L_{bj},W_{bj},H_{bj}Lbj​,Wbj​,Hbj​表示重塑尺寸；( x i , y i , z i ) (x_i,y_i,z_i)(xi​,yi​,zi​)是物品左后下角坐标。六组二进制相对位置变量分别表示左右、前后、上下关系，三组方向变量决定物品长、宽、高与坐标轴的对应关系。模型目标为

min ⁡ ∑ j ∈ J ∑ b ∈ B j c j n b j . \min \sum_{j\in J}\sum_{b\in B_j}c_jn_{bj}.minj∈J∑​b∈Bj​∑​cj​nbj​.

模型用大M MM约束保证同一袋内任意两个物品至少沿一个方向分离，用归属约束保证每件物品恰好进入一个袋子，用容量约束和三维边界约束确保物品位于重塑袋内；方向约束允许六种正交旋转，重塑约束则保持X j = L b j + H b j X_j=L_{bj}+H_{bj}Xj​=Lbj​+Hbj​、Y j = W b j + H b j Y_j=W_{bj}+H_{bj}Yj​=Wbj​+Hbj​。

5.CBD-BS 求解方法

组合 Benders 分解

算法先用 first-fit 启发式缩减每类袋子候选数量，再把 MILP 分解为主问题（MP）和单袋子问题（SP）。MP 决定每件物品分配到哪个袋子、哪些袋子被启用；每个整数解产生若干“袋子—物品集合”模式。SP 只检查一个模式能否在对应重塑袋中完成三维放置。若 SP 不可行，返回组合 Benders 割排除当前模式；若所有 SP 可行，则获得完整装箱方案。相较原始模型，SP 只包含一个袋子和一个物品子集，变量及大M MM约束显著减少。

极点束搜索 EP-BS

刚性箱装箱常用矩形剩余空间表示空闲区域，但袋体尺寸随装载变化，这种表示不再稳定。EP-BS 用极点（extreme point，EP）记录可能的放置起点：初始极点为( 0 , 0 , 0 ) (0,0,0)(0,0,0)，放置一个物品后最多生成六个新极点。物品放置到极点后，算法构造包络袋，即包住当前所有物品的最小三维矩形，要求

L e + H e ≤ X j , W e + H e ≤ Y j . L_e+H_e\leq X_j,\qquad W_e+H_e\leq Y_j.Le​+He​≤Xj​,We​+He​≤Yj​.

束搜索树的节点记录已放置物品、可用极点和剩余物品。剩余物品按体积降序、再按高度降序排列；每层从可行的极点—方向组合扩展子节点，只保留宽度β \betaβ个最有希望的节点。评估优先级依次为包络袋体积、H e H_eHe​、W e W_eWe​和L e L_eLe​的较小值。若搜索深度达到物品数，模式可行；否则判定为不可行。

剪枝与加速

当包络袋深度超过Y j / 2 Y_j/2Yj​/2时，算法直接剪枝，因为存在对称的较浅重塑方案。对单袋物品总体积求方程V I p = ( X j − H j ) ( Y j − H j ) H j V_{I_p}=(X_j-H_j)(Y_j-H_j)H_jVIp​​=(Xj​−Hj​)(Yj​−Hj​)Hj​可得到H j H_jHj​的上下界，再由最大物品的长宽高检查模式是否必然不可行；若违反边界，立即生成 Benders 割。EP-BS 搜索失败时，把已放置物品与下一个无法放入的物品组成更小的不可行集合，形成比只排除当前模式更强的增强割。

若模式物品数不超过阈值γ \gammaγ，直接调用 MILP 求解器；否则调用 EP-BS。

6.实验结果

论文从一家电商企业收集 57 个真实订单，订单平均含 7.4 件物品，超过 75% 的订单不超过 9 件；物品共 212 种，尺寸范围为 10–380 mm，40 个订单含重复物品。基于真实订单随机生成小、中、大三类实例，每类 50 个，物品数分别为 10、20 和 30，共得到 207 个实例。指标S Y I SY_ISYI​表示订单中与其他物品相同的物品比例，用于区分弱同质和强同质订单。

比较对象包括商业求解器 CPLEX、GRASP 和遗传算法（GA）。CBD-BS、GRASP 和 GA 均采用单线程、2 min 时间限制。

7.参考文献

Feng J, Ma H, Xu Z. Optimizing Three-Dimensional Bag Packing[J]. IEEE Transactions on Automation Science and Engineering, 2025, 23: 1519-1532.

8.算法辅导·应用定制·读者交流

xx