基于动作空间的求解三维矩形装箱问题的穴度算法  

Action Space Based Caving Degree Approach for the 3D Rectangular Packing Problem

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

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

出　　处：《计算机科学》2010年第10期181-183,220,共4页Computer Science

基　　金：国家自然科学基金资助项目(No.60773194)资助

摘　　要：基于拟人途径求解三维矩形装箱问题。在穴度算法的基础之上,通过定义当前格局下的极大空闲矩形空间即动作空间,使得穴度的定义既能反映其本质,同时又大能幅度地缩减计算量,从而使算法能在较短的时间内得出空间利用率较高的布局图案。试算了OR-Library中无方向约束的全部47个算例。实验结果表明,改进后的穴度算法得到的平均空间利用率为95.24%,将目前的最好结果提高了0.32%,且花费了更少的计算时间。This paper solved the three-dimensional rectangular packing problem with a quasi-human approach.By defining the maximal rectangular spaces at current iteration,the action space,we improved our caving degree approach such that the computation is largely speeded up at the same time the excellent characteristic of the caving degree is still kept.In this way a good solution could be achieved in a shorter time.In the experiments,we tested the improved algorithm with 47 without-orientation-constraint instances in the OR-Library.Computational results show an average space utilization of 95.24%,which improves current best result reported in the literature by 0.32%.In addition,the results also show less running time compared with other algorithms.

关 键 词：NP难度 三维装箱 启发式 拟人 穴度 

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