基于病毒協同遺傳算法的自動化立體倉庫貨位優化模型

李鵬飛，馬 航

(西安郵電大學經濟與管理學院，陜西 西安 710121)

?

基于病毒協同遺傳算法的自動化立體倉庫貨位優化模型

李鵬飛，馬 航

(西安郵電大學經濟與管理學院，陜西 西安 710121)

自動化立體倉庫是一個錯綜復雜的存儲系統，貨位優化問題直接影響自動化立體倉庫的工作效率。針對自動化立體倉庫的貨位選擇問題，本文提出以出入庫效率和貨架穩定性為優化因素的貨位優化模型，并采取病毒協同遺傳算法對優化模型進行仿真。最后對仿真結果及貨位優化前，病毒協同遺傳算法優化后，傳統遺傳算法優化后三者的對比結果進行分析，結果說明病毒協同遺傳算法(VEGA)能有效實現自動化立體倉庫貨位優化，是提高貨物出入庫效率和貨架的穩定性的一種有效方法。

自動化立體倉庫；貨位優化；病毒協同遺傳算法

1 引言

近些年隨著現代物流企業對倉儲的貨位調度水平要求越來越高，自動化立體倉庫的貨位優化問題成為關注的焦點。自動化立體倉庫是現代物流、倉儲技術和計算機技術的高集成產物，它不僅可以實現貨物的自動化并行存取，而且可以提高貨物存取的效率和準確性。

國外研究有：Lam等[1]提出貨位優化問題是倉儲貨位管理的核心問題之一。Kubota等[2]提出了基于病毒進化理論的遺傳算法VEGA(Virus co-evolution genetic algorithm)，并成功將VEGA應用于旅行商問題、背包問題、自組織系統的調度問題等。Koster等[3]梳理了手工貨位分配作業流程設計與控制的決策方案，包括貨位布局設計、貨位分配方法、分區等；Ma Yongjie等[4]提出了利用遺傳算法解決倉儲調度問題，并指出傳感遺傳算法的局限性。Kim等[5]將儲位再分配問題定義為一個多物料流問題,以最小化運輸和庫存的成本。Zu Qiaohong等[6]提出一種運用混合遺傳算法的解決貨位優化問題，遺傳算法是一種模擬自然界生物進化的自搜索方法，該方法在解決最優化問題具有較大優勢，但是該種混合遺傳算法在解決貨位優化問題時會存在局部收斂的問題。

國內研究有：在貨物進行出入庫操作時，選擇合適的貨位可以提高貨物出入庫的效率，并減少出入庫的成本。當貨物存放不合適的貨位時，就需要對貨物進行貨位調整，實現貨位的優化。目前針對貨位優化問題的研究有很多，薛桂香[7]提出了一種網格任務調度模型，用以解決自動化倉儲調度問題，該種方法雖然解決了貨物調度的問題，但是并未使貨位優化達到最優。鄧愛民等[8]以醫藥為例提出一種基于時間的貨位優化多目標模型，結果表明優化前后數據記錄能有效進入倉儲自動管理環節，可以降低倉庫管理成本。鄂曉征等[9]根據汽車零配件倉儲的特點，提出了基于遺傳算法的智能倉儲貨位調度方法，結果表明零部件的出庫效率有所改善，但是遺傳算法自身具有局限性，有時不能較好的收斂。王進業和宋宇博[10]分析了旁通式自動化立體倉庫的工作特點，將遺傳算法用于模型的路徑優化，仿真結果顯示這種方法是可行的、有效的。

從上面文獻綜述可以看出，目前很多倉庫貨位優化的研究只考慮貨物重量和貨物分類擺放問題，但對于貨物出入庫效率和貨架穩定性考慮的較少。針對這些問題，考慮傳統遺傳算法不能實現全方位優化，存在局部優化缺陷，本文提出以出入庫效率和貨架穩定性為優化因素的病毒協同遺傳算法對貨位優化問題進行研究。

2 構建貨位優化多目標優化數學模型

2.1 模型假設

根據自動化立體倉庫在貨物調度時遇到的問題和應該遵循的效率原則和重力原則[11-12]，本文對模型的部分參數進行假設。

假設自動化立體倉庫共有貨架a排，每排貨架有貨位b層c列，其中距離地面最近的為第1層，距離出入口最近的為第1列，距離貨物進出口最近的為第1排，每個貨位的長寬高均為L(假設L=1即模型中取貨位長寬高為1單位大小)，模型中不用考慮巷道之間的距離，故可以將這個模型簡單理解為一個三維立體空間的點集，也就是處于第x排第y層第z列的貨位可以定義坐標為(x，y，z)，其中xyz均為正整數[13]。

