求解三维装箱问题的混合遗传模拟退火算法  

Study on Hybrid Genetic and Simulated Annealing Algorithm for Three-Dimensional Packing Problems

作　　者：张钧 贺可太[1] ZHANG Jun;HE Ketai(School of Mechanical Engineering,University of Science and Technology Beijing,Beijing 100083,China)

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

出　　处：《计算机工程与应用》2019年第14期32-39,47,共9页Computer Engineering and Applications

基　　金：国家自然科学基金(No.71601009)

摘　　要：集装箱装载是货物运输过程中重要的一步,其属于NP-hard 问题。为了提高效率,降低成本,提出了以集装箱体积利用率最大化为目标建立三维装载模型,同时考虑体积约束、重量约束、重心约束、方向约束。利用混合遗传、模拟退火与三空间分割启发式装载算法求解模型,算法中融入局部最优解保存策略来避免局部较好解在后续的算法过程中出现适应度降低的情况。通过强异类算例与弱异类算例对算法进行性能测试,并结合具体的货物装载数据,得出三维装载图与目标函数值。结果表明,该算法应用于集装箱装载有着较好的效果。The container loading is an important step in the process of cargoes transportation. It belongs to the NP-hard problem. In order to improve the efficiency and reduce the cost, it proposes that the three- dimensional loading model should be established with the maximization of the volume utilization rate. At the same time, the conditions of the volume constraints, the weight constraints, the center of gravity constraints and the directional constraints are considered. The hybrid genetic algorithm, simulated annealing algorithm and three-space division heuristic algorithm are used to solve the model. The local optimal preservation strategy is incorporated into the algorithm to avoid fitness reduction in subsequent algorithm. Through the performance test of the strongly heterogeneous and weakly heterogeneous examples, the 3D load map and the objective function value are obtained by combining with the specific data of cargo loading. The results show that the algorithm in this paper has good effect on container loading.

关 键 词：三维装箱问题 启发式算法 遗传算法 模拟退火算法 

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