基于改進遺傳算法和多目標決策的貨位優化策略

陳曉艷，張東洋，蘇學斌，代鈺賀，趙春東

(1. 天津科技大學電子信息與自動化學院，天津 300222；2. 青海通達油脂加工有限責任公司，西寧 810000)

近年來，倉庫管理信息化、自動化程度日趨提高．自動化立體倉庫是現代物流技術、倉儲技術、自動化技術與計算機技術高度集成化的產物[1]．目前，自動化立體倉庫應用廣泛，提高倉庫空間利用率、優化貨物存儲方案是降低倉儲成本、提高工作效率的關鍵[2]．

隨著人工智能技術的發展，遺傳算法成為解決上述問題的有效解決方法之一．Lam等[3]提出貨位優化問題是倉儲貨位管理的核心問題之一；Celebi[4]提出使用遺傳算法控制集中分配網絡中的庫存，并以土耳其汽車制造商作為案例研究；Ene等[5]研究倉庫中挑揀操作和適當存儲策略，并采用遺傳算法解決能耗問題；Dai等[6]依據安全距離規則，建立倉庫安全布局的數學模型，通過遺傳算法優化存儲布局．但上述研究中運用傳統遺傳算法仍存在一定不足，如收斂速度不夠快、易陷入局部最優、出現未成熟收斂等．

為了獲得更佳的優化結果，提升算法性能，Ehsan等[7]提出一種改進的交叉、逆、插入、交換變異算子，獲得了更高質量的解；Yan等[8]利用自適應遺傳算法構建多目標分配模型，實現庫存的動態貨位分配；Manatkar 等[9]、Homayouni等[10]、Zu 等[11]將遺傳算法與其他智能算法(粒子群算法、模糊決策等)結合起來，通過混合遺傳算法實現對庫存的優化．

綜合國內外遺傳算法在貨位優化問題上的研究及應用現狀可以發現，大多研究專注于獲得比傳統遺傳算法更佳的優化結果，而對算法的收斂速度鮮有明確闡述．本文結合青海省通達油脂加工有限責任公司的實際需求，提出一種改進的遺傳算法，通過增加二次優化環節，提高算法的收斂速度，同時綜合考慮倉庫出入庫效率、貨物分類擺放合理性、貨架穩定性三方面需求，通過構建多目標優化模型、改進算法、仿真驗證，獲得了一個綜合、可行的貨位優化解決方案，從而實現了隨機庫存的在線動態貨位分配．

1 模型構建

1.1 模型假設

貨位位置采用三維坐標(x，y，z)表示，即第 x排y列z層．倉庫貨位共有n排k列l層．為研究方便，在構建模型之前，本文提出如下假設：

(1)貨物出入庫方式為單端口出入．

(2)不考慮存取貨物的用時與方式，只提出優化存儲策略．

(3)貨位規格統一，且滿足國際化標準托盤存放最低要求．

(4)貨物采用標準化托盤存放，單個托盤內貨物種類相同．

(5)只考慮貨物重量，不計貨架重量．

1.2 構建過程

貨物存儲問題是一個復雜的多維度的優化問題，不僅要考慮到貨物的整體出入庫效率和分類存放的合理性，還要盡可能的使貨架的重心接近地面，保證貨架的穩定性．綜合考慮這 3方面因素，本文提出基于多目標決策方式構建優化模型．

1.2.1 出入庫效率

提高出入庫效率的關鍵在于減少貨物的出入庫時間，當叉車存取托盤及運輸速度不變的情況下，貨物移動的距離將成為影響貨物出入庫時間的關鍵因素．本文研究貨位優化問題的目標之一就是調整貨物存放位置，實現貨位的自動分配，從而盡可能縮短貨物出入庫的距離，提升出入庫效率．具體模型見式(1)．

式中：s表示當前倉庫已存放貨物的貨位數；(xi, yi, zi)表示第i個已存放貨物的貨位坐標．

1.2.2 分類存放合理性

如果貨物不按照分類隨意擺放，會大大增加庫存管理和取貨的難度，降低工作效率．因此，在貨物存放中，將同類貨物存放在該類貨物的中心貨位附近，從而實現貨物的合理分類存放．具體模型見式(2)．

式中：(a*, b*, c*)表示當前種類貨物的中心貨位坐標，模型采用歐幾里得度量描述貨位之間的距離．

1.2.3 貨架穩定性

貨架的穩定性取決于其重心的高度，其重心越低，穩定性越高，將較重的貨物擺放在貨架的低層可以增加貨架的整體穩定性，使得貨架的重心到地面的距離最短．具體模型見式(3)．

式中：s表示當前倉庫已存放貨物的貨位數；mi為第i個貨位中的貨物質量．

綜上所述，貨位優化問題的多目標數學模型為

2 算法原理

遺傳算法(genetic algorithm，GA)是一種基于生物進化機制的隨機搜索算法，能夠有效地進行概率意義下的全局搜索，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱并行性和更好的全局尋優能力；采用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則．遺傳算法的基本運算過程包含初始化、個體評價、選擇運算、交叉運算、變異運算、終止條件判斷幾個部分．

