基于微粒群技術(shù)的多分揀區(qū)產(chǎn)品存儲的算法設(shè)計

陳彥如 楊 璐 魏朝恒 曾東紅

1. 西南交通大學(xué)，經(jīng)濟(jì)與管理學(xué)院，成都 610031

2. 西南交通大學(xué)，交通運(yùn)輸與物流學(xué)院，成都 610031

0 引 言

為了提高分揀效率，許多配送中心分別設(shè)置了分揀區(qū)（Forward area）和存儲區(qū)(Reserve area)。分揀區(qū)用于快速分揀,存儲區(qū)用于大量存儲、補(bǔ)貨及未指派至分揀區(qū)的產(chǎn)品的分揀。如何解決在有限的分揀區(qū)存放多少數(shù)量的何種產(chǎn)品，便形成了 FRP（the forward-reserve problem）—— 分揀區(qū)存儲優(yōu)化問題。

根據(jù)分揀區(qū)設(shè)置的數(shù)目可將 FRP問題分為單分揀區(qū)FRP與多分揀區(qū)FRP。目前單分揀區(qū)FRP的研究成果較為豐富[1-4]，由于該問題屬于NP難問題，因此該問題的求解大多考慮啟發(fā)式算法。而多分揀區(qū)FRP問題研究成果較少，同時因?yàn)樯婕岸鄠€分揀區(qū)的協(xié)調(diào)優(yōu)化，求解更為復(fù)雜?？紤]到精確算法的局限性及微粒群算法在求解大規(guī)模組合優(yōu)化問題的優(yōu)勢[5]，本文嘗試設(shè)計求解多分揀區(qū) FRP的微粒群算法，并用算例驗(yàn)證了該算法的有效性。

1 模型描述[6]

符號說明：

i——產(chǎn)品種類， i = 1 ,2,3,… ,I ；

j——存儲方式， j = 1 ,2,3,…,J

k——分揀區(qū)， k = 1 ,2,3,…,K

Ck——分揀區(qū)k單位面積的建設(shè)成本；

Sk——分揀區(qū)k的空間；

aij——產(chǎn)品i以存儲方式 j存儲時，每單位可存儲產(chǎn)品i的個數(shù)；

Di——產(chǎn)品i的需求量；

Cr——產(chǎn)品i以存儲方式 j存儲在存儲區(qū)的分

ij

揀成本；

多分揀區(qū)產(chǎn)品存儲模型可描述如下：

2 算法設(shè)計

微粒群算法（Particle Swarm Optimization，PSO）是美國心理學(xué)家Kennedy與電氣師Barnhart在1995年提出的，其算法思想來源于對鳥群覓食這一生物現(xiàn)象的模擬。鳥群中的每一只鳥稱為一個粒子，每一個粒子在空間搜索最優(yōu)目標(biāo)。粒子的行為受到兩個方面的影響：一是自身最優(yōu)位置，二是群體最優(yōu)位置。在這兩個因素下，粒子朝著最優(yōu)的方向不斷尋覓，而整個粒子群最終尋覓到的就是最優(yōu)結(jié)果。PSO算法為每個粒子都定制了類似于鳥類運(yùn)動的行為規(guī)則，從而使整個粒子群的運(yùn)動表現(xiàn)出與鳥類覓食相似的特性，用于求解復(fù)雜的優(yōu)化問題。具體的算法步驟如圖1所示。

圖1 微粒群算法流程Fig.1 Process of particle swarm optimization

2.1 粒子編碼

本階段需要對問題的可行解進(jìn)行編碼?？紤]到將C種產(chǎn)品以J種存儲方式放在K個分揀區(qū)，因此所設(shè)計的粒子總長度為C*J*K+C+K。粒子包括三個部分，第一部分長度為C*J*K，表示C種產(chǎn)品以J種方式在K個分揀區(qū)的存儲方案。第二部分長度為C，表示C種產(chǎn)品的存儲方式是否發(fā)生改變。第三部分長度為K,表示K個分揀區(qū)是否建立。

以C=4，J=2，K=3為例的編碼如圖2所示。

圖2 粒子編碼示例Fig.2 Coding pattern of a particle

其中第一部分010000100000000100000001由四段構(gòu)成，每段對應(yīng)一個產(chǎn)品，各段內(nèi)每3位表示3個分揀區(qū)內(nèi)的一種存儲方式，該粒子的第一段 010000表示第一個產(chǎn)品以第一種存儲方式存放在第二個分揀區(qū)內(nèi)，第二段100000表示第二個產(chǎn)品以一種存儲方式存放在第一個分揀區(qū)。由于每個產(chǎn)品只能以一種存儲方式存放在一個分揀區(qū)，因此每段只能有一個值為1。第二部分0101表示4種產(chǎn)品的存儲方式是否發(fā)生改變，如果為0，表示未改變，反之為1。該部分表示第2種和第4種產(chǎn)品的存儲方式發(fā)生了改變。第三部分110表示3個分揀區(qū)的設(shè)置決策，即僅設(shè)置第一個和第二個分揀區(qū)。

