粒子群算法在揀選路徑中的應(yīng)用研究

李沖 陳偉峰

[摘 要]文章通過運(yùn)用模擬仿生學(xué)中的粒子群算法，探討當(dāng)前物流企業(yè)如何有效的提高揀選效率。首先探討了配送中心運(yùn)作過程花費(fèi)的時(shí)間構(gòu)成，然后對(duì)粒子群算法進(jìn)行對(duì)應(yīng)的結(jié)構(gòu)改造，最后通過對(duì)具體數(shù)據(jù)進(jìn)行仿真計(jì)算，得到最終優(yōu)化結(jié)果。

[關(guān)鍵詞]供應(yīng)鏈管理；人工揀選；粒子群算法

[DOI]10.13939/j.cnki.zgsc.2017.12.251

1 引 言

隨著電子商務(wù)的迅速發(fā)展，大批量、小額以及個(gè)性化的訂單的配送成為人們普遍思考的問題，揀選作業(yè)在配送中心的整個(gè)作業(yè)流程中占的比例較大，有效地減少揀選所用的時(shí)間對(duì)于提高整個(gè)配送中心物流效率具有重要的意義。通過優(yōu)化訂單分批方式以及揀選員的行走路徑能夠有效地減少配送中心的配送成本，提高顧客的滿意度。[1]

2 粒子群算法

在求解訂單分批的問題中粒子群算法具有獨(dú)特的優(yōu)越性，本文應(yīng)用粒子群算法對(duì)訂單分批問題進(jìn)行求解，在PSO算法中，粒子群中的每一個(gè)都是在一個(gè)n維空間中搜尋，其中每一個(gè)粒子所處的位置都可以看成模型的一個(gè)解，每個(gè)粒子通過速度更新公式不斷調(diào)整自己的位置，每一個(gè)粒子對(duì)形成的最優(yōu)解具有記憶力，記作Pid，粒子群運(yùn)動(dòng)過程中最好位置，記作Pgd，每一個(gè)粒子都有自己的一個(gè)速度V。粒子群算法的基本公式如下：

PSO算法是一種進(jìn)化計(jì)算方法，采用一代一代迭代的方式進(jìn)行更新，在這個(gè)過程中，粒子群體中的粒子通過初始化賦予每個(gè)粒子初始位置，根據(jù)速度更新公式，產(chǎn)生下一代更好的個(gè)體，新一代粒子群體在前一代的基礎(chǔ)上產(chǎn)生，經(jīng)過比較后，用適應(yīng)度更好的粒子來取代當(dāng)前粒子。PSO算法其余的啟發(fā)式算法一樣具有快速的尋優(yōu)能力，其次可以改變其中的參數(shù)對(duì)算法進(jìn)行調(diào)整適應(yīng)性強(qiáng)，算法簡(jiǎn)單。

3 PSO算法模型仿真

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

對(duì)于像分批這種離散問題，采用數(shù)字對(duì)所有的訂單進(jìn)行編碼，把每一個(gè)批次用一個(gè)自然數(shù)字串與之對(duì)應(yīng)，在該自然數(shù)字串中有不同或者相同的數(shù)字，分別表示order所在的batch，設(shè)有訂單解數(shù)字序列（O1，O2，…，ON），該數(shù)字序列對(duì)應(yīng)著N個(gè)位置，由該數(shù)字串生成的每一個(gè)基本數(shù)字串都代表這一個(gè)基本的批訂單粒子，比如X={x1，x2，…，xN}表示一個(gè)批訂單，每一個(gè)批訂單數(shù)字串xi=j，j∈（1，2，…，batch），數(shù)字串里的每一個(gè)元素表示當(dāng)前訂單被分配到哪個(gè)批次中去。[2]

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

