馬廷偉 雷全勝 李軍 羅盛照

摘 要：物流中心是現(xiàn)代物流活動(dòng)的關(guān)鍵場(chǎng)所，而訂單分揀環(huán)節(jié)占到其工作的50%以上。文章旨在通過(guò)制定合理的訂單分批策略以改善人工揀選系統(tǒng)中揀選作業(yè)的工作效率。訂單分批通過(guò)將多個(gè)訂單合成一個(gè)批次或更大的訂單以減少工作量并讓分揀過(guò)程得以更有效的實(shí)施。文章提出的基于粒子群的分批算法考慮將粒子群算法用于求解訂單分批問(wèn)題，為了使算法匹配所要求解的問(wèn)題，對(duì)二進(jìn)制粒子群算法進(jìn)行了改進(jìn)。最后利用Matlab仿真軟件進(jìn)行仿真實(shí)驗(yàn)，進(jìn)而得出了較經(jīng)典的啟發(fā)式算法更好的求解結(jié)果。

關(guān)鍵詞：供應(yīng)鏈管理；分揀策略；訂單分批；粒子群算法

中圖分類號(hào)：F251 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： Logistics center is the key place of modern logistics activities， and the order picking process accounts for more than 50% of the work. Order batching reduces the amount of work and make the sorting process more effective by synthesizing a batch or larger order with multiple orders. In order to solve the problem of the requirements for the algorithm， the binary particle swarm optimization algorithm is improved in order to solve the problem. At last， the simulation experiment is carried out by using Matlab simulation software， and the result is better than the classical heuristic algorithm.

Key words： supply chain management； sorting strategy； order batching； particle swarm optimization

0 引 言

物流系統(tǒng)是供應(yīng)鏈準(zhǔn)確高效運(yùn)作的基本保障，在物流系統(tǒng)各個(gè)環(huán)節(jié)中，物流中心連接了供應(yīng)鏈的各個(gè)部分，是物品流通的關(guān)鍵節(jié)點(diǎn)，也是管理者關(guān)注的重點(diǎn)。在物流中心的各項(xiàng)活動(dòng)中，分揀是最為重要的一項(xiàng)活動(dòng)，其成本約是整個(gè)中心運(yùn)營(yíng)成本的50%～65%[1]，分揀的效率不僅關(guān)系到整個(gè)運(yùn)營(yíng)的成本，還直接影響到客戶服務(wù)水平。人工分揀系統(tǒng)可以分為人到貨系統(tǒng)和貨到人系統(tǒng)，本文主要研究人到貨系統(tǒng)，即揀選人員駕駛揀貨設(shè)備逐個(gè)到貨位進(jìn)行揀選。在人工分揀系統(tǒng)中管理者通常要考慮三個(gè)操作層面的問(wèn)題：儲(chǔ)位分配即貨物如何在存儲(chǔ)區(qū)進(jìn)行存放以及對(duì)不同的貨物如何設(shè)計(jì)存放位置；訂單分批即如何將訂單進(jìn)行分批處理以節(jié)省總的揀選時(shí)間；路徑優(yōu)化即如何最小化每一次揀選的路程。其中訂單分批對(duì)訂單揀選的運(yùn)作效率起到非常關(guān)鍵的作用，良好的分批方法能有效減少揀選人員用于采集訂單指定物品所需的時(shí)間從而提高產(chǎn)能增加柔性。本文介紹了粒子群算法的概念與主要步驟，提出了一種適用于訂單分批問(wèn)題的算法PSOBM（Particle Swarm Optimization Bat-ching Method）。

1 粒子群算法

粒子群優(yōu)化算法（Particle Swarm Opti-mization， PSO）是一種基于群的隨機(jī)優(yōu)化技術(shù)，由Kennedy和Eberhart[2]在1995提出，粒子群算法涉及到演化計(jì)算，并與遺傳和進(jìn)化策略有著密切的聯(lián)系。群體智能是該算法中一個(gè)核心的思想，內(nèi)容為在群體中對(duì)信息的社會(huì)共享使得整個(gè)群體具有一定演化優(yōu)勢(shì)。粒子群優(yōu)化算法的基本思想是：一個(gè)群體中的每個(gè)個(gè)體都能夠“記憶”一個(gè)最佳值以及與這個(gè)最佳值相關(guān)的位置信息，同時(shí)每個(gè)個(gè)體還知道其他個(gè)體所了解到的最佳值與位置信息，這樣對(duì)每個(gè)個(gè)體來(lái)說(shuō)可以根據(jù)這些信息調(diào)整自己的位置以保持與其它個(gè)體的同步[3]。因此，對(duì)這樣的個(gè)體需包含至少三方面的內(nèi)容：當(dāng)前運(yùn)動(dòng)的方向、自己的經(jīng)驗(yàn)、群體的經(jīng)驗(yàn)，相比其他的表述，粒子更適合描述具有速度和加速度這樣概念的個(gè)體，這也是為什么這一算法被稱為粒子群。群體對(duì)兩個(gè)質(zhì)量因子pbest和gbest做出反應(yīng)，在兩個(gè)因子間響應(yīng)的定位確保了響應(yīng)的多樣性。群體只有在gbest改變時(shí)才改變其狀態(tài)。

