Two-stage Algorithm for Multi-specification Cargo Pallet Loading Problem Based on Hierarchical Decision-making

LIU Jia; CHANG Daofang; WANG Yunhua; WANG Shuai

doi:10.19554/j.cnki.1001-3563.2025.11.030

PDF(2653 KB)

Packaging Engineering ›› 2025, Vol. 46 ›› Issue (11) : 277-284. DOI: 10.19554/j.cnki.1001-3563.2025.11.030

Green Packaging and Circular Economy

Two-stage Algorithm for Multi-specification Cargo Pallet Loading Problem Based on Hierarchical Decision-making

LIU Jia, CHANG Daofang, WANG Yunhua, WANG Shuai

Author information +

History +

Abstract

The work aims to address the multi-specification cargo pallet loading problem by proposing a method to optimize the arrangement of boxes on pallets and their layered stacking, aiming to maximize space utilization. Considering real-world constraints, a model was established with the goal of maximizing the utilization rate of pallet stacks. The problem was decomposed into two sub-problems and solved through a two-stage approach. In the first stage, a rotation-enabled matching algorithm was designed to analyze and combine box heights, forming stable loading units with similar heights, thereby transforming the 3D problem into a 2D one. In the second stage, a hybrid approach integrating PPO reinforcement learning and an improved skyline heuristic algorithm was proposed. The reinforcement learning component provided an initial packing sequence for the heuristic algorithm, effectively addressing the cold-start problem and improving packing efficiency. Experimental results on weakly and strongly heterogeneous instances of varying scales demonstrated that the algorithm achieved an average volume utilization rate of 92.5% for strongly heterogeneous cargo, with over 98% of boxes fully supported. Additionally, the algorithm reduced running time by 38.6%. The proposed algorithm offers a fast and efficient solution for large-scale multi-specification cargo pallet loading problems.

Key words

palletizing / improved skyline algorithm / reinforcement learning / layered decision

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

LIU Jia, CHANG Daofang, WANG Yunhua, WANG Shuai. Two-stage Algorithm for Multi-specification Cargo Pallet Loading Problem Based on Hierarchical Decision-making[J]. Packaging Engineering. 2025, 46(11): 277-284 https://doi.org/10.19554/j.cnki.1001-3563.2025.11.030

References

[1] GEORGE J A, ROBINSON D F.A Heuristic for Packing Boxes into a Container[J]. Computers & Operations Research, 1980, 7(3): 147-156.
[2] BISCHOFF E E, MARRIOTT M D.A Comparative Evaluation of Heuristics for Container Loading[J]. European Journal of Operational Research, 1990, 44(2): 267-276.
[3] EGEBLAD J, PISINGER D.Heuristic Approaches for the Two- and Three-Dimensional Knapsack Packing Problem[J]. Computers & Operations Research, 2009, 36(4): 1026-1049.
[4] ELEY M.Solving Container Loading Problems by Block Arrangement[J]. European Journal of Operational Research, 2002, 141(2): 393-409.
[5] KILINCCI O, MEDINOGLU E.An Efficient Method for the Three-Dimensional Container Loading Problem by Forming Box Sizes[J]. Engineering Optimization, 2022, 54(6): 1073-1088.
[6] 侯莹, 吴毅琳, 白星, 等. 数据驱动选择策略的多目标差分进化算法[J]. 控制与决策, 2023, 38(7): 1816-1824.
HOU Y, WU Y L, BAI X, et al.Multi-Objective Differential Evolution Algorithm with Data-Driven Selection Strategy[J]. Control and Decision, 2023, 38(7): 1816-1824.
[7] 张晶蓉, 贺占文, 周艳杰, 等. 基于混合整数规划的工厂产品托盘打包及装箱问题研究[J]. 包装工程, 2023, 44(17): 143-151.
ZHANG J R, HE Z W, ZHOU Y J, et al.Pallet Packing and Container Loading of Factory Products Based on Mixed Integer Programming Approach[J]. Packaging Engineering, 2023, 44(17): 143-151.
[8] 李孙寸, 施心陵, 张松海, 等. 基于多元优化算法的三维装箱问题的研究[J]. 自动化学报, 2018, 44(1): 106-115.
LI S C, SHI X L, ZHANG S H, et al.Multi-Variant Optimization Algorithm for Three Dimensional Container Loading Problem[J]. Acta Automatica Sinica, 2018, 44(1): 106-115.
[9] 刘胜, 沈大勇, 商秀芹, 等. 求解三维装箱问题的多层树搜索算法[J]. 自动化学报, 2020, 46(6): 1178-1187.
LIU S, SHEN D Y, SHANG X Q, et al.A Multi-Level Tree Search Algorithm for Three Dimensional Container Loading Problem[J]. Acta Automatica Sinica, 2020, 46(6): 1178-1187.
[10] 宋卫生, 薛阳. 托盘装载优化设计系统的开发[J]. 包装工程, 2021, 42(13): 205-211.
SONG W S, XUE Y.Development of Pallet Loading Optimization Design System[J]. Packaging Engineering, 2021, 42(13): 205-211.
[11] ARAYA I, MOYANO M, SANCHEZ C.A Beam Search Algorithm for the Biobjective Container Loading Problem[J]. European Journal of Operational Research, 2020, 286(2): 417-431.
[12] 于明正, 徐斌, 陈佳. 基于双层启发式遗传算法的三维装箱问题[J]. 科学技术与工程, 2020, 20(5): 2042-2047.
YU M Z, XU B, CHEN J.3D Packing Problem Based on Double-Layer Heuristic Genetic Algorithm[J]. Science Technology and Engineering, 2020, 20(5): 2042-2047.
[13] 张长勇, 翟一鸣. 考虑预分配策略的航空货物多箱装载优化[J]. 包装工程, 2020, 41(15): 75-80.
ZHANG C Y, ZHAI Y M.Multi-Container Loading Optimization of Air Cargo Considering Pre-Distribution Strategy[J]. Packaging Engineering, 2020, 41(15): 75-80.
[14] 张钧, 贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39.
ZHANG J, HE K T.Study on Hybrid Genetic and Simulated Annealing Algorithm for Three-Dimensional Packing Problems[J]. Computer Engineering and Applications, 2019, 55(14): 32-39.
[15] 侯克金, 袁锐波, 杨灏泉, 等. 基于混合蚁群算法的货物码垛模型研究[J]. 轻工机械, 2022, 40(6): 96-104.
HOU K J, YUAN R B, YANG H Q, et al.Cargo Palletizing Model Based on Hybrid Ant Colony Algorithm[J]. Light Industry Machinery, 2022, 40(6): 96-104.
[16] 尹昊, 陈帆, 和红杰. 基于深度强化学习的四向协同三维装箱方法[J]. 自动化学报, 2024, 50(12): 2420-2431.
YIN H, CHEN F, HE H J.A Four Directional Cooperative Three-Dimensional Packing Method Based on Deep Reinforcement Learning[J]. Acta Automatica Sinica, 2024, 50(12): 2420-2431.
[17] KARIMI-MAMAGHAN M, MOHAMMADI M, MEYER P, et al.Machine Learning at the Service of Meta-Heuristics for Solving Combinatorial Optimization Problems: A State-of-the-Art[J]. European Journal of Operational Research, 2022, 296(2): 393-422.