Randomized Local Search on the 2D Rectangular Bin Packing Problem with Item Rotation

The two-dimensional orthogonal rectangular Bin Packing Problem without orientation (here abbreviated as 2D-BPP) asks us to place, without overlap, sets of rectangular items into as few rectangular bins as possible. The items can have different sizes and can be rotated by 90 degrees. Their edges must be parallel to the edges of the bins. All bins have the same fixed size. We analyze the performance of Randomized Local Search (RLS) on the recently published 2DPackLib benchmark dataset. The RLS works on the space of signed permutations and applies a variant of the Improved Bottom Left heuristic as decoding step. We test seven objective functions that drive the search towards solutions occupying fewer bins. The RLS yields surprisingly good performance when minimizing the number of bins and, at lower priority, the area under the skyline of objects in the bins. We provide the complete set of results and all algorithm implementations in an immutable archive.