基于列生成和分支定界算法的两阶段二次装箱问题
来源：计算机集成制造系统杂志2025年第1期北京时间：
作者：杨玉冰, 杨松坡
单位：北京工业大学北京市交通工程重点实验室
摘要：为将切割和装箱问题作为一条完整的生产物流链进行研究,设计考虑将两者契合在一起,构建了两阶段二次装箱模型,第一阶段为二维切割问题,第二阶段为二维装箱问题。为求解上述问题,提出了两阶段基于列生成和分支定界算法的求解方式。利用列生成算法对问题的线性松弛主问题进行求解后,使用分支定界进行后续问题的求解,最终原整数规划问题通过该方法得到了最优解。通过二次装箱策略将装箱问题分解为一次装箱和二次装箱,进而简化其求解复杂度。一次装箱类似于快递包装,在箱子上进行标记,记录箱子内装载货物的规格和数量位置,二次装箱类似于包裹的转载运输。二次装箱策略可以对货物进行分类包装,能够跟踪货物的后续搬运过程,进而减少物流企业在各需求地的搬运成本,帮助物流企业在后续配送过程中提高工作效率。通过对实例的测试,结果表明列生成和分支定界算法适用于所提出模型的求解,研究成果为二维切割和装箱组合问题的求解提供了有效途径。
关键词：物流工程,二维装箱问题,二次装箱策略,列生成算法,分支定界,两阶段求解
基金资助：国家自然科学基金资助项目(72001008,52002008);北京市自然科学基金资助项目(9214022)。
