Reinforcement Learning Applied to 2D Strip Packing Problem: A Q-Learning Approach

Abstract

This study addresses the two-dimensional rectangular strip packing problem (2D-SPP), a significant combinatorial optimization challenge. A novel approach combining Q-learning with the Bottom-Left-Fill (BLF) algorithm, referred to as QL-BLF, is proposed. Our method aims to enhance packing efficiency by optimizing the sequence and orientation of items. We evaluated the performance of the QL-BLF algorithm against the traditional BLF algorithm using two datasets of 10 and 15 items, each tested across 10 distinct series to ensure comprehensive and reliable results. The computational experiments demonstrated that the QL-BLF algorithm consistently outperformed the BLF algorithm by significantly reducing the strip height and minimizing free space. These findings underscore the effectiveness of reinforcement learning in enhancing traditional heuristic methods for solving complex packing problems.