基于蟻群算法的分區揀貨法的改進與實例研究

孟慶巖，王晶晶

（1.煙臺黃金職業學院信息工程系，山東煙臺 265400；2.煙臺黃金職業學院機電工程系，山東煙臺 265400）

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

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

文中基于網上超市訂單揀貨的方法問題，研究了分區揀貨法的效率，并對分區揀貨法加以改進與評估。

1 評價模型的建立

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

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

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

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

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

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

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

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

由于工人的揀貨效率是不同的，且要求完成訂單的順序與發放訂單的順序完全一致，而揀貨區共有m個，這就造成了每個分區的揀貨效率是不同的，假設每個分區的工作效率βj為每個分區的揀貨效率，則。現假設一批訂單到達該網上超市，第一張訂單發放時刻為t0，設αij為第i張訂單在第j分區的數量，tij為第j分區完成第i張訂單的時刻距離t0的時間，故有：

下面來求每個分區的空閑時間，設每個分區的空閑時間為tj，由于第一分區每完成一張訂單就執行下一張訂單，故其空閑時間為：

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

綜上所述，各分區的空閑時間為上述每張訂單等待時間之和：

設ηj為第j分區的工作效率，η為總效率，則：

2 評價模型求解

令m=5,n=15，當每個分區的揀貨效率均衡時，對于隨機產生的五批訂單，每批訂單有100 張，求其總效率以及各分區的效率，并相互比較。通過LINGO 編程，得到如表1 所示分組。

表1 分區人員情況

此時，每個分區的擁擠度相同都為C(3)，得到結果如表2、表3 所示。

表2 擁擠度結果

表3 各分區的效率情況

在熟練度因子與擁擠度因子的作用下，發現分區揀貨法與單人揀貨法的完成時間有很大的差距，分區揀貨法的完成時間明顯低于單人揀貨法。

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

3 不均衡配置下的分區揀貨法

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

同樣取m=5,n=15，每個分區的工作人員都為3 人，建立比例分配模型。通過統計網上超市的訂單中各類商品的數量，得到各類商品的數量比例為wj，則當各個的揀貨效率按該比例分配時得到每個分區的實際揀貨效率為：

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

當vj已知時，也已知。

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

引入0，1 變量，

設Ej為實際的各分區最終效率，建立如下優化模型：

目標函數：

約束條件：

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

使用查找的實際商品數量比例數據，利用建立的按比例分配模型與均衡配置模型作對比可以得出，按比例分配模型的效率遠高于均衡配置模型，證明這種改進方法是值得提倡且具有實際應用價值[13]。

4 基于蟻群算法的分區揀貨模型

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

4.1 螞蟻揀貨法及其假設

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

該文在以下假設下計算螞蟻揀貨法的時間：

假設一：工人在貨架上走動的時間可以忽略。

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

假設三：訂單交接的時間忽略不計。

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

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

4.2 螞蟻揀貨法的完成時間

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

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

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

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

以此類推，執行n張訂單的時間為

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

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

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

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

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

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

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

在Case2.1 中，在ti+j-1時間內，工人j會追上工人j+1，由假設四，工人j不能繼續往下揀貨，只能跟在工人j+1 的后面，當工人j+1 在貨架gdowni-1,j+1完成訂單i-1 時，工人j再把訂單i給工人j+1，故有gupi,j+1=gdowni-1,j+1,ai,j+1=0。

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

綜上所述，可以得到：

4.3 螞蟻揀貨法的空閑時間

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

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

對于訂單i(1

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

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

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

由此可以計算每個人的總空閑時間：

4.4 模型的求解

4.4.1 螞蟻揀貨的算法實現及流程

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

圖1 算法流程圖

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

4.4.2 螞蟻揀貨法的結果

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

表4 螞蟻揀貨法的完成時間及空閑

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

5 結果分析

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

圖2 不同數目訂單完成時間

6 結論

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