立體倉儲系統(tǒng)貨位優(yōu)化算法比較與分析

劉倚瑋，楊 嘉，趙章榮

（1.北京物資學院，北京 101100；2.燕山大學 電氣工程學院，河北 秦皇島 066004）

1 引言

隨著我國物流業(yè)的快速發(fā)展，物流公司的數量也在逐年增加，如何在物流資源有限的情況下合理優(yōu)化物流流程，提高物流效率、降低物流成本是增強企業(yè)核心競爭力的主要因素。隨著自動化立體倉庫的普遍采用，面對種類繁多的物流商品，如何提高配送中心倉儲效率將是企業(yè)不得不面對的現實問題。配送中心是接受并處理用戶的貨物需求信息，對加工生產企業(yè)配送過來的多種商品進行分類，根據客戶訂貨需求進行選配、組合、包裝等作業(yè)并進行送貨的設施和機構。國內的中小企業(yè)已經逐漸認識到配送中心縮短響應時間和降低倉儲成本是提高物流服務水平的關鍵，因此貨位優(yōu)化是不容忽視的重點之一。

貨位優(yōu)化是規(guī)定每一個貨物在合適的儲藏方法下的儲存位置的設置，具有差別的設施種類的特性、貨物劃分、儲位計劃、內部勞動力成本等要素來完成最優(yōu)的貨位構造。在立體倉儲系統(tǒng)諸多問題中，貨位優(yōu)化問題極為重要，與企業(yè)的生產力增長密切掛鉤。最大化的利用可以使用的空間，也就是提高儲存區(qū)的利用率，是研究配送中心儲存區(qū)規(guī)劃問題的目的所在，讓勞動力和配置都發(fā)揮其應有的成效，裝運貨品要既安全又實惠，貨物要做好保護和管理，這樣才能降低物流中心的總成本。

2 貨位優(yōu)化算法研究

貨位優(yōu)化是配送中心縮短響應時間、降低倉儲成本和提高物流服務水平的關鍵環(huán)節(jié)。目前出現了許多貨位優(yōu)化算法，但是由于貨位優(yōu)化的特殊性，主要以遺傳算法為主。當然相關學者也提出了一些其他優(yōu)化方法。

2.1 基于遺傳算法的貨位優(yōu)化

遺傳算法主要仿照自然界的生物演變規(guī)律并用計算機進行模擬研究，通過模擬自然算法來解決最優(yōu)問題。該方法從問題解的串集方面進行搜索，涉及到更大的范圍，且使用并行化方式，綜合水平較高。

文獻[1]研討了自動化存儲體系中優(yōu)化貨物空間不能及時分配的弊端，并通過合并遺傳算法和模擬退火算法來解決這個弊端。文獻[2]針對有貨位載重約束的自動化立體倉庫展開研究，引入“貨物系”概念，以出庫時間最短和貨架的整體穩(wěn)定性為目標函數，設計了非支配排序遺傳算法對模型進行求解。文獻[3]對自動化立體倉庫展開研究，以貨物出入庫作業(yè)時間、貨架整體等效重心和關聯(lián)產品間相對聚集程度為目標函數，將多目標模型加權歸一化處理后，用簡單加權遺傳算法求解，并且為避免出現未成熟收斂問題，運用多種群遺傳算法進行求解。文獻[4]探討了Srinivas M提出的線性自適應遺傳算法，并在此基礎上，根據實際情況對算法進行改進，使用種群個體適應度的標準差代替fmax-favg，得出了改進的自適應遺傳算法。文獻[5]針對普通立體倉庫展開研究，并將貨位優(yōu)化問題分為選擇優(yōu)化層和順序優(yōu)化層，通過結合遺傳算法和啟發(fā)式算法來對模型求解。文獻[6]對同端式出/入庫立體倉庫展開研究，以貨架的穩(wěn)定性和出入庫效率為目標函數，基于向量評估、非支配排序、小生境Pareto 等理論方法設計了三種多目標遺傳算法（MGA）。

2.2 基于其它算法的貨位優(yōu)化

