二维矩形件排样的切割式填充算法

Cut-filling Algorithm of 2D Rectangle Packing

针对二维矩形件排样困难的问题,提出了一种简单且高效的切割式填充矩形件排样算法.首先根据对矩形件进行优化排样的要求,建立起数学规划模型.然后采用降维的思想,对矩形行列虚拟化分割.在第一行(列)上进行矩形件排样,使其填充率最高.接着将此行(列)切割掉,形成新的矩形.最后重复上述步骤,直到矩形无法再填充下任何一种规格的矩形件为止.数值实验表明了切割式填充算法的可行性和高效性.

A simple and efficient Cut-filling rectangle packing algorithm was proposed for the two dimensional rectangle packing problem.First of all,according to the requirement of optimizing packing of rectangular pieces,a mathematical programming model is established.Then,spliting the rectangular into row and column virtually,with the idea of dimensionality reduction.Using rectangular pieces to nest on the first row(column)to maximize its filling rate.Cut this row(column)out to form a new rectangle.Finally,repeat the above steps until the rectangle can not be filled with any one of the rectangles.After virtualizing a rectangular row and column,use a rectangle to nest the first row(column)to maximize its fill rate and then cut the row(column)out to form a new rectangle.Repeat the above steps until the rectangle can not be filled with any one of the rectangles.Numerical experiments show the feasibility and high efficiency of the Cut-filling algorithm.