EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A deep reinforcement learning algorithm for the rectangular strip packing problem

Jie Fang iD, Yunqing Rao iD, Mingliang Shi

PLOS ONE · 16.03.2023 · 18 (3) · e0282598

DOI: 10.1371/journal.pone.0282598 ↗

Kurz gefasst

Fachartikel in der Zeitschrift PLOS ONE, online erschienen am 16.03.2023. Verfasst von Jie Fang und 2 weiteren Autor:innen. Beteiligte Einrichtung: State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, Wuhan, China. Hauptthemen laut MEDLINE: Algorithms, Reinforcement, Psychology. Die Arbeit wurde bisher 19-mal zitiert (Crossref) und nennt 62 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China, Fundamental Research Funds for the Central Universities.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

As a branch of the two-dimensional (2D) optimal blanking problem, rectangular strip packing is a typical non-deterministic polynomial (NP-hard) problem. The classical packing solution method relies on heuristic and metaheuristic algorithms. Usually, it needs to be designed with manual decisions to guide the solution, resulting in a small solution scale, weak generalization, and low solution efficiency. Inspired by deep learning and reinforcement learning, combined with the characteristics of rectangular piece packing, a novel algorithm based on deep reinforcement learning is proposed in this work to solve the rectangular strip packing problem. The pointer network with an encoder and decoder structure is taken as the basic network for the deep reinforcement learning algorithm. A model-free reinforcement learning algorithm is designed to train network parameters to optimize the packing sequence. This design can not only avoid designing heuristic rules separately for different problems but also use the deep networks with self-learning characteristics to solve different instances more widely. At the same time, a piece positioning algorithm based on the maximum rectangles bottom-left (Maxrects-BL) is designed to determine the placement position of pieces on the plate and calculate model rewards and packing parameters. Finally, instances are used to analyze the optimization effect of the algorithm. The experimental results show that the proposed algorithm can produce three better and five comparable results compared with some classical heuristic algorithms. In addition, the calculation time of the proposed algorithm is less than 1 second in all test instances, which shows a good generalization, solution efficiency, and practical application potential.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsReinforcement, PsychologyRewardHeuristics

Autor:innen und Institutionen

  • State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, Wuhan, China.
  • Laboratory of Multimedia Stream Computing and Storage, Huazhong University of Science and Technology, Wuhan, China.

ORCID-Profile: Jie Fang, Yunqing Rao

Förderung

  • National Natural Science Foundation of China
  • Fundamental Research Funds for the Central Universities

Zitieren

APA

Fang, J., Rao, Y., & Shi, M. (2023). A deep reinforcement learning algorithm for the rectangular strip packing problem. PLOS ONE, 18(3), e0282598. https://doi.org/10.1371/journal.pone.0282598

Vancouver

Fang J, Rao Y, Shi M. A deep reinforcement learning algorithm for the rectangular strip packing problem. PLOS ONE. 2023;18(3):e0282598. doi:10.1371/journal.pone.0282598

BibTeX
@article{Fang2023,
  author = {Fang, Jie and Rao, Yunqing and Shi, Mingliang},
  title = {A deep reinforcement learning algorithm for the rectangular strip packing problem},
  journal = {PLOS ONE},
  year = {2023},
  volume = {18},
  number = {3},
  pages = {e0282598},
  doi = {10.1371/journal.pone.0282598}
}
Kostenlos starten →