单一尺寸长方体三维装箱问题的一种求解算法

目的研究单一尺寸长方体物品的三维装箱问题,即在一个给定的箱子中装入尽可能多的单一尺寸长方体物品。方法采用分层装载方案简化装载操作,首先运用动态规划技术确定所有层中长方体物品的排列方式;然后求解一维背包问题确定箱中层的最优组合,得到最优装载方案。将文中算法与文献中三维装箱算法进行对比。结果文中算法生成的装载方案箱体空间利用率由文献中三维装箱算法的98.10%提高到了99.14%。结论文中算法可以在合理的时间内得到装载操作简单、箱体空间利用率较高的装载方案。

An Algorithm for Solving the Problem of Three-dimensional Packing of Single-sized Cuboids

This paper discussed the issue of three-dimensional packing of single-sized cuboid items, namely, arrangement of single-sized cuboid items in a given box as much as possible. Using the hierarchical loading scheme to simplify the loading operation, firstly the dynamic programming technique was used to determine the arrangement of cuboids in all layers, then the one-dimensional knapsack problem was solved to determine the optimal combination of the layers in the box, thus obtaining the optimal loading scheme. The algorithm in this paper was compared with other three-dimensional packing algorithms in literatures. The experimental results showed that the algorithm in this paper can work out a loading scheme which increased the utilization rate of box space from 98.10% to 99.14%. This algorithm can achieve a loading scheme with simple operation and high utilization rate of box space in reasonable time.