Rectangle packing with a recursive Pilot Method

We propose a deterministic tree search procedure for the Rectangle Packing Problem, where a set of rectangular items must be packed into a rectangular container such that the unoccupied area of the container is the minimum possible. The tree search is based on two literature methods whose strong points complement each other. First, a skyline-based heuristic strongly restricts the number of items that must be evaluated and the number of positions where they may be placed. Also, a generalization of the Pilot Method meta-heuristic expands the search tree gradually, iteratively increasing the tree size within a given time limit. We also devise tree pruning strategies to further reduce the exploration size. Empirical results surpass state-of-the-art solutions on most benchmark data sets, subject to computation time limits comparable to those of the literature, and we analyze how the quality of the solutions varies depending on the geometry of the items.