2.2 初始化粒子群

給定各參數(shù)的初始值，在指定的優(yōu)化范圍內(nèi)初始化粒子群中每個粒子的速度和位置；初始化加速因子c1、c2和其他相關(guān)參數(shù)。設(shè)每個粒子的個體最優(yōu)值為pBesti。設(shè)種群的全局最優(yōu)值為gBest。

因?yàn)槊總€粒子存在著諸多的屬性，要想更好地描述粒子群的性質(zhì)，需要首先聲明一個粒子群的結(jié)構(gòu)體。聲明如下：

struct population //定義粒子群結(jié)構(gòu)體

{

string str;//本粒子的解編碼string sub1,sub2,sub3;

long X[100][2][5],V[100],Y[5];

long max1,max2,max3,fitness;//本粒子適應(yīng)值string pstr;//歷史最優(yōu)粒子

long pfitness;//歷史最優(yōu)適應(yīng)值

};

其中包含的屬性分別有：粒子的編碼、各決策變量的編碼、各決策變量的存儲數(shù)組、該粒子的適應(yīng)值、該粒子歷史最優(yōu)解的編碼以及該粒子的歷史最優(yōu)適應(yīng)值。

按照粒子群結(jié)構(gòu)體的特點(diǎn)，隨機(jī)生成一定規(guī)模的具有多屬性的粒子群。

2.3 粒子評價

判斷粒子的質(zhì)量優(yōu)劣，主要依據(jù)模型的目標(biāo)函數(shù)，即來進(jìn)行。質(zhì)量越優(yōu)的粒子目標(biāo)函數(shù)值越大。

2.4 更新最優(yōu)值

如果更新后粒子的適應(yīng)度值優(yōu)于原來的值，則將新的適應(yīng)度值作為該粒子的適應(yīng)度值，新的粒子的位置作為該粒子的pBesti。如果更新后粒子的適應(yīng)度值優(yōu)于原來的全局最優(yōu) gBest，則將該粒子的位置作為新的全局最優(yōu)gBest。

2.5 粒子位置與速度更新

粒子群中所有粒子的每一維在每一次迭代中都會有一個速度，因此每一次的迭代都會對該粒子的一系列屬性進(jìn)行更新操作。由于多分揀區(qū) FRP產(chǎn)品存儲為0—1整數(shù)規(guī)劃問題，更新速度的計算不再是連續(xù)的計算，因此與一般的粒子群的更新有所區(qū)別。公式（5）即為當(dāng)前粒子的速度公式：

式（5）不考慮前一次迭代中的速度，只考慮影響粒子速度的主要因子“自身認(rèn)知”c1·ra n d()·(pBestij-Xij)和“社會認(rèn)知”c2·ra n d ( )·(gBestj-Xij)。其中c1,c2分別為自身認(rèn)知系數(shù)和社會認(rèn)知系數(shù)，分別代表著自身歷史和全局對當(dāng)前速度的影響權(quán)重。rand（）為 0—1之間的隨機(jī)變量，表示可能會出現(xiàn)的隨機(jī)情況。pBestij為該粒子的歷史最優(yōu)組合，gBestj為該粒子群的全局最優(yōu)組合。

為了使每次迭代后的Xij值只取1或者0，論文將速度轉(zhuǎn)化為相應(yīng)Xij取1或者0的概率。具體步驟是首先借助 sigmoid 函數(shù)將粒子速度的值映射到區(qū)間[0,1]，如式（6）所示：

rand ()是一個隨機(jī)數(shù)，從區(qū)間[0,1]隨機(jī)產(chǎn)生。Sig(Vij)表表示位置Xij取1的概率，即sigmoid函數(shù)的變換并不是代表位Xij變化的概率，而只是代表位取Xij取 1的概率。綜上所述，以此種步驟來完成粒子群速度的更新以及粒子各維度位的更新。

3 算例驗(yàn)證

某配送中心設(shè)有存儲區(qū)與三個分揀區(qū)，在存儲區(qū)中存儲著配送中心每一品類的存貨?，F(xiàn)有A、B、C、D四種產(chǎn)品被分配到某個分揀區(qū)，現(xiàn)假設(shè)三個分揀區(qū)單位空間的建設(shè)成本相同，均為 10。每個產(chǎn)品的存儲、分揀與補(bǔ)貨作業(yè)操作均以托盤為單位，假設(shè)產(chǎn)品大小相同，產(chǎn)品的存儲方式有2種：以第一種方式存儲時，每個托盤每次可以存放10個產(chǎn)品；以第二種存儲方式存儲時，每個托盤每次可以存放20個產(chǎn)品。三個分揀區(qū)的存儲容量分別為可以存儲1 000，500，1000個單位。A、B、C、D四種產(chǎn)品的需求分別為226、238、287、259。四種產(chǎn)品在存儲區(qū)、分揀區(qū)的分揀成本、處理成本與補(bǔ)貨成本如表1至表4所示。

