求解三维装箱问题的遗传算法研究【毕业论文】

《求解三维装箱问题的遗传算法研究【毕业论文】》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、本科毕业设计（20届）求解三维装箱问题的遗传算法研究29摘　要【摘要】三维装箱问题是合理地选择需要租用的集装箱并将给定数量的木箱全部装进租用的集装箱中。木箱的装载方案和集装箱的选择方案都会对集装箱的空间利用率及租用的总成本产生很大的影响，所以如何在两方面进行有效的优化，是目前装箱问题上最需关注的话题。本文先对装箱问题及目前的研究现状进行了阐述，然后提出了单箱装箱问题的启发式算法，接着在此基础上，提出了多集装箱装箱问题的遗传算法，最后通过实例证明了该方法能得出该问题的较优解。【关键词】三维装箱问题；启发式算法；遗传算法。Abstra

2、ct【ABSTRACT】Three-dimensionalpackingproblemisareasonablechoiceofcontainerforstuffingagivennumberofboxes.Woodenboxesloadingprogramsandtheoptionsofthecontainerwillhaveahugeeffectonthespaceutilizationofcontainerandthetotalcostofrenting.Sohowtomakeaneffectiveoptimizationo

3、nthetwoaspectsisthekeyproblemnow.Thearticlefocusesonpackingproblemsandcurrentresearcharesurveyedindetail.Asingleboxpackingheuristicalgorithmandageneticalgorithmonmulti-containerloadingproblemwereproposed.Thesimulationresultsshowthattheproposedalgorithmscanobtaintheopt

4、imumsolutionoftheproblem.【KEYWORDS】Three-dimensionalPackingProblem；Heuristic；GeneticAlgorithm。29目　录摘　要IIAbstractIII目　录IV1绪论11.1装箱问题11.2现有装箱问题的解决方法11.3课题研究内容22面向单箱装箱问题的启发式算法32.1单箱装箱要求32.2算法思想32.2.1放置点介绍32.2.2放置点的合并42.2.3启发式算法42.3程序设计43基于遗传算法多集装箱装箱问题53.1遗传算法53.1.1遗传算法的过

5、程53.1.2遗传算法的特点63.1.3遗传算法的组成要素63.2求解多集装箱装箱问题的遗传算法设计83.2.1编码设计83.2.2遗传算子的设计83.2.3适应度函数设计93.3程序设计103.3.1算法流程大体介绍103.3.2算法关键部分详细说明104仿真研究124.1算例自动生成程序124.2测试算例124.2.1层级1到层级2的装载134.2.2层级2到层级3的装载135结论与展望155.1结论155.2展望15参考文献16致谢17附录一算例自动生成源程序18附录二表4-1中的部分算例及输出结果22291绪论1.1装箱问

6、题装箱问题通常指的是装载给定箱子集合的一个子集到容器中，使得被装载的箱子总体积最大。根据维数的不同，可分为一维装箱问题、二维装箱问题、三维装箱问题三种。一维装箱问题比较简单，已经没有研究的必要了，二维装箱问题目前虽然没有高效精确的算法，但很多学者都提出了比较高效的近似算法，也逐渐淡出了研究的邻域，而与现实生活密切相关的是三维装箱问题，许多物流公司都渴望拥有一个比较有效的三维装箱软件，来降低实际装载运输的成本，而三维装箱问题是一个多约束条件下的组合优化问题，虽然一些学者提出了比较高效的近似算法，但都是基于某些约束条件的，所以仍然有必

7、要研究特殊约束条件下的高效的三维装箱算法和更加通用的三维装箱算法。用数学方式来描述三维装箱问题，可以描述为：给定n个物品，长宽高分别为li、wi、hi（1<=i<=n），再给定一个集装箱的尺寸，长宽高分别为L、W、H，问从n个物品中挑选哪些物品装入集装箱中，使得集装箱的空间利用率最大，也就是装入的物品体积总和最大。这里有些条件未加说明，是默认的，在下文也是如此，这些条件为：物品和集装箱都是长方体型的、物品之间及物品与集装箱之间不允许有任何边界重叠的情况。1.2现有装箱问题的解决方法从20世纪70年代初开始，装箱问题就被广泛地关注和

8、研究[1]。到80年代末，各种近似求解装箱问题的算法被提了出来，如下次适应、首次适应和调和算法等[2]。但这些算法都只针对一维、二维装箱问题，因为相比之下三维装箱问题的复杂性大得多，直到80年代后才出现了比较实用的算法：杨传民等人[3]通过全面枚举