改進遺傳算法在電商倉儲貨位分配中的研究

詹長書，張世林

（東北林業大學交通學院，黑龍江哈爾濱 150040）

信息化的發展帶來了人們對于網購的依賴性，電商倉儲也成為各大平臺的競爭要素。尤其是在“雙十一”、“雙十二”和“618”等節日常常出現爆單的情況下，合理的貨位分配，極大地影響著倉儲的效率。貨位管理運用的核心在于在遵循貨物存儲的基本原則下提高貨位的使用率，盡量提高倉庫使用效率[1]。

針對貨位分配問題，Jiao Y L等[2]采用多種群遺傳算法和簡單加權遺傳算法對比的方式，對立體倉庫貨位進行優化，多種群遺傳算法更加有效；Yang L Q 等[3]提出一種新的自適應遺傳算法求解貨位分配問題，證明了改進算法的有效性；Yan B 等[4]采用自適應遺傳算法求解LCM 模塊產品倉庫多目標貨位分配模型，該模型能有效地收斂到最優解。國內學者在此方面也進行了很多研究，董海等[5]提出一種基于非均勻消除-擴散概率的情緒化細菌覓食算法，驗證了該算法在解決該類問題上具有較好的收斂性并保證了種群的多樣性；郭娟等[6]提出采用粒子群算法來對目標貨位進行優化，并且驗證了粒子群算法對于立體倉庫的作業效率和成本問題的有效性；王賀[7]提出一種二次優化的遺傳算法來進行模型的求解，并通過對比基本遺傳算法的求解結果，得出改進遺傳算法的有效性；蔡安江等[8]采用改進的混合蛙跳算法對雙向式立體倉庫模型求解，對比基本遺傳算法證明了改進算法的高效性。

綜上所述，以上方法雖都能有效提高倉儲效率，但是算法收斂時間較長，基于此，該文根據貨物出庫效率、最優揀選路徑以及貨架的穩定性建立模型，采用一種無放回基于排序的多輪盤賭選擇算子的遺傳算法[9]進行求解模型，不僅能提高算法的收斂性，而且能提高倉儲的效率。

1 立體倉庫優化模型構建

1.1 貨位分配建模的條件假設

為了便于模型的建立和研究，做出以下假設：

1）為了減少復雜性，貨物的出入庫均視為勻速直線運動。

2）每個貨架上的貨位尺寸大小相同，貨物可大小不一，但均不超過貨架的最大尺寸容量。

3）每個托盤的尺寸大小均相同，且貨物種類是已知的，相同種類的貨物可放置一起，但不能超過貨位的承載度。

4）堆垛機在x、y、z方向上均進行勻速直線運動。

5）對貨物進行揀選時，只計算貨物從貨位到放置區的時間，其余所用的時間不計入運算中。

6）貨物均采用相同規格的托盤存放。

1.2 貨位分配模型建立過程分析

該文根據電商物流中心的特點，以及其他輔助工具的參數來確定研究的模型，主要涉及到倉庫中便于分揀的原則、揀選路徑最佳的原則以及貨架穩定性的原則來進行對整個倉庫分配優化模型的建立。

1.2.1 提高揀貨效率

提高揀貨效率，主要從縮短揀貨的距離方面考慮。揀貨距離指的是貨物移動的總體距離，其中包括貨物在貨位上移動的總體位移和貨物從貨位到出口位置所發生的位移。貨物在貨位上移動的位移為：

貨位到出口位置的總位移主要包括第i排貨架上相對應的貨物到出口位置所發生的水平位移C1和垂直位移C2。

綜上可得，貨物從相對應貨架到出庫口的總體位移的表達式為：

因此可得揀貨效率模型：

1.2.2 提高貨物出入庫效率

由于電商物流中心商品種類繁多，而且貨物周轉頻繁，尤其是在一些特殊節日，往往會出現爆倉的狀況。為避免問題的產生，往往會根據以往訂單來判斷貨物所放的位置，結合周轉率，將出入庫頻繁的貨物放置于靠近庫口的位置。由此得出具體模型：

其中，(xi、yj、zk)表示第s個貨物位于第i排、第j列、第k層。

1.2.3 提高貨架穩定性

對于電商物流中心而言，貨物種類繁多，貨物質量大小不一，譬如一些汽車零配件的質量往往高于一些化妝品的質量。因此，為了確保立體貨架的穩定性，盡可能做到貨架重心下移，即上輕下重。該文將貨物儲位的高度與其對應貨物質量的乘積之和最小即視為存儲有效，因此得到的表達式如式（6）所示：

綜上可得立體倉庫貨位分配的數學模型，如式（7）所示：

模型的約束條件如下：

優化模型中涉及的模型參數含義如表1 所示。

表1 參數含義

1.3 模型的轉化

多目標問題的優化需要從出入效率、揀選路徑以及貨架穩定性進行求解分析，使各個目標函數在一定范圍內向最優化的方向靠近，以此達到三個目標函數的最優化，因此對各個子目標函數賦予權重，使其轉化為單目標問題，目標函數表達式如式（9）所示：

1.4 權重值的分配

權重值的確定方法有專家打分法[10]、德爾菲法[11]、CRITIC 權重法[12]、熵值法[13]、主成分分析法[14]、層次分析法（Analytic Hierarchy Process，AHP）[15]等。層次分析法能夠將多決策目標、多準則層要素這類復雜問題轉化為單目標問題進行處理[16]，因此該文采用層次分析法來求解各子目標函數的權重值。對于AHP方法，通過判斷矩陣的方式進行權重確定，標度aij的取值通常同1-9 的標度，判斷矩陣的標度及定義如表2 所示。

