倉配一體化倉庫揀貨路徑優(yōu)化策略應(yīng)用研究

閆 軍，王璐璐，常 樂

（蘭州交通大學(xué) 機電技術(shù)研究所，蘭州 730070）

0 引言

近幾年，電子商務(wù)的快速發(fā)展使倉庫效率成為一個熱點話題，由于商品流通規(guī)模的不斷擴大，倉配一體化[1]逐漸成為物流行業(yè)的一個發(fā)展趨勢。在普通倉庫的所有作業(yè)中，經(jīng)研究發(fā)現(xiàn)，揀貨作業(yè)就占用60%，貨物移動成本占大約90%，揀貨作業(yè)時間至少占其全部作業(yè)時間的35%。故如何提高倉庫內(nèi)部工作效率、降低成本成為倉配一體化企業(yè)越來越的關(guān)注問題，倉庫內(nèi)貨物的揀選路徑優(yōu)化研究也成為一個熱點問題。本文以西北某倉配一體化企業(yè)為研究對象，對貨物揀選路徑優(yōu)化問題進行研究。

目前，針對倉庫貨物揀選路徑問題的研究，學(xué)者主要圍繞S型揀貨路徑策略（穿越策略）、中點穿越策略、返回策略、最大間隙策略、混合策略以及最優(yōu)路徑策略等幾種策略進行研究。常用研究算法有：遺傳算法、模擬退火算法、蟻群算法等。

國外學(xué)者Hall.R.W[2]在文章中通過分析S型揀貨策略、返回策略以及最大間隙策略，得出如果將三種策略進行有效結(jié)合，可以提高揀貨效率，從而提出混合型揀貨策略。Lu,Chen[3]等將倉庫貨位分配和自動存取交叉問題進行綜合研究，以啟發(fā)式算法和禁忌搜索算法相輔相成作為優(yōu)化過程。Chen-Yang[4]等在研究多品種、少批量情況下的貨物時，以揀貨批量及揀貨路徑為研究重點，采用蟻群算法和粒子群算法兩者結(jié)合的混合算法，求解最佳揀貨批量的揀貨路徑問題。Yang C L[5]等考慮到貨物的特征、相關(guān)存儲的限制，以分類存儲策略為基礎(chǔ)，運用聚類分析方法中的主成份分析方法，得出貨位檢索時間相比之前提高33%。Chabot T,Coelho L C[6]等針對狹窄通道的倉庫，結(jié)合工廠的實際情況，建立3D模型，運用啟發(fā)式算法對揀貨作業(yè)的路徑及行走距離進行求解，使揀貨人員在倉庫中的總行走距離達到最小。

國內(nèi)學(xué)者穆聰聰[7]等研究在單區(qū)倉庫中，產(chǎn)品頻度與偏離度對貨物出入庫貨位分配策略的影響，將出入庫頻率高的貨物分配在離出入口較近的貨位上，貨物在出庫時采用偏離度的優(yōu)化策略，快速完成揀貨作業(yè)，有效提高揀貨效率。房殿軍，彭一凡[8]等針對多巷道倉庫，對多條橫向通道揀貨路徑進行研究，提出一種組合式啟發(fā)式算法可以有效提高揀貨作業(yè)效率。杜穎[9]在動態(tài)貨位指派與揀貨路徑系統(tǒng)優(yōu)化研究一文中，提出貨位與揀貨協(xié)同作業(yè)的揀貨方式。根據(jù)市場變化，達到存揀合一，有效提高揀選人員的工作效率。

本文研究的是倉配一體化倉庫揀貨路徑優(yōu)化策略應(yīng)用研究，在庫存策略不變的條件下，結(jié)合倉配一體化實體倉庫信息建立揀貨路徑優(yōu)化模型，將遺傳算法、遺傳模擬退火算法的運行時間、距離以及收斂度進行比較，得出不同水平下算法的優(yōu)劣程度。

1 倉配一體化倉庫揀貨路徑優(yōu)化模型概述

1.1 建立倉庫二維坐標(biāo)系定義貨位坐標(biāo)

西北地區(qū)某倉配一體化倉庫平面圖如圖1所示：一個倉庫主要分為兩個區(qū)，可看作雙區(qū)型倉庫，倉庫兩個區(qū)中有儲存貨物的若干個貨架，在倉配一體化倉庫內(nèi)建立平面坐標(biāo)系，根據(jù)雙區(qū)型倉庫內(nèi)部給定的編碼確定貨位，且每一個貨位只能存儲一個SKU，再確定該貨位對應(yīng)的坐標(biāo)。

