改進遺傳算法在自動化立體倉庫貨位分配中的應用

□ 趙 陽

(蘭州交通大學 機電工程學院，甘肅 蘭州 730070)

1 引言

在當今社會互聯網、電商等各類技術與產業競相發展的背景下，物流倉儲在社會物質生產活動中的地位日益提升。倉儲的運作管理對優化物流產業，提高經濟活動的運行質量和效率都具有重大意義。自動化立體倉庫(AS/RS)要達到在能耗小和成本低的條件下對貨物進行存取的客戶需求，在規定的期限內將物品準確提供給客戶[1]。貨位管理運用的核心在于：在遵循貨物存儲的基本原則下提高貨位的使用率，盡量提高倉庫使用效率。

近年針對倉儲貨位分配策略優化問題的研究主要有：李鵬飛等[2]以出入庫效率為優化目標建模，采取病毒協同遺傳算法進行仿真，表明病毒協同遺傳算法是進行貨位優化的一種有效方法；李霞等[3]從入庫、出庫和倒庫三個階段來對動態貨位優化進行建模與仿真，選用遺傳算法求解模型并驗證了算法的有效性；劉萬強等[4]從提高AGV小車作業效率出發，研究棋盤格密集倉庫的貨位分配問題，設計相應的改進算法，解決貨位分配問題的同時，AGV小車的作業效率也大幅提升；彭小利等[5]提出基于制造物聯技術的智能倉庫，引入RFID技術實現物品、貨架、叉車、工人等的智能化；徐偉華等[6]針對密集型倉庫使用實際，根據兩種工況設計模型，利用遺傳算法進行求解有效提升了堆垛機搬運貨物的效率。

從已有的文獻可以總結出，較多現有研究對具體問題的優化目標考慮不夠詳盡，有的研究只考慮貨物分類擺放和貨架重量的問題，有的研究只考慮貨物的出入庫效率問題而又忽略了貨架的整體穩定性，將多目標結合起來建模求解的研究還較少。同時對于多目標問題求解的優化算法選擇也存在一些問題，部分求解算法收斂性不好、計算速度慢、解的質量低等問題仍然存在。另外在現代智能優化算法的研究中，算法參數的選取與具體操作的設計是影響算法性能指標的關鍵環節。因此，本文提出以貨架穩定性、貨物周轉率、貨物相關性等原則為基礎的多目標貨位優化模型，并設計雙種群遺傳算法[7]進行求解，對立體倉庫的貨位分配策略進行研究。

2 自動化立體倉庫貨位分配模型

2.1 貨位分配規則

倉庫貨位分配在考慮貨位利用率的同時，還需要同時兼顧貨架整體穩定性、各類物品的時效性和總體的出入庫效率等。通過對實際場景的研究和分析，本文建立的貨位分配規則涵蓋以下幾個方面。

①較重物品低層存放?，F有研究通常僅單純考慮節約堆垛機存取貨物耗時，并未充分考慮不同種類貨位存儲時重量、體積差異給貨架穩定性帶來的影響。本文設置“重物品分配較低層，輕物品分配較高層”的規則，使貨架承載穩定。

②周轉頻率較高的貨物靠近巷道口存放。為減少堆垛機對同類物品反復存取耗時，提高出入庫效率，應將該類物品靠近巷道口存放。

③相關物品靠近存放。對于關聯物品種類，通常會出現同時需要進行出庫操作的情況，一次要安排盡可能靠近存放，以便提高物品的查找和存取。

④物品先進先出。先進先出原則的設置是考慮到例如食品、藥品等種類的貨物要求有較強的時效性，避免因長時間存儲為之后的使用帶來問題，需考慮先入庫的物品在出庫操作時擁有較高的優先級。

2.2 貨位分配建模

2.2.1 基本條件假設

為方便將實際問題抽象成為數學問題，在保證符合實際操作原理的基礎上，本文需將數學模型的建立進行以下假設：