同時假設倉庫中可以存放N種不同的貨物，并且每種貨物只允許存放在一個貨位中，不允許同一貨位中存放不同類型的貨物。每個貨物有其基本信息，貨物的重量用M表示，貨物的周轉率用P表示，其中M的單位是kg，P的單位是頻次即某貨物在一定時間內的周轉次數，本文用P次/月表示。

根據以上描述，假設總結如下：

(1)立體倉庫模型的整體布局被定義為一個標準的空間長方體的點集合(x，y，z)，暫以理想模型考慮。

(2)貨物的種類已知，相同種類的物品可以合并托盤放在同一貨架中(大小不得超過貨位容量)，而且貨物重量要均勻分布。

(3)考慮到曲線運動計算的復雜性，本文貨物在進出庫時是按照直線運動。

(4)本模型是一個三圍立體的空間模型，為簡單起見，假設貨位的長寬高均為單位1，貨位的體積為1m3。

(5)堆垛機存取貨物的時間暫時不記，僅考慮傳送帶和堆垛機的運行速度。

(6)所有貨架的托盤尺寸都是相同的，但是托盤上貨物重量不一定相同。

(7)每個巷道只有一臺堆垛機。

(8)傳送帶只沿著X軸方向水平運動，運行速度是Vx；堆垛機只在Z軸方向上做水平移動速度和垂直移動，運行速度分別為Vz和Vy，單位均為米/每秒。

2.2 模型分析建立過程

根據模型的假設條件描述，本文模型主要優化目標是提高出入庫的效率，降低貨位重心并提高貨架穩定性[14]。模型分析如下。

2.2.1 出入庫效率分析

為了提高出入庫的效率，就必須考慮出入庫距離和時間兩個因素，若假設條件中Vx=Vy=Vz，即傳送帶的搬運速度和堆垛機的水平和垂直速度相同，距離和時間就是正比關系，無論是距離最短還是時間最短都是一樣的；若假設中的Vx≠Vy≠Vz，即傳送帶的搬運速度和堆垛機的水平垂直速度不同，則在判斷出入庫效率的時候就必須主要考慮時間因素，因為時間是衡量效率的標準之一。假設立體貨架某貨位的坐標是(x,y,z)，貨物進出口坐標記為原點(0,0,0)，由于傳送帶和堆垛機的移動不能按照距離最短的直線移動。根據提高倉庫進出貨效率的就近原則和周轉率大小原則，即使所有貨物的出入庫時間和周轉率頻率的乘積之和最小。其中，Pxyz為貨位在貨位(x,y,z)處的周轉率，建立數學模型的目標函數f1(x,y,z)如公式(1)所示：

(1)

2.2.2 貨架穩定性分析

任何一個倉庫的立體貨架，它的承重能力都是有限的，所以在存放貨物的時候，要想保持貨架有良好的穩定性就要使貨架的整體重心最低。也就是說要將較重的貨物放在貨架的底層，將較輕的貨物放在立體貨架的上層。在實際問題中，立體貨架的穩定性主要和重心有關，其重心越低，貨架的穩定性就越好。因此，按照上輕下重的擺放原則可以減輕貨架的重心，從而達到提高貨架穩定性的效果。

在本文模型當中，假設貨位(x,y,z)處貨物的質量為Mxyz，根據貨架承重遵循“上輕下重”重心最低的存儲原則，即每個托盤上的貨物質量與其所在層的乘積之和最小，此時貨架的穩定性最好，由此可以建立數學模型的目標函數如公式(2)所示：

(2)

因此，根據貨位優化的目標可以得到多目標數學模型，如公式(3)所示：

(2-3)

模型中變量說明：

Pxyz為貨位在貨位(x,y,z)處的周轉率，即根據數據可以得的已知變量；

Mxyz為貨架第x排第y層第z列貨物的質量，為已知變量；

L為貨位的單位長度，模型中視為1，為已知變量。

2.3 問題轉化

在多目標優化問題求解時需要綜合考慮各個目標，使得各個目標函數的函數值都在給所定的區域上盡可能地向著求解的方向靠攏或接近，而達到多個目標的最優化。本文采用病毒協同遺傳算法，結合權重法，將算法進化分解成若干群體，各子群體在不同的權重系數進行不同方向上的搜索獲得妥協解[15]。

給每個目標函數fi(x)(i=1,2,…，q)各自賦予權重wi(i=1,2…，q)，此處權重wi表是各子目標對fi(x)的重要程度。那么，多目標優化問題可以表示為，如公式(4)所示：

(4)

