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

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

为了针对电商订单货物进行快速经济选箱,在建立多箱型三维装箱问题(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.