三维装箱问题的模型与改进遗传算法  

A Mixed Integer Programming Model of Three-Dimensional Bin-Packing Problem and Improved Genetic Algorithms

作　　者：陈德良[1,2] 陈治亚[1] 

机构地区：[1]中南大学交通运输工程学院,湖南长沙410075 [2]中南林业科技大学物流学院,湖南长沙410004

出　　处：《数学的实践与认识》2010年第2期142-147,共6页Mathematics in Practice and Theory

基　　金：湖南省自然科学基金(07JJ3134)

摘　　要：三维装箱问题是一类NP-hard的组合优化问题,构建一个适当的数学模型并设计高效快速的算法具有重要的理论和现实意义.该文将箱子空间划分为立方体单元,依此构建三维装箱问题的混合整数规划模型,并通过改进遗传算法求解,剔除大量不可行解提高了收敛速度.实验结果表明此算法运算过程及结果稳定,具有较强的实际应用价值,能有效解决复杂的三维装箱问题.The three-dimensioned bin-packing problem is complicated but a high level of interest in developing effective way to solve this kinds of NP-hard problem. First a Mixed Integer Programming model was worked out in this paper, which resorted to dividing box space into unit cube. Then an improved genetic algorithm was mainly developed. Tests on hundreds of problems show that this algorithm makes the most of volume utilization in minimal time making.

关 键 词：三维装箱问题 空间划分 混合整数规划模型 改进遗传算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]