Solving rectangular strip packing problem with reinforcement learning: a comparative case study

This paper examines the value-based reinforcement learning method applied to the optimization of the rectangular strip packing problem with three different approaches to define the state and the action. The episode in the reinforcement learning is defined as a round of placement of all the given pieces. We analyze the drawbacks of two previously designed approaches and propose that the state is defined by the stage along with the selected piece. We also record the fitness value of the placement during the packing and design a fitness-based reward. The three methods are evaluated on a group of random packing problems in terms of time consumption by searching for the particular state, memory consumption by recording the past state, and the efficiency of packing optimization. The results show that the proposed reinforcement learning with fitness-based reward delivers a good comprehensive performance. The proposed method is also tested on a few well-known benchmark problems, and the results indicate that the proposed method could be an effective tool. We discuss the similarities and differences between the reinforcement learning method and the local search method.