基于二叉樹算法的三維裝箱求解

2019-08-12 12:55:22左先旺榮先釗

科技與創新 2019年14期

左先旺，榮先釗

基于二叉樹算法的三維裝箱求解

左先旺，榮先釗

（三峽大學電氣與新能源學院，湖北宜昌 443002）

近年來，經濟的發展使得物流行業急劇擴張，集裝箱進出口貨物以及快遞運輸包裹均在急劇增加。基于此對于如何高效、快速地裝載不同尺寸的貨物，并且能夠相對較好地利用容器箱的裝載空間顯得尤為重要。采用生成優選條及優選層的方法將三維裝箱問題簡化為二維裝箱問題求解，極大地簡化了三維空間不確定性對三維問題帶來的復雜度問題，并且采用二叉樹搜索算法對裝載問題進行求解，使得求解更加簡單、準確，對于三維裝箱問題求解水平有顯著提高。

優選條；優選層；三維裝箱；二叉樹搜索算法

1 背景及意義

隨著經濟的發展，貨物運輸需求逐漸增多。目前，集裝箱內貨物的裝載大多依靠人工的技能和經驗，對于大規模以及大尺寸的貨物裝載運輸會存在極大的空間浪費問題。而三維裝箱問題即是將一組三維長方體放置在三維空間內，以使得空間的填充率最大或者利用率最高。

本文主要研究單容器裝箱問題，其形式化的定義如下：給定一個容器（其長為，寬為，高為，體積為）和一系列待轉載的箱子（其長為i，寬為i，高為i，體積為i），給定的容器和箱子都為長方體，目標為確定一個可行的箱子裝載方案，使得在滿足給定的裝載約束條件下，使容器中所裝箱子總體積或者箱子的填充率/盡可能的大。需要滿足的約束條件主要有以下兩個：①裝載的箱子平行放置，不能與其他箱子之間有重疊，且箱子外形不能被破壞；②裝載的箱子的長寬高不能超出容器箱子的長寬高。

除此之外，在結合不同實際情況下，還會考慮以下約束條件：①質量約束。裝載貨物的總質量必須小于或者等于容器的最大承載質量。②方向性約束。在實際應用中，對箱子的裝載具有方向性約束，比如有的箱子不能倒置，因此，部分箱子只能有其中的一條或者兩條邊作為高。③穩定性約束。在實際的應用中，為了裝載貨物的安全性，通常會對裝載貨物進行穩定性約束。即要求每個裝載貨物的箱子必須得到容器底或其他已經裝載貨物箱子的支撐。即上一層貨物的長、寬不能超過下一層裝載貨物的長、寬。

2 模型建立

本文主要針對集裝箱對目標箱子的裝載情況進行研究，因此，對一些其他因素進行了假設，對問題進行了簡化?，F對模型做出以下假設：①假設貨物在裝載箱子內質量分布均勻；②貨物能夠進行疊加，不會被壓壞；③不考慮中途的貨物增加或卸載。

2.1 目標函數

目標函數為容器裝箱體積利用率最高：

式（1）中：為容器箱體積利用率；為貨物的序號，=1，2，3，…，；i為第件貨物的體積；為容器箱的體積。

2.2 約束條件

約束條件一，裝載貨物長、寬、高約束為：

式（2）中：i，i，i為裝載貨物的位置參考坐標；i，i，i為第件裝載貨物的長、寬、高；，，為容器箱的長、寬、高。

約束條件二，裝載貨物總質量約束為：

式（3）中：i第件貨物的質量；為容器箱所允許的最大裝載質量。

約束條件三，裝載貨物總體積約束為：

式（4）中：i第件貨物的體積；為容器箱的體積。

約束條件四，裝載貨物方向性約束為i，i，i。

3 問題求解

該模型求解基于二叉樹算法，首先生成優選條，組成優選條集合，再生成優選層，生成優選層集合，最終選擇容器箱體積利用率最高的方案為最優方案。

3.1 生成優選條

從長方體裝載貨物箱子中選擇生成一個子集，子集中的箱子滿足方向性約束，優選條沿著軸豎直地堆疊成一摞，形成長方條，長方條在軸方向上滿足容器箱的高度c約束限制。在長寬方向上，jl為此長方條在軸上的長度，jw為此長方條在軸上的寬度。則此長方條的填充率為Sj=/（jl×jw×c）。

其中填充率最高的長方條的子集形成的長方條定義為優選條mj。

多個優選條mj組成集合，即產生了優選條集合{m1，m2，…，mn}。

3.2 生成優選層

從優選條集合{m1，m2，…，mn}中選擇一個子集，中的優選條沿著軸或者軸的方向排成一排，形成豎直層j，若是沿著軸排列的，則在軸上長度不超過容器箱長度m的限制，其在軸方向上的寬度為jw。如果是沿著軸排列的，則在軸上長度不超過容器箱長度m的限制，其在軸方向上的寬度為jl。

則豎直層的j的填充率為：

優選條沿軸方向排列時，填充率Lj最高時豎直層的子集，形成的豎直層定義為沿軸方向的優選層x；優選條沿軸方向排列時，填充率Lj最高時豎直層的子集，形成的豎直層定義為沿軸方向的優選層y。

3.3 算法求解

本算法先將所有待裝載箱子組合成多個沿著容器箱子方向上擺放的優選條mj，這樣便將三維裝箱問題降低維度到裝載優選條的二維裝箱問題。通過構建二叉樹，對應不同的裝載方案，如圖1所示。二叉樹上每一個節點對應了一個裝載方案，下一層節點是在上一層節點裝載方案的基礎上繼續裝載新的優選條形成的，根節點為空載容器箱。

在根節點的基礎上產生優選條集合，隨機選擇不同的優選條裝入容器箱中，形成不同的節點裝載方案；在上一節點裝載方案的基礎上，繼續生成裝載新的優選條，子節點是在母節點的基礎上繼續裝載而成的；不斷更新容器箱子剩余空間的體積，生成新的優選條，產生新的裝載方案。直到剩余空間無法再裝載下任何優選條，包括只包含任意箱子的最小優選條在內。證明該種裝載方案最終完成。比較所有裝載方案的填充率大小。其中，填充率最大的即為最優裝載方案。