基于揀貨單排序的貨物動態(tài)協(xié)同與路徑聯(lián)合優(yōu)化研究

孫軍艷， 閆春妍， 陳智瑞， 牛亞儒

(陜西科技大學 機電工程學院， 陜西 西安 710021)

揀選作業(yè)作為配送中心的核心工序之一，其效率水平直接影響著配送中心的效率和水平。影響揀貨作業(yè)效率的主要有揀選路徑、儲位分配、訂單分批、揀選單排序等因素，國內外學者分別在這方面做了大量的研究。

在揀貨路徑優(yōu)化方面，國內外學者大多采用智能算法如遺傳算法、混合蟻群算法、禁忌搜索算法等對揀貨路徑和時間進行優(yōu)化，以最大限度地減少揀選行程距離和時間，從而提高倉庫運營效率。閆軍等[1]對貨物揀取路徑順序進行優(yōu)化，以最短揀貨路徑為目標，建立了TSP模型優(yōu)化揀貨路徑，將GASA算法和GA算法進行比較，結果表明GASA算法優(yōu)于GA算法，揀貨路徑比之前節(jié)約了0.6% 。Zhou等[2]針對V型倉儲布局，建立了返回型隨機揀選路徑模型，利用大數(shù)據(jù)技術進行仿真，驗證了返回型揀貨路徑策略優(yōu)于S型，提高了揀貨效率。張水旺等[3]針對多區(qū)型倉庫，建立了揀貨路徑優(yōu)化模型，并采用人工魚群算法求解，驗證了算法的有效性。

科學的貨物存儲分配方法可以縮短步行距離，減少搜索時間，提高倉庫揀選效率。在貨物動態(tài)存儲策略方面，Hadi等[4]開發(fā)了一種動態(tài)存儲分配模型，動態(tài)確定貨物的適當存儲位置，從而提高了系統(tǒng)性能。Li等[5]基于貪婪遺傳算法，應用數(shù)據(jù)挖掘技術計算了產(chǎn)品間的關聯(lián)度，解決了動態(tài)貨物存儲位置分配問題，該算法計算效率較高，且顯著改善了揀選訂單的行程距離。Manzini等[6]建立了混合整數(shù)線性規(guī)劃模型，基于時間將存儲區(qū)域內的貨物動態(tài)分配給不同的儲位，該模型可優(yōu)化復雜的倉儲系統(tǒng)揀貨決策。

在訂單排序或者揀選單排序方面，葉楠等[7]通過分配揀貨單的順序，使各揀貨單的復核臺位置首尾相連，使用遺傳算法動態(tài)優(yōu)化揀貨路徑，該動態(tài)調整算法可為大規(guī)模、復雜倉庫提供更高效的揀貨路徑規(guī)劃。胡金昌等[8]通過建立0-1整數(shù)規(guī)劃模型來求解同時分揀多客戶訂單的訂單排序問題，提高了系統(tǒng)的揀選效率。夏德龍等[9]提出了一種適用于"貨到人"的訂單排序模型，并用改進k-means聚類算法求解了揀選臺內相鄰訂單和揀選臺之間訂單的共用貨架數(shù)量，以減少貨架的搬運次數(shù)。

顯然，揀選作業(yè)過程中，路徑規(guī)劃、存儲分配、訂單分批、揀貨單排序之間相輔相成、相互影響，各環(huán)節(jié)的獨立優(yōu)化很難做到全局的優(yōu)化。有學者進行了兩兩聯(lián)合優(yōu)化，比如Ardjmand等[10]針對基于揀選臺的分揀系統(tǒng)，研究訂單分批和路徑優(yōu)化問題，提出了一種基于列表的模擬退火算法(LBSA)和一種混合遺傳算法(GA-LBSA)。研究發(fā)現(xiàn)，對于較小規(guī)模的問題，LBSA在解決方案的質量方面是一個更好的選擇，而當考慮CPU時間時，根據(jù)問題的大小，GA-LBSA可能是更好的選擇。Kübler 等[11]建立了動態(tài)存儲位置分配和揀貨路徑聯(lián)合優(yōu)化模型，提出了一種迭代啟發(fā)式算法，結果表明，這種方法可以顯著節(jié)省行程距離。Cano等[12]對分批后的揀貨單進行排序并優(yōu)化揀貨路徑，建立了聯(lián)合揀選模型，同時最小化總行程和客戶訂單延誤，提高了訂單分揀流程的效率。Cai等[13]對存儲位置分配和路徑進行協(xié)同優(yōu)化，考慮了貨物位置分配和路徑規(guī)劃之間的關系，提出了一種貨架周轉的位置分配策略，通過模擬研究確定了該方法的有效性。

