基于蟻群算法的分區(qū)揀貨法的改進(jìn)與實(shí)例研究

孟慶巖，王晶晶

（1.煙臺(tái)黃金職業(yè)學(xué)院信息工程系，山東煙臺(tái) 265400；2.煙臺(tái)黃金職業(yè)學(xué)院機(jī)電工程系，山東煙臺(tái) 265400）

互聯(lián)網(wǎng)給電子商務(wù)帶來了巨大的發(fā)展機(jī)遇，如何能在眾多的電商中脫穎而出，除了產(chǎn)品的物美價(jià)廉外，還有非常重要的一個(gè)方面就是貨物的高效送達(dá)，這就涉及到倉庫的揀貨與物流[1]。對于大多數(shù)的個(gè)體電商而言，貨物運(yùn)輸選擇高效的物流公司即可，而在倉庫的揀貨方面，則存在著很大的改善空間[2]。

傳統(tǒng)的倉庫的揀貨方式分為兩種，分別為單人揀貨法與分區(qū)揀貨法。所謂單人揀貨法，即一張訂單上所有商品的分揀都由一名揀貨員完成，不管商品的種類及數(shù)量，這個(gè)揀貨員可能需要經(jīng)過整個(gè)揀貨區(qū)進(jìn)行揀貨[3]。而分區(qū)揀貨法[4]，則是先把揀貨工人分成與商品區(qū)數(shù)量相同的小組，各區(qū)的揀貨員只負(fù)責(zé)分揀訂單上該區(qū)的貨物，當(dāng)完成該區(qū)所有貨物的分揀后，就把訂單交到下個(gè)區(qū)的交接點(diǎn)。以此類推，訂單依次經(jīng)過所有商品區(qū)，最終完成分揀[5]。

文中基于網(wǎng)上超市訂單揀貨的方法問題，研究了分區(qū)揀貨法的效率，并對分區(qū)揀貨法加以改進(jìn)與評估。

1 評價(jià)模型的建立

網(wǎng)上超市的分區(qū)揀貨問題是一個(gè)實(shí)際問題，假設(shè)揀貨區(qū)一共有m個(gè)分區(qū)，要求完成訂單的順序與發(fā)放訂單的順序完全一致，則在真實(shí)的工作環(huán)境中肯定會(huì)出現(xiàn)每張訂單上所包括各類商品的比例不一樣，而造成不同分區(qū)的工作量分配變化很大，從而造成工人的工作時(shí)間不同[6]。衡量一種揀貨方法效率是否達(dá)到預(yù)期，標(biāo)準(zhǔn)是在某種工人配置下，其空閑時(shí)間占實(shí)際完成時(shí)間的比率，而比較不同揀貨方法時(shí)，還要考慮不同方法完成相同訂單所需的實(shí)際工作時(shí)間[7]。因此，通過橫向與縱向兩個(gè)方面對分區(qū)揀貨法的效率進(jìn)行了評價(jià)，而當(dāng)引入工人人數(shù)的多少造成的擁擠度因子、工作的熟練度因子這兩個(gè)因子時(shí)，模型得到了優(yōu)化。

設(shè)在一定區(qū)域的擁擠度因子為C(N)，工人熟悉自己所在分區(qū)貨架的熟悉度因子為S(d)，擁擠度與熟悉度影響的都是工人的單位時(shí)間工作量即工作效率，這里假設(shè)n名工人的最高工作效率為γk(k=1,2,…,n)，則實(shí)際工作效率為：

其中d為訂單數(shù)。在一定分區(qū)內(nèi)，工人一起進(jìn)行工作，彼此之間肯定會(huì)產(chǎn)生影響，由于分區(qū)場地大小的限制，該分區(qū)內(nèi)工人的人數(shù)越多，影響的程度就越大，揀貨效率就會(huì)越低，即擁擠度因子的大小隨著人數(shù)的增多而減小[8]，因此得到不同分區(qū)的揀貨效率為：

其中j為分區(qū)的數(shù)量，在本問題中的分區(qū)揀貨法的分區(qū)數(shù)為j=m，而單人揀貨法中j=1。

通過分析可知，熟練度因子S(d)隨著時(shí)間的增長而增大，且增長率是先變大后變小，最終趨于1[9]，這與種群增長的S 型曲線異曲同工，因此使用S 型曲線的表達(dá)式來表示熟練度因子為：

