資源描述：
《基于禁忌搜索算法集裝箱裝載問題的的研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、沈陽(yáng)工業(yè)大學(xué)碩士學(xué)位論文摘要集裝箱裝載問題(ContainerLoadingProblem，簡(jiǎn)稱CLP)屬于“切割和裝入”問題，在數(shù)學(xué)理論上為NP完全問題，即不能在多項(xiàng)式時(shí)間內(nèi)找到問題的最優(yōu)解。CLP雖然求解困難，但隨著計(jì)算機(jī)技術(shù)的發(fā)展，使用計(jì)算機(jī)輔助求解CLP成為可能，但因CLP本身特征，實(shí)際應(yīng)用中無法采用純數(shù)學(xué)方法，而是采用基于啟發(fā)式的近似求解方法。計(jì)算機(jī)輔助布局優(yōu)化能夠有效提高空問裝載效率，在鐵路和遠(yuǎn)洋運(yùn)輸中能夠降低運(yùn)輸成本，研究成果還可以推廣到計(jì)算機(jī)內(nèi)存分配等空間資源優(yōu)化領(lǐng)域，因此有著重要
2、的實(shí)際意義。近年來CLP逐漸成為人們關(guān)注的焦點(diǎn)。本文緒論先對(duì)CLP的產(chǎn)生背景及實(shí)際意義進(jìn)行論述，然后對(duì)其研究范疇和分類予以介紹，最后在查閱大量文獻(xiàn)的基礎(chǔ)上闡明了CLP的國(guó)內(nèi)外發(fā)展現(xiàn)狀。禁忌搜索算法(TabuSearch，簡(jiǎn)稱TS)是近年來逐漸引起人們興趣的一種現(xiàn)代啟發(fā)式算法，因其特殊的“記憶”機(jī)制，表現(xiàn)出極好的全局尋優(yōu)能力，在對(duì)一些復(fù)雜、困難問題的求解中取得了很好效果。本文從TS的原理、搜索技術(shù)以及收斂理論等方面進(jìn)行說明。應(yīng)用TS求解CLP在國(guó)內(nèi)還沒有相關(guān)研究，本文結(jié)合CLP的實(shí)際特征，提出了不同
3、于Bortfeldt和Gehring方法的新的編碼、解碼及鄰域解構(gòu)造方法；在解碼中引入了新的空間合并策略，提高了集裝箱利用率；應(yīng)用“組合塊”思想減少了剩余空間的零碎劃分，降低了搜索代價(jià)；本文創(chuàng)造性的將TS應(yīng)用于求解多箱裝載問題，取得了理想效果。結(jié)果顯示對(duì)于集裝箱裝載系統(tǒng)的應(yīng)用有重要意義，本文給出了數(shù)據(jù)顯示和圖形顯示兩種方式。數(shù)據(jù)顯示精確描述裝載方案中物體順序、位置等信息；圖形顯示提供了裝載方案的可視化效果，更便于用戶觀察。實(shí)例分析部分通過對(duì)4個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行測(cè)試，證明了用TS求解CLP的有效性和實(shí)
4、用性，同時(shí)討論了算法中存在的優(yōu)點(diǎn)與不足。最后對(duì)全文工作進(jìn)行總結(jié)并對(duì)以后的研究方向進(jìn)行了展望。關(guān)鍵詞：集裝箱裝載問題，禁忌搜索，布局優(yōu)化，胛完全問題，啟發(fā)式算法基于禁忌搜索算法的集裝箱裝載問題研究ResearchonContainerLoadingProblemBasedonTabuSearchAbstractContainerloadingproblem(CLP)belongsto”cuttingandpacking”problemandaNPcompleteprobleminmathematic
5、s．Forthiscase，itcannotbeusedtogetthebestsolutioninpolynomialtime．AlthoughCLPiscomplex,withthedevelopmentofcomputerscience，CLPcanbesolved、撕tllthehelpofcomputer．OwningtotheattributeofCLPitself,CLPcannotbcdealtinonlypuremathematicwayinpractice．butinanapp
6、roximateway,suchasheuristicmethod．Computeraidedlayoutoptimizationcanimprovethecontainerloadingefficiency．Forthisreason,thetransportationcostof期ilwayandoceanshippingcanbecutdown．Andtheproductionofresearchcanbeextendedintospaceresourceallocation,such鶴co
7、mputermemoryallocation．Thus，CLPisbecomingastheresearchfocusinrecentyears．ThepaperintroductionfirstlydiscussesthegenerationbackgroundandpracticalmeaningofCLP，andthenexplainsthecategoryofCLP，atlastconcludestheresearchstatusinquoaccordingtoagreatdealofli
8、teratures。Tabusearchalgorithm(TS)isakindofmeta-heuristicalgorithms，andisfamousforitsspecial’’memory”mechanism．Ithasamazingabilitytosearchglobally．Goodresultsofsomedifficultandhardproblemshavebeenachievedforthisreason．ThepaperintroducesTSfrompr