兩兩聯(lián)合優(yōu)化明顯提高了揀貨作業(yè)效率，但仍存在一定的局限。在揀貨流程中，訂單分批、揀貨單排序、貨物動態(tài)協(xié)同、揀貨路徑優(yōu)化等是一個系統(tǒng)工程，兩兩聯(lián)合優(yōu)化依然只是局部優(yōu)化，很難達到系統(tǒng)全局的優(yōu)化。

本文在訂單分批形成揀貨單的前提下，對揀貨系統(tǒng)中最重要的環(huán)節(jié)——揀貨單排序、貨物動態(tài)協(xié)同、揀貨路徑優(yōu)化三者進行聯(lián)合優(yōu)化，以求在系統(tǒng)層面實現(xiàn)全局最優(yōu)。具體研究思路為：將揀貨單排序的思想融入貨物動態(tài)協(xié)同與揀貨路徑優(yōu)化中，設計了一種揀貨單路徑優(yōu)化-貨物動態(tài)協(xié)同-揀貨單排序的多階段循環(huán)揀貨策略，利用揀貨單之間、最優(yōu)路徑之間的相似性，盡最大可能利用揀貨車的剩余容量，減少后續(xù)揀貨單的揀選距離，從整體上對揀貨作業(yè)進行優(yōu)化。

1 動態(tài)揀貨策略設計

對于揀選作業(yè)，通常情況下，在一個揀貨周期內，揀選系統(tǒng)會根據(jù)一定的規(guī)則和揀貨車的容量，將具有相似性的訂單形成揀選單，揀貨員根據(jù)揀貨單最優(yōu)路徑循環(huán)完成揀貨作業(yè)，以達到減少揀選員的行走路徑，提高揀貨效率的目的，我們將該策略稱為傳統(tǒng)揀貨策略。

為進一步提高揀貨效率，一種動態(tài)揀貨策略被提出[14]，其主要思想是利用相鄰揀貨單之間共同的揀選路徑，在揀選上一張揀貨單h的同時，提前將下一張揀貨單h+1上的某個貨品順路揀出，以最大可能地減少下一張揀貨單h+1的揀選路徑，以此類推，最終實現(xiàn)所有揀貨單總揀貨時間的縮減，提高揀貨效率。

本文將上述動態(tài)揀貨策略與揀貨單排序相結合，提出了對揀選作業(yè)進行“路徑優(yōu)化-貨物動態(tài)協(xié)同-揀貨單排序”的循環(huán)揀貨策略(簡稱“排序協(xié)同策略”)，該策略的核心思想是：首先對所有揀貨單進行路徑優(yōu)化，然后計算在揀選揀貨單h的貨物時能夠協(xié)同揀選的揀貨單h+1的貨物組合，要求使揀貨單h+1的最優(yōu)路徑減少最多，以此類推，得到兩兩揀貨單之間能夠使對方路徑減少最多的路徑節(jié)約矩陣；最后以路徑節(jié)約矩陣為基礎進行揀貨單排序，以“邊排序邊協(xié)同”的方式，達到縮短所有揀貨單揀選時間的目的。

具體流程見圖1，具體步驟如下。

圖1 基于揀貨單排序的貨物動態(tài)協(xié)同與路徑協(xié)同優(yōu)化流程圖Fig.1 Flow chart of dynamic cargo collaboration and path collaboration optimization based on picking orders sorting

Step1：初始條件設置

確定倉庫布局，在揀貨臺處設置一個位置，作為被協(xié)同貨物的臨時存放處。明確貨位信息、揀貨車容量、貨位之間、貨位與揀貨臺之間的距離等信息。