其中C1、C2是與d、k相關(guān)的常數(shù)，通過Matlab仿真實(shí)驗(yàn)，發(fā)現(xiàn)k=2 時(shí)，所得到的圖像較為符合本題要求，令S(2 000)=1，即工作2 000 張訂單后，工人的熟練度因子為1，因此得到熟練度因子的表達(dá)式為：

同理，擁擠度因子是隨著時(shí)間的減小，其增長速度呈遞減趨勢，這與柯西分布隸屬度函數(shù)較為相似，因此使用柯西分布隸屬度函數(shù)來表達(dá)擁擠度：

通過Matlab 仿真實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)k=0.8 時(shí)所得到的圖像較為符合要求，我們令C(n)=0.5，即工人數(shù)為15 時(shí)，擁擠度為0.5，得到擁擠度因子的表達(dá)式為：

由于工人的揀貨效率是不同的，且要求完成訂單的順序與發(fā)放訂單的順序完全一致，而揀貨區(qū)共有m個(gè)，這就造成了每個(gè)分區(qū)的揀貨效率是不同的，假設(shè)每個(gè)分區(qū)的工作效率βj為每個(gè)分區(qū)的揀貨效率，則?，F(xiàn)假設(shè)一批訂單到達(dá)該網(wǎng)上超市，第一張訂單發(fā)放時(shí)刻為t0，設(shè)αij為第i張訂單在第j分區(qū)的數(shù)量，tij為第j分區(qū)完成第i張訂單的時(shí)刻距離t0的時(shí)間，故有：

下面來求每個(gè)分區(qū)的空閑時(shí)間，設(shè)每個(gè)分區(qū)的空閑時(shí)間為tj，由于第一分區(qū)每完成一張訂單就執(zhí)行下一張訂單，故其空閑時(shí)間為：

而對于第j分區(qū)，當(dāng)i=1 時(shí)，分別要等待t1,j-1，當(dāng)i>1，若第i-1 張訂單已完成而第i張訂單還沒到，則需等待ti,j-1-ti-1,j，反之則不需等待[10]。

綜上所述，各分區(qū)的空閑時(shí)間為上述每張訂單等待時(shí)間之和：

設(shè)ηj為第j分區(qū)的工作效率，η為總效率，則：

2 評價(jià)模型求解

令m=5,n=15，當(dāng)每個(gè)分區(qū)的揀貨效率均衡時(shí)，對于隨機(jī)產(chǎn)生的五批訂單，每批訂單有100 張，求其總效率以及各分區(qū)的效率，并相互比較。通過LINGO 編程，得到如表1 所示分組。

表1 分區(qū)人員情況

此時(shí)，每個(gè)分區(qū)的擁擠度相同都為C(3)，得到結(jié)果如表2、表3 所示。

表2 擁擠度結(jié)果

表3 各分區(qū)的效率情況

在熟練度因子與擁擠度因子的作用下，發(fā)現(xiàn)分區(qū)揀貨法與單人揀貨法的完成時(shí)間有很大的差距，分區(qū)揀貨法的完成時(shí)間明顯低于單人揀貨法。

在單人揀貨法中，每個(gè)人的空閑時(shí)間少，但是完成時(shí)間卻較長，這是由于單人揀貨法每個(gè)人要熟悉50 個(gè)貨架所有的擺放位置，而且15 個(gè)人同時(shí)在揀貨通道里進(jìn)行工作，給揀貨造成了一定的影響。而分區(qū)揀貨法通過分區(qū)使得揀貨通道的各段都得到利用，同時(shí)每個(gè)人只需熟悉10 個(gè)貨架，提高了揀貨效率，因此分區(qū)揀貨法的揀貨效率要明顯高于單人揀貨法，但由于其均衡配置使得分區(qū)揀貨法也存在著很高的改進(jìn)空間[11]。

3 不均衡配置下的分區(qū)揀貨法

實(shí)際生活中，各類商品的需求是不一致的，為了使模型更加貼近實(shí)際，具有可操作性，選取5 個(gè)分區(qū)：食品區(qū)、飲料區(qū)、日用品區(qū)、電器區(qū)與禮品區(qū)。通過查找資料，得到5 類商品的生活實(shí)際購買需求占比分別為：食品區(qū)占22.99%；飲料區(qū)占5.75%；日用品區(qū)占43.10%；電器區(qū)占17.53%；禮品區(qū)占10.63%[12]。

