An Effective Heuristic Algorithm for the Two-Dimensional Orthogonal Packing Problem

This paper investigates the classic two-dimensional orthogonal packing problem (2DOPP), which aims to determine whether a set of rectangular items can be packed orthogonally into a given rectangular container. To address this problem, we introduce a new scoring rule for evaluating the positions of rectangular items and design a skyline-based decoding procedure. Moreover, based on this decoding procedure, we propose a randomized local search method to rapidly improve the solution quality. We assess the performance of the local search algorithm by applying it to a set of benchmark instances, which were extensively used in the literature. The computational results demonstrate that the decoding procedure can quickly generate a packing configuration and that the proposed local search algorithm is highly effective. Experimental analysis shows that the scoring function plays a crucial role for the high performance of proposed algorithm.