[發(fā)明專利]基于三維移動模式序列與密母算法的三維裝箱方法

有效

• 申請?zhí)枺?/td>: 201410798189.3
• 申請日: 2014-12-19
• 公開（公告）號: CN104504468B
• 公開（公告）日: 2018-03-13
• 發(fā)明（設(shè)計）人: 劉靜;焦李成;韓二麗;朱園;馬文萍;馬晶晶
• 申請（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12
• 代理公司: 陜西電子工業(yè)專利中心61205
• 代理人: 王品華,王喜媛

技術(shù)領(lǐng)域

本發(fā)明屬于計算機優(yōu)化技術(shù)領(lǐng)域，進一步涉及三維裝箱方法，可用于優(yōu)化箱子放置的坐標(biāo)，實現(xiàn)物流等行業(yè)裝箱的優(yōu)化。

背景技術(shù)

三維裝箱3D-BPP是工業(yè)生產(chǎn)中常遇到的問題，如船舶集裝箱裝卸、飛機貨運管理、倉庫管理等。在貨物裝載以及運輸過程中，資源以及運輸空間的高效利用是公司間的核心競爭力。因此，由于其實際的需求，尋求一種合理有效的放置策略仍然是研究的重要方向。

Karabulut等發(fā)表的“A hybrid genetic algorithm for packing in 3D with deepest bottom left with fill method”(《Advances in Information Systems》，文章編號:441-450(2004))，該文章的核心是將箱子放置在三維空間中，使得坐標(biāo)點z最小，而后y最小，最后x最小，該算法可以產(chǎn)生很好的效果，但每放入一個箱子，就要記錄以及刪除極點，即是記錄可以放置箱子的點，以及已經(jīng)放置了箱子的點并將其刪除，最后要重新給極點排序，時間復(fù)雜度很高。

張德富等發(fā)表的“求解三維裝箱問題的混合模擬退火算法”(《計算機學(xué)報》，文章編號:2147-2156(2009)32-11)中提出了復(fù)合塊作為放置策略，采用模擬退火算法優(yōu)化3D-BPP。該算法研究的是帶有穩(wěn)定性和方向約束的單一三維裝箱問題，對部分弱異構(gòu)箱子可以得到好的填充率，而對于強異構(gòu)箱子而言，若采用復(fù)合塊的放置策略，復(fù)合塊中會產(chǎn)生空隙并且對于每個復(fù)合塊而言不能夠再次填充，從而使得填充率降低。

何琨等發(fā)表的“基于長方體Packing問題的捆綁穴度算法”(《軟件學(xué)報》，文章編號：842-851(2011)2-5)中公開了一種用捆綁穴度算法對三維裝箱問題進行優(yōu)化的方法。該方法的實現(xiàn)過程為，首先對所有箱子進行捆綁，形成新的箱子組合，其次采用穴度算法對三維裝箱問題進行優(yōu)化。該方法的不足之處在于，只適用于弱異構(gòu)三維裝箱問題，對于箱子種類多的裝箱其獲得的體積利用率低。

發(fā)明內(nèi)容

本發(fā)明的目的在于針對上述已有技術(shù)的不足，提出一種基于三維移動模式序列與密母算法的三維裝箱方法，以減小空間復(fù)雜度，提高容器的體積利用率。

為實現(xiàn)上述目的，本發(fā)明的技術(shù)方案包括如下步驟：

(1)參數(shù)設(shè)定：

設(shè)N為遺傳算法中種群中的個體數(shù)，N為大于或等于2的整數(shù)，M為每個個體中箱子個數(shù)，M為大于或等于1的整數(shù)；用W、H、L分別表示裝箱容器的寬、高、長；Mgen表示進化的最大代數(shù)，pc0為箱子順序交叉概率，pc1為移動模式交叉概率，pc2為旋轉(zhuǎn)模式交叉概率，其中pc0、pc1、pc2為0到1之間的實數(shù)；pm為變異概率，取值為0到1之間的實數(shù)；w、h、l分別為箱子的寬、高、長，x、y、z為箱子放置坐標(biāo)點的值，m為移動模式值，取值為0、1、2；r為旋轉(zhuǎn)模式值，取值為0～5之間的整數(shù)；num為箱子的序號；TEM為爬山法的迭代次數(shù)；RX、RY、RZ分別表示最小立方體包絡(luò)的寬、高、長；gen為進化代數(shù)；結(jié)構(gòu)體數(shù)組best[N]用于保存每一代中適應(yīng)度最大的個體，結(jié)構(gòu)體Best用于保存爬山法得到的適應(yīng)度最大的個體；

(2)隨機產(chǎn)生初始種群，即隨機產(chǎn)生箱子序號0～M-1的排列，隨機產(chǎn)生旋轉(zhuǎn)模式0～5的排列，隨機產(chǎn)生移動模式0～2的排列，產(chǎn)生N個這樣的個體組成初始種群；計算每個個體的適應(yīng)度值，設(shè)gen＝0；

(3)判斷是否滿足gen<Mgen，若是，執(zhí)行步驟(4)，否則執(zhí)行步驟(9)；

(4)根據(jù)種群中每個個體的適應(yīng)度值，用二元錦標(biāo)賽法從中選擇N個適應(yīng)度值大的個體；

(5)隨機產(chǎn)生0到1之間的隨機數(shù)temp；隨機選擇兩個個體，若temp<pc0，則對這兩個個體的箱子順序進行交叉；若temp<pc1則對這兩個個體的移動模式進行交叉；若temp<pc2，則對這兩個個體的旋轉(zhuǎn)模式進行交叉，并重新計算這兩個個體的適應(yīng)度值；

(6)隨機產(chǎn)生0到1之間的隨機數(shù)temp₁，若temp₁<pm，隨機選擇種群中的一個個體，隨機對該個體的箱子順序、移動模式、旋轉(zhuǎn)模式進行變異，并重新計算該個體的適應(yīng)度值；

(7)對種群中的個體按適應(yīng)度值從大到小進行排序，將當(dāng)前代中適應(yīng)度值最大的個體存放在結(jié)構(gòu)體數(shù)組best[N]中；

(8)對gen自加1，返回步驟(4)；