同樣取m=5,n=15，每個(gè)分區(qū)的工作人員都為3 人，建立比例分配模型。通過統(tǒng)計(jì)網(wǎng)上超市的訂單中各類商品的數(shù)量，得到各類商品的數(shù)量比例為wj，則當(dāng)各個(gè)的揀貨效率按該比例分配時(shí)得到每個(gè)分區(qū)的實(shí)際揀貨效率為：

其中，S(d)與訂單的數(shù)量有關(guān)，而在按訂單比例分配揀貨效率的時(shí)候，S(d)也是按訂單比例增長的，所以S(d) 對開始進(jìn)行的人員分配不影響。Cj(N)=S(3)，每個(gè)工人的理想揀貨效率為從而實(shí)際揀貨效率為：

當(dāng)vj已知時(shí)，也已知。

在每個(gè)分區(qū)限制3人，每名工人的揀貨效率為1-15，共5個(gè)分區(qū)的約束條件下，建立優(yōu)化模型如下：

引入0，1 變量，

設(shè)Ej為實(shí)際的各分區(qū)最終效率，建立如下優(yōu)化模型：

目標(biāo)函數(shù)：

約束條件：

利用之前的評價(jià)模型可得到的效率為η1。

使用查找的實(shí)際商品數(shù)量比例數(shù)據(jù)，利用建立的按比例分配模型與均衡配置模型作對比可以得出，按比例分配模型的效率遠(yuǎn)高于均衡配置模型，證明這種改進(jìn)方法是值得提倡且具有實(shí)際應(yīng)用價(jià)值[13]。

4 基于蟻群算法的分區(qū)揀貨模型

分區(qū)揀貨法使得揀貨員限制在相對封閉區(qū)域工作，在此揀貨系統(tǒng)中的揀貨員會(huì)越發(fā)熟悉自己負(fù)責(zé)區(qū)域里的產(chǎn)品，這樣不僅可以提高揀貨效率，也提高了作業(yè)準(zhǔn)確性。然而，在實(shí)際中，由于各分區(qū)工作量難以達(dá)到均衡，經(jīng)常出現(xiàn)當(dāng)某一分區(qū)揀貨員回到上一個(gè)交接點(diǎn)時(shí)，由于前一分區(qū)還沒有已完成訂單，但又不能越過交接點(diǎn)去幫忙，只能無奈的等待[14]。這給人員和設(shè)備的利用率造成很大的浪費(fèi)，也導(dǎo)致傳統(tǒng)網(wǎng)上超市分區(qū)揀貨中各分區(qū)的空閑度差異較大，整體效率不高。為此，我們放松區(qū)域限制，采用螞蟻揀貨法對分區(qū)揀貨法進(jìn)行改進(jìn)。

4.1 螞蟻揀貨法及其假設(shè)

在螞蟻揀貨法中，15 名工人在揀貨流水線上來回作業(yè)。按照工人所在流水線位置由上游到下游的順序，分別把工人編號(hào)為：1、2、……15。他們的揀貨效率分別為γj，按照貨架所在流水線位置由上游到下游的，分別把貨架編號(hào)為：1、2、……50。n(n>1) 張訂單每種貨物揀貨量矩陣A=(Aij)n×50。

該文在以下假設(shè)下計(jì)算螞蟻揀貨法的時(shí)間：

假設(shè)一：工人在貨架上走動(dòng)的時(shí)間可以忽略。

假設(shè)二：工人j與工人j+1 在貨架k交接時(shí)，無論工人在本貨架的揀貨作業(yè)是否完成，都立刻把訂單交給下一工人，若貨架k的揀貨作業(yè)未完成，則由工人j+1 完成。

假設(shè)三：訂單交接的時(shí)間忽略不計(jì)。

假設(shè)四：在揀貨過程中工人j在流水線上的位置不可能超過j+1，最多兩者在同一貨架。

注：工人j手中訂單需要揀的貨物較少時(shí)，趕上了下游正在揀貨的j+1 工人，俗稱“追尾”。此時(shí)不能超越j(luò)+1 工人，直到j(luò)+1 工人掉頭才能將訂單及揀貨筐轉(zhuǎn)交給j+1 工人。

4.2 螞蟻揀貨法的完成時(shí)間

