A new approach for bin packing problem using knowledge reuse and improved heuristic
Abstract The two-dimensional (2D) irregular packing problem is a combinatorial optimization problem with NP-complete characteristics, which is common in the production process of clothing, ships, and plate metals. The classic packing solution is a hybrid algorithm based on heuristic positioning and...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2024-12-01
|
| Series: | Scientific Reports |
| Subjects: | |
| Online Access: | https://doi.org/10.1038/s41598-024-81749-5 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841559485493018624 |
|---|---|
| author | Jie Fang Xubing Chen Yunqing Rao Yili Peng kuan Yan |
| author_facet | Jie Fang Xubing Chen Yunqing Rao Yili Peng kuan Yan |
| author_sort | Jie Fang |
| collection | DOAJ |
| description | Abstract The two-dimensional (2D) irregular packing problem is a combinatorial optimization problem with NP-complete characteristics, which is common in the production process of clothing, ships, and plate metals. The classic packing solution is a hybrid algorithm based on heuristic positioning and meta-heuristic sequencing, which has the problems of complex solving rules and high time cost. In this study, the similarity measurement method based on the twin neural network model is used to evaluate the similarity of pieces in the source task and the target task. The reusability evaluation of packing tasks is designed to select appropriate source task knowledge. The transfer operator is used to transfer the piece sequence knowledge from the source task to complete the reuse of packing knowledge in the target task. The bottom-left algorithm is improved to complete the placement of 2D irregular pieces. The computational experiments show that the proposed algorithm for the bin packing problem using knowledge reuse and improved heuristic (KRIH) has good robustness. The KRIH algorithm can obtain 8 equal or better results on 16 instances in a relatively short time compared with some classical heuristic algorithms, which has good application potential. |
| format | Article |
| id | doaj-art-1dc0453456d94b18a85a5f656146531f |
| institution | Kabale University |
| issn | 2045-2322 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Scientific Reports |
| spelling | doaj-art-1dc0453456d94b18a85a5f656146531f2025-01-05T12:27:08ZengNature PortfolioScientific Reports2045-23222024-12-0114112010.1038/s41598-024-81749-5A new approach for bin packing problem using knowledge reuse and improved heuristicJie Fang0Xubing Chen1Yunqing Rao2Yili Peng3kuan Yan4Hubei Provincial Key Laboratory of Chemical Equipment Intensification and Intrinsic Safety, Wuhan Institute of TechnologyHubei Provincial Key Laboratory of Chemical Equipment Intensification and Intrinsic Safety, Wuhan Institute of TechnologyState Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and TechnologyHubei Provincial Key Laboratory of Chemical Equipment Intensification and Intrinsic Safety, Wuhan Institute of TechnologySchool of Mechanical & Electrical Engineering, Wuhan Institute of TechnologyAbstract The two-dimensional (2D) irregular packing problem is a combinatorial optimization problem with NP-complete characteristics, which is common in the production process of clothing, ships, and plate metals. The classic packing solution is a hybrid algorithm based on heuristic positioning and meta-heuristic sequencing, which has the problems of complex solving rules and high time cost. In this study, the similarity measurement method based on the twin neural network model is used to evaluate the similarity of pieces in the source task and the target task. The reusability evaluation of packing tasks is designed to select appropriate source task knowledge. The transfer operator is used to transfer the piece sequence knowledge from the source task to complete the reuse of packing knowledge in the target task. The bottom-left algorithm is improved to complete the placement of 2D irregular pieces. The computational experiments show that the proposed algorithm for the bin packing problem using knowledge reuse and improved heuristic (KRIH) has good robustness. The KRIH algorithm can obtain 8 equal or better results on 16 instances in a relatively short time compared with some classical heuristic algorithms, which has good application potential.https://doi.org/10.1038/s41598-024-81749-5Packing problemIrregular pieceKnowledge reuseKnowledge transferHeuristic algorithms |
| spellingShingle | Jie Fang Xubing Chen Yunqing Rao Yili Peng kuan Yan A new approach for bin packing problem using knowledge reuse and improved heuristic Scientific Reports Packing problem Irregular piece Knowledge reuse Knowledge transfer Heuristic algorithms |
| title | A new approach for bin packing problem using knowledge reuse and improved heuristic |
| title_full | A new approach for bin packing problem using knowledge reuse and improved heuristic |
| title_fullStr | A new approach for bin packing problem using knowledge reuse and improved heuristic |
| title_full_unstemmed | A new approach for bin packing problem using knowledge reuse and improved heuristic |
| title_short | A new approach for bin packing problem using knowledge reuse and improved heuristic |
| title_sort | new approach for bin packing problem using knowledge reuse and improved heuristic |
| topic | Packing problem Irregular piece Knowledge reuse Knowledge transfer Heuristic algorithms |
| url | https://doi.org/10.1038/s41598-024-81749-5 |
| work_keys_str_mv | AT jiefang anewapproachforbinpackingproblemusingknowledgereuseandimprovedheuristic AT xubingchen anewapproachforbinpackingproblemusingknowledgereuseandimprovedheuristic AT yunqingrao anewapproachforbinpackingproblemusingknowledgereuseandimprovedheuristic AT yilipeng anewapproachforbinpackingproblemusingknowledgereuseandimprovedheuristic AT kuanyan anewapproachforbinpackingproblemusingknowledgereuseandimprovedheuristic AT jiefang newapproachforbinpackingproblemusingknowledgereuseandimprovedheuristic AT xubingchen newapproachforbinpackingproblemusingknowledgereuseandimprovedheuristic AT yunqingrao newapproachforbinpackingproblemusingknowledgereuseandimprovedheuristic AT yilipeng newapproachforbinpackingproblemusingknowledgereuseandimprovedheuristic AT kuanyan newapproachforbinpackingproblemusingknowledgereuseandimprovedheuristic |