本文在傳統遺傳算法基礎上，提出了一種改進的二次優化遺傳算法(quadratic optimization genetic algorithm，QOGA)．遺傳算法魯棒性高，尋優能力強，結合二次優化環節，加速算法收斂，能夠在短時間內計算出最優解．由于各目標函數之間互有影響，單獨進行研究無法解決問題，依據多目標決策方案，采用權重系數法賦予各個目標函數不同的權重，將該模型轉化為方便計算的單目標函數問題．其模型為

二次優化遺傳算法流程如圖1所示．

圖1 二次優化遺傳算法流程圖Fig. 1 Flow chart of QOGA

3 算法實現

3.1 初始化

3.1.1 編碼

編碼是遺傳算法的第一步，常用的編碼方式有二進制編碼、浮點數編碼以及格雷碼編碼等．本文中將貨物存儲信息作為決策變量，為了適應所研究的問題，采用十進制整數編碼，一個染色體個體的編碼代表一種可行的貨位分配方案．貨架上的貨位由行數、列數和層數這3個維度確定，每條染色體的基因個數為3N個(N代表存貨貨位的個數)．

3.1.2 控制參數

控制參數包含種群規模、遺傳代數、終止條件、交叉概率、變異概率等．參數初始化是依據算法設計規則，對控制參數賦合理的初值．參數符號及初值見表 1．

表1 算法參數初值及含義Tab. 1 Initial values and meanings of parameters

3.1.3 初始種群

在開始算法迭代過程之前，需要對種群進行初始化．確定種群規模，即確定種群里的個體數量，一般隨機生成初始種群，但是如果知道種群的實際分布，也可以按照此分布來生成初始種群．根據表 1確定的種群規模，創建一個psize行、3N列的初始種群矩陣pop．

3.1.4 適應度函數

遺傳算法中構建的適應度函數將影響算法的收斂速度以及能否得到最優解．個體的適應度值是對個體優良與否的評價指標，適應度值與被遺傳的幾率成正比．本文通過目標函數變換得到適應度函數

3.2 選擇、交叉、變異操作

3.2.1 選擇操作

選擇操作即從前代種群中選擇個體到下一代種群的過程．一般根據個體適應度的分布來選擇個體．適應度值與被遺傳的幾率成正比，即優秀的個體有更大的幾率存活下來，更有機會參與后續的交叉和變異，更有權利繁衍后代．本文選用錦標賽法，每次隨機從種群矩陣pop中抽取兩個個體比較其適應度，選擇適應度高的個體直接保留到下一代，并淘汰適應度低的個體，循環直至個體數達到原種群規模．

3.2.2 交叉操作

交叉操作是對任意兩個個體進行的，是遺傳算法中個體染色體進行交配的運算規則，目的是保證種群的穩定性，朝著最優解的方向進化．本文采用單點交叉，隨機選擇兩個個體，同時生成一個(0，1)上的隨機數，若生成的實數小于預設的交叉概率，則對這兩個個體進行交叉，再隨機選擇交叉位置，將兩個體交叉點位置之后的整數串進行對換，如圖2所示．

圖2 交叉操作示意圖Fig. 2 Crossover operation diagram

3.2.3 變異操作

變異操作是對單個個體進行的，是為了保證種群的多樣性，避免交叉可能產生的局部收斂．本文選用均勻變異算子進行單點變異(圖 3)，規則為用符合約束條件的隨機數根據變異概率代替染色體上的原有基因，然后在(0，1)上生成隨機數，若隨機數小于變異概率則進行變異運算，否則不進行變異運算．

圖3 變異操作示意圖Fig. 3 Mutation operational diagram

3.3 二次優化環節

為了適應研究的問題，加快算法求解速度，本文在傳統遺傳算法的基礎之上進行了改進——在種群的每一次迭代中增加了二次優化環節，實時追蹤全局最優個體，同時將每一代種群中的最差個體用全局最優個體代替，保證每一代種群中的優勢個體數量，減少劣勢個體數量．用優勢個體去進行交叉、變異等進一步的尋優，有更大的概率找尋到更優個體，提升算法求解效率．

在二次優化環節中，首先引入變量 Best追蹤全局最優個體及其適應度值，在每一次迭代過程中，比較Best與當前種群最優個體的適應度值，若Best優于當前種群最優個體，Best保持不變，更新當前種群最優個體，用 Best代替．若 Best劣于當前種群最優個體，更新Best，保證Best為整個迭代過程中的最優個體．然后依據個體適應度確定當前種群中的最差個體，用最優個體替代當前種群最差個體．通過“否定”掉當前最不適應環境的個體，并將其替換為當前最適應環境的個體，盡可能的讓更適應環境的個體去生存、繁衍，保證優秀父代的規模與質量，能夠大大提升算法求解效率．其操作流程如圖 4所示．其中：Best為迭代全局最優解；pop_best為每一代種群中的最優解；pop_worst為每一代種群中的最差解．

圖4 二次優化環節操作流程Fig. 4 Flow chart of quadratic optimization