首先要安排15 名工人在流水線上的初始位置，顯然工人1 從辦公室拿到訂單從貨架1 開始揀貨，其初始位置即為貨架1。而其他工人的初始位置則依次安排在貨架5、8、11、15、18、21、25、28、31、35、38、41、45、48。

對于訂單1，由假設(shè)一和三可知，工人1 從開始執(zhí)行訂單1 到把訂單交給工人2 所花的時(shí)間僅僅用在揀貨上，即工人1 執(zhí)行訂單1 的時(shí)間t1，則執(zhí)行訂單1 共用時(shí)：

對于訂單2，由于工人1 把訂單1 交給工人2 后馬上返回辦公室拿訂單2，并且根據(jù)假設(shè)一，可以認(rèn)為工人2 執(zhí)行訂單1 與工人1 執(zhí)行訂單2 是同時(shí)開始的。而t2時(shí)間后，工人2 將訂單1 交給工人3，馬上返回從工人1 接過訂單2，再由假設(shè)一，可認(rèn)為工人1執(zhí)行訂單2 的時(shí)間也是t2。同理可知：工人j(2 ≤j≤14)執(zhí)行訂單2 的時(shí)間分別為：t3,t4,…,t15，而工人15 執(zhí)行訂單2 的時(shí)間則單獨(dú)記為：t16。則執(zhí)行訂單2 一共用時(shí)：

考慮到訂單2 是在訂單1 執(zhí)行t1時(shí)間后與訂單1同時(shí)執(zhí)行，故執(zhí)行者兩張訂單的時(shí)間T總2應(yīng)該為T1與T2之和減去重疊的時(shí)間，即：

以此類推，執(zhí)行n張訂單的時(shí)間為

設(shè)a=(aij)n×15表示在執(zhí)行訂單i工人j與工人j-1 交接時(shí)，工人j-1 在交接貨架上未完成的揀貨量，對于j=1，則默認(rèn)ai1=0,i=2,3,…,n，對于訂單1，認(rèn)為a1j=0,j=1,2,…,15。

gup=(gupij)n×15表示在執(zhí)行訂單i時(shí)，工人j與上游交接時(shí)所在的貨架編號(hào)，其中，認(rèn)為gup1,2=4,gup1,3=7,…,gup1,15=47，gupi1=0,i=1,2,...,n。

gdown=(gdownij)n×15表示在執(zhí)行訂單i時(shí)，工人j與下游交接時(shí)所在的貨架編號(hào)，其中認(rèn)為gdown11=4,gdown12=7,gdown13=10,...,gdown1,14=47，gdowni,15=50,i=1,2,…,n。顯 然 有g(shù)downij=gupi,j+1,i=1,2,…,n,j=1,2,…,14。

下面討論如何求t16,t17,…,tn+14：

考慮執(zhí)行訂單i過程中工人j和j+1 的交接情景，由假設(shè)四可知，只有兩種可能：

Case1 說明工人j從工人j-1 手中接過訂單i時(shí)所在貨架與工人j+1 將訂單i-1 交給工人j+2時(shí)所在貨架是同一貨架，此時(shí)工人j立刻把訂單給工人j+1，則有：

而在Case2 中，則需要考慮在工人j執(zhí)行訂單i的時(shí)間ti+j-1內(nèi)是否會(huì)追上工人j+1，此時(shí)亦有兩種可能，即：

在Case2.1 中，在ti+j-1時(shí)間內(nèi)，工人j會(huì)追上工人j+1，由假設(shè)四，工人j不能繼續(xù)往下揀貨，只能跟在工人j+1 的后面，當(dāng)工人j+1 在貨架gdowni-1,j+1完成訂單i-1 時(shí)，工人j再把訂單i給工人j+1，故有g(shù)upi,j+1=gdowni-1,j+1,ai,j+1=0。

在Case2.2 中，在ti+j-1時(shí)間內(nèi)，工人j追不上工人j+1，他們會(huì)在貨架k交接（貨架k在貨架gupij與gdowni-1,j+1之間，k的求法將在圖1 中給出），故有：

綜上所述，可以得到：

4.3 螞蟻揀貨法的空閑時(shí)間

記rest(restij)n×15為工人的空閑時(shí)間矩陣，其中restij表示在訂單i中，工人j的空閑時(shí)間[15]。