假設(shè)搜索空間中有P個(gè)粒子，每個(gè)粒子是一個(gè)n維向量，其中第i個(gè)粒子遵循下面的運(yùn)動(dòng)規(guī)律：

慣性權(quán)重系數(shù)使得搜索更加靈活并提高了搜索的精確程度，大大提升了粒子群算法的可用性，因此具有慣性權(quán)重系數(shù)的粒子群算法被稱為標(biāo)準(zhǔn)粒子群算法（Standard Particle Swarm Optimization），粒子的運(yùn)動(dòng)過(guò)程如圖1所示：

當(dāng)w≥1時(shí)，粒子的速度在整個(gè)迭代期間會(huì)不斷增加，并導(dǎo)致粒子逐漸脫離種群；

當(dāng) 0

Shi和Eberhart還建議對(duì)慣性權(quán)重的取值逐漸減小，即慣性權(quán)重系數(shù)是隨時(shí)間遞減的函數(shù)wt，并指出其取值范圍在0.4，1.2之間算法具有較好的搜索效果，其中權(quán)重值在0.4，0.9區(qū)間上具有很好的局部搜索能力，而值在0.9，1.2區(qū)間上具有很好的全局搜索能力，至于更側(cè)重局部搜索能力還是全局搜索能力要視具體問(wèn)題而定。

加速度C和C也被稱作學(xué)習(xí)因子，一般C和C取值相同且大于零，即C=C>0，此時(shí)粒子被“吸引”向最優(yōu)位置靠攏，若C>C有利于求解多峰問(wèn)題，而如果C

2 粒子群算法設(shè)計(jì)

本文采用粒子群算法解決訂單分批問(wèn)題出于以下幾點(diǎn)考慮：

（1）粒子群具有快速的搜索能力，取得一個(gè)滿意的解比尋找最優(yōu)解更加實(shí)際；

（2）粒子群算法同樣是一種隨機(jī)搜索算法，通過(guò)改變參數(shù)的方式可以靈活地進(jìn)行調(diào)整；

（3）粒子群算法規(guī)則簡(jiǎn)單易于實(shí)現(xiàn)。

2.1 粒子群算法的步驟

利用粒子群算法進(jìn)行求解分批問(wèn)題遵循下列步驟：

2.2 編碼設(shè)計(jì)

編碼方式的選擇從很大程度上影響到搜索空間的規(guī)模和搜索的質(zhì)量，對(duì)于離散空間來(lái)說(shuō)一般將一個(gè)二進(jìn)制串作為問(wèn)題的一個(gè)解[6]，為了求解訂單分批問(wèn)題，本文對(duì)所有解進(jìn)行自然數(shù)編碼，即問(wèn)題的每一個(gè)解是一個(gè)自然數(shù)串，串中的每一位表示在該位置的訂單所放入的批次號(hào)，設(shè)有訂單向量該向量在搜索空間映射了N個(gè)位置，每個(gè)位置可以用一個(gè)粒子表示。若表示一個(gè)粒子的位置向量，該向量的每個(gè)分量x=j， j∈1，BatchNum代表了訂單被分到第j批次，編碼過(guò)程如表1所示。

解向量中相同編號(hào)的數(shù)字表示對(duì)應(yīng)序號(hào)的訂單被放入了同一個(gè)批次。

2.3 粒子群的拓?fù)浣Y(jié)構(gòu)

