【作者】 张丽岩；

【导师】 吴中；

【作者基本信息】 河海大学 ， 交通运输规划与管理， 2006， 硕士

【摘要】 装箱问题是一个典型的组合优化问题,这类问题大量存在于日常生活中,它们的共性就是将一堆“物品”,装入所谓的“箱子”中,而使它们不相互叠迭。对应于现实生活中,即是如何在满足要求的情况下,合理有效地利用时间或空间等现有资源。因此,装箱问题具有重要的研究价值。 装箱问题,从20世纪70年代初开始,就引起了人们的关注。到目前为止,世界上研究的比较多的是一维及二维装箱问题。虽然经过几代人的努力,但迄今尚无成熟的理论和有效的数值计算方法。因此,从80年代开始,陆续提出的装箱算法都是各种近似算法,如下次适应、首次适应、最佳适应算法和调和算法等。 本文在总结了前人用来解决装箱问题的算法后,确定了利用遗传算法来求解装箱问题,并详细分析了基本遗传算法在装箱问题中的应用;在此基础上,作者首次提出了用于解决装箱问题的结合BFD思想的混合遗传算法,并用VC实现了基于数据库的图形用户界面(GUI)程序,详细说明了程序实现的步骤,并给出了关键算法的程序流程图;最后通过算例比较,得出以下结论:在求解装箱问题时,结合了BFD思想的混合遗传算法要比基本遗传算法优化许多,具有很高的实用价值。更多还原

【Abstract】 Bin-packing Problem (BP) is one of the combination optimization problems. It lies in our daily life. The commonness of BP is putting some "goods’" into some "boxes" and not overlapping. In other words, use the resource suitably after fulfilling our needs. So, there is an important value in studying the BP.BP has aroused man’s attention from the early 1970s. We mostly study linear BP and 2-D BP up to now. There are no mature theory and numerical implementation by far. Scholars began to study approximate algorithms from 1980s, such as next fit (NF), first fit (FF), best fit (BF) and harmonic algorithms.The article utilizes Genetic Algorithm (GA) in solving BP on the basic of the superiors. It analyses the Standard Genetic Algorithm (SGA) using in the field of BP in detail. The article advanced a hybrid genetic algorithm which is constituted by Best Fit Decreasing (BFD) algorithm and SGA in resolving BP. And implement GUI procedure based on the Database in VC. The article discusses the detail steps of the procedure and the main procedural flow charts. After the comparison of the example, we have a conclusion that the hybrid genetic algorithm constituted by BFD and SGA is better than SGA in solving BP and it has an applied value.更多还原