對于訂單1，顯然工人1 的空閑時(shí)間為0，即rest11=0。而工人j(j>1)的空閑時(shí)間產(chǎn)生即為工人1開始執(zhí)行訂單1 的時(shí)刻開始，到工人j從工人j-1手上接過訂單的這段時(shí)間，故：

對于訂單i(1

在Case1 中，空閑時(shí)間為工人j+1 完成訂單i-1的時(shí)間，故restij=ti+j-1。

在Case2.1 中，在工人j(j<15) 執(zhí)行訂單i的時(shí)間里，本應(yīng)完成揀貨量δj×ti+j-1，卻因不能超過工人j+1 而只能在完成揀貨量之后進(jìn)入空閑狀態(tài)，等待工人j+1 完成訂單i-1，故：

對于訂單n，工人j的空閑時(shí)間除了在HOTO(i,j)過程中產(chǎn)生外，還產(chǎn)生在交出訂單n后等待后面的工人把訂單n完成的時(shí)間段，前者記為ttj，后者記為tt′j。ttj的計(jì)算方法前面已給出，而，故：

由此可以計(jì)算每個(gè)人的總空閑時(shí)間：

4.4 模型的求解

4.4.1 螞蟻揀貨的算法實(shí)現(xiàn)及流程

在4.3 中已解決執(zhí)行訂單i過程中工人j與j+1交接的問題，稱解決該問題的上述過程為HOTO(i,j)過程[16-17]，其中i表示訂單號(hào)，j表示工人j和工人j+1 交接，該算法流程如圖1 所示。

圖1 算法流程圖

有了HOTO(i,j)過程，就可以求t16,t17,…,tn+14，從而可以計(jì)算得到與總空閑時(shí)間

4.4.2 螞蟻揀貨法的結(jié)果

通過以上的螞蟻揀貨算法，我們采用不均衡配置模型中按比例生成的訂單，得到在該模型的基礎(chǔ)上的完成時(shí)間及平均空閑時(shí)間，如表4 所示。

表4 螞蟻揀貨法的完成時(shí)間及空閑

從表4 發(fā)現(xiàn)螞蟻揀貨法的空閑度相對比較大，這是由于在該揀貨法中，第一名工人在進(jìn)行第一張訂單的揀貨時(shí)，其他14 名工人都處于空閑狀態(tài)，這就造成了相當(dāng)大的空閑時(shí)間，均衡配置下的分區(qū)揀貨法完成時(shí)間最長，其次為按比例分配的分區(qū)揀貨法，最后為螞蟻揀貨法，這說明我們利用螞蟻揀貨法比分區(qū)揀貨法的效率高，完成時(shí)間短，這是一種較好的揀貨法。

5 結(jié)果分析

螞蟻揀貨法可以充分利用每個(gè)工人的揀貨效率，比按比例分配法的效率明顯提高，使用這種方法可以不需要頻繁調(diào)動(dòng)工人工作分區(qū)，提高揀貨效率。圖2中增加了訂單數(shù)，使得5批訂單每批訂單都有200張。從圖中可以看出，隨著訂單數(shù)的增加，螞蟻揀貨法的效率也會(huì)增長，到達(dá)收斂值時(shí)增長比較緩慢，但是利用螞蟻揀貨法完成同樣數(shù)目的訂單時(shí)間明顯會(huì)越來越短。

圖2 不同數(shù)目訂單完成時(shí)間

6 結(jié)論

采用螞蟻揀貨法過程中，優(yōu)化了揀貨員的排序，但是依然不可避免地出現(xiàn)部分“追尾”現(xiàn)象，如果在訂單期限允許范圍內(nèi)能對訂單的順序做進(jìn)一步優(yōu)化排序，進(jìn)一步減少“追尾”，則所得的結(jié)果會(huì)更理想，這是該模型的不足之處。最后，揀貨問題是物流業(yè)中的重要研究課題，建立的模型能更好地接近實(shí)際問題，實(shí)用性就越強(qiáng)。在該問題給出的條件中，忽略了工人在各貨架或分區(qū)間走動(dòng)的距離，簡化了問題。如果將工人行走距離、工人和設(shè)備的成本、訂單期限、作業(yè)準(zhǔn)確率和顧客滿意度等考慮進(jìn)去，建立基于成本分析的優(yōu)化模型，會(huì)使模型更具實(shí)用性。