A goal-driven approach to the 2D bin packing and variable-sized bin packing problems

In this paper, we examine the two-dimensional variable-sized bin packing problem (2DVSBPP), where the task is to pack all given rectangles into bins of various sizes such that the total area of the used bins is minimized. We partition the search space of the 2DVSBPP into sets and impose an order on the sets, and then use a goal-driven approach to take advantage of the special structure of this partitioned solution space. Since the 2DVSBPP is a generalization of the two-dimensional bin packing problem (2DBPP), our approach can be adapted to the 2DBPP with minimal changes. Computational experiments on the standard benchmark data for both the 2DVSBPP and 2DBPP shows that our approach is more effective than existing approaches in literature.

Highlight
► We devise a goal-driven approach for the 2D variable-sized bin packing problem.
► The solution search space is partitioned into subsets by objective value.
► The search is designed to rapidly approach the subset containing optimal solutions.
► We outperform existing approaches on standard benchmarks for 2DVSBPP.
► We outperform existing approaches on the well-studied 2D bin packing problem.