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

0 引言

現代物流企業對于倉儲的現代化管理要求越來越高，自動化立體倉庫（AS/RS）在提升庫存量，提升空間利用率、減少占地和節約人力等方面具有巨大優勢，是物流系統發展和優化的關鍵環節。如何進行貨位分配是影響自動化立體倉經濟效益和安全性的核心問題，貨位在遵循貨位分配原則的基礎上如何優化，通常從優化目標以及優化算法入手。由于自動化立體倉庫會因為建筑形式、貨架樣式等因素產生不同的細分類別，也會因為揀選輸送系統、存取作業設備、存儲條件和策略等因素的不同，在對貨位分配問題上應用的優化方法有很大的區別。

Fonseca[1]將貨位優化問題總結為多目標的求解問題，并且分析了多目標進化方法，提出多目標優化問題難以求得最優解，只能通過平衡、協調多個目標達到Pareto 最優解。此外，許多國內外學者把貨位優化問題總結為以出入庫效率、貨架穩定性、堆垛機路徑優化為主的多目標優化模型[2-4]。對于貨位優化的多目標優化問題，在優化算法的選擇上許多學者采用遺傳算法進行求解。鄧愛民等[5]以貨架穩定性、分巷道存放和出入庫效率為目標的基于時間的多目標模型，李梅娟[6]提出了采用Pareto 遺傳算法解決該問題，針對提高貨架穩定性和存取效率取得了不錯的優化效果。

除此之外有非常多的優化算法被應用在貨位優化問題上，陳月婷、何芳[7]提出了基于Pareto 最優解的改進粒子群算法來解決貨位優化問題。李鵬飛等[8]通過對比分析提出病毒協同遺傳算法是解決貨位優化問題的一種有效方法。大量學者熱衷于算法應用上的創新，在優化目標選擇上主要集中于提高存取效率以及貨架穩定性，鮮有考慮工作量均衡的研究，雖然目標優先級是次要的，在實際應用中也是容易被忽視，但卻是很可能出現的問題。此方面的研究首先要界定工作量的定義，通常是指進行存取作業的設備工作量，立體倉庫的作業設備不盡相同，除堆垛機外也有應用提升機與子母穿梭車的立體倉庫，著眼于作業設備工作量均衡的優化模型在設計過程中要考慮實際情況下會產生許多工程上的限制因素，同時模型所需數據存在一定的難度，在尋求通用的優化模型上，唐文獻等[9]在貨位優化模型中設計了以出入庫頻率為核心的巷道工作量均衡模型，并以細菌覓食算法進行求解，在仿真過程中驗證了單一考慮某個優化目標時的優化效果，由于目標函數之間可能存在約束或沖突，同時考慮多個優化目標才更符合自動化立體倉庫的實際需求。

本文正是針對我國應用最為廣泛的單元貨格式立體倉庫[10]，在以提高存取效率和貨架穩定性為優化目標以外，考慮到可能出現部分巷道任務過多，而部分巷道任務偏少的工作量不均衡問題，為減少此類生產浪費，額外設置工作量均衡的優化目標。考慮到數據的獲取難度，在模型中通過控制巷道與巷道之間總出入庫數量差值最小來達到基于任務量的巷道工作量均衡目標，該模型不會被巷道操作設備的選擇所影響，對這個多目標優化問題采用遺傳算法進行求解，通過仿真驗證模型的優化效果良好。

1 貨位分配原則

對自動化立體倉庫進行貨位分配時應當遵循以下原則：（1）貨架穩定性原則。貨架首先應當保證具有足夠安全性，貨品的存放應當從下至上，上輕下重，降低貨架重心。（2）就近出入庫原則。在自動化立體倉庫中，使存儲位置放置在距離出庫臺附近，尤其是出入庫頻率高的貨物，存放在出庫口附近可以有效減少作業距離，從而提高存取效率。（3）先進先出原則。同一種貨物在出庫時，應當遵循入庫早的先出庫的原則。避免貨物存放時間過長而造成不必要的損失。

2 問題描述與基本假設

描述如下：在M 公司的倉庫庫區中選擇共有a 排貨架，每排貨架有b 列c 層，將距離出庫口最近的一排貨架記為第一排，最近的一列記為第一列，最底下一層為第一層。那么，貨位坐標(x,y,z)代表位于第X 排Y 列Z 層的貨格，（x=1,2,…,a;y=1,2,…,b；z=1,2,…,c；a 為偶數）。每一組貨架都由兩排貨架組成，兩排貨架共用一臺堆垛機完成出入庫作業，如圖1 所示。出庫臺位置記作(0,0,0)，數學模型涉及的符號說明如表1 所示。

