目录1.摘要2.研究背景与问题定义3.袋体重塑规则与柔性容量4.3D-BGPP 混合整数模型5.CBD-BS 求解方法6.实验结果7.参考文献8.算法辅导·应用定制·读者交流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 . XLH,\qquad YWH.XLH,YWH.其中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{XY-\sqrt{(X-Y)^2XY}}{3}.H∗3XY−(X−Y)2XY​​.该规则把难以直接建模的连续不规则形变压缩为一族可计算的三维矩形同时保留不同深度、长度和宽度之间的联动。4.3D-BGPP 混合整数模型二进制变量n b j n_{bj}nbj​表示是否使用第j jj类的袋b bbs 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_jL_{bj}H_{bj}Xj​Lbj​Hbj​、Y j W b j H b j Y_jW_{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 pointEP记录可能的放置起点初始极点为( 0 , 0 , 0 ) (0,0,0)(0,0,0)放置一个物品后最多生成六个新极点。物品放置到极点后算法构造包络袋即包住当前所有物品的最小三维矩形要求L e H e ≤ X j , W e H e ≤ Y j . L_eH_e\leq X_j,\qquad W_eH_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 mm40 个订单含重复物品。基于真实订单随机生成小、中、大三类实例每类 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