粒子通過一次次的更新迭代，調(diào)整自己的行為，同時(shí)也根據(jù)自己對(duì)整個(gè)群體的認(rèn)知情況調(diào)整自己的行為，每個(gè)粒子都可以決定自己向群體中的哪個(gè)粒子進(jìn)行學(xué)習(xí)，如果這個(gè)粒子是整個(gè)群體中的，則把他稱為精英粒子，如果是該粒子周圍的粒子則稱為鄰近精英粒子，如何選擇精英粒子進(jìn)行學(xué)習(xí)決定了整個(gè)算法的收斂速度，經(jīng)過試驗(yàn)驗(yàn)證，采用向整個(gè)群體中具有最好適應(yīng)值的精英粒子進(jìn)行學(xué)習(xí)具有更好的收斂性。每一個(gè)粒子學(xué)習(xí)的粒子數(shù)量還可以不只是一個(gè)，可以是多個(gè)精英粒子，精英粒子越多，收斂速度也就越快。

3.3 位置更新方式

訂單分批問題是典型的離散值更新公式，學(xué)者劉建華[3]通過對(duì)PSO算法公式進(jìn)行了適用于分批的改造，每個(gè)粒子的位置采用一種二進(jìn)制數(shù)表示，每個(gè)批訂單粒子通過sigmoid函數(shù)映射到區(qū)間[0-1]上去。在這些的基礎(chǔ)上進(jìn)行了改進(jìn)：前面采用了自然數(shù)而不是0和1對(duì)每組分批訂單進(jìn)行了分批的編碼，因此每一組粒子位置向量的解向量取值就不是0和1，而是訂單分為幾批就有幾個(gè)自然數(shù)，如果訂單分為8批，出現(xiàn)的批次數(shù)為1，2，3，4，5，6，7，8這8個(gè)自然數(shù)，如果某一位為m則表示第i個(gè)訂單被分到了第m批次中。而粒子的運(yùn)動(dòng)過程是由粒子的速度決定的，而訂單的分批過程中沒有這個(gè)概念，這里將每個(gè)粒子的速度映射為概率串，它表示每一位增加或者減少的可能性，位置的改變同樣不再是加上速度，通過設(shè)定一定的概率，每一個(gè)粒子依據(jù)這個(gè)概率進(jìn)行加減一個(gè)常數(shù)操作，這里的常數(shù)設(shè)為C是一個(gè)預(yù)設(shè)的常量，如果訂單的數(shù)目較少的話，C的取值可以較小，如果訂單數(shù)目較多，可以適量增大C的值以加快收斂速度。

其中rand（）的值在[0-1]之間取值，通過速度映射函數(shù)的圖像可以看出，如果速度的取值過大，也就是接近于1的話，那么位置一定會(huì)改變，訂單分批方式一定會(huì)改變，這樣的分批就失去了隨機(jī)性，因此必須隨速度值進(jìn)行限制，這里做出如下規(guī)定，即速度值最大為6。

3.4 可行解保證

經(jīng)過速度位置公式的變更可能產(chǎn)生一些不滿足要求的解，因此必須對(duì)解的范圍進(jìn)行限制，比如說可能產(chǎn)生這樣的解，X=（0，1，-5，3，7，5，17），在這個(gè)數(shù)據(jù)串中的每一個(gè)數(shù)字代表的是訂單所屬編號(hào)，但這里出現(xiàn)了類似負(fù)數(shù)這種不合理的編號(hào)，這明顯是不符合分批要求的，但卻是合理的，如果僅用不同的 數(shù)字表示不同的批次是有意義的，只需要保證批次的編號(hào)是連續(xù)的。將X按照升序進(jìn)行排列得到Y(jié)=[-5，0，1，3，5，17]，依次檢查X中的每一個(gè)分量，將X中的分量與Y中的分量一一對(duì)應(yīng)，如果X中的第m個(gè)分量等于Y中的第n個(gè)分量，那么久將X中的第m個(gè)分量變?yōu)閚，Xi=（4，2，1，2，3，3，4），通過這個(gè)變換后，沒有了負(fù)數(shù)以及較大的數(shù)，但是還是無法保證完美，為了更好地在分批中應(yīng)用，這里加入一個(gè)條件，通過把數(shù)據(jù)代入到一個(gè)改正函數(shù)中去，從而使得數(shù)據(jù)具有可行性。

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