在每一次迭代中，每個(gè)粒子都根據(jù)自己的認(rèn)知和社會(huì)認(rèn)知調(diào)整自己的行為，當(dāng)群體的數(shù)目決定之后即確定了一個(gè)社會(huì)規(guī)模，每個(gè)粒子可以決定向群體中的某些個(gè)體學(xué)習(xí)，這些個(gè)體往往被稱為精英粒子，或者向鄰近的粒子學(xué)習(xí)。不同的學(xué)習(xí)方式?jīng)Q定了整個(gè)算法的收斂速度，一般來(lái)說(shuō)，采用學(xué)習(xí)精英粒子（群體中具有最好適應(yīng)值的粒子）的策略使得算法收斂更快，局部搜索能力也更好；而采用向鄰近粒子學(xué)習(xí)的方式則具有更好的全局搜索能力。另外粒子還能夠選擇需要學(xué)習(xí)的相鄰粒子的數(shù)量，數(shù)量越多意味著包含精英粒子的幾率也越大，所以收斂的速度也就越快，將粒子的鄰近視為一個(gè)個(gè)的搜索鄰域，選擇和定義這些鄰域的方式稱為粒子群的拓?fù)浣Y(jié)構(gòu)。本文采用向群體的精英粒子學(xué)習(xí)的方式，該種方式能夠充分發(fā)揮粒子群算法快速搜索的特點(diǎn)。

2.4 位置更新方式

標(biāo)準(zhǔn)的粒子群算法由于速度更新公式產(chǎn)生的是連續(xù)的值，因此特別適合處理具有連續(xù)搜索空間的問(wèn)題，前面介紹了標(biāo)準(zhǔn)粒子群的一種改進(jìn)版本——二進(jìn)制粒子群算法，該種算法嘗試通過(guò)改變位置更新的方式來(lái)適應(yīng)離散的模型，本質(zhì)上講二進(jìn)制粒子群算法不同于粒子群算法，每個(gè)粒子的位置用取值0和1的向量來(lái)表示，速度被映射到0，1區(qū)間上得到一個(gè)長(zhǎng)度等同于粒子位置向量的概率串，表示每個(gè)位取0或1的概率。劉建華[7]提出了一種改進(jìn)的二進(jìn)制粒子群算法并驗(yàn)證了其魯棒性，本文借鑒其研究成果，提出一種適用于分批問(wèn)題的離散粒子群算法PSOBM。

根據(jù)前面所采用的編碼方式，粒子的位置向量即解向量每一位取值不是0和1，而是一系列取值上連續(xù)的正整數(shù)，若某一位為j則表示與該位對(duì)應(yīng)的訂單i被分到了第j個(gè)批次。為了表示粒子的運(yùn)動(dòng)過(guò)程，將速度映射為概率串，表示每一位增加或減少的可能性，位置更新不是以概率變?yōu)?或1，而是以一定概率加上C或減去C，從而使得粒子的某一位置分量向精英粒子的對(duì)應(yīng)位置分量靠近。對(duì)于訂單數(shù)目較少時(shí)C取值為1，當(dāng)訂單數(shù)目較大時(shí)可以考慮采用較大的C來(lái)加快算法收斂的速度。前面提到的速度映射sigmoid函數(shù)變成了如下的形式：

rand是取值均勻分布在0，1區(qū)間上的隨機(jī)變量，在圖2中注意到如果速度v的取值過(guò)大則所映射的概率也越接近于1，也就是說(shuō)位置值一定改變，從而失去了隨機(jī)性，為了避免這種情況的發(fā)生引入一個(gè)最大速度值V從而將v限定在-V，V范圍內(nèi)。V的取值不易過(guò)大，這樣就失去了設(shè)置該值的意義，本文將V取值為6。

2.5 可行解的保證

經(jīng)過(guò)上述變化過(guò)程，解的結(jié)構(gòu)發(fā)生了改變，由于所要求解的問(wèn)題帶有約束條件，從而可能產(chǎn)生一些無(wú)法滿足要求的解，需要保證解的可行性。經(jīng)過(guò)上述映射變換后的解向量可能具有如下這樣的形式：X=16，0，-2，0，5，5，16。

向量的每一個(gè)分量表示的是批次編號(hào)，而這里卻出現(xiàn)了負(fù)數(shù)和很大的數(shù)字，而且各編號(hào)的值也不是連續(xù)的，這似乎不是我們希望得到的結(jié)果，其實(shí)這樣的解是有意義的，如果僅僅用不同的數(shù)字代表不同的批次，所讓人困惑的就只是序號(hào)的問(wèn)題，可以通過(guò)下面的算法保證批次的序號(hào)是連續(xù)的：