根據上文分析，立體倉庫貨位優化問題是由出入庫效率和貨架穩定性兩個目標組成的多目標優化問題，通過公式(4)可將多目標優化問題轉化為單目標優化問題進行求解，可描述為公式(5)：

F(x,y,z)=ω1f1(x,y,z)+ω2f2(x,y,z)

(5)

2.4 權重的確定

確定權重的方法包括德爾菲法、AHP層次分析法和熵值確定權重法等，其中最常用的是AHP層次分析法，而本文將德爾菲法和AHP層次分析法相結合，步驟如下：

(1)貨位優化的目的是為了降低庫存成本并提高出入庫效率。根據實際經驗可以得出，對于出入庫效率和貨架穩定性兩個因素，前者要比后者重要，根據系統工程的標度定義aij(如表1所示)，本文選取1、3、5、7、9標度。

表1 判斷矩陣標度定義

(2)根據德爾菲法的基本原理，本文邀請12位專家組成專家小組，并對標度的選擇進行三次投票，投票結果如表2所示。

表2 德爾菲法投票結果

表3 一致性檢驗

綜上所述，變型可得貨位優化模型為，如公式(2-6)所示：

(6)

3 病毒協同遺傳算法

3.1 病毒協同遺傳算法的原理

病毒協同遺傳算法基本思想是優秀基因的識別和優秀基因的增長，其基本操作步驟主要是首先初始化種群，將種群中的每一個個體作為一個基因，經過選擇、交叉和感染操作過程，獲得適應度函數最優解[16-17]。病毒協同遺傳算法的基本流程如圖1所示。

圖1 病毒協同遺傳算法基本流程圖

3.2 病毒個體的感染操作

病毒個體的感染包括如下三個操作：

(1)感染(Infection)操作

主個體中的染色體相應的基因被病毒染色體感染，進化產生新的病毒染色體因，從而產生進化解。如果在主個體在受到病毒個體以Pinfect概率感染后適應度值變小了，則丟棄感染前的主個體，選擇感染后的主個體，如圖2所示。

圖2 感染操作

(2)復制(Copy)操作

復制操作一般存在兩種情況，一種是初始病毒復制，另一種是非初始病毒復制。初始病毒復制是通過“無感染能力”的病毒個體的復制操作產生新的病毒個體，如圖3a所示；而非初始病毒復制則是病毒個體從主個體獲取基因改變自己的基因，從而產生新的病毒個體，如圖3b所示。

圖3a 初始病毒復制操作

圖3b 非初始病毒復制操作

(3)刪減(Cut)操作

病毒染色體每個基因以概率Pcut用通配符進行替換，用以刪減個體部分基因，減少病毒個體的長度，降低進化的計算能力，如圖4所示。

圖4 刪減操作

3.3 病毒協同遺傳算法實現

病毒協同遺傳算法實現步驟如下：

(1)編碼

模型采用實數編碼方式，因為實數編碼方式的染色體的空間拓撲結構和它的表現型的空間拓撲結構是一致的。編碼方式如下：

①條染色體代表一種貨位分配方式。

②一條染色體可以分為N段，每段代表一個基因，每個基因代表一個貨位的位置(x,y,z)，每個基因都對應一個貨物的編號，其中N為這個染色體中貨物的個數。

③每段基因都是由三位整數表示，其中百位代表x的值，十位代表y的值，個位代表z的值。

假設分揀緩存區有4個貨物要進行入庫，其中1號貨物要放在(1，2，3)的位置上；2號貨物要放在(2，2，3)的位置上；3號貨物要放在(3，2，4)的位置上；4號貨物要放在(4，4，4)的位置上。那么“123”、“223”、“324”、“444”分別表示一個染色體的基因，這時候染色體就形成了一個解“123223324444”，表示一種貨位分配的方式。如圖5所示。

圖5 編碼方式

(2)初始化種群

在初始化種群的時候，可先設置種群規模M，然后根據個體長度為N，采用隨機配的方法產生M個這樣的個體，這就完成了種群規模為M的初始化工作。

(3)選擇操作

在模型中選用輪盤賭選擇(Roulette wheel selection)方法，它是比例選擇中較為常用的方法，其基本思想是：個體被選中的概率取決于該個體的相對適應度。而相對適應度如公式(7)所示：

(7)

(4)交叉操作

交叉選擇的是實屬交叉，實數交叉又分為離散交叉和算術交叉，本文使用的是離散交叉，離散交叉是在兩個父代個體的編碼向量都選取0.5的概率進行交換，從而生產新的向量。這種兩兩配對的方式是病毒協同算法進行感染操作的第一步。假如兩個父代個體的n維向量如公式(8)所示：