Step2：揀貨單最優(yōu)路徑模型的建立

建立以揀貨時間最短為目標的數(shù)學模型，設計啟發(fā)式算法，求解各揀貨單的最優(yōu)路徑。

Step3：建立揀貨單列表，求解各揀貨單的最優(yōu)路徑集合

根據(jù)一個周期內揀貨單h(h=1,2,…,M)的數(shù)量M，建立揀貨單列表H={揀貨單1,揀貨單2, …,揀貨單M}，基于Step1中的模型和算法，循環(huán)求解各揀貨單h的最優(yōu)路徑。

Step4：建立動態(tài)協(xié)同貨物組合最優(yōu)模型

對于揀貨單h和揀貨單g，在滿足揀貨車容量的前提下，根據(jù)共同路徑，在揀取揀貨單h的同時，協(xié)同(捎取)揀貨單g的某些貨物，以使揀貨單g的最優(yōu)路徑減少最多，得到揀貨單h協(xié)同揀貨單g的最優(yōu)貨物組合，以此類推，建立最優(yōu)協(xié)同貨物矩陣。

Step5：建立揀貨單循環(huán)排序模型

根據(jù)最優(yōu)協(xié)同貨物矩陣，計算當各揀貨單去掉被協(xié)同貨物時，最優(yōu)路徑的減少值，建立最優(yōu)路徑節(jié)約矩陣。

Step5.1：當前沒有排序優(yōu)先的揀貨單。從最優(yōu)路徑節(jié)約矩陣中找出節(jié)約值最大的一對揀貨單，將協(xié)同揀貨單作為排序優(yōu)先的揀貨單，被協(xié)同揀貨單作為下一個揀貨單。

Step5.2：當前有排序優(yōu)先的揀貨單。將當前排序優(yōu)先的揀貨單作為協(xié)同揀貨單，在最優(yōu)路徑節(jié)約矩陣中，定位當前排序優(yōu)先揀貨單所在的行，找出最大值，將其對應的揀貨單作為被協(xié)同揀貨單，被協(xié)同揀貨單作為下一個揀貨單。

Step6：對排序優(yōu)先的揀貨單和被協(xié)同貨物組合進行協(xié)同揀選

對排序優(yōu)先的揀貨單根據(jù)最優(yōu)路徑進行揀選，同時對共同路徑上的下一張揀貨單的最優(yōu)貨物組合進行協(xié)同揀貨，將其捎取到揀選臺被調整處。

Step7：更新被協(xié)同揀貨單的揀貨任務

更新揀貨單列表H。將排序優(yōu)先的揀貨單從中刪除，更新被協(xié)同揀貨單的揀貨任務，并將其更新為排序優(yōu)先的揀貨單。

如果排序優(yōu)先的揀貨單有揀選任務：更新被協(xié)同揀貨單的最優(yōu)路徑。更新最優(yōu)協(xié)同貨物矩陣，刪除排序優(yōu)先的揀貨單所在的行與列，根據(jù)更新后的揀貨單列表，更新被協(xié)同揀貨單所在的行。更新最優(yōu)路徑節(jié)約矩陣，刪除排序優(yōu)先的揀貨單所在的行與列，根據(jù)更新后的最優(yōu)協(xié)同貨物矩陣，更新被協(xié)同揀貨單所在的行。將被協(xié)同揀貨單更新為排序優(yōu)先的揀貨單。進入step8.1。

如果排序優(yōu)先的揀貨單沒有需要揀選的貨物，則將其從揀貨單列表H中刪除，更新揀貨單列表。更新最優(yōu)協(xié)同貨物矩陣，刪除其所在的行與列。更新最優(yōu)路徑節(jié)約矩陣，刪除其所在的行與列。進入step8.2。

Step8：判斷揀貨單列表中是否有揀貨單

Step8.1:根據(jù)揀貨單列表H，判斷排序優(yōu)先的揀貨單是否是最后一個揀貨單，如果否，進入step5.2；如果是，根據(jù)最優(yōu)揀貨路徑完成該揀貨單的揀貨任務，結束。

