粒子群算法在揀選路徑中的應用研究

李沖 陳偉峰

[摘 要]文章通過運用模擬仿生學中的粒子群算法，探討當前物流企業如何有效的提高揀選效率。首先探討了配送中心運作過程花費的時間構成，然后對粒子群算法進行對應的結構改造，最后通過對具體數據進行仿真計算，得到最終優化結果。

[關鍵詞]供應鏈管理；人工揀選；粒子群算法

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

1 引 言

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

2 粒子群算法

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

PSO算法是一種進化計算方法，采用一代一代迭代的方式進行更新，在這個過程中，粒子群體中的粒子通過初始化賦予每個粒子初始位置，根據速度更新公式，產生下一代更好的個體，新一代粒子群體在前一代的基礎上產生，經過比較后，用適應度更好的粒子來取代當前粒子。PSO算法其余的啟發式算法一樣具有快速的尋優能力，其次可以改變其中的參數對算法進行調整適應性強，算法簡單。

3 PSO算法模型仿真

3.1 編碼設計

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

3.2 粒子群的拓撲結構

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

3.3 位置更新方式

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

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

3.4 可行解保證

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

3.5 參數設置

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

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

4 結 論

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

參考文獻：

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

[2]陳曦.離散粒子群算法的改進及其應用研究[D].合肥：安徽大學，2014.

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