Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems

TLDR

Two‑dimensional bin packing involves placing non‑overlapping rectangles into the fewest identical bins with edges parallel, allowing fixed or 90° rotations and optional edge‑to‑edge cut constraints. This study examines the full set of problem variants generated by all combinations of these requirements. The authors propose a dedicated heuristic for each variant and a unified tabu‑search framework that selects the appropriate heuristic for neighborhood exploration, with performance assessed by extensive computational experiments.

Abstract

Two-dimensional bin packing problems consist of allocating, without overlapping, a given set of small rectangles (items) to a minimum number of large identical rectangles (bins), with the edges of the items parallel to those of the bins. According to the specific application, the items may either have a fixed orientation or they can be rotated by 90°. In addition, it may or not be imposed that the items are obtained through a sequence of edge-to-edge cuts parallel to the edges of the bin. In this article, we consider the class of problems arising from all combinations of the above requirements. We introduce a new heuristic algorithm for each problem in the class, and a unified tabu search approach that is adapted to a specific problem by simply changing the heuristic used to explore the neighborhood. The average performance of the single heuristics and of the tabu search are evaluated through extensive computational experiments.