Step8.2：根據(jù)揀貨單列表H，判斷揀貨單列表H中揀貨單的數(shù)量。如果有2個及2個以上的揀貨單，進入step5.1；如果有1個揀貨單，根據(jù)最優(yōu)揀貨路徑完成該揀貨單的揀貨任務，結束；如果沒有揀貨單，結束。

2 數(shù)學模型的建立

2.1 基本假設

1) 采用摘果式“人到貨”的揀貨方式進行揀選；

2) 揀貨員可以沿縱向和橫向的通道雙向行走；

3) 每個貨位存儲一種貨物，即貨位和品項一一對應；

4) 貨位足夠大，揀貨過程中不存在貨位缺貨現(xiàn)象；

5) 訂單中貨物、各貨位的數(shù)量及其存儲位置已知；

6) 訂單分批形成揀貨單，訂單分批時不允許進行分割，保證一個訂單一次揀完，每張揀貨單的大小不超過揀貨車的最大容量；

7) 揀貨員一個循環(huán)完成一個揀貨單的揀選，一個工作周期內完成多個揀貨單的揀選任務；

8) 每張揀貨單在揀選過程中可以協(xié)同下一個揀貨單的多個貨物；

9) 在揀貨臺設置一個臨時存放處，用于暫存下一個揀貨單的被調整貨物。

2.2 參數(shù)設置

基本參數(shù)與符號定義如表1所示。

表1 基本參數(shù)和符號的定義Tab.1 Definition of basic parameters and symbols

變量定義如下：

2.3 模型的構建

由圖1可以看出，本文提出的排序協(xié)同策略涉及三個數(shù)學模型：揀貨單最優(yōu)路徑數(shù)學模型、貨物動態(tài)協(xié)同選擇的數(shù)學模型、揀貨單循環(huán)排序模型。

三個模型中，以模型3為中心，在運行模型3時，首先需要調用模型1，計算各揀貨單最優(yōu)路徑，建立揀貨單列表；接著調用模型2，計算最優(yōu)的貨物動態(tài)協(xié)同矩陣，得到最優(yōu)的路徑節(jié)約矩陣；以此為基礎，運行模型3得到排序優(yōu)先的揀貨單和被協(xié)同揀貨單，揀選完成后更新揀貨單列表。以此類推，模型3重復調用模型1和模型2，直到所有的揀貨單被排序。

2.3.1模型1：揀貨單最優(yōu)路徑數(shù)學模型

對于揀貨單h，以揀貨單最短路徑為目標建立數(shù)學模型。

目標函數(shù)為：

(1)

約束條件：

1)

(2)

2) 揀貨單h中每個貨物的貨位都要被訪問1次：

(3)

(4)

3) 揀貨單h的體積小于揀貨車容量Q：

(5)

4) 揀貨單h所包含的貨位的數(shù)量不能大于貨位的總數(shù)量：

(6)

決策變量：

(7)

2.3.2模型2：貨物動態(tài)協(xié)同選擇最優(yōu)模型

揀貨單h協(xié)同揀貨單g時，以剩余揀貨單g最優(yōu)路徑減少最多為目標，建立揀貨單h的最優(yōu)協(xié)同貨物選擇模型。

目標函數(shù)為：

(8)

(9)

(10)

約束條件為：

1)

(11)

2) 揀貨單g中每個貨物對應的貨位都要被訪問1次：

(12)

(13)

3) 揀貨單g的體積小于揀貨車容量Q：

(14)

4) 揀貨單g所包含的貨位的數(shù)量不能大于貨位的總數(shù)量：

(15)

5)

(16)

6) 揀貨單g中，被協(xié)同的貨物與剩余的貨物之和等于揀貨單g上所有的貨物：

(17)

7) 去除協(xié)同貨物后，揀貨單g剩余貨物的貨位都要被訪問1次：

(18)

(19)

8) 被協(xié)同貨物不能超過揀貨車剩余容積：

(20)

9) 協(xié)同貨物數(shù)量不能超過共同路徑上的貨物數(shù)量：

(21)

決策變量：

2.3.3模型3：揀貨單循環(huán)排序模型

