Robust Optimization for the Two-Dimensional Strip-Packing Problem with Variable-Sized Bins

Kaiyuan Liu, Hongyu Zhang, Chong Wang, Hui Li (), Yongquan Chen () and Qiong Chen
Additional contact information
Kaiyuan Liu: Department of Logistics and Transportation, Shenzhen International Graduate School, Tsinghua University, Shenzhen 518055, China
Hongyu Zhang: Department of Logistics and Transportation, Shenzhen International Graduate School, Tsinghua University, Shenzhen 518055, China
Chong Wang: Department of Logistics and Transportation, Shenzhen International Graduate School, Tsinghua University, Shenzhen 518055, China
Hui Li: Shenzhen Institute of Artificial Intelligence and Robotics for Society, Chinese University of Hong Kong, Shenzhen 518172, China
Yongquan Chen: Shenzhen Institute of Artificial Intelligence and Robotics for Society, Chinese University of Hong Kong, Shenzhen 518172, China
Qiong Chen: Navigation College, Jimei University, Xiamen 361021, China

Mathematics, 2023, vol. 11, issue 23, 1-22

Abstract: 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.

Keywords: robust optimization; two-dimensional strip-packing problem; variable-sized bins; column generation; contiguous relaxation; one-dimensional bin-packing problem; KKT conditions (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/23/4781/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/23/4781/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:23:p:4781-:d:1288569

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().