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

Biased random-key hybrid genetic algorithm for three-dimensional loading problem

作　　者：游伟[1] 雷定猷[1] 朱向[1] 

机构地区：[1]中南大学交通运输工程学院,长沙410075

出　　处：《计算机工程与应用》2014年第22期265-270,共6页Computer Engineering and Applications

基　　金：中国铁路总公司资助项目(No.2013X009-1)

摘　　要：考虑实践约束的三维装箱问题属于复杂的组合优化问题,具有典型NP难问题的特点。针对一般遗传算法求解装箱问题易陷入局部最优的缺点,提出使用偏随机密钥遗传算法进行装载序列搜索,结合基于极点的启发式方法实现货物的优化布置,进而通过部分装载物品的位移来改善整体重心分布。经过实例运算和分析,证明提出的方法能快速制定货物优化布置方案,达到装载工具高效利用及货物安全运输的要求。The three-Dimensional Container Loading Problem（3DCLP）with practice constrains is a complex combinato-rial optimization problem and has the typical characters of NP-hard. As to the tendency of convergence into local optimi-zation 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.

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

分 类 号：U294[交通运输工程—交通运输规划与管理]