矩形件优化排样的研究

Research on Rectangular Packing Problem

提出了满足BL条件的最低轮廓线搜索算法,并与模拟退火算法相结合,用于矩形件排样的求解。计算实例表明该算法能在50 ms内获得近百个矩形件的较优排放图,并能获得较少矩形件的最优排放图;其排样效果和效率优于SA+最低水平线算法和SA+BLF算法,是解决大规模矩形件排样的一种有效方法。

A new heuristic placement algorithm -- search lowest outline algorithm is proposed for decoding for a permutation of packing pattern. It preserves bottom left（BL） stability. It is hybridized with simulated annealing method to solve rectangular packing problem. This study compares the hybrid algorithm with SA ＋ BLF and SA ＋ LHL （ lowest horizontal line） in terms of solution quality and computation time on a number of packing problems of different size. Experimental results show that this hybrid heuristic algorithm can not only give better placement pattern, but also run in shorter time, so it is suitable for large scale rectangular packing problem.