多约束三维装箱问题的启发式优化算法

Heuristic Optimization Algorithm for Multi-constrained Three dimensional Container Loading Problem

针对多约束三维装箱问题,传统的启发式算法往往很难满足所有约束条件,无法提高集装箱的装载率。为此,提出结合块装载算法的启发式优化算法,在满足多约束条件下采用块装载算法得到简单块,通过剩余空间的分割和合并确定块装载的目标空间,采用装载序列优化每个装载阶段的块选择,得到最优装载方案。基于BR经典算例结合正态分布法生成多约束BRw算例对该算法进行测试,实验结果表明,基于块装载算法的启发式优化算法平均装载率达到83.7%,比传统启发式算法提高了4%。基于块装载算法的启发式优化算法不仅能有效应对装载过程中的多种约束条件,而且能增加每次集装箱装载时的箱子体积,减少装载时间,同时也能提高集装箱的装载率。

Aiming at the multi-constrained three-dimensional container loading problem,traditional heuristic algorithms are often difficult to meet all constraints to improve the container loading rate.Therefore,a heuristic optimization algorithm based on the block loading algorithm is proposed,which obtains simple blocks according to the block loading algorithm under the condition of satisfying multiple constraints,and determines the target space of block loading by dividing and merging the remaining space.The loading sequence is used to optimize the block selection in each loading stage to obtain the optimal loading scheme.The algorithm is tested by multi-constrained BRw cases generated by the BR classical cases combined with the normal distribution method.The experimental results show that the average loading rate of the heuristic optimization algorithm based on the block loading algorithm reaches 83.7%,which is 4%higher than the average loading rate of the traditional heuristic algorithm.The heuristic optimization algorithm based on the block loading algorithm can not only effectively deal with the various constraints in the loading process,but also increase the volume of each container loading,reduce the loading time,and improve the container loading rate.