求解二维矩形Packing问题的一种优美度枚举算法  

A beauty degree enumeration algorithm for the 2D rectangular packing problem

作　　者：王磊[1,2] 尹爱华[3] 

机构地区：[1]武汉科技大学计算机科学与技术学院,武汉430081 [2]智能信息处理与实时工业系统湖北省重点实验室,武汉430081 [3]江西财经大学软件与通信工程学院,南昌330013

出　　处：《中国科学：信息科学》2015年第9期1127-1140,共14页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61262011;61100055;61472293);湖北省自然科学基金(批准号:2014CFC1121);江西省自然科学基金(批准号:20142BAB207024)资助项目

摘　　要：针对二维矩形Packing问题,提出了基于角区的基本算法.在此基础上提出了优美度枚举算法.计算了两组有代表性的问题实例c1～c21和zdf1～zdf16,算法的表现优于当前文献中报道的表现领先的优秀算法.针对矩形块方向固定的情形,算法对zdf6～zdf9得到了比此前国际上已报道记录更优的布局,其中对zdf8和zdf9首次找到最优布局.To address the 2D rectangular packing problem, this paper presents a basic algorithm based on corner areas, and presents a beauty degree enumeration algorithm. For two sets of representative benchmark instances c1-c21 and zdfl-zdfl6, the algorithm outperforms the best algorithms in the literature. When the orientation of the rectangles is fixed, the algorithm finds better packing configurations than the best reported results of four open benchmark instances zdf6-zdf9. The proposed algorithm finds the optimal solutions for zdf8 and zdf9; to the best of our knowledge, this is the first time this has been achieved.

关 键 词：PACKING问题 NP难度 组合优化 启发式算法 拟人 

分 类 号：O241.6[理学—计算数学]