求解三維裝箱問(wèn)題的遺傳算法研究【畢業(yè)論文】

《求解三維裝箱問(wèn)題的遺傳算法研究【畢業(yè)論文】》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、本科畢業(yè)設(shè)計(jì)（20屆）求解三維裝箱問(wèn)題的遺傳算法研究29摘　要【摘要】三維裝箱問(wèn)題是合理地選擇需要租用的集裝箱并將給定數(shù)量的木箱全部裝進(jìn)租用的集裝箱中。木箱的裝載方案和集裝箱的選擇方案都會(huì)對(duì)集裝箱的空間利用率及租用的總成本產(chǎn)生很大的影響，所以如何在兩方面進(jìn)行有效的優(yōu)化，是目前裝箱問(wèn)題上最需關(guān)注的話(huà)題。本文先對(duì)裝箱問(wèn)題及目前的研究現(xiàn)狀進(jìn)行了闡述，然后提出了單箱裝箱問(wèn)題的啟發(fā)式算法，接著在此基礎(chǔ)上，提出了多集裝箱裝箱問(wèn)題的遺傳算法，最后通過(guò)實(shí)例證明了該方法能得出該問(wèn)題的較優(yōu)解。【關(guān)鍵詞】三維裝箱問(wèn)題；啟發(fā)式算法；遺傳算法。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裝箱問(wèn)題11.2現(xiàn)有裝箱問(wèn)題的解決方法11.3課題研究?jī)?nèi)容22面向單箱裝箱問(wèn)題的啟發(fā)式算法32.1單箱裝箱要求32.2算法思想32.2.1放置點(diǎn)介紹32.2.2放置點(diǎn)的合并42.2.3啟發(fā)式算法42.3程序設(shè)計(jì)43基于遺傳算法多集裝箱裝箱問(wèn)題53.1遺傳算法53.1.1遺傳算法的過(guò)

5、程53.1.2遺傳算法的特點(diǎn)63.1.3遺傳算法的組成要素63.2求解多集裝箱裝箱問(wèn)題的遺傳算法設(shè)計(jì)83.2.1編碼設(shè)計(jì)83.2.2遺傳算子的設(shè)計(jì)83.2.3適應(yīng)度函數(shù)設(shè)計(jì)93.3程序設(shè)計(jì)103.3.1算法流程大體介紹103.3.2算法關(guān)鍵部分詳細(xì)說(shuō)明104仿真研究124.1算例自動(dòng)生成程序124.2測(cè)試算例124.2.1層級(jí)1到層級(jí)2的裝載134.2.2層級(jí)2到層級(jí)3的裝載135結(jié)論與展望155.1結(jié)論155.2展望15參考文獻(xiàn)16致謝17附錄一算例自動(dòng)生成源程序18附錄二表4-1中的部分算例及輸出結(jié)果22291緒論1.1裝箱問(wèn)

6、題裝箱問(wèn)題通常指的是裝載給定箱子集合的一個(gè)子集到容器中，使得被裝載的箱子總體積最大。根據(jù)維數(shù)的不同，可分為一維裝箱問(wèn)題、二維裝箱問(wèn)題、三維裝箱問(wèn)題三種。一維裝箱問(wèn)題比較簡(jiǎn)單，已經(jīng)沒(méi)有研究的必要了，二維裝箱問(wèn)題目前雖然沒(méi)有高效精確的算法，但很多學(xué)者都提出了比較高效的近似算法，也逐漸淡出了研究的鄰域，而與現(xiàn)實(shí)生活密切相關(guān)的是三維裝箱問(wèn)題，許多物流公司都渴望擁有一個(gè)比較有效的三維裝箱軟件，來(lái)降低實(shí)際裝載運(yùn)輸?shù)某杀荆S裝箱問(wèn)題是一個(gè)多約束條件下的組合優(yōu)化問(wèn)題，雖然一些學(xué)者提出了比較高效的近似算法，但都是基于某些約束條件的，所以仍然有必

7、要研究特殊約束條件下的高效的三維裝箱算法和更加通用的三維裝箱算法。用數(shù)學(xué)方式來(lái)描述三維裝箱問(wèn)題，可以描述為：給定n個(gè)物品，長(zhǎng)寬高分別為li、wi、hi（1<=i<=n），再給定一個(gè)集裝箱的尺寸，長(zhǎng)寬高分別為L(zhǎng)、W、H，問(wèn)從n個(gè)物品中挑選哪些物品裝入集裝箱中，使得集裝箱的空間利用率最大，也就是裝入的物品體積總和最大。這里有些條件未加說(shuō)明，是默認(rèn)的，在下文也是如此，這些條件為：物品和集裝箱都是長(zhǎng)方體型的、物品之間及物品與集裝箱之間不允許有任何邊界重疊的情況。1.2現(xiàn)有裝箱問(wèn)題的解決方法從20世紀(jì)70年代初開(kāi)始，裝箱問(wèn)題就被廣泛地關(guān)注和

8、研究[1]。到80年代末，各種近似求解裝箱問(wèn)題的算法被提了出來(lái)，如下次適應(yīng)、首次適應(yīng)和調(diào)和算法等[2]。但這些算法都只針對(duì)一維、二維裝箱問(wèn)題，因?yàn)橄啾戎氯S裝箱問(wèn)題的復(fù)雜性大得多，直到80年代后才出現(xiàn)了比較實(shí)用的算法：楊傳民等人[3]通過(guò)全面枚舉