基于空间优化的3维装箱问题求解方法

Three-dimensional Packing Problem Solving Method Based on Space Optimization

针对3维装箱中的空间分解问题,提出新型空间分解方法:每装入一个货物,箱子空间被划分为上空间和L型空间,对L型空间再根据其空间占用率划分为左右空间.该方法可有效减少畸形空间的产生,利于后续货物的装载;另外,定义了一种改进的3叉树结构来表达上、左、右子空间的分解.实验结果表明,采用改进后的空间划分方法比现有的空间划分方法具有更好的装载效果.

We propose a new method to solve the key issue of space decomposition for three-dimensional packing： Once loaded with a cargo, the box space is divided into an upper-space and an L-space. According to the space occupancy rate of the L-space, the L-space is divided into left-space and right-space. Thus the method can effectively reduce deformity space, which facilitates the subsequent loading of goods. Furthermore, we provide an improved ternary tree structure to express the decomposition of the upper-space, the left-space and the right-space. The experimental results show that the modified space decomposition method has a better loading effect compared with the conventional loading space decomposition method.