An adaptive selection approach for the 2D rectangle packing area minimization problem

This paper investigates the 2D rectangle packing area minimization problem (RPAMP), in which the objective is to pack a set of rectangles into a container with variable sizes and minimize the area of the container. The RPAMP is transformed into a series of 2D strip packing problems (2DSPs). Instead of selecting the set of most promising widths initially, a novel adaptive selection approach is proposed to choose a candidate width at each iteration. An iterative doubling search strategy is introduced to avoid spending too much effort on the same width. A skyline based best-fit heuristic is adapted to solve the 2DSP. Compared to previous approaches, the proposed one is much simpler as it does not need any control parameter. Computational experiments on the benchmark test sets show that the proposed method outperforms all existing approaches and improves the best-known solutions for most of the instances (28 out of 39 instances). Especially for the well-studied instances Ami33 and Ami49, the approach finds better solutions. (C) 2017 Elsevier Ltd. All rights reserved.