An efficient constructive heuristic for the rectangular packing problem with rotations.
The rectangular packing problem has been extensively studied over the years due to its wide application in industry. However, most of the research efforts are devoted to positioning techniques of the rectangles for various problem variants, the efficient implementation of the packing procedure is re...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2023-01-01
|
| Series: | PLoS ONE |
| Online Access: | https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0295206&type=printable |
| _version_ | 1797366470676578304 |
|---|---|
| author | Xusheng Zhao Yunqing Rao Peng Qi Qianhang Lyu Piaoruo Yang Shoubo Yu |
| author_facet | Xusheng Zhao Yunqing Rao Peng Qi Qianhang Lyu Piaoruo Yang Shoubo Yu |
| author_sort | Xusheng Zhao |
| collection | DOAJ |
| description | The rectangular packing problem has been extensively studied over the years due to its wide application in industry. However, most of the research efforts are devoted to positioning techniques of the rectangles for various problem variants, the efficient implementation of the packing procedure is relatively less studied. In this paper, we propose an efficient constructive algorithm for the rectangular packing problem with rotations. We design a preprocess procedure with four data structures to store the information used for item selection. The gaps on the skyline are categorized into three types according to their associated edges for the placement procedure, during which the item is searched and packed in a descending order of the fitness value. The entire constructive phase takes a time complexity of O(nlogn). For the packing improvement phase, we optimize the packing through random perturbation on the sequence and orientation of the item. Three classes of stochastic problems are generated ranging from small-scale to extra-large-scale, the recorded running time confirms the efficiency of the proposed algorithm. We also test the proposed algorithm on the benchmark problem C21, N13, NT, Babu and CX, the computational results show that it delivers a good performance. |
| first_indexed | 2024-03-08T17:04:35Z |
| format | Article |
| id | doaj.art-0e6b017ba6bc42fe9c04060be6bc144a |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-03-08T17:04:35Z |
| publishDate | 2023-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-0e6b017ba6bc42fe9c04060be6bc144a2024-01-04T05:31:40ZengPublic Library of Science (PLoS)PLoS ONE1932-62032023-01-011812e029520610.1371/journal.pone.0295206An efficient constructive heuristic for the rectangular packing problem with rotations.Xusheng ZhaoYunqing RaoPeng QiQianhang LyuPiaoruo YangShoubo YuThe rectangular packing problem has been extensively studied over the years due to its wide application in industry. However, most of the research efforts are devoted to positioning techniques of the rectangles for various problem variants, the efficient implementation of the packing procedure is relatively less studied. In this paper, we propose an efficient constructive algorithm for the rectangular packing problem with rotations. We design a preprocess procedure with four data structures to store the information used for item selection. The gaps on the skyline are categorized into three types according to their associated edges for the placement procedure, during which the item is searched and packed in a descending order of the fitness value. The entire constructive phase takes a time complexity of O(nlogn). For the packing improvement phase, we optimize the packing through random perturbation on the sequence and orientation of the item. Three classes of stochastic problems are generated ranging from small-scale to extra-large-scale, the recorded running time confirms the efficiency of the proposed algorithm. We also test the proposed algorithm on the benchmark problem C21, N13, NT, Babu and CX, the computational results show that it delivers a good performance.https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0295206&type=printable |
| spellingShingle | Xusheng Zhao Yunqing Rao Peng Qi Qianhang Lyu Piaoruo Yang Shoubo Yu An efficient constructive heuristic for the rectangular packing problem with rotations. PLoS ONE |
| title | An efficient constructive heuristic for the rectangular packing problem with rotations. |
| title_full | An efficient constructive heuristic for the rectangular packing problem with rotations. |
| title_fullStr | An efficient constructive heuristic for the rectangular packing problem with rotations. |
| title_full_unstemmed | An efficient constructive heuristic for the rectangular packing problem with rotations. |
| title_short | An efficient constructive heuristic for the rectangular packing problem with rotations. |
| title_sort | efficient constructive heuristic for the rectangular packing problem with rotations |
| url | https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0295206&type=printable |
| work_keys_str_mv | AT xushengzhao anefficientconstructiveheuristicfortherectangularpackingproblemwithrotations AT yunqingrao anefficientconstructiveheuristicfortherectangularpackingproblemwithrotations AT pengqi anefficientconstructiveheuristicfortherectangularpackingproblemwithrotations AT qianhanglyu anefficientconstructiveheuristicfortherectangularpackingproblemwithrotations AT piaoruoyang anefficientconstructiveheuristicfortherectangularpackingproblemwithrotations AT shouboyu anefficientconstructiveheuristicfortherectangularpackingproblemwithrotations AT xushengzhao efficientconstructiveheuristicfortherectangularpackingproblemwithrotations AT yunqingrao efficientconstructiveheuristicfortherectangularpackingproblemwithrotations AT pengqi efficientconstructiveheuristicfortherectangularpackingproblemwithrotations AT qianhanglyu efficientconstructiveheuristicfortherectangularpackingproblemwithrotations AT piaoruoyang efficientconstructiveheuristicfortherectangularpackingproblemwithrotations AT shouboyu efficientconstructiveheuristicfortherectangularpackingproblemwithrotations |