(22)

其次，基于最優(yōu)路徑節(jié)約矩陣ΔS，得到最優(yōu)協(xié)同貨物矩陣：

(23)

(24)

1) 模型3.1：當前沒有排序優(yōu)先的揀貨單

以最優(yōu)路徑減少最多為目標，在最優(yōu)路徑節(jié)約矩陣中，尋找排序優(yōu)先揀貨單和被協(xié)同揀貨單，目標函數(shù)為：

(25)

其對應的h即為排序優(yōu)先揀貨單，g為被協(xié)同揀貨單。

2) 模型3.2：當前有排序優(yōu)先的揀貨單h

以最優(yōu)路徑減少最多為目標，在最優(yōu)路徑節(jié)約矩陣中，在第h行中尋找被協(xié)同揀貨單g，目標函數(shù)為：

(26)

2.3.4所有揀貨單的總作業(yè)時間

在揀貨單排序的協(xié)同優(yōu)化策略下，對于排序為k的揀貨單，除了需要根據(jù)前一個揀貨單k-1已經(jīng)捎取的貨物，更新排序為k的揀貨單的揀貨任務；另一方面，需要采用循環(huán)判斷找出可使下一個揀貨單k+1揀貨距離減少最多的貨物組合，對其進行動態(tài)調整。若排序為k的揀貨單為揀貨單h，則排序為k的揀貨單的揀選時間包括三部分：更新后的行走時間、更新后的作業(yè)時間、協(xié)同貨物時間。優(yōu)化后，1個周期內所有揀貨單總的揀貨時間TC為：

(27)

(28)

其中：

每個排序位置只能有一張揀貨單。

3 算法設計與算例分析

3.1 算法設計

根據(jù)協(xié)同揀貨策略和數(shù)學模型可知，該問題屬于三階段循環(huán)NP-hard決策問題。由于各階段決策密不可分，環(huán)環(huán)相扣，循環(huán)更新，具有連貫性、協(xié)同性、多約束等特點，除了算法的可靠性以外，算法的效率至關重要。本文算法的設計思想是在確保解合理性的前提下，盡量提高各階段算法的運算效率。

1) 模型1，采用混合遺傳模擬退火(GASA)算法對揀貨單路徑進行優(yōu)化。GASA算法將模擬退火算法(SA)較強的局部搜索能力與遺傳算法融合，解決了群體的多樣性和收斂速度的矛盾，可避免算法陷入局部最優(yōu)，同時提升了算法的收斂速度。具體步驟如下。

Step1：編碼設計。對揀貨單的揀貨位編號采用自然數(shù)編碼。例如，對于有6個揀貨位的揀貨單，該揀貨單的編碼串(即染色體C1)為[2，15，22，13，53，7]，其中基因值為需揀取的揀貨位編號，基因位對應揀貨位的排序，此編碼串表示該揀貨單的揀貨順序為2-15-22-13-53-7。隨機生成初始種群。

Step2：適應度函數(shù)。適應度函數(shù)f1為揀貨單最優(yōu)路徑Sh的倒數(shù)。計算種群中所有個體的適應度值：

Step3：遺傳操作。由于本文在設計交叉和變異算子時，新解只能在可行區(qū)域內產(chǎn)生，所以遺傳交叉過程中只會產(chǎn)生可行解。

a) 選擇算子，采用線性排序選擇。通過排序給每個個體安排相應的選中概率。種群中的個體首先根據(jù)適應度值進行排序，然后給所有個體賦予一個序號，最好的個體序號為N，被選中的概率為Pmax，最差的個體序號為 1，被選中的概率為Pmin，設Pi為第i個個體被選中的概率，則

b) 順序交叉算子，交叉概率為Pc。如圖2所示，在兩個父代中隨機選擇起始和結束位置，將父代1中選中的基因復制到子代1相同的位置，在父代2中將其缺少的基因按順序填入，另一個子代以相同的方式得到。

圖2 交叉操作示意圖Fig.2 Cross operation diagram

c) 變異算子，變異概率為Pm。隨機選擇一個插入位和一個基因位，把染色體中的基因位移到插入位，將其之后的基因順移。例如，插入位是第3位，基因位是第6位，則變異后的染色體如圖3所示。

