資源描述：
《三維裝箱問題的智能啟發(fā)式算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、萬方數(shù)據(jù)第29卷第3期2009年6月中南林業(yè)科技大學(xué)學(xué)報JournalofCentralSouthUniversityofForestry＆TechnologyVoI．29NO．3Jun．2009文章編號：1673—923X(2009)03--0134一04三維裝箱問題的智能啟發(fā)式算法陳德良1’2，陳治亞1(1．中南大學(xué)交通運輸工程學(xué)院，湖南長沙410075I2．中南林業(yè)科技大學(xué)物流學(xué)院，湖南長沙410004)摘要：三維裝箱問題是一類典型的NP—hard組合優(yōu)化問題．找到一個高效快速的算法具有重要的現(xiàn)實意義．模
2、擬人們在實際裝箱時總是盡量保證每一層裝的比較“平直”思想，設(shè)計了一種智能啟發(fā)式算法，借以克服一般啟發(fā)式算法依賴“經(jīng)驗”的不足．給出了詳細(xì)算法流程和關(guān)鍵數(shù)組的定義．該算法結(jié)構(gòu)簡單，實驗表明算法收斂速度快，能有效解決三維裝箱問題．關(guān)鍵詞：物漉工程I三維裝箱}啟發(fā)式算法；智能啟發(fā)式中圖分類號：U169．61文獻(xiàn)標(biāo)志碼：AAnIntelligentHeuristicApproachtoThree-DimensionalBin-packingProblemCHENDe—lian91“．CHENZhi—yal(1．Scho
3、olofTraffic＆TransportationEngineering。CentralSouthUniversity·Changsha410075，Hunan，China；2．SchoolofLogistics。CentralSouthUniversityofForestry&Technology，Changsha410004，Hunan，China)Abstract：Thethree—dimensionalbin-packingproblemisveryhardtOsolvebutthereisahigh
4、levelofinterestindevelopinganeffectivewaytOsolvethisitinordertoreducethetime．energyandotherresourcesspentinbinpacking．ThispaperdevelopsapowerfulintelligentapproachtOitssolution．imitatinghumanintelligencetopackbinsstraightandflatasfaraspossible．Thisapproachis
5、ofsimplestructureandovercomesthedeficiencyingeneralheuristicalgorithmsdependingonprivateexperience．Thepaperalsoprovidesadetailedalgorithmprocessandkeydefinitionsofthearray．Testsonsuchproblemsshowthatourapproachmakesthemostofvolumeutilization．Keywords：logisti
6、csengineering；three·-dimensionalbin--packingproblem；heuristicalgorithm；intelligentheuristic裝箱問題(BinPackingProblem)是一典型的組合優(yōu)化問題．由于需要考慮維數(shù)、形狀、約束、目標(biāo)等不同因素，從計算復(fù)雜性來說，裝箱問題是NP—hard難題[1]．裝箱問題在現(xiàn)實生活中具有廣泛的應(yīng)用，如計算機(jī)領(lǐng)域中的多處理器的任務(wù)調(diào)度、內(nèi)存分配等．特別在現(xiàn)代物流中，很多問題都可以抽象化為裝箱問題或裝箱問題的變形，如車輛如何裝車
7、，才能充分利用車輛．到目前為止，人們對裝箱問題提出了許多算法【2一]，但都有明顯不足：窮舉法在箱子數(shù)目稍大時就存在“組合爆炸”；而一般的啟發(fā)式算法引入的啟發(fā)信息依賴于個人經(jīng)驗，并且同樣存在“組合爆炸”；神經(jīng)網(wǎng)絡(luò)方法在解決裝箱問題時效果明顯，但它收斂速度慢，易陷入局部極優(yōu)．因此，找到一個高效快速的算法具有重要的現(xiàn)實意義．裝箱問題的數(shù)學(xué)模型考慮三維裝箱問題，即：給定長方體箱子B(D，W，日)，D、W、H分別為箱子的三維尺寸，以及T1個長方體物品m正(dJ，甜』，hs)l歹∈{1，2，?，理}]，其中西、硼J、h』分
8、別為物品的尺寸．問題是選擇其中的一些物品裝入箱子中，使箱子的空間利用率最大．裝人時任一物品的擺放方向與箱子的三維保持正交(稱為正交擺放)，即物品的三方向的中軸線與箱子的三條中軸線保持平行．另外假設(shè)所有物品的最小尺寸不大于箱子的最大尺寸，收稿日期：2008．09—01基金項目：中南林業(yè)科技大學(xué)青年科學(xué)基金資助(2006年重點項目)}湖南省自然科學(xué)基金(07JJ3134)．作者簡介：陳德良
