Abstract: The three-Dimensional Container Loading Problem（3DCLP） with practice constrains is a complex combinatorial optimization problem and has the typical characters of NP-hard. As to the tendency of convergence into local optimization of the basic Genetic Algorithm（GA）, the paper puts forward a method to optimize the loading sequence based on the biased random-key GA. Then the optimal layout to the boxes can be determined using a heuristic based on extreme-points approach. And the balance of the whole loading gravity center can be improved by the moving of parts of items lastly. The instance demonstrates that the algorithm can generate the optimizing packing plan quickly, in which the available capacity of the vehicle is utilized well and the requirements for the transportation safely are met.

Key words: three-Dimensional Container Loading Problem（3DCLP）, hybrid genetic algorithm, biased random-key, heuristic algorithm, balancing constraints

摘要： 考虑实践约束的三维装箱问题属于复杂的组合优化问题，具有典型NP难问题的特点。针对一般遗传算法求解装箱问题易陷入局部最优的缺点，提出使用偏随机密钥遗传算法进行装载序列搜索，结合基于极点的启发式方法实现货物的优化布置，进而通过部分装载物品的位移来改善整体重心分布。经过实例运算和分析，证明提出的方法能快速制定货物优化布置方案，达到装载工具高效利用及货物安全运输的要求。

关键词: 三维装箱, 混合遗传算法, 偏随机密钥, 启发式算法, 重心平衡