圖1 一組貨架示意圖

表1 符號說明

根據如上描述，將本文進行貨位優化的基本假設總結如下：（1）該自動化立體倉庫系統的存取方式是單元貨格式，即倉庫的每一個通道中都有一臺巷道堆垛機，其兩側各有一排貨架，每一排貨架都是相同的，貨架上的每個貨格也都大小相同，每個貨格只能存儲一個貨品，由托盤承托，所有托盤尺寸相同。（2）堆垛機可以對其兩側的貨架托盤進行存取作業且兩側作業情況一致。（3）立體倉庫的出入庫方式為單端口，采用隨機存儲策略。（4）存取貨品消耗時間忽略不計。（5）巷道堆垛機可以在水平和垂直方向即Y 向和Z 向向上同時做勻速運動。

3 數學模型的建立

3.1 出入庫效率最高的目標

根據就近出入庫原則，要實現距離最短，使得作業時間最短即可，則所有貨物的存取頻率和堆垛機運行時間乘積之和最小，由此建立數學模型：

3.2 貨架穩定性的目標

根據貨架穩定性原則，要降低貨架整體的重心，使得貨架整體下重上輕，即使貨品的質量mxyz與貨位(x,y,z)所在的層數z的乘積之和最小，由此建立數學模型：

3.3 工作量均衡的目標

為了達到工作量均衡的目標，即每個巷道的工作量均衡，通過控制巷道與巷道之間的出庫任務量差來使得巷道達到工作量均衡的狀態，在此策略下還能一定程度上使得貨位數量均勻分布，間接達到工作量均衡的目的，配合目標函數（2）可以使貨架有較好的抗傾覆能力[11]，由此建立數學模型：

3.4 約束條件

由空間約束條件可知，貨位(x,y,z)是處于貨架內的坐標，因此有：

3.5 多目標貨位優化模型

根據以上三個目標函數和約束條件可得貨位優化的多目標函數表達為：

4 多目標遺傳算法模型求解

解決多目標優化問題的基本思路是把多目標問題轉化為單目標問題，遺傳算法全局搜索能力強，魯棒性好，在解決多目標優化問題的研究領域內應用廣泛且效果顯著。故本文采用遺傳算法對模型進行求解。

4.1 多目標問題轉化

給三個目標函數分別賦予目標相應的權重值Wi(i=1,2,3)，權重越大表示目標函數的重要程度越大，因此多目標優化問題可以表示為：

4.2 編 碼

編碼方式選擇自然數編碼。用自然數1,2,3…來代表貨位(x,y,z)，那么染色體的長度就與貨物的總數量一致。

4.3 種群初始化

初始化工作采用隨機方法產生種群規模K=100 的初始種群。

4.4 適應度函數的確定

遺傳算法中采用適應度函數來衡量個體的優劣，適應度值要求必須為負數，適應度值較大的個體被認為是優良的個體，所以適應度值越大越好。遺傳算法經常把目標函數作為適應度函數，對于本文三個目標函數都是求全局最小值，而且都是非負數，那么可以直接取目標函數的倒數作為適應度函數。

為了防止函數值差值過大影響遺傳算法的性能，在進行倒數操作前，先將各目標函數去量綱處理，消除單位對數值的影響后再對目標函數求倒數來構造適應度函數。對目標函數線性變換處理，轉化為無量綱函數。

經過線性變換后三個目標函數均映射到(0,1)區間，式中fi代表第i 個目標函數，原目標函數分布情況不會因為線性變換而改變，不會影響遺傳算法的性能。為了避免出現數據溢出的情況，在分母上加1 避免適應度函數值趨向于無窮大。轉換后的適應度函數表達式為：

4.5 選擇操作

選擇操作對初始種群的各個染色體進行評價，本文選擇輪盤賭選擇法，首先計算每個染色體得到適應度值Fi和整個初始種群的適應度總和；其次計算種群中每個染色體個體被選中的概率pi；然后按照次序計算每個染色體個體被選擇的累計概率；最后隨機生成一個介于0 到1 之間的隨機數R,依次與累計概率進行對比，如果滿足在累計概率范圍內則被選中。即R＜P1，就選擇第一個個體，如果PK-1≤R≤PK,則選擇第K 個個體。

