Randomized Greedy Strategy with Corner Filling for the Irregular 2D Bin Packing Problem

We are given a finite set of irregular items and an unlimited number of identical rectangular bins. Items presented as two-dimensional, possibly non-convex polygons. The length and width of bins are given. We need to pack all items without overlapping and minimize the number of used bins. The rotations of items by 90, 180, and 270 angles are allowed. In the packing algorithm, we apply a fitness function based on the gravity center of the packing area and idea of the well-known sky-line approach for regular packing problem. To improve the result, we apply a special rule to fill the corners of bins. This rule is based on a function to evaluate how good a corner of each item fits in the corner of the bin. We select a subset of items with the best values of this function and randomly choose one of them to pack in the corner. We present computational results with filling of one, two, three, and four corners of some bins before packing. The comparison with well-known algorithms is presented on the real test instances from Novosibirsk car mats manufacturer company with up to 50 items.