Abstract: To study the problem of cutting and packing as a complete production logistics chain,the consideration of combining the two together is designed to construct a two-stage quadratic packing model.The first stage is a two-dimensional cutting problem,and the second stage is a packing problem.To solve the above problem,a two-stage method based on column generation and branch and bound algorithm was proposed.After solving the main problem of linear relaxation by using the column generation algorithm,the subsequent problems were solved by using the branch and bound method.Finally,the optimal solution of the original integer programming problem was obtained by this way.The problem was decomposed into primary and secondary packing by the quadratic packing strategy,thus the complexity of solving the problem was simplified.The primary packing was similar to the express packing,and marks were made on the boxes to record the specifications and quantity positions of the goods inside the boxes.The secondary packing was similar to the reloading and transportation of packages.The quadratic packing strategy could classify the goods for reducing the identification work of the goods in the subsequent handling process to a certain extent,and the handling cost of logistics enterprises in each demand place were thus reduced,which could also help logistics enterprises improve work efficiency in the follow-up delivery process.Through the test of the example,the results showed that that the column generation and branch and bound algorithms were suitable for solving the proposed model,and the research results provided an effective way for solving the two-dimensional cutting and packing combination problems.

Key words: logistics engineering, two-dimensional packing problem, quadratic packing strategy, column generation algorithm, branch-and-bound, two-stage solution

摘要： 为将切割和装箱问题作为一条完整的生产物流链进行研究,设计考虑将两者契合在一起,构建了两阶段二次装箱模型,第一阶段为二维切割问题,第二阶段为二维装箱问题。为求解上述问题,提出了两阶段基于列生成和分支定界算法的求解方式。利用列生成算法对问题的线性松弛主问题进行求解后,使用分支定界进行后续问题的求解,最终原整数规划问题通过该方法得到了最优解。通过二次装箱策略将装箱问题分解为一次装箱和二次装箱,进而简化其求解复杂度。一次装箱类似于快递包装,在箱子上进行标记,记录箱子内装载货物的规格和数量位置,二次装箱类似于包裹的转载运输。二次装箱策略可以对货物进行分类包装,能够跟踪货物的后续搬运过程,进而减少物流企业在各需求地的搬运成本,帮助物流企业在后续配送过程中提高工作效率。通过对实例的测试,结果表明列生成和分支定界算法适用于所提出模型的求解,研究成果为二维切割和装箱组合问题的求解提供了有效途径。

关键词: 物流工程, 二维装箱问题, 二次装箱策略, 列生成算法, 分支定界, 两阶段求解