圖1 倉配一體化倉庫平面示意圖

如圖1所示，在倉配一體化雙區(qū)型倉庫里，包括三條過道和多條揀貨巷道?，F(xiàn)以倉庫左下角O點視為平面坐標(biāo)系中的原點坐標(biāo)，O點向右為x軸正方向，O點向上為y軸正方向。假設(shè)左下角距離原點的地方有一點S，其坐標(biāo)為（xs，ys）。假設(shè)庫內(nèi)貨架的間距寬為hc，兩排貨架合并起來寬度為2hc，當(dāng)揀貨員進行揀貨時，經(jīng)過每個貨位的中點即為揀貨員行走的路程[10]。設(shè)倉庫中某一貨架對應(yīng)貨位的坐標(biāo)為W（x，y），則貨位橫坐標(biāo)為：

C為倉庫貨架的巷道數(shù)。

如圖1所示，假設(shè)倉庫中任一貨位距離S點的縱向距離為Y，則該貨位的縱坐標(biāo)為：y=Y+ys。

假設(shè)在一列貨架中，每排貨架對應(yīng)的編號為B，即貨架最大編號為Bmax，貨架長度為D2，兩貨架之間的間隔為D1，在忽略貨架立柱的影響下，每節(jié)貨架的內(nèi)部長度為ln，若在長度為ln的貨架上安排Pmax個貨位，則每一個貨位對應(yīng)的長度為lnp，幾個參數(shù)之間的關(guān)系如下：

即倉庫中貨位的縱坐標(biāo)為：

根據(jù)式(1)～式(5)可以得出倉庫中任一貨位的坐標(biāo)。

1.2 根據(jù)坐標(biāo)生成距離矩陣

當(dāng)接到客戶訂貨單，生成波次揀貨單時，所揀貨物的貨位已確定，倉庫揀貨人員根據(jù)波次揀貨單進行播種式揀貨，將每批訂單上的同類貨物先累加然后揀取，集中搬運到統(tǒng)一的分揀場所，然后再根據(jù)每個客戶所需貨物的數(shù)量進行二次分揀，直至所有訂單揀取完成。在分揀過程中，根據(jù)貨位編號建立距離矩陣。

假設(shè)倉庫中有兩個貨位分別為S1（x1，y1），S2（x2，y2），且二者之間的最短行走距離為D12，設(shè)：

式中：X12為兩貨位間行走最短折線路徑的橫向長度總和；Y12兩貨位間行走最短折線路徑的縱向長度總和；（i=1,2）為倉庫某一貨位Si（xi，yi）當(dāng)前位置距離貨架最右邊的距離，即：

式(8)表示任意兩個貨位S1和S2之間最短路徑的縱向距離的總和為兩坐標(biāo)點的縱向距離。式(9)表示當(dāng)揀取的兩個貨位為同一區(qū)不同巷道時，揀貨人員會繞過貨架行走，取向左和向右行走的較小值，其他情況則表示揀貨人員不存在繞行的情況。Si表示貨位，Dij表示兩貨位之間的最短距離，N表示揀貨總量，由此可以得到倉庫內(nèi)任意兩個貨位間的距離矩陣，如表1所示。

表1 貨物間的距離矩陣

2 模型假設(shè)

假設(shè)TSP模型建立如下：

現(xiàn)假設(shè)揀貨員手中持有一個波次的揀貨單，從起點S0（0,0）點出發(fā)揀貨，當(dāng)揀選完一個波次的貨物后再回到起點，這一揀貨過程遍歷的所有SKUs所在貨位分別記為S1,S2,…,Sn，且貨位與貨位之間兩兩互不重復(fù)。所有SKUs的貨位坐標(biāo)表示為Si(xi,yi),i=1,2,…,n。假設(shè)貨位Si和Sj之間的最短距離為Dij，在此基礎(chǔ)上引入?yún)?shù)dij，（i=0,1,2，…,n,j=0,1,2,…,n）表示得意義如下所示：

對于距離及參數(shù)，有以下條件：Dij=Dji，且di0=d0i=Di+yi。待揀貨位至倉庫出入口的距離矩陣如表2所示。

表2 待揀貨位至倉庫出入口的距離矩陣

3 模型構(gòu)建

一般傳統(tǒng)低效率的揀貨方式是揀貨人員根據(jù)平時積累的經(jīng)驗以及根據(jù)貨物按照巷道順序的記憶進行揀取，當(dāng)某一波次的訂單生成，由于未對被揀貨物揀取路徑順序進行優(yōu)化，使得不同貨物在揀取時均采用同一模式，導(dǎo)致貨物揀選效率不高，故采用混合遺傳模擬退火（GASA）算法來優(yōu)化揀貨路徑。

