.png){kind=icon}
Return
A Q-learning-based algorithm for the 2D-rectangular packing problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s00500-023-08381-9.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Rectangular packing problem
Combinatorial optimization
Fitness degree
Reinforcement learning
Journal
IF:
2.5
Papers:
1.0W
Citations:
2.2W
Organization
Cited Papers
ShareSaveShareSaveShareSaveShareSaveThe effect of 3-nitropropionic acid on behavioral dysfunction, neuron loss and gliosis in the brain of adult male rats: The case of prefrontal cortex, hippocampus and the cerebellum.png)
Toxicon
ToxiconIF0
PREAI
ShareSaveTwo-dimensional strip packing problem with load balancing, load bearing and multi-drop constraints
OAAI
OAAIShareSave
View more