圖3 變異操作示意圖Fig.3 Mutation operation diagram

Step4：模擬退火操作。

a) 模擬退火初始化。初始化模擬退火參數(shù)，包括初始溫度T0、降溫速率θ和溫度下迭代次數(shù)L，并以遺傳操作產(chǎn)生的子代作為初始解。對當前解Cj作隨機擾動，過程如圖4所示，隨機選擇兩個揀貨位然后交換它們的位置，產(chǎn)生一個新解Cj′。計算新解的適應度值f(Cj′)。

圖4 產(chǎn)生新解的過程示意圖Fig.4 Diagram of the process for generating a new solution

b) 降溫函數(shù)。在未滿足終止退火條件，同時已達到溫度下迭代次數(shù)時，進行降溫操作，迭代n+1次時的溫度為Tn+1=θ×Tn。

c) Metropolis準則。遵循Metropolis準則給出的以一定概率接受新狀態(tài)，計算適應度函數(shù)值增量Δf，令Δf=f(Cj)-f(C′j)，若Δf≤0，則接受該新解為當前解；否則，若exp(-Δf/T)大于[0,1]之間的隨機數(shù)，則接收當前解為新解。

Step5：判斷是否達到最大迭代次數(shù)，如果是，則輸出最優(yōu)路徑結果，否則返回Step3。

2) 模型2，動態(tài)協(xié)同貨物選擇的最優(yōu)。由于最優(yōu)協(xié)同貨物模型是一個多約束的嵌套組合問題，它是以協(xié)同貨物組合的可行解為基礎，循環(huán)調用模型1，根據(jù)揀貨單最優(yōu)路徑的節(jié)約值的變化，不斷的在協(xié)同貨物組合的可行解中尋優(yōu)。本文提出一種嵌套GASA算法，外層采用遺傳算法對揀貨單協(xié)同貨物組合進行優(yōu)化，內層采用GASA算法對揀貨單路徑進行優(yōu)化。具體步驟如下。

Step1：調用GASA算法計算各揀貨單的最優(yōu)路徑。

Step2：計算兩兩揀貨單之間共同路徑上的貨位的貨物，得到協(xié)同貨物矩陣D。

Step3：計算D中的各元素Dh,g(h≠g,h∈H,g∈H)的最優(yōu)協(xié)同貨物組合。

Step4：編碼設計。采用二進制編碼，對協(xié)同貨物矩陣D中的元素Dh,g，即揀貨單g的可能被協(xié)同貨物進行編碼設計。染色體C2=[i1,i2,i3,…,im,…,in]，基因位對應揀貨位編號，基因值im為0時，代表該貨物被揀貨單h協(xié)同，基因值im為1時，代表該貨物留在揀貨單g中揀選，隨機生成初始種群。

Step6：產(chǎn)生新個體。選擇操作采用輪盤賭法，交叉操作采用多點交叉算子，變異操作采用單點突變法，產(chǎn)生新種群。

Step7：判斷是否達到最大迭代次數(shù)，若是，則生成揀貨單g的最優(yōu)路徑節(jié)約值和最優(yōu)協(xié)同貨物組合；若否，則判斷新種群的新個體是否滿足揀貨車剩余容量，若滿足，則返回Step5，若不滿足，則返回Step6產(chǎn)生新個體。

3.2 實例分析

本文以雙區(qū)型倉庫為實例，如圖5所示。設貨架的長和寬均為1m，每個巷道的寬度為1m?？v向有20列、橫向有40排貨架，共800個貨位。

圖5 倉庫布局圖Fig.5 Warehouse layout

3.2.1初始參數(shù)設置

模型的參數(shù)設置：揀貨人員的平均行走速度v=1 m/s，正常揀貨時間tu=2 s，協(xié)同揀貨時間t′u=2.5s，揀貨車容量Q=80 m3。種群規(guī)模N=80，T0=50 000，交叉概率Pc=0.4，變異概率Pm=0.08。實驗數(shù)據(jù)來源于某電商的訂單數(shù)據(jù)，每張揀貨單包含了若干張訂單，每個訂單中包含了不同貨物的品類與數(shù)量。

