[發明專利]基于三維空間求解具有多重量約束裝箱的優化方法

有效

• 申請號: 201410139428.4
• 申請日: 2014-04-09
• 公開（公告）號: CN103870893B
• 公開（公告）日: 2017-02-15
• 發明（設計）人: 劉嘉敏;王溪波;張曉蕊;朱世鐵;魏東;常燕
• 申請（專利權）人: 沈陽工業大學
• 主分類號: G06F17/00
• 分類號: G06F17/00;G06N3/00
• 代理公司: 沈陽智龍專利事務所(普通合伙)21115
• 代理人: 宋鐵軍

1.一種基于三維空間求解具有多重量約束裝箱的優化方法，其特征在于：該三維裝箱優化方法包括以下步驟：

步驟1：根據訂單中貨物和集裝箱信息，為提高計算效率，設計用于蟻群算法計算的路徑圖；

步驟2：設計蟻群算法的啟發因子、結點上信息素和更新信息素方法以及轉移和選擇策略關鍵技術；

布驟3：在保證穩定裝載的條件下，給出每個重量約束的描述方法，并確定三維空間與約束之間的關系；

步驟4：設計與三維空間處理相結合的裝入啟發算法，來驗證多個螞蟻遍歷路徑圖生成的不同路徑，給出評價函數計算出每條路徑的適宜值；

步驟5：輸出具有最好適宜值的路徑，繪制裝載布局三維圖，顯示出每個貨物裝載的位置。

2.根據權利要求1所述的基于三維空間求解具有多重量約束裝箱的優化方法，其特征在于：在步驟1、2中所述蟻群算法，對該算法中下列關鍵技術設計了改進：

（1）路徑圖的構造；

為提高搜索最優解效率，根據貨物種類的數量來構造路徑圖G=(V,E)，路徑中的結點V表示貨物的種類，兩個結點之間的邊E表示兩種貨物體積或重量之和；每個螞蟻通過覓食策略遍歷圖中所有結點，得到一個路徑鏈，即是一種貨物裝載順序；

（2）信息素更新；

本方法采用局部和全局兩種形式對圖中結點的信息素進行動態更新：

局部更新：當螞蟻訪問一個結點后，更新剛訪問結點的信息素，其更新信息素量的計算公式如下:

τ_ij(t+1)＝(1-λ)τ_ij(t)+λA

其中，t表示某一時刻，τ_ij(t)表示螞蟻在t時刻從結點i到結點j邊上信息素量，λ是局部揮發因子，A是總貨物體積或重量的常數；

全局更新：當螞蟻訪問所有結點后，需要更新所有結點的信息素，其更新信息素量的計算公式如下:

τ_ij(t+1)＝(1-ρ)τ_ij(t)+ρΔτ^k(t)

Δτk(t)=11-fk(t)]]>

其中，k為某一只螞蟻，τ_ij(t+1)是從t到t+l時刻留在從結點i到結點j邊上信息素量，ρ為全局更新信息素因子，它決定螞蟻選擇結點以及螞蟻的移動方向，f^k(t)為第k只螞蟻在t時刻遍歷圖中所有結點得到的適宜值，其包含貨物的重量和重量平衡信息，它是在t時刻最好的適宜值，Δτ^k(t)為第k只螞蟻在t時刻釋放的信息素量；

（3）轉移概率；

每只螞蟻根據結點間邊上的信息素量來確定其移動的方向；當第k只螞蟻在t時刻從結點i移動到結點j時，選擇結點j概率P_ij的計算公式如下：

pijk(t)=τijα(t)ηijβ(t)Σj∈Nikτijα(t)ηijβ(t)]]>

其中，τ_ij(t)表示第k只螞蟻在t時刻從結點i到結點j邊上信息素量，α和β表示信息因子和期望啟發因子，η_ij表示從結點i到結點j期望啟發值，即這里V為集裝箱的體積，v_i和v_j分別為第i和j種貨物的體積，l_j、w_j和wg_j為第j種貨物底面的長和寬以及重量，這樣在選擇下一個結點j時，運用體積利用率、承載能力和重量信息來指導螞蟻的移動，a₁,a₂,a₃是邏輯變量用來確定要考慮的目標，集合表示第k只螞蟻在結點i時可選后續結點的集合；

（4）適宜值；

它用來衡量一個可行解，即一種裝載順序的好壞程度，也是蟻群算法產生每個可行解的評價標準；本發明除了目標為空間利用率最大之外，還要考慮多個重量約束，根據重量最大和重量平衡約束的特性，將它們轉為問題的目標；因此，每個解評價函數的適宜值f計算公式如下：

f=0ifΣi=1k~wgi×ki′>WGa1×Σi=1k~vi×k′V+a2×Σi=1k~wgi×k′WG+a3×GifΣi=1k~wgi×ki′≤WG]]>

其中，a₁,a₂,a₃為空間利用率、裝載重量與額定值比率和裝載重心的權值系數，根據約束需求的強度給它們分配不同的值,V為集裝箱的體積，v_i和wg_j分別為第i種貨物的體積和重量，和k′為裝到箱中貨物種類數量和第i種貨物的數量，WG為集裝箱的額定重量，G為箱中全部裝載貨物的總重心；當裝載貨物超載時，適宜值為零；蟻群算法經過上述改進后，將它與裝入啟發算法相結合，求得最優裝載布局結果。