表1 產(chǎn)品在存儲區(qū)的分揀成本Tab.1 Picking costs in a reserve area

表2 產(chǎn)品在分揀區(qū)的分揀成本Tab.2 Picking costs in a forward area

表3 產(chǎn)品處理成本Tab.3 Handling costs

表4 產(chǎn)品補(bǔ)貨成本Tab.4 Replenishment costs

所設(shè)計的微粒群參數(shù)設(shè)置為：粒子群規(guī)模為20，迭代次數(shù)為10，認(rèn)知系數(shù)和社會系數(shù)都為0.5。進(jìn)行算法對比時，論文選取了CPLEX軟件的Branch & Cut算法。為了更加客觀的對算法進(jìn)行驗(yàn)證，論文對算例獨(dú)立運(yùn)行了20次。兩種算法的適應(yīng)度與運(yùn)行時間對比如圖3所示。

圖3 4個產(chǎn)品兩種算法的適應(yīng)度及計算時間對比Fig.3 Comparison of fitness value and computation time between PSO and Branch & Cut algorithms in the case of 4 products

論文同時對10、50、90個產(chǎn)品進(jìn)行了測試（相關(guān)數(shù)據(jù)略），結(jié)果如圖 4~6所示。當(dāng)產(chǎn)品數(shù)為 50與90時，Branch & Cut算法已經(jīng)無法在有效的時間內(nèi)給出最優(yōu)解。

圖4 10個產(chǎn)品的兩種算法適應(yīng)度對比Fig.4 Comparison of fitness value between PSO and Branch & Cut algorithms in the case of 10 products

圖5 50個產(chǎn)品微粒群算法的適應(yīng)度和計算時間Fig.5 Comparison of fitness value and computation time between PSO and Branch & Cut algorithms in the case of 50 products

圖6 90個產(chǎn)品的兩種算法的計算時間對比Fig.6 Comparison of fitness value and computation time between PSO and Branch & Cut algorithms in the case of 90 products

從結(jié)果可以看出，產(chǎn)品數(shù)目較小時Branch & Cut算法可以以較短的時間找到最優(yōu)解，但隨著產(chǎn)品數(shù)目的增加，該算法所用時間大幅上升，尤其當(dāng)產(chǎn)品數(shù)達(dá)到90時，該算法陷入“維度災(zāi)難”，只能人為終止算法。而本論文中所設(shè)計的算法，在產(chǎn)品規(guī)模增大后時間優(yōu)勢比較明顯，可以在較短的時間內(nèi)得到較滿意的方案，甚至部分方案優(yōu)于Branch & Cut算法所得的方案。

4 結(jié) 論

多分揀區(qū)的產(chǎn)品存儲問題是典型的組合優(yōu)化問題，隨著問題規(guī)模的增加，求解會變得越來越困難?？紤]到微粒群算法在求解組合優(yōu)化問題的優(yōu)勢，本文設(shè)計了多分揀區(qū)產(chǎn)品存儲的微粒群算法。通過和Branch & Cut算法相比較發(fā)現(xiàn)，當(dāng)產(chǎn)品規(guī)模較小時，Branch & Cut算法的優(yōu)勢較為明顯，但隨著產(chǎn)品規(guī)模的增大，所設(shè)計的微粒群算法時間優(yōu)勢較明顯，可以在較短的時間內(nèi)得到較滿意的解。

論文的研究結(jié)果有助于解決多分揀區(qū)的產(chǎn)品存儲優(yōu)化問題，但研究依然存在一定的局限性，如選用更大規(guī)模的產(chǎn)品數(shù)對算法進(jìn)行驗(yàn)證，以及考慮和其他啟發(fā)式算法進(jìn)行組合以進(jìn)一步提高求解效率，這將是論文進(jìn)一步研究的方向。

[1] Heragu S S, Du L, Mantel R J, et al. Mathematical model for warehouse design and product allocation[J].International Journal of Production Research, 2005,43(2): 327-338.

[2] Van den Berg J P, Sharp G P, Gademann A N, et al.Forward-reserve allocation in a warehouse with unit-load replenishments[J]. European Journal of Operational Research, 1998, 111(1): 98-113.

[3] Frazelle E H, Hackman S T, Passy U, et al. The forward-reserve problem[M]. John Wiley & Sons,Inc., 1994.

[4] Gu J, Goetschalckx M, McGinnis L F. Solving the forward-reserve allocation problem in warehouse order picking systems[J]. Journal of the Operational Research Society, 2010, 61(6): 1013-1021.

[5] 謝曉鋒, 張文俊, 楊之廉. 微粒群算法綜述[J]. 控制與決策, 2003, 18(2):129-134.

[6] 陳彥如, 單翠, 蔣陽升, 等. 多分揀區(qū) FRP的GA&SS算法設(shè)計[J/OL]. 重慶交通大學(xué)學(xué)報（自然科學(xué)版）, http://www.cnki.net/kcms/ detail/50.1190.U.20141205.1507.013.html