Block-based Strategy for Solving 2D Bin Packing Problems

ZHAO Xiangling; SU Tanjie; QIN Xue; LI Zhaoyang; CHEN Xiaogang

doi:10.19554/j.cnki.1001-3563.2026.01.013

PDF(2002 KB)

Packaging Engineering ›› 2026, Vol. 47 ›› Issue (1) : 111-121. DOI: 10.19554/j.cnki.1001-3563.2026.01.013

Automatic and Intelligent Technology

Block-based Strategy for Solving 2D Bin Packing Problems

ZHAO Xiangling¹, SU Tanjie¹, QIN Xue², LI Zhaoyang³, CHEN Xiaogang²

Author information +

History +

Abstract

The work aims to address the two-dimensional strip packing problem (2D-SPP) to enhance space utilization and computational efficiency for complex loading scenarios in logistics and manufacturing. A two-stage optimization algorithm which integrates block partitioning and layered stacking was proposed. In Stage 1, a block partitioning strategy divided the container into segments, targeting minimal block count and maximal total block length, each block mapped to a specific item length. In Stage 2, a dynamic layered stacking mechanism was introduced to construct an efficient single-block assembly method. Comparison between 17 sets of classic benchmark data and the adaptive block partitioning strategy and the Gurobi solver showed that the proposed algorithm achieved an average solution time of just 0.10 seconds and an area utilization of 85.06%, compared with an adaptive block partitioning strategy (0.97 seconds, 72.96% utilization) and the Gurobi solver (1 285.15 seconds, 72.91% utilization). When compared with other methods from the literature, the algorithm achieved an average area utilization of 84.70% with a standard deviation of 0.56 in a mean runtime of 0.51 seconds, outperforming most competing algorithms. Furthermore, its practical value was validated on five real-world air cargo cases with up to 565 items, where the planning time was only 2.81 seconds, meeting the demands for real-time industrial applications. The proposed method offers a balanced trade-off between packing performance and computational speed, making it well-suited for real-time, reliability-critical industrial applications and providing a scalable solution for complex logistics loading optimization.

Key words

two-dimensional bin packing problem / block strategy / area utilization rate / combinatorial optimization / heuristic algorithm

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

ZHAO Xiangling, SU Tanjie, QIN Xue, LI Zhaoyang, CHEN Xiaogang. Block-based Strategy for Solving 2D Bin Packing Problems[J]. Packaging Engineering. 2026, 47(1): 111-121 https://doi.org/10.19554/j.cnki.1001-3563.2026.01.013

References