將x升序，不重復(fù)的排列到向量Y=-2，0，5，…，16，檢查X的每一個(gè)分量，如果第m個(gè)分量的值等于Y中第n個(gè)分量的值，則將改變X中的那個(gè)分量變?yōu)閚，n即是Y個(gè)分量的索引值。該過(guò)程的matlab代碼如下：

for n = 1： lengthY

for m = 1： lengthX

if Xm=Yn

Xm=n

end

end

end

經(jīng)過(guò)上面的步驟，X=4，2，1，2，3，3，4，這樣還是沒(méi)法保證解是可行的，為了滿足約束，引入一個(gè)糾正函數(shù)Check_and_Correct。將任意解轉(zhuǎn)化為分批問(wèn)題可行解的步驟如下：

（1）分別考察每個(gè)批次；

（2）對(duì)當(dāng)前考察的批次，判斷是否違反約束，在這里是保證每批次訂單物品數(shù)量不超過(guò)揀選設(shè)備容量；

（3）如果滿足約束條件則考察下一批次；

（4）如果不滿足約束條件，則對(duì)當(dāng)前的批次進(jìn)行拆分，拆分的原則是取該批次中的第一個(gè)訂單；

（5）將（4）中拆分出來(lái)的訂單放入物品數(shù)量最小的一個(gè)批次，如果放入該批次后使得原本滿足約束變?yōu)椴粷M足，則打開(kāi)一個(gè)新的批次；

（6）返回（4）直到考察批次滿足約束為止；

（7）直到考察完最后一個(gè)批次。

該過(guò)程的偽代碼如圖3所示。

2.6 程序流程設(shè)計(jì)

圖4顯示了利用粒子群算法求解分批問(wèn)題的程序流程設(shè)計(jì)，該設(shè)計(jì)采用模塊化編程，在主函數(shù)PSOBM中包含了算法的整個(gè)流程，在外圍有三個(gè)主要的子函數(shù)以供調(diào)用，分別是糾正函數(shù)，位置更新函數(shù)和適應(yīng)度計(jì)算函數(shù)。在有子函數(shù)調(diào)用的地方做出了標(biāo)注。

3 參數(shù)選擇

3.1 慣性權(quán)重

為了平衡粒子群算法局部搜索能力和全局搜索能力，Shi和Eberhart為最早提出的粒子群算法引入了一個(gè)慣性權(quán)重w，具有慣性權(quán)重的粒子群算法被稱為標(biāo)準(zhǔn)粒子群算法，Shi和Eberhart還建議將w取值為0.9，1.2，這樣能夠取得較好的優(yōu)化效果。慣性權(quán)重定義了粒子的當(dāng)前速度受先前速度的影響程度，權(quán)重越大局部搜索能力越弱，而全局搜索能力得到加強(qiáng)。對(duì)于本文所研究的模型來(lái)說(shuō)，慣性權(quán)重定義了某種隨機(jī)性使得能夠在更大的范圍內(nèi)搜索到有用的解，然而在算法的后期這種隨機(jī)性使局部搜索不夠。Shi和Eberhart在此基礎(chǔ)上還提出了一種適應(yīng)策略，即權(quán)重值是一個(gè)變化范圍，在迭代的一開(kāi)始采用較大的權(quán)重值

W，隨著迭代次數(shù)增加權(quán)重逐漸減小到一個(gè)固定值W，每次迭代慣性權(quán)重取值為：

w=w-w-w （7）

這樣算法就能在一開(kāi)始擁有很好的全局搜索能力，而在后期擁有不錯(cuò)的局部搜索能力，鑒于此本文將采用這種慣性權(quán)重設(shè)置。

3.2 初始速度

由速度更新公式（3），如果沒(méi)有右邊的第一項(xiàng)v則粒子群算法就等效為一個(gè)局部搜索算法，v提供了粒子變化的方向，因此進(jìn)行第一次迭代時(shí)的初始速度V的選取就非常關(guān)鍵，然而，由于粒子群算法是一種隨機(jī)搜索算法，一開(kāi)始我們并不知道對(duì)哪兒子空間進(jìn)行搜索會(huì)最快找到最優(yōu)解，所以要想確定最優(yōu)的初始速度顯得有些困難，本文采用隨機(jī)的方式產(chǎn)生初始速度V。

3.3 學(xué)習(xí)因子

