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

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

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

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

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

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

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

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

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

1 動(dòng)態(tài)揀貨策略設(shè)計(jì)

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

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

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

具體流程見(jiàn)圖1，具體步驟如下。

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

Step1：初始條件設(shè)置

確定倉(cāng)庫(kù)布局，在揀貨臺(tái)處設(shè)置一個(gè)位置，作為被協(xié)同貨物的臨時(shí)存放處。明確貨位信息、揀貨車容量、貨位之間、貨位與揀貨臺(tái)之間的距離等信息。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 基本假設(shè)

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

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

3) 每個(gè)貨位存儲(chǔ)一種貨物，即貨位和品項(xiàng)一一對(duì)應(yīng)；

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

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

6) 訂單分批形成揀貨單，訂單分批時(shí)不允許進(jìn)行分割，保證一個(gè)訂單一次揀完，每張揀貨單的大小不超過(guò)揀貨車的最大容量；

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

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

9) 在揀貨臺(tái)設(shè)置一個(gè)臨時(shí)存放處，用于暫存下一個(gè)揀貨單的被調(diào)整貨物。

2.2 參數(shù)設(shè)置

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

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

變量定義如下：

2.3 模型的構(gòu)建

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

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

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

對(duì)于揀貨單h，以揀貨單最短路徑為目標(biāo)建立數(shù)學(xué)模型。

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

(1)

約束條件：

1)

(2)

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

(3)

(4)

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

(5)

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

(6)

決策變量：

(7)

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

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

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

(8)

(9)

(10)

約束條件為：

1)

(11)

2) 揀貨單g中每個(gè)貨物對(duì)應(yīng)的貨位都要被訪問(wèn)1次：

(12)

(13)

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

(14)

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

(15)

5)

(16)

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

(17)

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

(18)

(19)

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

(20)

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

(21)

決策變量：

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

(22)

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

(23)

(24)

1) 模型3.1：當(dāng)前沒(méi)有排序優(yōu)先的揀貨單

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

(25)

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

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

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

(26)

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

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

(27)

(28)

其中：

每個(gè)排序位置只能有一張揀貨單。

3 算法設(shè)計(jì)與算例分析

3.1 算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

Step4：模擬退火操作。

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

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

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

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

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

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

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

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

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

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

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

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

3.2 實(shí)例分析

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

圖5 倉(cāng)庫(kù)布局圖Fig.5 Warehouse layout

3.2.1初始參數(shù)設(shè)置

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

3.2.2策略的合理性驗(yàn)證

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

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

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

3.2.3算法有效性分析

為驗(yàn)證本文提出的嵌套GASA算法的有效性，將其與嵌套GA算法進(jìn)行對(duì)比，如表3所示。

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

表3 不同算法下揀貨時(shí)間的對(duì)比結(jié)果Tab.3 Comparison results of picking time by different pick methods

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

分別以5張、13張、54張揀貨單為例進(jìn)行仿真實(shí)驗(yàn)，如表4所示。

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

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

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

4 結(jié) 語(yǔ)

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

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