(8)

則交叉隨機選擇第k個以后的分量，生成兩個新的個體向量如公式(9)所示：

(3)

(5)病毒個體感染操作

利用病毒染色體基因替換主染色體中相應的模式基因，從而產生新的主個體。每個病毒個體以一定概率Pinfect感染每個主個體，如果主個體感染后的適應度值減小了，則用感染后的主個體替換感染前的主個體。一個個體的適應度值越小，它被遺傳到下一代種群中的概率也就越大，遺傳算法種群進化的過程中，基本上都是根據適應度函數作為優勝劣汰的標準。

4 仿真與結果分析

本文采用MATLAB7.0對模型進行仿真，數據收集如下：

(1)倉庫基本參數(見表4)

表4 倉儲基本參數信息

(2)貨物基本信息收集

貨物的基本信息如表5所示，本文選擇17件貨物作為仿真數據，其中貨物的重量是貨物分揀后托盤的重量。而貨物的周轉率是根據以往數據算出的，即平均每個月該貨物進出倉庫的次數。

表5 貨物基本信息

(3)遺傳算法參數選取

遺傳算法參數的選取會影響最終輸出結果的優劣，因此在進行仿真的時候要對參數進行測驗。但是考慮仿真結果客觀性，程序中初步選取的遺傳算法參數如表6所示。

表6 遺傳算法參數選取

利用收集的仿真數據，通過MATLAB仿真實驗得出結果如圖6所示。從圖中可以看出VEGA適應度值隨著迭代次數逐漸降低，相比GA較早出現收斂，而且VEGA曲線幾乎一直低于GA曲線。可見，VEGA算法相比傳統的GA算法在解決貨位優化問題上具有較好的收斂性，同時也具有較快的收斂速度，避免了傳統遺傳算法陷入局部最優解的缺陷，從而提高了自動化立體倉庫的貨位優化水平。

圖6 VEGA與GA算法MATLAB仿真結果

病毒協同遺傳算法與傳統遺傳算法的貨位優化的數據結果如表7所示，結果分析如圖7與圖8所示，包括貨位優化前、GA優化后和VEGA優化后的數據結果。

(1)從圖7可以看出，優化前較GA和VEGA優化后的貨物出入庫距離更長，說明通過兩種算法優化后的貨位距離出口更近；比較GA與VEGA的算法結果，VEGA優化后的貨物出入庫距離較短。

(2)從圖8可以看出，優化前較GA和VEGA優化后的貨物出入庫時間更長，說明通過兩種算法優化后的貨位出入庫時間更短；比較GA與VEGA的算法結果， VEGA優化后的貨物出入庫時間較短。

表7 VEGA與GA仿真數據結果

圖7 優化結果數據對比分析(一)

圖8 優化結果數據對比分析(二)

(3)穩定性數值越小說明貨架穩定性越好，從圖9可以看出通過GA和VEGA優化后的貨架穩定性較優化前更穩定，而VEGA相比GA優化后的穩定性系數更低一些，說明通過VEGA優化后的貨架穩定性更好。

圖9 優化結果數據對比分析(三)

通過病毒協同遺傳算法與傳統的遺傳算法在貨物出入庫距離、貨物出入庫時間、貨架穩定性等方面的對比，可以發現經過優化后，貨物的擺放更加規范，表明病毒協同遺傳算法能有效解決貨位優化問題，并驗證了提出方法的有效性。

5 結語

貨位優化問題是倉儲貨位管理的核心問題之一，本文得出以下三個結論：

(1)病毒協同遺傳算法相比傳統的遺傳算法具有較好的收斂性，擁有較快的收斂速度，避免了傳統遺傳算法陷入局部最優解的缺陷，從而提高了自動化立體倉庫的貨位優化水平。

(2)病毒協同遺傳算法優化后，提高自動化立體倉庫的貨物出入庫效率。能夠縮短貨物出入庫距離并且減少貨位入庫時間。

(3)病毒協同遺傳算法穩定性系數較低，能夠更好的提高貨架穩定性。

綜上所得，通過病毒協同遺傳算法能夠優化自動化立體倉庫貨位，提高出入庫效率和貨架穩定性。

[1] Lam C H Y, Choy K L, Chung S H.Framework to measure the performance of warehouse operations efficiency [C]. Proceedings of the 8th International Conference on Industrial Informatics,Oskar,Japan,July 13-16,2010.

[2] Kubota N, Arakawa T, Fukuda T,et al. Fuzzy manufacturing scheduling by virus-evolutionary genet- ic algorithm in selforganizing manufacturing system[C]//Proceedings of the 6th international conference on Fuzzy systems. Barcelona:IEEE,July 5,1997:1283-1288.

