A Hybrid Reinforcement Learning Algorithm for 2D Irregular Packing Problems

Jie Fang, Yunqing Rao (), Xusheng Zhao and Bing Du
Additional contact information
Jie Fang: School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China
Yunqing Rao: School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China
Xusheng Zhao: School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China
Bing Du: School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China

Mathematics, 2023, vol. 11, issue 2, 1-17

Abstract: Packing problems, also known as nesting problems or bin packing problems, are classic and popular NP-hard problems with high computational complexity. Inspired by classic reinforcement learning (RL), we established a mathematical model for two-dimensional (2D) irregular-piece packing combined with characteristics of 2D irregular pieces. An RL algorithm based on Monte Carlo learning (MC), Q-learning, and Sarsa-learning is proposed in this paper to solve a 2D irregular-piece packing problem. Additionally, mechanisms of reward–return and strategy-update based on piece packing were designed. Finally, the standard test case of irregular pieces was used for experimental testing to analyze the optimization effect of the algorithm. The experimental results show that the proposed algorithm can successfully realize packing of 2D irregular pieces. A similar or better optimization effect can be obtained compared to some classical heuristic algorithms. The proposed algorithm is an early attempt to use machine learning to solve 2D irregular packing problems. On the one hand, our hybrid RL algorithm can provide a basis for subsequent deep reinforcement learning (DRL) to solve packing problems, which has far-reaching theoretical significance. On the other hand, it has practical significance for improving the utilization rate of raw materials and broadening the application field of machine learning.

Keywords: irregular packing optimization; RL algorithm; machine learning; mathematical model; heuristic algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/2/327/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/2/327/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:2:p:327-:d:1028785

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().