3.2.2策略的合理性驗證

首先以5張揀貨單為例，利用上述嵌套GASA算法對其進行求解，揀貨單揀選順序為3-2-1-4-5，總揀貨時間為1 627 s，總揀貨路徑為1 291 m。每張揀貨單具體路徑如圖6所示。圖6(a)為排序第1的揀貨單3，黑點為揀貨單3中的揀貨位的貨物，紅點為被協(xié)同的揀貨單2的揀貨位的貨物，可以看出，在進行揀貨單3的揀選時，揀貨單2的4個貨物被協(xié)同揀選。圖6(b)的黑點為揀貨單2剩余的揀貨位的貨物，6個紅點為被協(xié)同的揀貨單4的揀貨位的貨物，綠點對應圖6(a)的紅點，為被揀貨單3已經(jīng)提前揀選的4個貨物。以此類推，可知后續(xù)揀貨單的貨物協(xié)同情況。對比表2所示的傳統(tǒng)揀貨策略，本文提出的排序協(xié)同揀貨策略的揀貨時間節(jié)約了185 s，揀貨距離縮短了191 m；和動態(tài)揀貨策略相比，協(xié)同貨物增加了6個。驗證了該策略的合理性。

表2 三種揀貨策略對比分析Tab.2 Comparative analysis of three kinds of picking strategies

圖6 貨物動態(tài)協(xié)同優(yōu)化路徑圖Fig.6 Dynamic cargo collaborative optimization path map

3.2.3算法有效性分析

為驗證本文提出的嵌套GASA算法的有效性，將其與嵌套GA算法進行對比，如表3所示。

由表3可知，對于不同揀貨策略，在對規(guī)模大小不同的揀貨單進行求解時，嵌套GASA算法的求解結果均優(yōu)于GA算法。傳統(tǒng)策略下，GASA比GA算法的揀貨時間平均少2.4%，動態(tài)策略下少5.1%，排序協(xié)同策略下少5.4%?？梢钥闯?， 不論哪種策略，GASA均優(yōu)于GA算法，并且在排序協(xié)同策略下效果更好。

表3 不同算法下揀貨時間的對比結果Tab.3 Comparison results of picking time by different pick methods

3.2.4不同規(guī)模揀貨單的對比分析

分別以5張、13張、54張揀貨單為例進行仿真實驗，如表4所示。

由表4可以看出，與傳統(tǒng)揀貨策略相比，排序協(xié)同策略的揀貨時間分別節(jié)約了12.8%、17.9%和24.7%，揀貨距離節(jié)約了16.7%、23.8%和39.7%。

表4 不同規(guī)模揀貨單的對比Tab.4 Comparison of picking lists of different sizes

與動態(tài)策略相比，排序協(xié)同策略的揀貨時間分別節(jié)約了5.13%、12.05%和15.69%，揀貨距離節(jié)約了6.69%、16.02%和24.20%。說明采用排序協(xié)同策略可使揀貨效率明顯提升，且隨著揀貨單數(shù)量的增加，揀貨效率提升越發(fā)明顯。

4 結 語

本文基于“邊揀貨邊協(xié)同貨物”的協(xié)同優(yōu)化思想，設計了路徑優(yōu)化-貨物動態(tài)協(xié)同-揀貨單排序”的循環(huán)揀貨策略，以總揀選時間最短為總目標，設計了一種多階段循環(huán)求解算法，首先基于GASA算法對揀貨單路徑進行優(yōu)化，然后使用嵌套GASA算法求解最優(yōu)協(xié)同貨物組合，最后采用遍歷法對揀貨單進行動態(tài)排序。

算例表明：與傳統(tǒng)揀貨策略或者動態(tài)揀貨策略相比，本文提出的排序協(xié)同策略在揀貨時間和揀貨路徑方面均具有一定的優(yōu)越性，且隨著揀貨單數(shù)量的增加，優(yōu)越性越發(fā)明顯。本文的揀貨策略、模型和數(shù)值仿真結果可為電商企業(yè)揀貨提供決策參考。