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

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

作　　者：刘胜[1,2] 朱凤华[1,2] 吕宜生[1] 李元涛[1] 

机构地区：[1]中国科学院自动化研究所复杂系统管理与控制国家重点实验室,北京100190 [2]中国科学院云计算产业技术创新与育成中心,广东东莞523808

出　　处：《计算机学报》2015年第8期1530-1543,共14页Chinese Journal of Computers

基　　金：国家自然科学基金(61104054;71232006;61233001)资助~~

摘　　要：文中提出了一种求解三维装箱问题的启发式二叉树搜索算法,首先将所有箱子组合成多个优条,每个优条中的箱子沿容器高度方向排成一列;接着开始构建二叉树,其根节点表示空的装箱方案,每个树节点沿长度方向增加一排优条形成左子树节点,沿宽度方向增加一排优条形成右子树节点,二叉树必须扩展到所有叶子节点都无法再放入任何剩余的箱子为止,所有叶子节点中填充率最高的装箱方案即为最终结果.该算法满足三维装箱的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.

关 键 词：三维装箱 启发式算法 二叉树 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]