改進(jìn)遺傳算法在電商倉儲貨位分配中的研究

詹長書，張世林

（東北林業(yè)大學(xué)交通學(xué)院，黑龍江哈爾濱 150040）

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

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

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

1 立體倉庫優(yōu)化模型構(gòu)建

1.1 貨位分配建模的條件假設(shè)

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

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

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

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

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

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

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

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

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

1.2.1 提高揀貨效率

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

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

綜上可得，貨物從相對應(yīng)貨架到出庫口的總體位移的表達(dá)式為：

因此可得揀貨效率模型：

1.2.2 提高貨物出入庫效率

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

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

1.2.3 提高貨架穩(wěn)定性

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

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

模型的約束條件如下：

優(yōu)化模型中涉及的模型參數(shù)含義如表1 所示。

表1 參數(shù)含義

1.3 模型的轉(zhuǎn)化

多目標(biāo)問題的優(yōu)化需要從出入效率、揀選路徑以及貨架穩(wěn)定性進(jìn)行求解分析，使各個目標(biāo)函數(shù)在一定范圍內(nèi)向最優(yōu)化的方向靠近，以此達(dá)到三個目標(biāo)函數(shù)的最優(yōu)化，因此對各個子目標(biāo)函數(shù)賦予權(quán)重，使其轉(zhuǎn)化為單目標(biāo)問題，目標(biāo)函數(shù)表達(dá)式如式（9）所示：

1.4 權(quán)重值的分配

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

表2 判斷矩陣標(biāo)度及定義

根據(jù)表2 中的標(biāo)度對權(quán)重值構(gòu)造相應(yīng)的判斷矩陣Q，如下所示：

采用求和方法計算各個權(quán)重系數(shù)：

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

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

所以得到其權(quán)重矩陣為[0.07 0.65 0.28]T。

2 改進(jìn)的遺傳算法設(shè)計

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

算法流程如下：

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

2）適應(yīng)度函數(shù)：種群個體的優(yōu)劣是根據(jù)適應(yīng)度的大小來判斷的，為防止適應(yīng)度函數(shù)為負(fù)值，得出適應(yīng)度函數(shù)的計算公式：

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

圖1 改進(jìn)選擇算子流程圖

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

圖2 單點交叉示意圖

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

圖3 單點變異示意圖

3 仿真案例分析

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

表3 優(yōu)化基本參數(shù)

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

表4 初始貨位信息表

利用Matlab R2019a 編寫的程序運行得出基本遺傳算法和改進(jìn)的遺傳算法目標(biāo)函數(shù)追蹤圖，如圖4所示。

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

表5 優(yōu)化后貨物信息表

圖4 改進(jìn)遺傳算法和遺傳算法優(yōu)化對比圖

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

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

圖5 優(yōu)化前后貨位對比圖

4 結(jié)論

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