An intelligent search algorithm for the two-dimensional rectangular packing problem based on packing information feedback

We present a new intelligent search algorithm for the two-dimensional rectangular strip packing problem. The rectangular packing problems are usually solved through the integration of a constructive packing algorithm and a meta-heuristic, in which the former constructs the solution by packing items piece by piece, and the latter explores different sequences of items. However, we observe two rarely studied factors that could impair the exploration efficiency of the meta-heuristic. We refer to them as packing aftereffect and partial layered placement, and we present a detailed analysis of their causes. We improve the constructive packing algorithm to record whether the item creates waste regions and the placement fitness value of the item, which serves as the packing information feedback. Then, we propose the feedback search (FS) algorithm to avoid the inefficiency caused by the packing aftereffect and the partial layered placement, where the solution update mechanism is assisted by the packing information. The execution test on three groups of random packing problems indicates that FS has higher exploration efficiency than the most commonly adopted genetic algorithm and simulated annealing. The computational results on a group of well-known benchmark problems show that FS is an effective method.