Cargando…
A deep reinforcement learning algorithm for the rectangular strip packing problem
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 g...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Public Library of Science
2023
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10019708/ https://www.ncbi.nlm.nih.gov/pubmed/36928505 http://dx.doi.org/10.1371/journal.pone.0282598 |
_version_ | 1784908083652198400 |
---|---|
author | Fang, Jie Rao, Yunqing Shi, Mingliang |
author_facet | Fang, Jie Rao, Yunqing Shi, Mingliang |
author_sort | Fang, Jie |
collection | PubMed |
description | 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. |
format | Online Article Text |
id | pubmed-10019708 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2023 |
publisher | Public Library of Science |
record_format | MEDLINE/PubMed |
spelling | pubmed-100197082023-03-17 A deep reinforcement learning algorithm for the rectangular strip packing problem Fang, Jie Rao, Yunqing Shi, Mingliang PLoS One Research Article 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. Public Library of Science 2023-03-16 /pmc/articles/PMC10019708/ /pubmed/36928505 http://dx.doi.org/10.1371/journal.pone.0282598 Text en © 2023 Fang et al https://creativecommons.org/licenses/by/4.0/This is an open access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. |
spellingShingle | Research Article Fang, Jie Rao, Yunqing Shi, Mingliang A deep reinforcement learning algorithm for the rectangular strip packing problem |
title | A deep reinforcement learning algorithm for the rectangular strip packing problem |
title_full | A deep reinforcement learning algorithm for the rectangular strip packing problem |
title_fullStr | A deep reinforcement learning algorithm for the rectangular strip packing problem |
title_full_unstemmed | A deep reinforcement learning algorithm for the rectangular strip packing problem |
title_short | A deep reinforcement learning algorithm for the rectangular strip packing problem |
title_sort | deep reinforcement learning algorithm for the rectangular strip packing problem |
topic | Research Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10019708/ https://www.ncbi.nlm.nih.gov/pubmed/36928505 http://dx.doi.org/10.1371/journal.pone.0282598 |
work_keys_str_mv | AT fangjie adeepreinforcementlearningalgorithmfortherectangularstrippackingproblem AT raoyunqing adeepreinforcementlearningalgorithmfortherectangularstrippackingproblem AT shimingliang adeepreinforcementlearningalgorithmfortherectangularstrippackingproblem AT fangjie deepreinforcementlearningalgorithmfortherectangularstrippackingproblem AT raoyunqing deepreinforcementlearningalgorithmfortherectangularstrippackingproblem AT shimingliang deepreinforcementlearningalgorithmfortherectangularstrippackingproblem |