基于空间分解的二维布局问题的启发式算法

A HEURISTIC METHOD FOR TWO-DIMENSIONAL PACKING PROBLEM BASED ON SPACE DECOMPOSITION

一种基于空间分解的解决矩形物体布局问题的启发式方法．按照深度优先的原则将布局空间逐步分解，每次放入相对于当前布局空间来说是满足特定条件的最优布局块，并将该布局块定位于当前布局空间的左上角来不同大小矩形物体的布局方案．通过调整调序因子ＫＡ和ＫＢ的值，可得到满足不同要求的优化布局方案，所得布局方案均满足工业上一刀切的要求．实验结果及与其他算法的比较证明了该算法的灵活性和有效性．

n this paper a heuristic method based on space decomposition for rectangular packing is proposed. Throuht the sequential decomposition of the packing space according to the depthfirst rule, the optimal packing scheme of various sized rectangular packing can be obtained by putting an optimal packing element each time that satisfies special conditions toward current packing sapce and locating it at the up-left corner of the current packing space. Different optimal packing schemes that satisfy different demands can be obtained by adjusting the values of the ordering factors KA and KB. In addition, the packing schemes obtained satisfy the guillotine cutting demands in glass industry. Both the experimental results and the comparison with other packing algorithms indicate that the algorithm is flexible and effective.