多約束三維裝箱問題的啟發式優化算法

廖云峰，單鴻濤，趙文潔

（上海工程技術大學電子電氣工程學院，上海 201620）

0 引言

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

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

1 模型建立

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

以集裝箱的裝載率最大為目標函數，表示為：

式中，F為集裝箱裝載率，i為貨物序號，φi為第i種箱子裝進集裝箱的數量。

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

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

2 基于塊裝載的啟發式算法

2.1 塊裝載算法

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

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

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

2.2 啟發式優化算法

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

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

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

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

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

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

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

剩余空間space表示為：

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

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

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

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

3 實驗結果分析

實驗環境：CPU 為Intel（R）Core（TM）i5-8500H @2.30GHz 2.30GHz，內存為8G，操作系統為Windows 10，算法實現語言為MATLAB R2018a。

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

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

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

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

4 結語

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