①各貨架整齊平行排列，巷道兩側僅各有一排貨架。貨架構造即各個貨架層、列、貨位的尺寸、數量均相同；

②為方便統計計算，將貨架靠近出入口的一列記為第一列，最下方一層為第一層；

③為便于實際操作和實例的分析轉化，每條巷道內設置一架堆垛機；

④考慮到計算的復雜性，假設堆垛機在搬運物品時進行的是勻速直線運動，水平和豎直方向的速度分別為vx和vy；

⑤貨物種類已知，相同種類的物品可以在不超過貨位容量的情況下合并放在同一個貨架中，且重量要均勻分布。

2.2.2 貨位分配規則建模

①根據“較重物品低層存放”原則建立的目標函數f1。

為保證整個貨架的穩定性，遵循“重心越低則越穩定”原則。貨架整體重心指標可以用托盤上物品質量與貨架層數的乘積來表示，乘積越小則重心越低。根據此建立的數學模型為

(1)

其中：r為區域內的貨架總數；p為一排貨架的層數；q為一排貨架的列數；k為物品所在貨架編號；i為物品所在貨架層；j為物品所在貨架列；mkij為第k排貨架第i層第j列貨位上的物品質量；f1為每個托盤上物品質量、物品所在貨架、物品所在層三個參數的乘積。

②根據“周轉率靠近出入口存放”原則建立的目標函數f2。

該規則要求出入庫過程堆垛機搬運的效率高，堆垛機搬運物品的效率與貨叉的移動距離有關，因此，物品存放位置直接影響堆垛機運用效率。為此出入庫頻率高的物品應分配靠近巷道出入口的貨位。物品的周轉率定義為某時間段貨物出入庫的數量與此物品總量的比值。由此可得到數學模型為：

(2)

其中：pkij為存放在(k,i,j)貨位物品的周轉率；tkij為堆垛機從巷道口出入庫點到(k,i,j)貨位運行耗時；f2為某物品周轉率與堆垛機運行耗時的乘積之和。此外：

因此，將tkij代入式(2)得：

(3)

約束條件為：

③根據“相關物品靠近存放”原則建立的目標函數f3。

出庫物品的種類常與其商業用途有關，以工廠生產車間物流配送為例，各類零部件配件往往會同時被需要。因此，具有相關性的物品入庫安排貨位時必須為同一貨架或相鄰貨架，且兩者之間的距離盡量小，否則認定為沒有達到相鄰的要求。假設具有相關性的兩物品存放位置分別為(k1,i1,j1)和(k2,i2,j2)，其所在貨架為同一貨架或同一巷道相鄰貨架。

可建立如下模型：

(4)

約束條件為：

其中：k1為物品1所在貨架的排；j1為所在貨架的列；i1為所在貨架的層；k2,j2,i2同理；w為兩貨架間巷道的寬度；m為相關物品的組數；c為相關物品的組序號；f3為相關性物品的距離之和。當k2-k1=0時，表示兩物品存儲在同一貨架；當k2-k1=1，表示兩物品存儲在相鄰貨架上，為確保物品存儲于同一巷道的兩排貨架，需將k1取奇數以滿足假設。

④根據“先進先出”原則建立的數學模型。

同種類物品是物品具有相關性的特殊情況，存放時應同時滿足“相關物品靠近存放”的規則，因此把“先進先出”原則的建模公式作為前者的約束條件。假設放置同種類例如食品：物品1、物品2，其中物品1在先前已入庫，物品2為待入庫的物品。根據以上分析，物品2所在貨位與巷道口的距離應遠于物品1，即堆垛機從出入庫點取走物品2的耗時大于取走物品1的耗時，即t2≥t1。設物品1貨位坐標為(k1,j1,i1)，物品2貨位坐標為(k2,j2,i2)，據此建模為：

化簡得：

2.3 多目標貨位分配模型

