CAJ | 학술논문

文中提出了一种求解三维装箱问题的启发式二叉树搜索算法，首先将所有箱子组合成多个优条，每个优条中的箱子沿容器高度方向排成一列；接着开始构建二叉树，其根节点表示空的装箱方案，每个树节点沿长度方向增加一排优条形成左子树节点，沿宽度方向增加一排优条形成右子树节点，二叉树必须扩展到所有叶子节点都无法再放入任何剩余的箱子为止，所有叶子节点中填充率最高的装箱方案即为最终结果。该算法满足三维装箱的3个著名的约束条件。在多样性最强的测试算例中，该文方法相对于现有最优秀装箱算法装箱率有显著提高。
문중제출료일충구해삼유장상문제적계발식이차수수색산법，수선장소유상자조합성다개우조，매개우조중적상자연용기고도방향배성일렬；접착개시구건이차수，기근절점표시공적장상방안，매개수절점연장도방향증가일배우조형성좌자수절점，연관도방향증가일배우조형성우자수절점，이차수필수확전도소유협자절점도무법재방입임하잉여적상자위지，소유협자절점중전충솔최고적장상방안즉위최종결과。해산법만족삼유장상적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 container-loading 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.