A BRKGA-RLS Metaheuristic for the Two-Dimensional Strip Packing Problem with Unloading Constraints

The Two-Dimensional Strip Packing Problem with Unloading Constraints (2D-SPU) consists of packing rectangular items from different customers into a rectangular strip of fixed width, in order to minimize the container height and enable the unloading of each customer's packages sequentially along a route. This work proposes a Biased Random-Key Genetic Algorithm (BRKGA) metaheuristic combined with Random Local Search (RLS) to solve the 2D-SPU. A warm-start strategy is employed to initialize the BRKGA-RLS populations with promising solutions. Furthermore, two cache-efficient data structures are utilized: a flat set, used to manage available spaces for packing, and a flat segment tree with lazy propagation used to handle the constraints. Experimental results show that the proposed approach achieved solutions at least as good as those from the state-of-the-art in 709 out of 825 instances, including 413 higher-quality solutions.