基于重力装载的自适应随机算法求解多箱型三维装箱问题  

Adaptive random algorithm based on gravity loading to solve 3D-MBSBPP

作　　者：吴蓓 丁文英[1] 杜彦华[1] 赵宁[1] WU Bei;DING Wenying;DU Yanhua;ZHAO Ning(School of Mechanical Engineering, University of Science and Technology, Beijing 100083, China)

机构地区：[1]北京科技大学机械工程学院,北京100083

出　　处：《计算机集成制造系统》2020年第11期3084-3093,共10页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(71301008)。

摘　　要：为了针对电商订单货物进行快速经济选箱,在建立多箱型三维装箱问题(3D-MBSBPP)数学模型的基础上,对空间搜索策略进行创新,提出两种求解算法。自适应随机算法实现货物与空间的自适应;粒子群算法采用动态编码,并实施5种类型的分段变异。采用重力式空间搜索策略求解已有三维装箱算例,使空间利用率提高2.16%,证明了重力式空间搜索策略的有效性。通过求解以三维装箱标准算例为基础构造的8类3D-MBSBPP实例来对比两种算法,自适应随机算法在8类算例上的表现均更优,且平均gap值优于粒子群算法19.59%,证明了自适应随机算法的优越性和稳定性。To make the fast-economical box selection for e-commerce orders based on the Three-Dimensional Multiple Bin-Size Bin Packing Problem(3D-MBSBPP)model,the newspace search strategy and two algorithms were proposed.The self-adaptive stochastic algorithm realized the self-adaptation of cargo to space,and the cargo search rule realized the reasonable subdivision of cargo.The Particle Swarm Optimization(PSO)algorithm used dynamic coding,and implemented five types variation.To solve the existing three-dimensional packing cases,the space utilization rate was increased by 2.16%,which proved the effectiveness of the search strategy.The results of eight types of 3D-MBSBPP examples based on three-dimensional packing standard example were compared to the two algorithms.The adaptive random algorithm performed better on all examples,and the average gap value was better than the PSO by 19.59%.The superiority and stability of the adaptive random algorithm were proved.

关 键 词：多箱型三维装箱问题 重力式空间搜索策略 自适应算法 粒子群算法 动态编码 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论] TP391[自动化与计算机技术—计算机科学与技术]