學(xué)習(xí)因子定義了粒子向群體最優(yōu)粒子以及相鄰粒子學(xué)習(xí)的能力，學(xué)習(xí)分為兩個(gè)部分，自我認(rèn)知部分即該粒子歷史最好的位置和社會(huì)認(rèn)知部分即鄰域中粒子的最好位置，分別用c和c兩個(gè)參數(shù)來(lái)進(jìn)行控制。問(wèn)題是對(duì)特定的問(wèn)題，我們并不知道c和c的取值應(yīng)該是多少，只能通過(guò)反復(fù)試驗(yàn)的方法，通常的文獻(xiàn)中取c=c=2，為討論學(xué)習(xí)因子的取值對(duì)算法的影響，設(shè)有30個(gè)訂單，初始慣性權(quán)重w=1.2，初速度V隨機(jī)產(chǎn)生，首先看看兩個(gè)因子中有一個(gè)取0的情況：

圖5、圖6中顯示的是粒子群中的精英粒子隨著迭代次數(shù)的變化，最小路徑的取值情況。當(dāng)c=0， c=3時(shí)，算法的收斂很快，在50代左右取到了最優(yōu)值，當(dāng)c=3， c=0時(shí)算法收斂于一個(gè)較大的值，原因是算法中強(qiáng)調(diào)了精英粒子的重要性，因此通過(guò)向精英粒子學(xué)習(xí)能夠獲得更好的適應(yīng)值，而只通過(guò)自我認(rèn)知?jiǎng)t幾乎沒(méi)有可能找到最優(yōu)的值，但是自我認(rèn)知仍然是有用的，它擴(kuò)大了算法的搜索范圍，圖7顯示算法在目標(biāo)值為2 200左右進(jìn)行了搜索。為了找到更好的解，不僅需要搜索更大的范圍，同時(shí)也要求更多地向優(yōu)秀的粒子學(xué)習(xí)。圖7給出了在c=1， c=3時(shí)的情況，在此種情況下不僅搜索范圍更大而且所得目標(biāo)值也更好。

4 算法性能與結(jié)果分析

為了進(jìn)一步驗(yàn)證上述算法的有效性，在此將先進(jìn)先出算法和在許多文獻(xiàn)中證明有很好效果的節(jié)約算法作為參考基準(zhǔn)，粒子群算法的參數(shù)設(shè)置如表2所示：

揀選設(shè)備容量設(shè)為60，實(shí)驗(yàn)結(jié)果如圖8所示：

圖8的結(jié)果顯示，粒子群算法在訂單數(shù)目變化的情況下都具有比先到先服務(wù)準(zhǔn)則（FCFS）和節(jié)約算法（SAVING）更好的性能，PSOBM平均比節(jié)約算法有5%～6%的改善，并且基于群的演化方法具有更好的適應(yīng)性，體現(xiàn)在對(duì)不同的環(huán)境都有類似的表現(xiàn)，因而可以認(rèn)為采用粒子群算法求解訂單分批問(wèn)題得到的效果更好。

5 結(jié)束語(yǔ)

粒子群算法是近年來(lái)比較熱門的研究方向，由于算法簡(jiǎn)便易行且計(jì)算快速而受到各個(gè)鄰域的關(guān)注，本文依照粒子群算法提出了一種適用于訂單分批問(wèn)題的算法PSOBM，討論了算法設(shè)計(jì)的各個(gè)細(xì)節(jié)，并給出算法程序流程設(shè)計(jì)，最后通過(guò)實(shí)驗(yàn)結(jié)果與其他方法進(jìn)行了比較，得出粒子群方法效益更高的結(jié)論。

參考文獻(xiàn)：

[1] Manzini R. Warehousing in the Global Supply Chain[M]. London： Springer， 2012：105-155.

[2] Eberhart R， Kennedy J. Particle Swarm Optimization[C] // IEEE， 1995.

[3] 陳恩修. 離散群體智能算法的研究與應(yīng)用[D]. 濟(jì)南：山東師范大學(xué)（博士學(xué)位論文），2009.

[4] Shi Y， Eberhart R. A Modified Particle Swarm Optimizer[C] // IEEE， World Congress on Computational Intelligence， AK， USA， 1998：69-73.

[5] 嚴(yán)露. 粒子群算法研究與應(yīng)用[D]. 成都：電子科技大學(xué)（碩士學(xué)位論文），2013.

[6] 陳曦. 離散粒子群算法的改進(jìn)及其應(yīng)用研究[D]. 合肥：安徽大學(xué)（碩士學(xué)位論文），2014.

[7] 劉建華. 粒子群算法的基本理論及其改進(jìn)研究[D]. 長(zhǎng)沙：中南大學(xué)（博士學(xué)位論文），2009.