現(xiàn)以揀貨人員在倉庫中行走的最短揀貨路徑為目標(biāo)，可建立如下數(shù)學(xué)模型：

式(10)表示從起點出發(fā)途經(jīng)n個貨位后回到起點的最小化的總路徑長度，式(11)和式(12)表示揀貨路徑經(jīng)過貨位的次數(shù)恰為一次，式(13)表示揀貨路徑經(jīng)過所有貨位構(gòu)成一個完整的回路。式(14)表示變量為0-1變量約束。

4 算法求解與案例分析

4.1 算法求解

本文將揀貨路徑問題等同于NP-hard問題，傳統(tǒng)意義上一般采用S形啟發(fā)式算法來求解。遺傳算法（GA）在運行的過程中只著重于局部，在算法進行優(yōu)化時只考慮遺傳算子的變異率和交叉率等參數(shù)的變化，很容易陷入“早熟”，對于大規(guī)模計算量的問題已經(jīng)不能很好地解決?；旌线z傳模擬退火算法（GASA）[11]是模擬退火算法在遺傳算法的基礎(chǔ)上針對遺傳算法局部限制的情況下，結(jié)合模擬退火局部尋優(yōu)融合而成的一種算法。本文分別采用遺傳（GA）算法、遺傳模擬（GASA）算法對案例進行分析與求解。

模擬退火算法是在蒙特卡洛思想設(shè)計的基礎(chǔ)上近似求解最優(yōu)化問題的一種方法。其算法流程如圖2所示：

圖2 模擬退火算法流程圖

4.2 案例分析

以西北某倉配一體化中心為案例背景，在倉庫揀貨人員接到揀貨單后，假設(shè)揀貨單上有30個待揀貨物，揀貨人員在倉庫中的平均行走距離為1.3m/s，巷道寬度為1.4m，通道橫向?qū)挾葹?.8m，操作員在對揀貨單進行掃描等一系列初始化的動作所花費的時間為2s，揀貨人員揀取貨物所花費的時間為1.7s。

1）基于遺傳（GA）算法求解

當(dāng)采用遺傳算法對30個貨物進行有效揀選時，揀選的最優(yōu)路徑順序為：0-1-27-28-29-26-25-24-15-14-8-10-21-20-19-7-11-9-18-3-2-6-5-4-13-16-17-22-23-12-30-0，總揀貨距離為：505.8162m，總揀貨時間為442.09s。揀貨路徑示意圖如圖3和圖4所示。

圖3 GA算法路徑示意圖

圖4 GA算法揀貨路徑

2）基于遺傳模擬（GASA）算法求解

當(dāng)采用遺傳模擬算法對30個貨物進行有效揀選時，揀選的最優(yōu)路徑順序為：0-16-17-22-23-12-13-4-5-30-6-2-9-3-18-20-21-10-19-7-11-8-14-15-24-25-26-29-28-28-0，總揀貨距離為：502.7799m，總揀貨時間為439.75s。揀貨路徑示意圖如圖5和圖6所示。

圖5 GASA算法路徑示意圖

圖6 GASA算法揀貨路徑

3）不同規(guī)模下揀貨單的對比

采用GA算法和GASA算法分別在揀貨數(shù)量為30、50、75的情況下進行對比，結(jié)果如表4所示。由表4分析得，隨著揀貨數(shù)量的增加，完成平均每張揀貨單的距離和時間會逐漸增加。

4）結(jié)果的對比及分析

由表3、圖7和圖8可以看出，GASA比GA更適合求解這類問題，以揀貨路徑和揀貨時間為例來說明，GASA求解的結(jié)果均小于GA，兩算法的最優(yōu)解均低于平均解，GA迭代次數(shù)達到599時，目標(biāo)函數(shù)基本上達到最優(yōu)；GASA迭代次數(shù)達到576時，目標(biāo)函數(shù)基本上達到最優(yōu)。從揀貨路徑來看，GA使用了505.8162m，GASA使用了502.7799m，路徑節(jié)約了0.6%，從揀貨時間來看，GA使用了442.0900s，GASA使用了439.7500s，時間節(jié)約了0.5%。

表3 算法對比

圖7 GA最優(yōu)解的搜索過程示意圖

圖8 GASA最優(yōu)解的搜索過程示意圖

5 結(jié)語

對于電商企業(yè)而言，揀貨作業(yè)在倉庫作業(yè)中占重要部分，合理的選擇揀貨路徑已經(jīng)成為物流企業(yè)亟待解決