在實際操作中對貨位進行分配時，需要同時考慮以上幾個規則，即貨位分配時需要同時滿足式(1)、(3)、(4)三個方程。

約束條件為：

根據實際問題構建的數學模型式(1)、(3)、(4)，對自動化立體倉庫的貨位優化問題進行求解，但本問題是多目標函數的求解問題，不易得出求解方案，因此為三個目標函數分配三個影響因子θ1、θ2、θ3，采用權值分配將其轉換成單目標函數求極值的問題。

minf=θ1f1+θ2f2+θ3f3

(5)

3 基于雙種群遺傳算法的模型求解

3.1 求解思路及算法流程

通過之前對數學模型的描述，將具體問題的數學模型分別建立為三個求極小值的目標函數，但由于三個目標函數之間互相影響，盡管將其轉化為單目標函數求極值，其實質仍是多目標函數的優化問題。大多數工程實例都會被轉化為多目標函數問題，對其有良好效果的智能求解方法一直是近年來的研究熱點。其中，遺傳算法對貨位分配策略優化求解效果優秀[8]。遺傳算法的基本原理是：根據生物“物競天擇，適者生存”的自然規則設置一定種群數量的候選解后，進行選擇、交叉、變異等一系列操作增加種群多樣性增加算法的計算性能，得出最優解，在求解同時能兼顧運算效率和運算精度。此外為改善傳統遺傳算法存在的缺陷，本文采用雙種群遺傳算法進行求解。算法流程如下：

第一步：根據工程問題構建的數學模型進行編碼；

第二步：根據問題模型隨機產生N個解構成初始種群，令i=0；

第三步：種群一進行適應度函數評價后采用錦標賽法進行選擇運算；

種群二進行適應度函數評價后采用輪盤賭選擇法進行選擇運算；

第四步：兩個種群在選擇運算后分別進行交叉、變異運算生成新一代物種；

第五步：兩種群合并再次進行遺傳運算；若i到達最大進化代數則輸出最大適應度個體；反之則在i+1后進行第三步操作；

第六步：結束。

3.2 參數設計及遺傳運算

3.2.1 編碼

本文模型選擇整數編碼的方法[9]。具體實現方法是：用坐標表示貨位編號，每條染色體表示一種分配方式；每條染色體都可以分為N段，每段代表一個基因，而每個基因代表空間內一個貨物貨位的位置(k,i,j),即每個基因都對應一個貨位的編號，其中N為這條染色體中貨位的個數。此外，每段基因都是由三位整數表示，百位k、十位i、個位j的值分別代表貨位所在貨架的編號、貨位水平方向在第幾行、豎直方向在第幾列。

假設緩存區域有五個貨物需要進行分揀入庫，其中1號貨物置于(3,2,1)即3號貨架的第2行第1列的位置；以下同理，2號貨物置于(3,2,2)；3號貨物置于(4,2,3)；4號貨物置于(4,4,4)，5號貨物置于(2,2,4)。那么“321”、“322”、“423”、“444”、“224”就分別表示一條染色體的五個基因，此時染色體“321322423444224”即為一個解，表示一種可能的貨位分配方式。

3.2.2 適應度評價函數

適應度值是算法評價染色體解的優劣的重要指標，適應度值大的個體被遺傳保留到新一代種群的可能性會更大，反之則很難被保留到下一代種群[10]。本算法采用建模過程中得到的函數模型式(5)的函數值來評價個體的優劣程度。

3.2.3 遺傳運算

①選擇運算。

選擇運算體現“適者生存”的自然原理，根據適應度函數值來選擇更適合進入下一代種群的個體。在此針對兩個種群分別選用“錦標賽法”和“輪盤賭法”作為選擇操作。其中種群一使用的“錦標賽法”：確定每次選擇的個體數量，種群中隨機選擇個體構成組，根據個體適應度值，選擇其中適應度最好的個體進入子代種群重復該操作直至種群規模達到要求。為了體現兩個種群的差異性，對于第二個種群的選擇運算使用“輪盤賭選擇法”，即將各目標函數分配權重后，以其加權和在總和中所占的比重作為選擇標準進行選擇，加權和越大的個體被選擇的概率越大。