在解決貨位優(yōu)化問題時，除了常見的遺傳算法，還有粒子群算法、嵌套分區(qū)算法、蟻群算法、入侵雜草算法、窮舉法、植物繁殖算法等。

文獻[7]對多層次倉庫貨架進行設計，綜合考慮貨架的定位、貨物用途之間的空間分配、起重機的數量、設施的整體配置等問題，據此提出了一種新的粒子群優(yōu)化算法（PSO）來確定最優(yōu)布局。文獻[8]對小型立體化倉庫展開研究，綜合考慮存儲效率、貨架穩(wěn)定性和工作效率等問題，將多目標問題轉化為單目標問題，并運用嵌套分區(qū)算法對問題進行優(yōu)化求解。文獻[9]對自動化存儲系統(tǒng)（AS/RS）展開研究，以貨物存放高度、空間使用率和運輸路徑為研究因素，運用多目標蟻群算法對貨位進行優(yōu)化，從而減少空間消耗和投資成本。文獻[10]對智能倉儲系統(tǒng)進行了研究，以貨架穩(wěn)定性和運作效率為目標函數，采用權重系數法將多目標函數轉化為單目標函數問題，最后運用窮舉法進行貨位優(yōu)化。文獻[11]對WMS 倉儲管理系統(tǒng)展開研究，以相同產品存儲相鄰位置、提高產品出入庫效率、提高貨架穩(wěn)定性建立多目標函數模型，運用入侵雜草算法對模型進行求解。文獻[12]對雙載具式多層穿梭車立體倉庫展開研究，以入庫時間最短為目標函數建立模型，通過在植物繁殖算法（PPA）中融入遺傳算法（GA）的交叉算子，并將固定邊界的復雜交換轉換為固定邊界的隨機亂序，從而避免算法過早收斂，降低k-opt交換方法的復雜度，得出了混合植物繁殖算法（HPPA）。

綜上所述，本文主要考慮貨物的重量和貨物的周轉率，并對這兩個要素進行深入的探討和研究。對于多目標函數問題，本文將窮舉法和遺傳算法進行比較分析，得出最優(yōu)解。在此考慮貨品周轉率的優(yōu)化原則為[13]：位于倉庫出入口較遠貨品的周轉率低，位于倉庫出入口較近貨品的周轉率高。考慮貨品負荷重量優(yōu)化的分布理論主要依據是：底層貨架存儲質量較重的貨品，更高層的貨架存儲更輕的產品。

3 模型建立

3.1 模型條件假設

本設計系統(tǒng)的假設條件為：

（1）該立體倉儲系統(tǒng)屬于單元貨格式儲存形式，現有堆垛機和貨架。

（2）貨架為矩形，總共有i列，j層，長度是L，高度是H。

（3）包含眾多物品，貨架上全部尺寸相同，且任何貨位都隨意擺放。

（4）系統(tǒng)中對不同貨物的需求相對清楚，且不會改變，不同貨物沒有關聯(lián)。

（5）堆垛機可以在兩個方向，即水平和垂直方向上同時進行運動，本文假設水平和垂直方向上的最大速度分別為Vx和Vy。

3.2 模型建立

多目標函數優(yōu)化問題的一種表現形式就是貨位優(yōu)化問題，因此用權重系數法把多目標問題轉化為單目標問題是解決貨位優(yōu)化問題的一種方法，本文僅考慮貨物周轉率和貨物重量這兩個關鍵要素在貨位分配優(yōu)化上產生的影響。

（1）立體倉庫基本參數。立體倉庫基本參數見文獻[10]，為了減小篇幅，貨架取5層10列。

（2）目標函數。基于堆垛起重機運行時間最少的原則，堆垛起重機的運行時間和貨物周轉率相乘之值最小時，可以得到第一個優(yōu)化目標條件：

式中，tij為堆垛起重機運行到第i 列第j 層貨位時的運行時間；fij為第i列第j層貨位對應的周轉率。

基于上輕下重的原則，設地面底層為第1 層，離I/O 口最近的列為第1 列，當每個貨品的所在層與其質量的乘積之和最小時，得到第二個優(yōu)化目標條件：

