閆 軍，王璐璐，常 樂(lè)

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

0 引言

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

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

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

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

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

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

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

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

圖1 倉(cāng)配一體化倉(cāng)庫(kù)平面示意圖

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

C為倉(cāng)庫(kù)貨架的巷道數(shù)。

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

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

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

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

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

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

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

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

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

表1 貨物間的距離矩陣

2 模型假設(shè)

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

現(xiàn)假設(shè)揀貨員手中持有一個(gè)波次的揀貨單，從起點(diǎn)S0（0,0）點(diǎn)出發(fā)揀貨，當(dāng)揀選完一個(gè)波次的貨物后再回到起點(diǎn)，這一揀貨過(guò)程遍歷的所有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）表示得意義如下所示：

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

表2 待揀貨位至倉(cāng)庫(kù)出入口的距離矩陣

3 模型構(gòu)建

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

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

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

4 算法求解與案例分析

4.1 算法求解

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

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

圖2 模擬退火算法流程圖

4.2 案例分析

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

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

當(dāng)采用遺傳算法對(duì)30個(gè)貨物進(jìn)行有效揀選時(shí)，揀選的最優(yōu)路徑順序?yàn)椋?-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，總揀貨時(shí)間為442.09s。揀貨路徑示意圖如圖3和圖4所示。

圖3 GA算法路徑示意圖

圖4 GA算法揀貨路徑

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

當(dāng)采用遺傳模擬算法對(duì)30個(gè)貨物進(jìn)行有效揀選時(shí)，揀選的最優(yōu)路徑順序?yàn)椋?-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，總揀貨時(shí)間為439.75s。揀貨路徑示意圖如圖5和圖6所示。

圖5 GASA算法路徑示意圖

圖6 GASA算法揀貨路徑

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

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

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

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

表3 算法對(duì)比

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

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

5 結(jié)語(yǔ)

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