基于遺傳算法的自動化立體倉庫儲位優化研究

周杰

(研林自動化科技有限公司,上海 201822)

0 引言

自動化立體倉庫是現代企業智能化物流的重要環節。該系統由現代物流技術、計算機應用技術、智能數據技術、電氣自動化智能控制等技術相結合[1]。依據程序算法控制指令,實現貨物的自動高效存取,已經成為重要研究方向,特別是自動化立體倉庫中貨物儲位分配策略方面問題更需要深入研究。貨物儲位分配問題直接影響立體倉庫系統的性能和運行效率。貨物儲位分配優化策略是依據貨物、貨架和客戶存取需求,保證立體倉庫內有限存儲空間更合理分配,從而提高存儲效率[2]。

結合立體倉庫的構造模型,貨物儲位分配策略的優化主要包括:以優化倉庫存儲效率為目標建模,良好的貨物儲位分配策略可以提高貨物周轉率,方便庫存盤點和移庫。儲位分配策略主要包括出入庫效率、保證貨架的穩定性和貨物周轉率。同時,通過遺傳算法求解多目標數學模型,最終得到優化的貨物分配方法。

1 自動化立體倉庫

1.1 立體倉庫的組成結構

自動化立體倉庫主要包括立體貨架、出入庫托盤輸送系統、有軌巷道堆垛機、鋼結構平臺、調節平臺、貨物掃碼系統、電線電纜橋架配電柜、電氣智能自動控制系統、工業通信系統和計算機智能信息管理系統等。典型的自動化立體倉庫結構示意圖如圖1所示[3]。

圖1 典型的自動化立體倉庫結構圖

1.2 立體倉庫貨物儲位分配原則與策略

自動化立體倉庫定義貨架位置坐標為x排y列z層。即該立體倉庫一共有a排b列c層。圖2為實際貨物位置與數學坐標對照示意圖。虛線的交點對應著每一個貨物位置的幾何質心。

圖2 實際貨物位置與空間坐標對照示意圖

自動化立體倉庫貨物儲位分配考慮的主要因素是貨物進出庫的效率、貨架的穩定性和貨物周轉率。在自動化倉儲管理中,通常情況下,貨物的分配應遵循以下幾個原則[4-5]。

1)貨物先進先出的原則。為避免長時間存放有實效性貨物(如:食品、藥品等),需要考慮倉庫中的貨物在出庫操作中具有較高的優先級。2)貨架穩定原則。貨物輕上重下可使貨架穩定。分散存放,使貨架均勻受力,防止貨架變形。其目的是提高訪問效率和降低運營和維保成本,這可以通過提高生產率和減少不必要的移動性來實現。3)就近原則(提高周轉率)。選擇最近巷道減少堆垛機平均移動距離。搜尋最靠近儲存巷道和最短存儲貨物位置的路徑,從而縮短裝載時間,提高堆垛效率。

2 自動化立體倉庫儲位優化模型建立

2.1 貨物儲位優化數學模型構建

在保證符合實際操作原理的基礎上,為方便起見,將實際問題抽象成數學問題。需對數學模型的建立進行以下假設[6]:1)為便于實際操作和實例的分析轉化,每條巷道內設置一架堆垛機;2)貨物用貨箱存放,貨物箱與貨箱外觀尺寸成正比;3)每個貨位只能存放一個貨物,不允許貨物混放。所以貨物儲位分配優化問題要從多方面考慮,既要權衡貨物的周轉率和關聯性,又要使貨物的擺放盡可能保證最低質心。這些因素是相互制約的,要想同時得到滿足,就必須按多目標問題來解決。

2.2 倉庫模型建立與求解

1)提高出入庫效率目標函數

出入庫效率的關鍵是減少貨物出入庫的時間,受堆垛機運行速度和貨物運送行程的限制,不可能在短時間內提高堆垛機的移動速度。因此縮短出入庫之間的距離是提高效率的關鍵。數學模型表示為

(1)

式中:xi,yi,zi是倉庫中貨物儲位的空間坐標;sx是堆垛機橫向速度;sy是縱向移動速度;sz是垂直移動速度;lc是貨架單元的長度;ls是貨架之間的距離間隔;Ti是存取i個貨物的周轉率。

2)貨架穩定性目標函數

貨架的穩定性取決于貨物質心的高度,將重物放在底部,貨架質心與地面之間的距離最近,可以提高貨架的整體穩定性。所以,該數學模型表示為

(2)

式中:Wabci是第i種貨物的質量;Mxyzi是貨物i在儲位的總數量;ls是貨架之間的距離間隔。

3)“周轉率靠近出入口存放原則”目標函數

要求堆垛機在出入庫時有更高的搬運效率,貨叉的移動距離對堆垛機搬運移動貨物時有直接影響。所以,頻繁進出的貨物,應該將其貨物位置布置在靠近巷道進口處。物品的周轉率定義為某時間段貨物出入庫的數量與該貨品總量的比值。數學模型表示為

(3)

式中:Ti是存取i種貨物的周轉率;Nabci是貨物出入庫的總數量;Txyzi是堆垛機從巷道進口處到貨物儲位所需要的運行時間。

3 基于遺傳算法模型求解

遺傳算法是一種通過實數編碼、種群初始化、適應度函數評價、回放式隨機選擇、單點交叉、均勻變異等操作,有規則地實現隨機搜索方法。像自然法則一樣,該算法是一種仿生物進化過程的優化算法[7]。遺傳算法魯棒性強,收斂速度快。遺傳算法工作流程如圖3所示。

圖3 遺傳算法流程圖

1)浮點數編碼

