多約束三維裝箱問題的啟發(fā)式優(yōu)化算法

廖云峰，單鴻濤，趙文潔

（上海工程技術(shù)大學(xué)電子電氣工程學(xué)院，上海 201620）

0 引言

三維裝箱問題是一種具有復(fù)雜約束的組合優(yōu)化問題，如果采用精確的求解算法，隨著問題規(guī)模的不斷擴(kuò)大，可能會發(fā)生組合爆炸的現(xiàn)象。啟發(fā)式求解算法可在可接受的計算成本內(nèi)搜尋最好的解，多用于解決非確定性多項(xiàng)式問題，成為裝箱問題的首選。例如，George 等［1］基于“層”提出了啟發(fā)式算法；在此基礎(chǔ)上，Araya 等［2］采用集束搜索算法處理雙目標(biāo)三維裝箱問題；Bischoff 等［3］設(shè)計了基于同類物體的塊算法，其中塊由完全相同的物體（物體的屬性和擺放約束均相同）組成，Eley 等［4］提出的樹算法，Mack等［5］提出的局部搜索算法和Zhu 等［6］提出的貪心前向搜索算法均結(jié)合了塊生成算法；還有許多優(yōu)秀的解決多約束裝箱問題的啟發(fā)式算法［7-9］。國內(nèi)學(xué)者對三維裝箱問題的研究也取得了許多優(yōu)秀成果，例如張德富等［10］提出一種組合啟發(fā)式算法；李孫寸等［11］利用多元優(yōu)化算法求解三維裝箱問題，得到了理想的裝箱效果；代愛民［12］結(jié)合啟發(fā)式算法和免疫遺傳算法提出混合免疫遺傳算法，用于提高裝載方案的空間利用率；朱瑩［13］提出混合遺傳算法求解單集裝箱問題；車玉馨［14］基于前向搜索樹算法提出剩余空間動態(tài)調(diào)整算法以提高解的質(zhì)量；劉勝等［15］采用二叉樹搜索算法求解三維裝箱問題。

目前啟發(fā)式算法在求解簡單約束的三維裝箱問題上均取得了較好效果，但很少有適用于實(shí)際情況中具有多約束條件三維裝箱問題的算法［16-19］。因此，針對約束條件相對復(fù)雜的三維裝箱問題，本文建立了以集裝箱體積利用率最大為目標(biāo)的數(shù)學(xué)模型，提出一種基于塊裝載算法的啟發(fā)式優(yōu)化算法，通過塊裝載算法考慮約束條件，如重量約束等，進(jìn)而生成裝載塊列表，然后在剩余空間中根據(jù)裝載序列選擇合適的裝載塊，得到最優(yōu)裝載方案。本文算法在測試算例中取得了較好的裝載結(jié)果，且能用于求解大規(guī)模的集裝箱裝載問題。

1 模型建立

多約束三維裝箱問題可以定義為：給定一個集裝箱C=(L，W，H)，其中L、W、H分別表示集裝箱的長、寬、高，最大容積和最大載重量分別為V和M，第i種貨物數(shù)量為ni，質(zhì)量為mi，體積為vi，長、寬和高分別為li、wi、hi，要求在裝載時滿足一定的約束條件，并將貨物盡可能多地裝入集裝箱內(nèi)，使得空間裝載率最大。

以集裝箱的裝載率最大為目標(biāo)函數(shù)，表示為：

式中，F(xiàn)為集裝箱裝載率，i為貨物序號，φi為第i種箱子裝進(jìn)集裝箱的數(shù)量。

裝載貨物時的范圍約束表示為：

式中，lxi、lyi、lzi為值為0 或1 的變量，分別表示第i種箱子的長是否平行于集裝箱的長、寬、高，例如若第i種箱子的長平行于集裝箱的長，則lxi=1，否則lxi=0；wxi、wyi、wzi為值為0 或1 的變量，表示第i種箱子的寬是否平行于集裝箱的長、寬、高；hxi、hyi、hzi為值為0 或1 的變量，表示第i種箱子的高是否平行于集裝箱的長、寬、高。

2 基于塊裝載的啟發(fā)式算法

2.1 塊裝載算法

不同于利用箱子進(jìn)行裝載的傳統(tǒng)啟發(fā)式算法，本文算法主要基于塊裝載算法建立裝載序列與放置方案的映射關(guān)系，其中塊裝載算法指的是簡單塊的生成。

簡單塊是一種同種類型箱子之間沒有絲毫縫隙堆疊而形成的長方體，其生成必須滿足3 個條件：①簡單塊的長寬高必須在集裝箱的體積范圍內(nèi)；②簡單塊的重量必須在集裝箱的承受范圍內(nèi)；③簡單塊使用的箱子數(shù)量必須符合該類箱子的剩余數(shù)量。圖1（a）和圖1（b）分別展示了箱子在兩種不同方向生成的簡單塊，其中nxi、nyi、nzi分別為簡單塊在每個坐標(biāo)軸上的箱子數(shù)量，nxi*nyi*nzi則是該簡單塊所需第i種類型箱子的總數(shù)量，通過枚舉第i種類型箱子在集裝箱內(nèi)所有滿足條件的組合(nxi，nyi，nzi)，將得到的每個簡單塊加入到裝載塊列表中。

Fig.1 Generation examples of simple blocks圖1 簡單塊的生成例子

2.2 啟發(fā)式優(yōu)化算法

