粒子群算法及其在訂單分批中的應用研究

馬廷偉 雷全勝 李軍 羅盛照

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

關鍵詞：供應鏈管理；分揀策略；訂單分批；粒子群算法

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

1 粒子群算法

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

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

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

當w≥1時，粒子的速度在整個迭代期間會不斷增加，并導致粒子逐漸脫離種群；

當 0

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

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

2 粒子群算法設計

本文采用粒子群算法解決訂單分批問題出于以下幾點考慮：

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

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

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

2.1 粒子群算法的步驟

利用粒子群算法進行求解分批問題遵循下列步驟：

2.2 編碼設計

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

解向量中相同編號的數(shù)字表示對應序號的訂單被放入了同一個批次。

2.3 粒子群的拓撲結(jié)構(gòu)

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

2.4 位置更新方式

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

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

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

2.5 可行解的保證

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

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

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

for n = 1： lengthY

for m = 1： lengthX

if Xm=Yn

Xm=n

end

end

end

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

（1）分別考察每個批次；

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

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

（4）如果不滿足約束條件，則對當前的批次進行拆分，拆分的原則是取該批次中的第一個訂單；

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

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

（7）直到考察完最后一個批次。

該過程的偽代碼如圖3所示。

2.6 程序流程設計

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

3 參數(shù)選擇

3.1 慣性權重

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

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

w=w-w-w （7）

這樣算法就能在一開始擁有很好的全局搜索能力，而在后期擁有不錯的局部搜索能力，鑒于此本文將采用這種慣性權重設置。

3.2 初始速度

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

3.3 學習因子

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

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

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

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

揀選設備容量設為60，實驗結(jié)果如圖8所示：

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

5 結(jié)束語

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

參考文獻：

[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] 陳恩修. 離散群體智能算法的研究與應用[D]. 濟南：山東師范大學（博士學位論文），2009.

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

[5] 嚴露. 粒子群算法研究與應用[D]. 成都：電子科技大學（碩士學位論文），2013.

[6] 陳曦. 離散粒子群算法的改進及其應用研究[D]. 合肥：安徽大學（碩士學位論文），2014.

[7] 劉建華. 粒子群算法的基本理論及其改進研究[D]. 長沙：中南大學（博士學位論文），2009.