A quasi-human algorithm for solving the three-dimensional rectangular packing problem  

作　　者：HE Kun & HUANG WenQi School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China 

出　　处：《Science China(Information Sciences)》2010年第12期2389-2398,共10页中国科学（信息科学）（英文版）

基　　金：supported by the National Natural Science Foundation of China (Grant No. 60773194)

摘　　要：Based on the concept of maximal rectangular space that can be filled at current time and the siege warfare tactics, we make several critical improvements on the quasi-human caving-degree approach to get a stronger algorithm ICDA for a classical NP hard problem： the three-dimensional rectangular packing problem. Within similar computing time, the new algorithm gained an average volume utilization of 90.92% on the natural and difficult 100 benchmarks, called BR15, where items to be packed are almost different in size. Compared with current best record just reported in the literature in 2010, our result makes an improvement by 0.54%.Based on the concept of maximal rectangular space that can be filled at current time and the siege warfare tactics, we make several critical improvements on the quasi-human caving-degree approach to get a stronger algorithm ICDA for a classical NP hard problem： the three-dimensional rectangular packing problem. Within similar computing time, the new algorithm gained an average volume utilization of 90.92% on the natural and difficult 100 benchmarks, called BR15, where items to be packed are almost different in size. Compared with current best record just reported in the literature in 2010, our result makes an improvement by 0.54%.

关 键 词：NP hard three-dimensional packing quasi-human action space caving degree 

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