表2 判斷矩陣標度及定義

根據表2 中的標度對權重值構造相應的判斷矩陣Q，如下所示：

采用求和方法計算各個權重系數：

1）先對判斷矩陣的每一列進行歸一化處理，再求每一行各元素之和得到WK。

2）對WK進行歸一化處理得:m1=W1/3=0.07；m2=W2/3=0.65；m3=W3/3=0.28。

所以得到其權重矩陣為[0.07 0.65 0.28]T。

2 改進的遺傳算法設計

遺傳算法模仿生物進化理論,是根據自然選擇的原理解決具有線性約束或非線性約束最優問題的一種算法[17]。傳統遺傳算法中的選擇操作常采用輪盤賭的方法，往往會導致優化過程出現退化。該文采用無放回的基于排序的輪盤賭選擇算子[9]，此算子能夠明顯提高算法的收斂速度，可以少時高效地得到優化結果。

算法流程如下：

1）種群初始化：對倉庫貨位隨機分配，形成初始的種群，采用整數編碼的方式對貨位進行編排，例如234 代表一條染色體，234456…789 代表一個個體。

2）適應度函數：種群個體的優劣是根據適應度的大小來判斷的，為防止適應度函數為負值，得出適應度函數的計算公式：

3）選擇運算：計算種群每個個體的適應度大小，采用無放回基于排序的輪盤賭選擇算子進行選擇操作。假設種群大小為N，初代種群為{B1,B2,B3,…,Bi,…,BN}，且每個個體的適應度值為，按照適應度值的大小對初始種群由高到低排序，排序后的種群為{C1,C2,C3,…,Ci,…,CN}，其中最大值個體G的適應度值為fitG。根據排序后總適應度值計算出每個個體被選中的概率，根據概率將[0,1]劃分為N個分段，用整數A1,A2,A3,…,Ai,…,AN代表N個分段上落在[0,1]之間隨機數的個數，轉動輪盤，將區間上個數最大的maxAi所對應的個體作為子代種群的個體儲存。多次進行輪盤賭直至得出的子代種群大小為N，找出子代種群適應度最低的個體K，用初代種群中個體G代替個體K，存儲所有新選出的個體并返回進行下一次運算。選擇運算流程簡圖如圖1 所示。

圖1 改進選擇算子流程圖

4）交叉運算：隨機選擇兩個個體進行交叉運算，該文采用單點交叉的方式，交叉概率一般為0.5～0.9。對交叉的個體隨機選擇交叉點的位置，并將相對應交叉點之后的染色體進行互換，如圖2 所示。

圖2 單點交叉示意圖

5）變異運算：變異運算是為了增強遺傳算法的局部搜索能力并增加種群的多樣性，依據設定的變異概率對種群進行變異操作，該文采用單點變異的方式，如圖3 所示。

圖3 單點變異示意圖

3 仿真案例分析

對于M 電商物流中心自動化立體倉庫，選取其中連續的8 排8 列8 層作為研究對象，用Matlab R2019a 進行編程求解。優化所需的基本參數如表3所示。

表3 優化基本參數

現有17 個貨位的信息，由于參數的選取直接影響算法的結果，在Matlab R2019a 程序中多次進行參數檢驗，取最大迭代次數Gen 為200代，種群大小Community 為120，交叉和變異概率分別為0.7、0.05，初始17 個貨位信息如表4 所示。

表4 初始貨位信息表

利用Matlab R2019a 編寫的程序運行得出基本遺傳算法和改進的遺傳算法目標函數追蹤圖，如圖4所示。

從圖4 中可以看出，改進的遺傳算法收斂情況明顯優于基本遺傳算法，在33 代以后趨于穩定，優化后的貨位信息如表5 所示。

表5 優化后貨物信息表

圖4 改進遺傳算法和遺傳算法優化對比圖

通過對比貨位的坐標，畫出貨位的三維立體對比圖，如圖5 所示。

通過圖5 優化前后對比圖可以得知，優化前貨物的擺放比較無序，且一些出庫頻率高的貨物都放在了離出庫口較遠的位置，這不僅增加了貨物揀選的時間，也降低了高頻出庫貨物的效率。對于一些質量較大的貨物，放在上層貨架會降低貨架的安全性，通過對比優化后的貨位分配圖，高頻率的貨物基本都放在離出庫口近的位置，相比較而言，質量大的貨物都位于貨架的底層，根據優化前貨位信息得出優化前總目標函數值Ftotal_Initialdata=503.854 4,優化后總目標函數值Ftotal=291.579 8，優化效率為42.12%，相比優化前得到較為明顯的改善。

圖5 優化前后貨位對比圖

4 結論

針對電商立體倉庫存儲存在的貨位分配問題，該文主要從出庫效率、揀選路徑選擇、貨架穩定性三個方面考慮，提出采用無放回基于排序的多輪盤賭選擇算子的遺傳算法，通過對選擇算子的改進，對貨位優化的三個原則建立數學模型，并利用Matlab R2019a 編程對仿真案例求解。從求解結果可知，改進的遺傳算法實際有效，不僅提高了算法的收斂性能，而且優化的效果更為明顯。由此可見，該方法在電商物流中心自動化立體倉庫中對貨位進行分配，不僅能夠提高貨物的出入庫效率，而且能夠提高整體貨架的安全性，有助于提高經濟效益。