目的 针对多规格货物托盘码垛问题,提出一种优化箱子在托盘上的布局以及按层码垛的方法,以最大化码垛的空间利用率。方法 在考虑现实条件的约束下,以最大化托盘码垛堆的利用率为目标建立模型。将所研究的问题分解为2个子问题,并分2个阶段进行求解。第1阶段,通过对箱子高度的分析和组合,设计带旋转的匹配算法,形成高度近似的稳定装载箱,将三维问题转化为二维;第2阶段,提出融合PPO强化学习和改进天际线启发式算法,强化学习能为启发式算法提供一个装箱序列,有效地改善启发式冷启动的问题,使得装箱效果更好。结果 通过弱异质和强异质算例,在不同大小规模下对算法进行性能测试,得出装载强异构货物平均体积利用率达到92.5%,超过98%的箱子,获得了完全支撑,并且算法运行时间减少了38.6%。结论 所提算法为求解大规模多规格货物托盘码垛问题提供了快速高效的解决方案。
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
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[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.
PDF(2653 KB)
渝公网安备 50010702501716号 渝ICP备15012534号-2
