计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (14): 32-39.DOI: 10.3778/j.issn.1002-8331.1902-0127

• 热点与综述 • 上一篇    下一篇

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

张  钧,贺可太   

  1. 北京科技大学 机械工程学院,北京 100083
  • 出版日期:2019-07-15 发布日期:2019-07-11

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

ZHANG Jun, HE Ketai   

  1. School of Mechanical Engineering, University of Science and Technology Beijing, Beijing 100083, China
  • Online:2019-07-15 Published:2019-07-11

摘要: 集装箱装载是货物运输过程中重要的一步,其属于NP-hard问题。为了提高效率,降低成本,提出了以集装箱体积利用率最大化为目标建立三维装载模型,同时考虑体积约束、重量约束、重心约束、方向约束。利用混合遗传、模拟退火与三空间分割启发式装载算法求解模型,算法中融入局部最优解保存策略来避免局部较好解在后续的算法过程中出现适应度降低的情况。通过强异类算例与弱异类算例对算法进行性能测试,并结合具体的货物装载数据,得出三维装载图与目标函数值。结果表明,该算法应用于集装箱装载有着较好的效果。

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

Abstract: 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.

Key words: three-dimensional container loading problem, heuristic algorithm, genetic algorithm, simulated annealing algorithm