基于分组策略的多目标三维装箱算法  

Multi-objective 3D Packing Algorithm Based on Grouping Strategy

作　　者：张长勇 吴刚鑫 ZHANG Chang-yong;WU Gang-xin(School of Electronic Information and Automation,Civil Aviation University of China,Tianjin 300300,China)

机构地区：[1]中国民航大学电子信息与自动化学院,天津300300

出　　处：《包装工程》2023年第21期204-213,共10页Packaging Engineering

基　　金：民航首台(套)重点项目(3122023PY04)。

摘　　要：目的针对现有三维装箱算法优化目标单一、优化效率低的问题,提出适用于求解大规模货物装载问题的多目标装箱算法,以提高装箱规划效率,确保货物运输安全。方法考虑5种现实约束条件,以体积利用率和装载垛型重心偏移量为优化目标,建立多目标货物装载优化模型。采用拟人式装箱对货物进行预分组,减小决策空间,然后结合分组信息与装箱算法生成初始解;引入数据驱动的装箱交叉算子提高算法收敛性;设计多策略变异算子提高算法结果的多样性。结果以公共数据集和真实航空货物数据作为实验数据进行实验。实验结果表明,在满足多种约束条件下,集装箱装载强异构货物平均体积利用率达到92.0%,重心位置空间偏移从20 cm减少到7.5 cm,并且算法运行时间减少了73.5%。结论本文所提算法应用于求解大规模多目标三维装箱问题,提高了装箱质量和效率,可为三维装箱算法的工程应用提供参考。The work aims to propose a multi-objective packing algorithm suitable for large-scale cargo loading to solve the problems of single optimization objective and low optimization efficiency of existing 3D packing algorithms,so as to improve the efficiency of packing planning and ensure the safety of cargo transportation.Firstly,considering five realistic constraints,a multi-objective cargo loading optimization model was established with the volume utilization and the shift of the center of gravity of the loading layout as the optimization objectives.Then,the cargoes were pre-grouped by anthropomorphic packing to reduce the decision space,and the initial solutions were generated by combining the grouping information with the packing algorithm;A data-driven cross operator was introduced to packing to improve the convergence of the algorithm;Multi-strategy mutation operators were designed to improve the diversity of algorithm results.With the public data set and real air cargo data as the experimental data,the experimental results showed that the average volume utilization rate of strongly heterogeneous cargoes in container loading reached 92.0%.The space offset of the center of gravity position was reduced from 20 cm to 7.5 cm.And the running time of the algorithm was reduced by 73.5% under various constraints.Therefore,the algorithm proposed in this paper is applied to solve the large-scale multi-objective three-dimensional packing problem,which improves the packing quality and efficiency,and can provide reference for the engineering application of the three-dimensional packing algorithm.

关 键 词：三维装箱 多目标优化 组合优化 多变异策略 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] TP311[自动化与计算机技术—计算机科学与技术]