基于聚类和网格覆盖的三维装箱算法  

Three-Dimensional Packing Algorithm Based on Clustering and Grid Coverage

作　　者：李少港 张宇辉 魏文红 LI Shaogang;ZHANG Yuhui;WEI Wenhong(School of Computer Science and Technology,Dongguan University of Technology,Dongguan 523808,China)

机构地区：[1]东莞理工学院计算机科学与技术学院,广东东莞523808

出　　处：《东莞理工学院学报》2022年第5期40-46,共7页Journal of Dongguan University of Technology

基　　金：国家自然科学基金资助项目(62106046);广东省自然科学基金资助项目(2019A1515110474)。

摘　　要：三维装箱问题是一类常见的组合优化问题,现有的研究工作集中于提升算法的装载效率,较少考虑算法决策时间的影响,而时间效率是决定算法能否应用于工业实践的重要标准之一。本文提出了一种改进的三维最优适配算法用于解决装箱问题,通过结合遗传算法和聚类算法,在降低搜索空间维度、提高算法收敛速度、减少算法运行时间的同时,寻找更优的解。在华为数据集上的实验结果表明,本文提出的算法在兼顾时间效率和装载效率的基础上,能够获得较好的结果。The three-dimensional bin packing problem is a common combinatorial optimization problem.Most of the existing studies focus on improving the loading efficiency of packing algorithms while ignoring the effect of decision time.However,time efficiency is one of the most important criteria that decides whether an algorithm can be deployed in industrial environments.This paper proposes an improved three-dimensional optimal adaptation algorithm to solve the packing problem.By combining the power of genetic algorithm and clustering algorithm,the proposed algorithm is able to reduce the search space size,improve the convergence speed,and reduce the running time.Experimental results on Huawei data sets show that the algorithm proposed in this paper can obtain better results with respect to both time efficiency and loading efficiency.

关 键 词：三维装箱 K-MEANS聚类 遗传算法 三维最优适配算法 启发式装箱算法 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]