A Beam Search Approach Based on Action Space for the 2D Rectangular Packing Problem

A beam search algorithm is presented to solve the 2D rectangular packing problem. The basic algorithms work according to 7 rule vectors of heuristic selection rules designed to select a corner-sticking action. Furthermore, the trade-off scheme of breadth first search (BFS) and the depth first search (DFS) increases the algorithm’s effectiveness and efficiency. The improved version of the algorithm adopts a rough phase to get a height for the stripe and a refine phase to obtain better solution for the problem. Computational experiments run on two sets of well-known benchmark instances and the computational results show that the algorithm outperforms the current best algorithms. Especially, for two benchmark instances ZDF6 and ZDF7, our algorithm finds the best packing configurations so far.