4.6 交叉算子

交叉操作是按照一定的方法交換染色體上的部分，從而得到兩個全新的個體。隨機從(0,1)之間生成一個數r，將這個數與交叉概率pc進行比較，pc一般取0.4 到0.99 之間，如果r≤pc就進行交叉運算，如果r＞pc則將兩個母代個體重新加入下一代的種群中。結合自然數編碼的編碼方式，本文選擇基于位置的交叉（Position-based Crossove）r。

5 基于Matlab 的模型求解和仿真分析

5.1 參數設定

本文對M 公司的倉儲信息系統中選擇某一區域進行采樣，經過處理和計算得到重量和初始坐標等信息，為了方便研究，只提取貨架的部分區域，對此優化區域的參數作一些假設，該貨架區域由4 排，5 列和8 層的貨架構成，共160 個貨位，當前優化區域有100 個貨品。立體倉庫貨架和堆垛機的基本參數、遺傳算法所需要的基本參數以及多目標模型的權重設置具體如表2 所示：

表2 仿真基本參數表

5.2 結果分析

為了驗證模型的有效性，對優化前后的貨位分配布局和目標函數值進行對比，優化前貨物分布圖如圖2 所示。

圖2 初始貨物分布圖

優化后的貨位分配情況如圖3 所示。

圖3 優化后貨位分配模擬圖

目標函數由三個子函數構成，每個子函數的權重都會直接影響最終的優化效果，權重的大小可以根據企業對于目標函數體現的存儲策略的側重程度靈活調整，在三個權重分別為0.4、0.3 和0.3 時貨位分配結果合理，模型運行結果如圖4 所示。

圖4 優化算法迭代曲線圖

將優化前后三個目標函數值及加權結果進行對比，結果如表3 所示。

由表3 可知，三個目標函數經過優化后都有不同程度的降低，三個目標函數的降低比率分別為15.83%,50.24%和100%，加權后的目標函數值降低比率達到50.21%。

表3 優化效果對比表

對子目標的權重進行調整，觀察權重對于優化結果的影響程度。倉儲貨品重量普遍較大的企業較之于貨品重量普遍較輕的企業，在存儲策略上往往在注重提高存取效率的前提下同樣非常重視貨架穩定性，因此將目標函數f1的權重保持不變，目標函數f2的權重提高0.1 之后重新運行，最終模型得出的優化結果如表4 所示。

表4 重設權重后的優化效果對比表

由表4 可以看出，再對目標函數的權重進行略微調整之后，總體優化效果依然超過了50%，優化效果顯著。

實際應用中部分立體倉庫對于貨架穩定性的要求不高，例如蔬果類乳品類企業會更加追求存取效率上的優化提升，出于對比目的以便觀察目標函數（1）的權重對于優化效果的影響，再次對子目標的權重進行調整，當三個目標函數的權重分別為0.5、0.3 和0.2 時，模型運行結果如表5 所示：

表5 二次調整權重后的優化效果對比表

由表5 數據可以發現，再次微調權重后的運行結果有略微變化，優化效果相比前文兩種權重配比變化不大，模型的優化效果仍然比較顯著，說明優化模型依舊充分發揮作用，起到了較明顯的優化效果。

6 結論與展望

本文通過對某食品企業M 公司自動化立體倉庫作業案例的考察，建立多目標優化的數學模型并以真實數據進行Matlab 仿真研究，優化結果表明該模型可以提高存取效率以及貨架穩定性，除此以外還能有效解決巷道工作量均衡的問題，以加權后的目標函數值為例，試用三種不同比例的權重分配模擬不同類型企業在存儲策略上可能做出的微調，模型運行結果比較穩定，加權后的目標函數值平均降低比率為50.23%，說明此優化模型在常規權重設置的條件下能夠達到50%左右的優化效果，對于不同存儲策略的單元貨格式自動化立體倉庫都可以發揮出實際應用價值。

本文是基于我國目前廣泛應用的單元或格式立體倉庫，隨著技術與設備的更新升級，像雙深位立體倉等新式立體倉不斷出現，也為該領域的研究開辟了新的疆土。另一方面，一些對模型的簡化所作的假設會對實際運行效果產生不同程度的影響，此方面仍有改善的空間，將作為今后進一步研究的方向。