倉配一體化倉庫揀貨路徑優化策略應用研究

閆 軍，王璐璐，常 樂

（蘭州交通大學 機電技術研究所，蘭州 730070）

0 引言

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

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

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

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

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

1 倉配一體化倉庫揀貨路徑優化模型概述

1.1 建立倉庫二維坐標系定義貨位坐標

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

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

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

C為倉庫貨架的巷道數。

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

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

即倉庫中貨位的縱坐標為：

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

1.2 根據坐標生成距離矩陣

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

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

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

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

表1 貨物間的距離矩陣

2 模型假設

假設TSP模型建立如下：

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

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

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

3 模型構建

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

現以揀貨人員在倉庫中行走的最短揀貨路徑為目標，可建立如下數學模型：

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

4 算法求解與案例分析

4.1 算法求解

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

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

圖2 模擬退火算法流程圖

4.2 案例分析

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

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

當采用遺傳算法對30個貨物進行有效揀選時，揀選的最優路徑順序為：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）算法求解

當采用遺傳模擬算法對30個貨物進行有效揀選時，揀選的最優路徑順序為：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）不同規模下揀貨單的對比

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

4）結果的對比及分析

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

表3 算法對比

圖7 GA最優解的搜索過程示意圖

圖8 GASA最優解的搜索過程示意圖

5 結語

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