[1] OLIVEIRA Ó, GAMBOA D, SILVA E.An Introduction to the Two-Dimensional Rectangular Cutting and Packing Problem[J]. International Transactions in Operational Research, 2023, 30(6): 3238-3266.
[2] BECKER H, ARAUJO O, BURIOL L S.Extending an Integer Formulation for the Guillotine 2D Bin Packing Problem[J]. Procedia Computer Science, 2021, 195: 499-507.
[3] GUIMARÃES G G, POLDI K C. Mathematical Models for the Cutting Stock with Limited Open Stacks Problem[J]. RAIRO - Operations Research, 57(4): 2067-2085.
[4] LIU C, SMITH-MILES K, WAUTERS T, et al.Instance Space Analysis for 2D Bin Packing Mathematical Models[J]. European Journal of Operational Research, 2024, 315(2): 484-498.
[5] GARDEYN J, WAUTERS T.A Goal-Driven Ruin and Recreate Heuristic for the 2D Variable-Sized Bin Packing Problem with Guillotine Constraints[J]. European Journal of Operational Research, 2022, 301(2): 432-444.
[6] BEYAZ M, DOKEROGLU T, COSAR A.Robust Hyper-Heuristic Algorithms for the Offline Oriented/Non-Oriented 2D Bin Packing Problems[J]. Applied Soft Computing, 2015, 36: 236-245.
[7] MARTINEZ-SYKORA A, ALVAREZ-VALDES R, BENNELL J A, et al.Matheuristics for the Irregular Bin Packing Problem with Free Rotations[J]. European Journal of Operational Research, 2017, 258(2): 440-455.
[8] ZHANG H, YAO S W, LIU Q, et al.An Exact Approach for the Constrained Two-Dimensional Guillotine Cutting Problem with Defects[J]. International Journal of Production Research, 2023, 61(9): 2986-3003.
[9] GONÇALVES J F, WÄSCHER G. A MIP Model and a Biased Random-Key Genetic Algorithm Based Approach for a Two-Dimensional Cutting Problem with Defects[J]. European Journal of Operational Research, 2020, 286(3): 867-882.
[10] POLYAKOVSKIY S, M'HALLAH R. Just-in-Time Two-Dimensional Bin Packing[J]. Omega, 2021, 102: 102311.
[11] MAO Z F, FU E Y, HUANG D, et al.Combinatorial Benders Decomposition for Single Machine Scheduling in Additive Manufacturing with Two-Dimensional Packing Constraints[J]. European Journal of Operational Research, 2024, 317(3): 890-905.
[12] ZIPFEL B, MHALLAH R, BUSCHER U.Scheduling for Additive Manufacturing with Two-Dimensional Packing and Incompatible Items[J]. Omega, 2024, 129: 103139.
[13] HU K X, CHE Y X, NG T S, et al.Unrelated Parallel Batch Processing Machine Scheduling with Time Requirements and Two-Dimensional Packing Constraints[J]. Computers & Operations Research, 2024, 162: 106474.
[14] AKÇAY F B, DELORME M. Solving the Parallel Processor Scheduling and Bin Packing Problems with Contiguity Constraints: Mathematical Models and Computational Studies[J]. European Journal of Operational Research, 2025, 323(3): 701-723.
[15] ZHAO X F, SHEN H.Online Algorithms for 2D Bin Packing with Advice[J]. Neurocomputing, 2016, 189: 25-32.
[16] ORTMANN F G, NTENE N, VAN VUUREN J H. New and Improved Level Heuristics for the Rectangular Strip Packing and Variable-Sized Bin Packing Problems[J]. European Journal of Operational Research, 2010, 203(2): 306-315.
[17] HONG S H, ZHANG D F, LAU H C, et al.A Hybrid Heuristic Algorithm for the 2D Variable-Sized Bin Packing Problem[J]. European Journal of Operational Research, 2014, 238(1): 95-103.
[18] SUN B F, LI G D, WANG S, et al.Two-Dimensional Bin-Packing Problem with Conflicts and Load Balancing: A Hybrid Chaotic and Evolutionary Particle Swarm Optimization Algorithm[J]. Computers & Industrial Engineering, 2025, 200: 110851.
[19] ZHANG H, LIU Q, WEI L J, et al.An Iteratively Doubling Local Search for the Two-Dimensional Irregular Bin Packing Problem with Limited Rotations[J]. Computers & Operations Research, 2022, 137: 105550.
[20] TOLE K, MOQA R, ZHENG J Z, et al.A Simulated Annealing Approach for the Circle Bin Packing Problem with Rectangular Items[J]. Computers & Industrial Engineering, 2023, 176: 109004.
[21] 阳名钢, 陈梦烦, 杨双远, 等. 求解二维装箱问题的强化学习启发式算法[J]. 软件学报, 2021, 32(12): 3684-3697.
YANG M G, CHEN M F, YANG S Y, et al.Reinforcement Learning Heuristic Algorithm for Solving the Two-Dimensional Strip Packing Problem[J]. Journal of Software, 2021, 32(12): 3684-3697.
[22] NEUENFELDT A J, SILUK J, FRANCESCATTO M, et al.A Framework to Select Heuristics for the Rectangular Two-Dimensional Strip Packing Problem[J]. Expert Systems with Applications, 2023, 213: 119202.
[23] YEHIA A, ASHOUR M, ABEDA A M, et al.A Review of Two-Dimensional Offline Rectangular Strip Packing Problem Heuristics[J]. European Chemical Bulletin, 2023, 12(7): 2761-2772.
[24] SOUZA F, GRIMES D.Combining Local Search and Genetic Algorithm for Two-Dimensional GuillotineBin Packing Problems with Partial Sequence Constraint[C]// AICS, 2020: 97-108.
[25] 刘佳, 苌道方, 王云华, 等. 基于分层决策的多规格货物托盘码垛问题的两阶段算法[J]. 包装工程, 2025, 46(11): 277-284.
LIU J, CHANG D F, WANG Y H, et al.Two-Stage Algorithm for Multi-Specification Cargo Pallet Loading Problem Based on Hierarchical Decision-Making[J]. Packaging Engineering, 2025, 46(11): 277-284.
[26] 杨玉冰, 杨松坡. 基于列生成和分支定界算法的两阶段二次装箱问题[J]. 计算机集成制造系统, 2025, 31(1): 341-354.
YANG Y B, YANG S P.Two-Stage Quadratic Packing Problem Based on Column Generation and Branch and Bound Algorithm[J]. Computer Integrated Manufacturing Systems, 2025, 31(1): 341-354.
[27] 尚正阳, 黄秋妍, 康正阳, 等. 一刀切约束下的二维装箱问题高效求解算法[J]. 包装工程, 2021, 42(7): 231-238.
SHANG Z Y, HUANG Q Y, KANG Z Y, et al.Efficient Heuristic Algorithm for the Two-Dimensional Guillotine Rectangular Bin Packing Problem[J]. Packaging Engineering, 2021, 42(7): 231-238.
[28] 尚正阳, 顾寄南, 丁卫, 等. 求解二维矩形装箱问题的启发式算法[J]. 计算机集成制造系统, 2018, 24(3): 583-590.
SHANG Z Y, GU J N, DING W, et al.Heuristic Algorithm for 2D Rectangle Packing Problem[J]. Computer Integrated Manufacturing Systems, 2018, 24(3): 583-590.
[29] ZHANG H, YAO S W, ZHANG S H, et al.A Block-Based Heuristic Search Algorithm for the Two-Dimensional Guillotine Strip Packing Problem[J]. Engineering Applications of Artificial Intelligence, 2024, 134: 108624.