A Q-learning-based algorithm for the 2D-rectangular packing problem

作者：Zhao, Xusheng; Rao, Yunqing^*; Meng, Ronghua; Fang, Jie

来源：SOFT COMPUTING, 2023, 27(17): 12057-12070.

DOI：10.1007/s00500-023-08381-9

• Rectangular packing problem
• Combinatorial optimization
• Fitness degree
• Reinforcement learning

This paper presents a Q-learning-based algorithm for sequence and orientation optimization toward the 2D rectangular strip packing problem. The width-filled skyline is used to represent the interior packing state, and a constructive rectangular packing algorithm with the commonly adopted fitness evaluation for placement is designed. Then, the consecutive item packing is simulated as Markov Decision Process, where the state is defined as the set of already packed items, and the action is defined as the rectangle selected to be packed along with its orientation. We propose the reverse updating of Q-value in the paradigm of Q-learning and use the algorithm to optimize the sequence and orientation of the rectangles. The decreasing-size-choice mechanism in Q-learning is studied on randomly generated problems to optimize the setting of epsilon-greedy policy. We also test the Q-learning-based algorithm on the benchmark instances of C21, N13, N-series from NT, Cgcut and Beng. Compared with a few state-of-the-art algorithms, the computational results show that the proposed algorithm can produce good packing quality when adequate execution time allowed.

• 单位
  华中科技大学