Robust Optimization for the Two-Dimensional Strip-Packing Problem with Variable-Sized Bins
The two-dimensional strip-packing problem (2D-SPP) emerges as a notable variant of the cutting and packing (C&P) problem, aiming to optimize the arrangement of small rectangular items within unique strips with a fixed width and infinite height to minimize the usage of height. Despite extensive a...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-11-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/23/4781 |
| _version_ | 1797399842903818240 |
|---|---|
| author | Kaiyuan Liu Hongyu Zhang Chong Wang Hui Li Yongquan Chen Qiong Chen |
| author_facet | Kaiyuan Liu Hongyu Zhang Chong Wang Hui Li Yongquan Chen Qiong Chen |
| author_sort | Kaiyuan Liu |
| collection | DOAJ |
| description | The two-dimensional strip-packing problem (2D-SPP) emerges as a notable variant of the cutting and packing (C&P) problem, aiming to optimize the arrangement of small rectangular items within unique strips with a fixed width and infinite height to minimize the usage of height. Despite extensive academic exploration, applying 2D-SPP solutions in industrial settings remains challenging. Two significant issues, often overlooked in academia yet frequently encountered in industrial contexts, are the uncertain demand for items, exacerbated by the bullwhip effect, and the need for diverse types of strips to cater to varying customer needs. Our paper addresses this academia–industry gap by proposing a robust optimization model for the uncertain 2D-SPP with variable-sized bins, aiming to manage the demand fluctuations within a box uncertainty set framework. Additionally, we employ the contiguous one-dimensional relaxation technique in conjunction with column generation to tighten the lower bound of the problem, thereby augmenting solution accuracy. Furthermore, we leverage the Karush–Kuhn–Tucker (KKT) condition to transform the model into a more tractable form, subsequently leading to an exact solution. Based on datasets from a real-life plastic-cutting company, comprehensive experiments validate the effectiveness and efficiency of our proposed relaxation method and algorithm, showcasing the potential for an improved industrial application of 2D-SPP solutions. |
| first_indexed | 2024-03-09T01:46:57Z |
| format | Article |
| id | doaj.art-6e1cee26c185409387eb7d0bbbe772f8 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T01:46:57Z |
| publishDate | 2023-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-6e1cee26c185409387eb7d0bbbe772f82023-12-08T15:21:45ZengMDPI AGMathematics2227-73902023-11-011123478110.3390/math11234781Robust Optimization for the Two-Dimensional Strip-Packing Problem with Variable-Sized BinsKaiyuan Liu0Hongyu Zhang1Chong Wang2Hui Li3Yongquan Chen4Qiong Chen5Department of Logistics and Transportation, Shenzhen International Graduate School, Tsinghua University, Shenzhen 518055, ChinaDepartment of Logistics and Transportation, Shenzhen International Graduate School, Tsinghua University, Shenzhen 518055, ChinaDepartment of Logistics and Transportation, Shenzhen International Graduate School, Tsinghua University, Shenzhen 518055, ChinaShenzhen Institute of Artificial Intelligence and Robotics for Society, Chinese University of Hong Kong, Shenzhen 518172, ChinaShenzhen Institute of Artificial Intelligence and Robotics for Society, Chinese University of Hong Kong, Shenzhen 518172, ChinaNavigation College, Jimei University, Xiamen 361021, ChinaThe two-dimensional strip-packing problem (2D-SPP) emerges as a notable variant of the cutting and packing (C&P) problem, aiming to optimize the arrangement of small rectangular items within unique strips with a fixed width and infinite height to minimize the usage of height. Despite extensive academic exploration, applying 2D-SPP solutions in industrial settings remains challenging. Two significant issues, often overlooked in academia yet frequently encountered in industrial contexts, are the uncertain demand for items, exacerbated by the bullwhip effect, and the need for diverse types of strips to cater to varying customer needs. Our paper addresses this academia–industry gap by proposing a robust optimization model for the uncertain 2D-SPP with variable-sized bins, aiming to manage the demand fluctuations within a box uncertainty set framework. Additionally, we employ the contiguous one-dimensional relaxation technique in conjunction with column generation to tighten the lower bound of the problem, thereby augmenting solution accuracy. Furthermore, we leverage the Karush–Kuhn–Tucker (KKT) condition to transform the model into a more tractable form, subsequently leading to an exact solution. Based on datasets from a real-life plastic-cutting company, comprehensive experiments validate the effectiveness and efficiency of our proposed relaxation method and algorithm, showcasing the potential for an improved industrial application of 2D-SPP solutions.https://www.mdpi.com/2227-7390/11/23/4781robust optimizationtwo-dimensional strip-packing problemvariable-sized binscolumn generationcontiguous relaxationone-dimensional bin-packing problem |
| spellingShingle | Kaiyuan Liu Hongyu Zhang Chong Wang Hui Li Yongquan Chen Qiong Chen Robust Optimization for the Two-Dimensional Strip-Packing Problem with Variable-Sized Bins Mathematics robust optimization two-dimensional strip-packing problem variable-sized bins column generation contiguous relaxation one-dimensional bin-packing problem |
| title | Robust Optimization for the Two-Dimensional Strip-Packing Problem with Variable-Sized Bins |
| title_full | Robust Optimization for the Two-Dimensional Strip-Packing Problem with Variable-Sized Bins |
| title_fullStr | Robust Optimization for the Two-Dimensional Strip-Packing Problem with Variable-Sized Bins |
| title_full_unstemmed | Robust Optimization for the Two-Dimensional Strip-Packing Problem with Variable-Sized Bins |
| title_short | Robust Optimization for the Two-Dimensional Strip-Packing Problem with Variable-Sized Bins |
| title_sort | robust optimization for the two dimensional strip packing problem with variable sized bins |
| topic | robust optimization two-dimensional strip-packing problem variable-sized bins column generation contiguous relaxation one-dimensional bin-packing problem |
| url | https://www.mdpi.com/2227-7390/11/23/4781 |
| work_keys_str_mv | AT kaiyuanliu robustoptimizationforthetwodimensionalstrippackingproblemwithvariablesizedbins AT hongyuzhang robustoptimizationforthetwodimensionalstrippackingproblemwithvariablesizedbins AT chongwang robustoptimizationforthetwodimensionalstrippackingproblemwithvariablesizedbins AT huili robustoptimizationforthetwodimensionalstrippackingproblemwithvariablesizedbins AT yongquanchen robustoptimizationforthetwodimensionalstrippackingproblemwithvariablesizedbins AT qiongchen robustoptimizationforthetwodimensionalstrippackingproblemwithvariablesizedbins |