基于动作空间的三维装箱问题的确定性高效率求解算法  

An Action Space Based Deterministic Efficient Algorithm for Solving the Three-Dimensional Container Loading

作　　者：何琨[1] 黄文奇[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机学报》2014年第8期1786-1793,共8页Chinese Journal of Computers

基　　金：国家自然科学基金(61173180)资助~~

摘　　要：三维装箱问题要求将有限个三维矩形物体尽可能多地装入到一个三维矩形箱子中,使得箱子的填充率即体积利用率最大.在求解三维装箱问题的穴度算法的基础之上,进一步做了以下改进:(1)将当前剩余空间中可能放入的每个体积最大的三维矩形虚拟物体所对应的空间定义为动作空间,在动作空间内放入物体并使穴度的定义体现放入物体与动作空间的吻合程度;(2)在物体放入位置的选择上直接体现"金角银边草肚皮"的思想,每一步只选择最靠近箱子边缘的一个动作空间来装载物体;(3)结合捆绑策略,将形状大小相同的物体捆绑为一个较大的矩形块进行放入,对捆绑块形状大小的选择为在不超出动作空间的前提下尽量用物体填满该空间的两至三个维度.实验结果表明,改进后的穴度算法在付出很少的开销代价的情况下显著地提高了箱子的填充率.The three dimensional （3D） container loading problem is a problem of loading a subset of 3D rectangular items into a 3D rectangular container,such that the stowed percentage,i.e.the container＇s volume utilization,is maximized.Based on the caving degree approach proposed for the 3D container loading problem,we present three improvement strategies in this paper.Firstly,＂action space＂ is defined for an empty space that a maximal dummy 3D rectangular item could be placed.Secondly,an action space nearest to the edge of the container is selected to stow items at each iteration step.In this way the nature of ＂gold corner,silver side and strawy void＂ is embodied directly on the candidate packing place.Finally,we bind items in the same size into a larger rectangular block and place the block into a selected action space.The size of the block is determined in such a way that two or three dimensions of the action space are stowed as fully as possible without beyond the boundary of the action space.Then,＂caving degree＂ is defined to reflect to which degree the block dovetail with the space.Experimental results suggest that the improved caving degree algor ithm increased the container ＇s volume utilization markedly within a short running time,and it outperforms many excellent algorithms published formally.

关 键 词：三维布局 装箱 启发式 动作空间 穴度 

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