②交叉運算。

交叉運算是算法過程中種群產生新個體的主要來源，兩個體的部分染色體在某概率下按照一定的規則進行交換。本文設計的交叉操作為：種群中的某個體為一種貨位分配方案，將種群中的兩個個體相交叉即可產生兩個全新的解。隨機配對方法是倉庫貨位分配中常采用的配對方法，設種群個體數目為N，進行配對時按隨機方式將其分為N/2組，在組內部的兩個體進行交叉運算。根據前述編碼方式的設計，本文選擇三點交叉方式進行交叉運算，交叉運算示意如圖1。

圖1 交叉運算操作

③變異運算。

遺傳算法的運算可使部分個體或染色體失去基因的多樣性，這其中可能包含有用基因，變異操作即是為了避免遺失部分有用的遺傳基因，避免失去檢驗有用基因的機會，從而保障解的質量。變異運算在遺傳算法中充當的角色是一種輔助手段，以相對于交叉概率來講的小概率來變換個體中部分基因。本文的變異操作采用基本位變異法，即在(0，1)之間隨機生成一個數，若該數小于變異概率，則執行變異操作，反之則不執行。倉庫貨位分配中的個體值為一種貨位分配排列，執行變異操作時，要注意貨架層、列、排的對應，例如，在操作時要設置好在第4和第10基因座進行操作。變異運算示意如圖2。

圖2 變異運算操作

4 實驗仿真與結果分析

根據前述建模過程，采用MATLAB工具對抽象出的貨位分配模型及其求解進行測試驗證。具體相關仿真數據設定如表1所示。

4.1 倉庫基本參數

表1 倉庫基本參數信息

4.2 貨物基本信息

本文選擇20件貨物作為仿真數據，其中貨物的重量是分揀后托盤和貨物的總重量。貨物的周轉率根據以往數據求得。如表2所示。

表2 貨物信息表及仿真結果

4.3 遺傳算法參數選取

遺傳算法參數的選取會影響最終輸出結果的優劣，因此，在進行仿真的時候要對參數進行測驗，但考慮仿真結果的客觀性，程序中初步選取的遺傳算法參數為：初始種群規模M為200，最大進化代數T為500，交叉概率pc為0.4，變異概率pm為0.05。

雙種群遺傳算法的貨位優化結果如表所示，本文設定三個貨位優化原則同等重要，即θ1=0.33、θ2=0.33、θ3=0.33?？梢园l現經過優化后，貨物的出入庫距離、貨物出入庫時間、貨架穩定性等方面均有一定提升，貨物的擺放更加規范，表明雙種群遺傳算法能有效給貨位優化問題提供解決方案，驗證了提出方法的有效性。

圖3 平均計算時間隨M變化的曲線

為了更好地對比雙種群遺傳算法相比傳

統遺傳算法的優越性，計算了兩種算法的平均計算時間的變化情況，對比結果見圖3。通過MATLAB的仿真實驗可以看出：雙種群遺傳算法具有更高的計算效率，改善了基本遺傳算法容易陷入局部最優解的缺陷，提高了貨位分配策略的效率和結果的可靠性。

5 結束語

本文采用雙種群遺傳算法(DGA)對AS/RS貨位分配策略進行優化研究，在得出最優分配策略的同時驗證了算法的有效性，并將其平均計算時間等方面與傳統遺傳算法進行了對比，充分體現出了DGA在貨位優化方面的優越性和可靠性，一定程度上改善了遺傳算法迭代次數多、收斂速度慢等問題。但對于倉庫貨位優化問題，包括各類構造不同的倉庫以及用怎樣的智能算法和改進策略還需要進一步的研究和探討。