游伟，雷定猷，朱向

中南大学交通运输工程学院，长沙 410075

三维装箱问题的偏随机密钥混合遗传算法

游伟，雷定猷，朱向

中南大学交通运输工程学院，长沙 410075

1 引言

三维装箱问题（three-Dimensional Container Loading Problem，3DCLP）是指从多件货物中选择若干件货物经过适当的组合并按照一定的顺序装入某个集装箱中，以达到箱子容积和载重量最大化利用的目的。货物是具有一定的尺寸和质量的矩形、匀质类物品，箱子为具有矩形空间容积及一定承载能力的矩形容器。货物以正交的形式放入集装箱，摆放方向任意，最多包含6种旋转方向。由于物品和容器存在不同规格，不同货物组合及其摆放位置都将对装载效果带来不同影响，同时还要求满足装载稳定性、货物表面承载能力及重心平衡等约束条件，因而装箱问题属于复杂组合优化问题，具有NP难问题的特点[1]。

实现货物的高效装载及合理布局，在空运、海运及铁路等装运领域具有重要的意义，已吸引了一批学者对此优化问题进行研究，并总结出一整套求解方法，主要包括确定性方法、随机搜索和混合方法等三类方法。

确定性方法中，Chen[2]的整数规划、Hifi[3]的分支定界法是其中典型的代表，这些方法主要适合规模较小的装载问题。对于规模较大的问题，可采用随机搜索方法并结合启发式规则进行求解，包括使用遗传算法[4-5]、模拟退火算法[6]、禁忌算法[7-8]、贪婪随机自适应搜索[9]等随机搜索机制寻优，以实现在相对较大的空间范围内对解的搜索。……