[3] de Koster R,Le-Duc T,Roodbergen K J.Design and control of warehouse order picking:A literature review [J].European Journal of Operational Research,2007,18 (12):48-50.

[4] Ma Yongjie, Yun Wenxia, Hou Wenjing. The research progress of genetic algorthm in the large warehouse system [C]// Proceedings of the 2010 Conferences on Optoelectronics and Image Processing,Barcelona:IEEE,November 11-12,2010:616-620.

[5] Kim K H,Park K T.Dynamic space allocation for temporary storage [J].International Journal of Systems Science,2003,34(1):11-20.

[6] Zu Qiaohong, Cao Mengmeng. Slotting optimization of warehouse based on hybrid genetic algorithm[C]// Proceedings of the 6th International Conference on Pervasive Computing and Applications,Bacelona:IEEE,October 26-28,2011:19-21.

[7] 薛桂香.基于智能優化算法的網格任務調度策略研究[D].天津:天津大學,2008.

[8] 鄧愛民,蔡佳,毛浪. 基于時間的自動化立體倉庫貨位優化模型研究[J]. 中國管理科學,2013,21(6):107-112.

[9] 鄂曉征,祖巧紅,曹萌萌.基于遺傳算法的汽車零件自動化倉儲貨位優化[J].系統仿真學報,2013,25(3):430-435+444.

[10] 王進業,宋宇博.旁通式自動化立體倉庫揀選作業和出口選擇的組合優化[J].河北科技大學學報,2015, 36(1):36-40.

[11] 張雄飛,柳少軍.一種改進遺傳算法及在多目標優化中的應用[J]. 系統管理學報,2007,16(3):315-319.

[12] 張群,顏瑞.基于改進模糊遺傳算法的混合車輛路徑問題[J]. 中國管理科學,2012,20(2):121-128.

[13] 常發亮,劉增曉,辛征,等.自動化立體倉庫揀選作業路徑優化問題研究[J]. 系統工程理論與實踐, 2007,27(2):139-143.

[14] 曹浪財,羅鍵. 可視化自動倉儲系統設計與貨位優化[J]. 廈門大學學報(自然科學版),2012,51(1):46-50.

[15] 孫艷豐. 基于GATS混合策略的多目標優化算法[J]. 管理工程學報,2000,14(4): 4-7.

[16] 胡仕成,徐曉飛,李向陽. 項目優化調度的病毒協同進化遺傳算法[J]. 軟件學報,2004,15(1):49-57.

[17] 戢守峰,李峰,董云龍,等. 基于遺傳算法的三級逆向物流網絡設計模型研究[J].中國管理科學,2007, 15(6):86-91.

Virus Based on Cooperative Genetic Algorithm Automated Warehouse Space Optimization Model

LI Peng-fei, MA Hang

(Xi'an University of Posts & Telecommunications,School of Econonnics and Management, Xi'an 710061,China)

Automated warehouse is an intricate system of storage, and slotting optimization problems directly affect the efficiency of the Automated Warehouse. To solve the dilemma of location selection of automatic stereo warehouse, a Slotting Optimization model which take the out of storage efficiency and shelf stability of storage as its optimization factors is proposed, the Multi-objective mathematical model of Slotting Optimization is established. According to the actual conditions of Automated Warehouse, with the help of Strategy Set Transformation, Delphi method and the Analytic Hierarchy Process(AHP) are used to determine the weight. And virus combined with genetic algorithm is taken to simulate the optimization model. In the MATLAB software environment, the Multi-objective genetic algorithm for virus is utilized to calculate the model solution. Finally, the results comparison among the simulation of the data before Slotting Optimization, the data after virus combined with genetic algorithm and the data after traditional genetic algorithm indicates that Virus Cooperative Genetic Algorithm(VEGA) can effectively optimize the automation stereoscopic warehouse slotting. It is also a kind of effective way to improve the efficiency of goods out of storage and stability of shelf.

automated warehouse; mization of the goods location; virus cooperative genetic algorithm

1003-207(2017)05-0070-08

10.16381/j.cnki.issn1003-207x.2017.05.009

2016-01-11；

2016-05-26

陜西省科技廳科研項目(2014K05-62)；陜西省教育廳科研項目(14JK1647)；陜西省社科基金重大項目(2016ZDA10)；西安郵電大學西郵新星團隊資助

李鵬飛(1975-)，男(漢族)，陜西戶縣人，西安郵電大學經濟與管理學院，博士，教授，研究方向：郵政及物流信息化，E-mail:lpf@xupt.edu.cn.

F273；C935

A