式中，Wij為第i列第j層貨位對應的貨物重量。

通過上述這些優(yōu)化函數可以看出，在進行貨位優(yōu)化時，既要考慮貨架是否穩(wěn)定，也要考慮存取效率如何，這是把多個目標組合起來進行優(yōu)化的問題。

在解決多目標函數問題轉化成單目標函數問題時，可以運用權重系數法。假設a和b為兩個函數的權重系數，然后分別對a 和b 進行賦值，令a+b=1，則所求的單目標函數公式為：

以5 層10 列的貨架為例，計算堆垛起重機運行到第i列第j層貨位時運行時間，公式為：

通過上述公式可以得出堆垛起重機從I/O 站臺到所有貨位的單層運行時間tij(s)。

4 貨位優(yōu)化仿真實現

假定倉庫內部存放10 類物品，有關物品周轉率以及重量數據參見表1。

表1 不同種類貨物周轉率和重量對應表

假定所有貨位的使用率是80%，參考現實系統(tǒng)以往的數據可知，明確不同類型物品的預估最高存儲量，把全部貨物隨意放置在庫中，未放置物品的則是空貨位。貨位分配優(yōu)化以前具體分布情況參見表2。當前，數字主要代表不同物品的編號，數字0代表貨位沒有放置產品。

表2 優(yōu)化前貨物分布狀態(tài)

4.1 窮舉法實現

倉儲系統(tǒng)貨位優(yōu)化的主要思路是對貨位交換的條件進行判斷，首先任意選取貨架上第i 列第j 層貨物，假設已知其周轉頻率為fij，其對應的重量為Wij，利用該貨物與第m列第n層貨物進行比較，同樣已知第m 列第n 層貨物對應的周轉頻率為fmn,重量為Wij。計算兩個貨位對應貨物的目標函數值的和P1：

然后再把貨架上第i 列第j 層貨物與第m 列第n層貨物進行交換，并通過求和計算P2值得到式（6）：

把P1的值和P2的值進行比較，如果P1的值大于P2的值，則第i列第j層貨品與第m列第n層貨品進行交換，反之不進行交換。通過逐一比較，從而獲得一個比較合理的貨位分配方案。相應的窮舉法流程如圖1所示。

圖1 算法流程圖

4.2 遺傳算法實現

利用真實庫存數據以及建立的優(yōu)化數學模型，按照遺傳算法操作步驟[14]，使用MATLAB進行遺傳運算，設定單一目標函數與多目標函數的權重系數進行求解。

（1）編碼。使用遺傳算法處理多目標優(yōu)化問題的首要步驟是，針對參數完成編碼，由于該方式無法解決參數，必須把上述參數全部變更成特殊的代碼信息，相當于遺傳學中的染色體。本文的約束標準表明i 和j 均為整數，故采用整數排列的編碼方式。用（i，j）表示貨品所在貨位第i 列第j 層，一個貨位代表染色體上的一個基因。

（2）適應度函數。在倉庫出入庫調度問題中，當任務量一定時，需要盡可能縮短整體倉儲設備的運行時間，一般是使用目標函數中的適應度函數來完成目標，從而提高倉儲運行效率。由于本文模型中的目標函數有多個，所以要把復雜函數變成簡單函數。本文采用窮舉法為多目標函數賦值來進行轉換，即令a 和b 為兩個目標函數的權重系數，且a+b=1。

在本文的優(yōu)化模型中，目標函數的取值范圍是（0，+∞），為了滿足適應度函數輸入結果為非負數，將原函數依次加1后再取倒數，這樣可以滿足遺傳算法中適應度函數的特點，見式（7）。

式中，f1=minQ，f2=minS。

（3）運算過程。運算過程主要包括選擇、交叉和變異3個環(huán)節(jié)。

選擇環(huán)節(jié)的主要基礎是種群內不同個體的適應度評估，使用fitness代表個體k適應度，此時k的選擇概率為：

