摘要
三维装箱问题是一类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.
出处
《数学的实践与认识》
CSCD
北大核心
2010年第2期142-147,共6页
Mathematics in Practice and Theory
基金
湖南省自然科学基金(07JJ3134)
关键词
三维装箱问题
空间划分
混合整数规划模型
改进遗传算法
three-dimensional bin-packing problem
space division
mixed integer programming model
improved genetic algorithms
