資源描述：
《一種求解集裝箱裝載問題的啟發(fā)式算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、計算機(jī)科學(xué)2008Vol135№18 一種求解集裝箱裝載問題的啟發(fā)式算法3)1 黃文奇2 尚明生1 傅 彥1陳端兵(電子科技大學(xué)計算機(jī)學(xué)院 成都610054)1 (華中科技大學(xué)計算機(jī)學(xué)院 武漢430074)2 摘 要 所謂集裝箱裝載問題,就是將若干大小不同的長方體盒子裝進(jìn)一個大小已知的長方體容器,其目標(biāo)是最大化容器的積載率。對這一問題,國內(nèi)外學(xué)者利用不同的哲學(xué)思想,提出了諸如遺傳算法、模擬退火算法等求解算法。本文提出一種求解此問題的基于最大穴度優(yōu)先原則的啟發(fā)式算法。算法中使用了兩個重要的策略:最大穴度原則和最小邊度原則。用一些公開的算例對算法性能進(jìn)行了實算測試,
2、測試結(jié)果表明:算法所得結(jié)果的容器積載率高,是求解集裝箱裝載問題的有效算法。關(guān)鍵詞 Packing問題,集裝箱裝載,啟發(fā)式算法,穴度,邊度 HeuristicAlgorithmforSolvingtheContainerLoadingProblemCHENDuan2bing1 HUANGWen2qi2 SHANGMing2sheng1 FUYan1(SchoolofComputerScience,UniversityofElectronicScienceandTechnologyofChina,Chengdu610054,China)1(SchoolofCompu
3、terScience,HuazhongUniversityofScienceandTechnology,Wuhan430074,China)2 Abstract Thecontainerloadingproblemistheproblemofloadingaseriesofboxeswithdifferentsizesintoafixedcu2
boidcontainer.Theobjectiveistomaximizethevolumeutilizationofthecontainer.Researchersproposemanyalgo2
rithmssuc
4、hasgeneticalgorithmandsimulatedannealingtosolveitbasedondifferentidea.Thispaperpresentsaheu2risticalgorithmbasedonmaximumcavingdegreefirstprincipleforsolvingthisproblem.Twoimportantstrategiesareconsideredinthealgorithmproposed.Oneisthemaximumcavingdegreeprinciple,theotheristheminimum
5、edgede2greeprinciple.Theperformanceofthealgorithmisevaluatedbysomepublictestproblems.Highvolumeutilizationisobtainedbyrunningthealgorithm.Experimentalresultsdemonstratethatthealgorithmproposedisfairlyefficientforsolvingthecontainerloadingproblem.Keywords Packingproblems,Containerload
6、ing,Heuristicalgorithm,Cavingdegree,Edgedegree 1 引言和Bortfeldt提出了求解此問題的并行遺傳算法[10],Bortfeldt等提出了并行禁忌搜索算法[11]。2002年,Pisinger在泥瓦工集裝箱裝載問題就是將若干大小不同的長方體盒子裝進(jìn)砌墻的實踐基礎(chǔ)上提出了一種新的啟發(fā)式算法[12]。2007年,一個大小已知的長方體容器。通常情況下,優(yōu)化的目標(biāo)是最楊德榮和楊超提出了求解三維裝箱布局的單向?qū)?yōu)搜索算大化容器的裝載效率,即最大化容器的積載率。在貨運碼頭、法,并對兩個典型算例進(jìn)行了實算[13]。物流、倉儲等
7、工作中均牽涉到這一問題。本文在最大穴度優(yōu)先的基礎(chǔ)上,提出了一種求解集裝箱集裝箱裝載問題屬于NP難問題[1],因而求解此問題的裝載問題的啟發(fā)式算法,其優(yōu)化目標(biāo)是最大化容器的積載率。算法大多是啟發(fā)式算法。國內(nèi)外學(xué)者利用不同的哲學(xué)思想提出了許多啟發(fā)式算法,如Loh和Nee[2],Bischoff和Rat2算法中使用了兩個重要的策略。第一個策略就是放進(jìn)容器的盒子始終占據(jù)一個角,甚至占穴,這一策略是文[14216]的一cliff[3],許光濘和俞金壽[4],等等。個發(fā)展和提高。另一個策略是即將放進(jìn)容器的盒子和其它已近年來,國內(nèi)外許多學(xué)者都在致力于集裝箱裝載問題求放進(jìn)容器的
8、盒子所形成的棱的數(shù)量要盡
