基于微粒群技術的多分揀區產品存儲的算法設計

陳彥如 楊 璐 魏朝恒 曾東紅

1. 西南交通大學，經濟與管理學院，成都 610031

2. 西南交通大學，交通運輸與物流學院，成都 610031

0 引 言

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

根據分揀區設置的數目可將 FRP問題分為單分揀區FRP與多分揀區FRP。目前單分揀區FRP的研究成果較為豐富[1-4]，由于該問題屬于NP難問題，因此該問題的求解大多考慮啟發式算法。而多分揀區FRP問題研究成果較少，同時因為涉及多個分揀區的協調優化，求解更為復雜。考慮到精確算法的局限性及微粒群算法在求解大規模組合優化問題的優勢[5]，本文嘗試設計求解多分揀區 FRP的微粒群算法，并用算例驗證了該算法的有效性。

1 模型描述[6]

符號說明：

i——產品種類， i = 1 ,2,3,… ,I ；

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

k——分揀區， k = 1 ,2,3,…,K

Ck——分揀區k單位面積的建設成本；

Sk——分揀區k的空間；

aij——產品i以存儲方式 j存儲時，每單位可存儲產品i的個數；

Di——產品i的需求量；

Cr——產品i以存儲方式 j存儲在存儲區的分

ij

揀成本；

多分揀區產品存儲模型可描述如下：

2 算法設計

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

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

2.1 粒子編碼

本階段需要對問題的可行解進行編碼。考慮到將C種產品以J種存儲方式放在K個分揀區，因此所設計的粒子總長度為C*J*K+C+K。粒子包括三個部分，第一部分長度為C*J*K，表示C種產品以J種方式在K個分揀區的存儲方案。第二部分長度為C，表示C種產品的存儲方式是否發生改變。第三部分長度為K,表示K個分揀區是否建立。

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

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

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

2.2 初始化粒子群

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

因為每個粒子存在著諸多的屬性，要想更好地描述粒子群的性質，需要首先聲明一個粒子群的結構體。聲明如下：

struct population //定義粒子群結構體

{

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

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

long max1,max2,max3,fitness;//本粒子適應值string pstr;//歷史最優粒子

long pfitness;//歷史最優適應值

};

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

按照粒子群結構體的特點，隨機生成一定規模的具有多屬性的粒子群。

2.3 粒子評價

判斷粒子的質量優劣，主要依據模型的目標函數，即來進行。質量越優的粒子目標函數值越大。

2.4 更新最優值

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

2.5 粒子位置與速度更新

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

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

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

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

3 算例驗證

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

表1 產品在存儲區的分揀成本Tab.1 Picking costs in a reserve area

表2 產品在分揀區的分揀成本Tab.2 Picking costs in a forward area

表3 產品處理成本Tab.3 Handling costs

表4 產品補貨成本Tab.4 Replenishment costs

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

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

論文同時對10、50、90個產品進行了測試（相關數據略），結果如圖 4~6所示。當產品數為 50與90時，Branch & Cut算法已經無法在有效的時間內給出最優解。

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

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

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

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

4 結 論

多分揀區的產品存儲問題是典型的組合優化問題，隨著問題規模的增加，求解會變得越來越困難。考慮到微粒群算法在求解組合優化問題的優勢，本文設計了多分揀區產品存儲的微粒群算法。通過和Branch & Cut算法相比較發現，當產品規模較小時，Branch & Cut算法的優勢較為明顯，但隨著產品規模的增大，所設計的微粒群算法時間優勢較明顯，可以在較短的時間內得到較滿意的解。

論文的研究結果有助于解決多分揀區的產品存儲優化問題，但研究依然存在一定的局限性，如選用更大規模的產品數對算法進行驗證，以及考慮和其他啟發式算法進行組合以進一步提高求解效率，這將是論文進一步研究的方向。

[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] 陳彥如, 單翠, 蔣陽升, 等. 多分揀區 FRP的GA&SS算法設計[J/OL]. 重慶交通大學學報（自然科學版）, http://www.cnki.net/kcms/ detail/50.1190.U.20141205.1507.013.html