Pk表示個體k 在種群內，占據所有個體適應度的比值。由于某個體占比高，其被選擇的可能性就更高。

交叉表示在生物遺傳學領域進行基因重組，也是本系統(tǒng)最重要的操作。因編碼表現模式不同，此算法各不相同。主要使用二進制交叉內的單點交叉完成求解任務，可能性為0.7。

變異是指為了找到最優(yōu)解而改變群體內不同個體的基因值。變異率的選擇與種群大小取決于染色體的長度，取值范圍一般在0.001-0.1 之間。本文將選取0.01為變異概率進行計算求解。

5 仿真結果分析

5.1 窮舉法結果

應用MATLAB 對以上窮舉法求解步驟編寫程序，取a=0.5,b=0.5，并運行，記錄總目標函數和兩個子目標函數的每一次迭代變化情況，繪制函數值的收斂曲線如圖2所示。

圖2 總目標函數V值迭代曲線圖

由圖2中的收斂曲線就能了解到，總目標函數值隨著迭代次數增多而降低，在降低到40 到50 區(qū)間時，具體數值并未出現明顯的改變，可以看出迭代基本已經達到收斂。

優(yōu)化前的總目標函數值為7 632，優(yōu)化后的總目標函數值為5 464。

經優(yōu)化后的倉庫貨物分布見表3。其中，數字代表不同貨物的編號，數字0表示該貨位為空。

表3 窮舉法優(yōu)化后貨物分布狀態(tài)

從表中可以看出，同種貨物被放置到了相近的儲位，周轉率或重量相似的貨物也被放置到了相近的儲位，距離I/O 臺較遠的儲位分配成空儲位，明顯提升了儲位的儲存效率，提升了儲位的整體穩(wěn)定性。

5.2 遺傳算法結果

將原始數據代入MATLAB 軟件進行仿真計算，求解初始數據，為得到更接近最優(yōu)解的數據，對其迭代50次，仿真結果如圖3所示。

圖3 50次迭代搜索過程

每次迭代都會產生不同的結果，影響貨位的分布和揀選效率。根據數據和往常經驗判斷，當迭代次數達到一定時，所得結果可以當作是最優(yōu)解。

優(yōu)化前的總目標函數值為7 632，優(yōu)化后的總目標函數值為7 068。

進行貨位分配優(yōu)化后，優(yōu)化后的倉庫貨物分布見表4。

表4 遺傳算法優(yōu)化后貨物分布

從優(yōu)化結果可以看出，基于考慮貨物重量和出庫率的優(yōu)化模型進行優(yōu)化，較重的貨物應該放置到貨架的底部，較輕的貨物盡量放置到貨架的上部，貨物周轉率高的被分配到了離I/O臺近的地方，周轉率小的被分配到了離I/O臺遠的地方，從而保證貨架的穩(wěn)定性。

5.3 結果比較與分析

通過不同方法對相同目標函數進行計算，表明不同目標函數都可以得到全面的優(yōu)化。在進行優(yōu)化之后，周轉率高的物品一般調節(jié)到離I/O 臺近的貨位，重量大的貨物則普遍存放于貨架底層貨位。經過對比，得出結果見表5。

表5 窮舉法與遺傳算法優(yōu)化結果比較

綜合比較可知，窮舉法優(yōu)化要好于遺傳算法，但窮舉法邏輯單一，通用性不強，后續(xù)研究可以通過改進遺傳算法，使其優(yōu)化數據更接近窮舉法。

6 結束語

本文以立體倉儲系統(tǒng)為研究對象，對目前較流行的兩種貨位優(yōu)化方法進行了比較分析。基于Matlab語言分別進行了窮舉法和遺傳算法的貨位優(yōu)化算法仿真研究，給出了立體倉儲系統(tǒng)考慮貨物周轉率、貨物重量、取貨機運行速度的貨位優(yōu)化模型最優(yōu)解。本文在對貨位進行優(yōu)化時，只考慮了貨物的重量和貨物的周轉率兩個方面，沒有考慮其他要素對貨位優(yōu)化的影響。今后可以結合實際情況，改變條件進行研究。