在PSO算法速度更新公式中有w、C1、C2三個(gè)參數(shù)，這些參數(shù)用來調(diào)節(jié)粒子對(duì)局部粒子的學(xué)習(xí)能力和全局粒子的學(xué)習(xí)能力，根據(jù)Shi和Eberhart最早提出一個(gè)權(quán)重系數(shù)來控制上代粒子對(duì)當(dāng)前粒子的影響程度，他們建議將w的值取在[0.9-1.2]之間，這樣由于數(shù)值較為接近1，表明上一代粒子的速度影響程度，這個(gè)值越大，粒子的局部搜索能力就越強(qiáng)，然而這樣設(shè)置到了后期容易陷入局部最優(yōu)，因此Shi和Eberhart把對(duì)參數(shù)的設(shè)置進(jìn)行了改造，決定重要性的參數(shù)不再是一個(gè)常數(shù)，而是一個(gè)可以變動(dòng)的數(shù)值，算法在剛開始進(jìn)行迭代計(jì)算的時(shí)候采用的是Wmax，伴隨著總的計(jì)算量的增加，參數(shù)逐漸變小，最小值設(shè)為Wmin.

學(xué)習(xí)因子定義了粒子的學(xué)習(xí)能力，這個(gè)因子分為兩部分，其一是向局部粒子的 學(xué)習(xí)能力，其二是向全局粒子學(xué)習(xí)的能力，分別用參數(shù)C1和C2來表示，之前的文獻(xiàn)中有的取值C1=C2=2，這里同樣采用，初始慣性權(quán)重值設(shè)為w=1.2，通過下圖可以看出當(dāng)C1=0，C2=3也就是C1取值較C2小時(shí)，在第50代就取到了最優(yōu)值，說明有良好的局部搜索能力，當(dāng)C2=0，C1=3時(shí)，路徑值收斂到了一個(gè)較大的值，這說明粒子具有良好的向精英粒子學(xué)習(xí)的能力，因此為了找到更好的解，這里設(shè)置C1=1，C2=3，這樣不僅搜索范圍更大，且具有良好的局部搜索能力。這里對(duì)具體參數(shù)設(shè)置如下：慣性權(quán)重w=1.2，學(xué)習(xí)因子C1=0，C2=3，種群數(shù)量50，迭代次數(shù)300。

4 結(jié) 論

當(dāng)C1=0，C2=3時(shí)，算法的收斂速度較快，在第50代左右就收斂到了最小值，算法收斂到1600。當(dāng)C1=3，C2=0是粒子群算法收斂到了一個(gè)較大的值2100，原因是C1的值比較大，算法強(qiáng)調(diào)向周圍精英粒子學(xué)習(xí)，容易陷入局部最優(yōu)，由于C2=0，對(duì)全局精英粒子不學(xué)習(xí)，因此收斂的值比較大，不是最優(yōu)的收斂結(jié)果。當(dāng)C1=1，C2=3時(shí)，算法收斂到1500左右，明顯優(yōu)于以上兩種情況，這是由于算法在計(jì)算的時(shí)候，即向局部精英粒子學(xué)習(xí)，又根據(jù)全局精英粒子對(duì)自己的位置進(jìn)行調(diào)整。這時(shí)對(duì)應(yīng)的batch size為5次，比之前模型求出的結(jié)果6相差不大，通過參數(shù)的設(shè)計(jì)最終收斂于1500m，相對(duì)于其他的記過有明顯的路徑方面的節(jié)省，通過對(duì)訂單分批進(jìn)行了粒子群算法的優(yōu)化，記過表明，通過應(yīng)用啟發(fā)式算法，確實(shí)能夠明顯減少訂單揀選時(shí)間，產(chǎn)生明顯的效果。采用粒子群算法，比先到先服務(wù)（FCFS）、固定時(shí)間窗分批、節(jié)約算法（SAVING）這些方法，PSO算法能有20%左右的改善，并且還具有良好的適應(yīng)性，因此采用粒子群算法具有良好的效果。

參考文獻(xiàn)：

[1]李澤.電子商務(wù)（B2C）作業(yè)下人工揀選成本分析[J].電子商務(wù)，2014（5）.

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

[3]劉建華.粒子群算法的基本理論及其改進(jìn)研究[D].長沙：中南大學(xué)，2009.