求解三维装箱问题的启发式正交二叉树搜索算法

A Heuristic Orthogonal Binary Tree Search Algorithm for Three Dimensional Container Loading Problem

文中提出了一种求解三维装箱问题的启发式二叉树搜索算法,首先将所有箱子组合成多个优条,每个优条中的箱子沿容器高度方向排成一列;接着开始构建二叉树,其根节点表示空的装箱方案,每个树节点沿长度方向增加一排优条形成左子树节点,沿宽度方向增加一排优条形成右子树节点,二叉树必须扩展到所有叶子节点都无法再放入任何剩余的箱子为止,所有叶子节点中填充率最高的装箱方案即为最终结果.该算法满足三维装箱的3个著名的约束条件.在多样性最强的测试算例中,该文方法相对于现有最优秀装箱算法装箱率有显著提高.

This paper presents a heuristic orthogonal binary tree search algorithm for three dimensional container loading problem.Firstly all boxes are composed into multiple good-strips.The boxes in each good-strip are arranged along a vertical line.Then a binary tree is created.Each tree node in the tree is a container-loading plan while the root node denotes an empty one.The left child node of each node is obtained by inserting a line of good-strips along the length of the container into the residual space of the container.Similarly,the right one is obtained by inserting a line of good-strips along the width of the container.The binary tree must be extended so that each leaf tree node must not accommodate any remaining boxes.The result is the containerloading plan with highest fill rate among all the leaf tree nodes.The algorithm satisfies three famous constraints on three dimensional container loading.It outperforms the best known algorithm in the most strongly heterogeneous test data.