設計遺傳算法首先要進行種群編碼。采用浮點數編碼方式,該方法具有較高的精度和較好的局部搜索能力,有利于處理復雜的決策變量并且提高找到最優解的概率。與二進制編碼不同,浮點數編碼無需解碼。例如:6(5,3,2)代表的意義就是6號貨物存放在5排、3列、2層。

2)種群初始化

編碼完成后,需要初始化種群,這也是求解前的準備工作。在種群初始化過程中,根據貨物位置數量定義貨物的類型。即使同一類貨物放在不同的貨物地點,也應視為不同的貨物。然后確定種群規模和種群中的個體數即決策變量。種群規模的大小可以在100～200之間隨機設置。種群越大可選擇優化解越多。

3)適應度函數

初始種群確定后,需要計算個體適應度值。個體適應度值的大小可以通過目標函數來計算。將設定基本參數和優化前后的貨物貨位坐標引入到仿真軟件中。

4)比例選擇操作

比例選擇操作是從當前群體中選擇或復制比較優良的個體并遺傳至下—代群體中。比例選擇操作也是一種隨機選擇[8]。設群體大小為P,個體i的適應度為Fi,則個體i被選中的概率pis為

(4)

由式(4)可見,適應度越高個體被選中的概率也越大,反之亦然。

5)單點交叉操作

首先在0.4～0.99之間隨機確定交叉概率。從比例中選出的優秀個體進行交叉配對。通過單點交叉選擇配對,將種群即(染色體)通過單點交叉選擇配對,再隨機選擇的位置點分割群體(染色體),并交換右側部份,從而獲得兩條不同的染色體。與其他交叉口相比單點交叉的混合速度較慢。該方法增加了種群的交叉粒度,降低了種群被破壞的概率。

6)均勻變異操作

在0.000 1～0.1之間隨機確定變異概率。均勻變異是指單個編碼串中的每個基因位點是變異點。從一對基因值范圍內取一個具有突變概率的基因值來替換原始基因值。均勻變異操作中搜索點在整個搜索空間中可以自由移動,增加了種群多樣性。變異點新基因值由式(5)表示為

(5)

7)遺傳算法終止條件

通過遺傳操作次數,算法的終止數達到設定的迭代數,讓最小和平均目標函數值逐漸接近或趨于穩定。

4 遺傳算法貨物位置分配仿真及分析

4.1 系統參數

自動化立體倉庫系統由模擬立體倉庫及儲運設備組成。立體倉庫共設6層×10行×10列立體貨架,相關參數設置如表1所示。

4.2 遺傳算法參數選取

遺傳算法的參數設置會影響最終結果。因此,需要在仿真運算之前檢查所有參數設置。初始化種群規模設置200,最高進化迭代設置3 000,交叉概率設置0.75,變異概率設置0.06。遺傳算法使個體種群(染色體)多樣化,剔除不適合的個體,保留具有更強的適應性個體。初始化迭代后,目標函數的值持續下降,這表明該算法能夠持續有效地找到可行解空間。從2 000次迭代增加到2 500次迭代。隨著迭代次數的增加,目標函數的收斂速度也加快。經過2 500次迭代后,多目標函數優化越來越穩定。利用MATLAB仿真實驗優化基本仿真參數和貨物儲位坐標,加速出入庫和保障貨架穩定性。最優和平均適應度函數值迭代趨勢圖如圖4所示。

圖4 適應度函數迭代趨勢圖

遺傳算法容易出現局部最優解,可以在短時間內獲得比較滿意的近似最優解,這大大提高了貨物儲位優化的計算效率,也提高了存儲分配布局策略的有效性。

4.3 實驗相關數據

為了使模型更理想化,設置堆垛機加減速時間和貨叉伸縮量消耗的時間被忽略。貨位編號如表2所示。

表2 貨物信息及仿真結果

4.4 仿真優化結果分析

通過MATLAB三維仿真效果圖顯示優化前的自動化立體倉庫貨物位置分配布局比較凌亂,布局不合理,倉庫儲位分配策略綜合性能較差。圖5顯示倉庫中貨物位置初始化分配布局。

優化后的儲位布局如圖6所示。在提高倉儲效率的基礎上,優化的倉儲空間也使貨架質心降低,提高貨架的穩定性。通過優化后,貨物位置分配集中在倉庫出入庫口,貨物集中在倉庫底部,總體布局合理,貨物的擺放更加規范。

圖6 貨物位置優化后儲位分配狀態顯示

從優化前后目標函數值對比(表3)可以看出,優化前后3個目標函數的變化分別下降了9.82%、16.53%和13.48%,整體下降率為11.89%,提高了出入庫效率、貨架穩定性和貨物周轉率。可以看出,在貨物儲位分配優化的具體應用中,由于自動化立體倉庫規模較大,可能會有更多的貨物需要處理。如果采用傳統的求解方法求解該問題,會增加一系列的計算時間,無法應用于實際問題中。

表3 優化前后目標函數值對比

表4和表5顯示堆垛機和貨架利用率優化前后數據對比分析。可以看出通過遺傳優化算法后,自動化立體倉庫的工作效率得到很大提升。

表4 堆垛機利用率對比 單位:%

表5 貨架利用率對比 單位:%

5 結語

通過貨物儲位分配的原則和策略,建立了合理的貨物位置分配數學模型。在此基礎上,設計3個目標函數,即貨物的出入庫效率、貨架的穩定性、貨物周轉率。該數學模型驗證貨物儲位分配優化,提高自動化立體倉庫作業效率,方便管理,增強穩定性。基于遺傳算法能夠得到多目標函數的最優解,該算法清晰且易于實現,在短時間內可以得到一個全局最優解。通過此案例分析優化后的目標函數值比優化前有所降低,達到了預期效果。也證明遺傳算法對解決提高自動化立體倉庫堆垛效率和性能是切實可行的。