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

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

针对二维矩形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.