二次優化環節有較大概率能夠對算法迭代前期的收斂起到加速作用．分析算法原理后發現，在每一次迭代之后用全局最優個體代替當前種群的最差個體就會降低當前種群的多樣性，依據瑪格列夫物種多樣性指數可知，每次當前種群最差個體被替代后，總物種數量S會減少1，總個體數量N不變，故瑪格列夫指數D減小，物種多樣性下降．瑪格列夫物種多樣性指數定義為

式中：D為瑪格列夫指數；N為總個體數量；S為總物種數量．

依據算法原理，種群物種多樣性下降會對遺傳算法的收斂效果產生影響，可能產生過早收斂的情況.經多次測試，改進二次優化遺傳算法并未出現明顯的過早收斂現象．

4 仿真與應用

首先，構建一個仿真的自動化立體倉庫，有 15個隨機存儲的貨位，其初始坐標見表 2，該倉庫中貨架共有4排4列4層，各類型貨物的中心貨位坐標分別設定為(2，2，2)、(3，2，2)、(2，3，2)．通過MATLAB軟件求解，分別得到改進二次優化遺傳算法和傳統遺傳算法求解過程中的最優適應度函數值隨種群迭代的變化曲線，如圖5所示．

由圖 5可知：改進二次優化遺傳算法能夠有效提升算法在前期的收斂速度；當種群迭代到 150次時，結果趨于穩定，且計算時間與誤差均在可接受范圍之內，但傳統遺傳算法大約需要400次迭代才能獲得相同結果；改進二次優化遺傳算法的收斂速度較傳統算法提升了約 2.7倍．按貨物編號順序，優化后的貨位坐標依次為(2，2，2)、(2，1，2)、(1，2，1)、(2，2，1)、(1，2，2)、(3，2，1)、(3，2，2)、(4，2，2)、(3，1，2)、(3，1，1)、(2，3，1)、(1，3，1)、(1，3，2)、(3，3，2)、(2，3，2)．

表2 貨位優化結果Tab. 2 Location optimization results

圖5 最優適應度函數值變化曲線Fig. 5 Optimal fitness function value curve

為了衡量優化效果，分別求解3個目標函數優化前后的函數值，結果見表3．由表3可以看出：3個目標函數值較優化前分別降低了 19.10%、43.26%、67.39%，優化效果各異，其中貨物合理分類存放方面的優化效果最好．

依據多目標決策分析整體優化效果時，需要將各方面的優化結果加以綜合．為使出入庫效率、分類存放合理性、貨架穩定性在分析整體優化效率時具有相近的影響力，令

即 89ω1＝15ω2＝223ω3，求得 ω 分別為 0.136、0.809、0.055．依據優化結果，照顧優化效果較差的出入庫效率，調整權重，得到最終結果：ω1＝0.155，ω2＝0.800，ω3＝0.045．

表3 優化前后目標函數值對比Tab. 3 Object function values before and after optimization

由表 3可知：依據多目標決策綜合分析，總的目標函數下降了 49.91%，優化效果顯著．對比優化前后貨位分布狀態(圖 6)可以發現：優化前貨位分布雜亂無章，布局混亂；優化后的貨位大多集中在出口位置附近，且多數貨物位于底層，整體布局合理有序．綜合分析倉庫的出入庫效率、貨物分類存放合理性和貨架的整體穩定性，較優化之前有了明顯的改善.

圖6 貨位優化前后分布狀態Fig. 6 Distribution before and after location optimization

本算法實地應用于青海省通達油脂加工有限責任公司．該公司的糧油倉庫占地面積約 8000m2，立體倉庫貨架分布為 8排 8列 4層．主要存儲產品類型有5類：5L海北花經典濃香菜籽油、5L海北花土榨菜籽油、20L雪蓮花純香菜籽油、20L潤百香純香四級菜籽油、22L互助通達純香菜籽油．采用QOGA算法為倉庫中5類共150件商品進行存儲貨位優化，初始時刻所有商品隨機存放，經算法 2000次迭代優化，評價函數指標由 1132.50降低至 957.05，下降約15.5%，優化效果比較明顯．

5 結 語

本文對倉庫的出入庫效率、貨架的穩定性和貨品的分類擺放方面構建目標函數優化數學模型，采用定量分析方式，實現倉庫貨物的動態貨位分配．同時在傳統遺傳算法基礎之上，提出了一種改進的二次優化遺傳算法，利用 MATLAB軟件求解，并與傳統遺傳算法求解曲線對比分析，求解結果清晰，算法收斂速度明顯提升，改進方案切實可行．通過算法分析可以看出，優化后的目標函數值較優化之前有明顯降低，優化效果顯著．結果表明，采用二次優化遺傳算法優化自動化立體倉庫的貨位問題行之有效，為自動化立體庫貨位分配和優化提供了一個綜合、可行的解決方案．同時經倉庫實際應用也驗證了本文算法具有可行性和實際應用價值．

本算法還具有智能推薦功能，體現在貨位優化后，對新入庫的貨物可智能化推薦合理的存儲貨位，使其符合出入庫效率高、分類存放合理、擺放貨架穩定的多目標要求．