參考張德富等［20］提出的啟發(fā)式算法，本文提出基于塊裝載的啟發(fā)式優(yōu)化算法。文獻(xiàn)［20］中的啟發(fā)式算法在每個裝載階段中根據(jù)剩余空間大小計算能使用的所有塊，然后從中選擇一個塊裝入剩余空間，這樣在裝載時不會考慮重心約束的條件。而本文在裝載過程中考慮每次裝載時的重心約束，使得箱子裝載完成時會有一個很好的平衡性。

將集裝箱大小作為剩余空間的初始值，圖2 中用前、右、上3個部分表示在裝載箱子后生成的3個剩余空間。

Fig.2 Division of residual space圖2 剩余空間分割

啟發(fā)式算法中裝載塊的編碼表示為：

式中，B表示裝載塊列表，包含生成的簡單塊；n表示列表中裝載塊的總數(shù)。

裝載塊bj表示列表中第j個裝載塊，其編碼表示為：

式中，j表示裝載塊列表中裝載塊的序號；(li，wi，hi，mi)分別表示裝載塊的長、寬、高和重量；(ni，di)分別表示該裝載塊所使用的箱子數(shù)量和箱子擺放類型。

剩余空間space表示為：

式中，(xa，ya，za)分別表示剩余空間能放置參考點(diǎn)的三維坐標(biāo)，即該空間的左、后、下頂點(diǎn)坐標(biāo)；(xb，yb，zb)表示剩余空間可放置的長、寬、高；γ=(1，2，3)表示裝載塊在前、右、上3個剩余空間中進(jìn)行裝載。

當(dāng)放置參考點(diǎn)為原點(diǎn)，即集裝箱空載時，(xb，yb，zb)為集裝箱的長、寬、高，初始剩余空間表示為：

如圖2 所示，將裝載塊bi放入剩余空間中，分別在3 個坐標(biāo)軸方向生成對應(yīng)的3 個剩余空間Space(m)，Space(m+1)和Space(m+2)，對應(yīng)的編碼分別表示為：

式中，m表示剩余空間的序號。在每個裝載階段都需要對剩余空間進(jìn)行一次新的劃分，在集裝箱未裝滿之前會不斷生成剩余空間，在搜索過程中對剩余空間進(jìn)行高度排序，規(guī)定其裝載優(yōu)先級，確保箱子的裝載是由下至上的，以提高裝載穩(wěn)定性。在剩余空間有可裝載塊時，根據(jù)裝載序列選擇塊裝載，重新對未裝載的剩余空間進(jìn)行切割；在剩余空間無可裝載塊時，對剩余空間進(jìn)行合并，直到無可用剩余空間。

3 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)環(huán)境：CPU 為Intel（R）Core（TM）i5-8500H @2.30GHz 2.30GHz，內(nèi)存為8G，操作系統(tǒng)為Windows 10，算法實(shí)現(xiàn)語言為MATLAB R2018a。

在求解多約束三維裝箱問題時需要考慮貨物的重量限制和集裝箱裝載的重心約束。文獻(xiàn)［13］中的BR1-BR7算例組中每組包含100 個單獨(dú)的子算例，由于BR 算例缺少重量限制，需通過正態(tài)分布的方法隨機(jī)增加重量限制。已知最常見的用于物流運(yùn)輸?shù)南渥用芏菵=753[kg/m3]，密度di滿足正態(tài)分布N(D，σ)，其中σ=0.5D，可得出帶有重量限制的BRw 算例，BR1w-BR7w 每個算例組中同樣包含100 個單獨(dú)的子算例，算例中箱子的重量限制與體積的關(guān)系如圖3所示。

圖4 中BR1w-BR7w 分別表示兩種啟發(fā)式算法在對應(yīng)算例上的平均裝載率，average 表示兩種模型在所有BR1w-BR7w 算例上的平均裝載率，其中Heuristic-box 表示僅利用箱子進(jìn)行裝載的啟發(fā)式算法，Heuristic-CLPw 表示基于塊裝載的啟發(fā)式算法。從圖4 可以看出，本文算法Heuristic-CLPw 在每一組BRw 算例上的平均裝載率都比算法Heuristic-box 要高，且本文算法的平均裝載率average 達(dá)到83.7%，比傳統(tǒng)利用箱子裝載的啟發(fā)式算法的平均裝載率要高出4%左右。

Fig.3 Relationship of weights and volumes for boxes in BRw instances圖3 BRw算例中箱子重量與體積的關(guān)系

Fig.4 Average loading rate of two different models for each group of BR1w-BR7w examples圖4 基于BR1w-BR7w算例的兩種不同模型的平均裝載率

4 結(jié)語

針對實(shí)際生活中多約束的三維裝箱問題，本文提出基于塊裝載的啟發(fā)式優(yōu)化算法。在帶有多種約束條件的BRw 算例上進(jìn)行實(shí)驗(yàn)，結(jié)果表明啟發(fā)式優(yōu)化算法的裝載率得到明顯提高，這是由于在裝載過程中引入的簡單塊增加了每次裝載時箱子的體積，有效提高了集裝箱中空隙的利用率。該方法雖然提高了空間利用率，但由于塊裝載算法需要先將箱子組合成簡單塊再進(jìn)行裝載，運(yùn)行算法消耗的時間不可避免地會增加，因此提高啟發(fā)式算法的運(yùn)行效率是后續(xù)研究目標(biāo)。