雙深式自動化立體倉庫的貨位優(yōu)化研究

1、遺傳算法在雙深式自動化立體倉庫貨位分配中的應(yīng)用研究 摘要：雙深式自動化立體倉庫在提高土地使用率的同時對貨位管理和分配提出了更高的要求，本文采用兩級庫位編碼的方式對雙深式立庫的貨位分配進(jìn)行研究，通過建立關(guān)于貨架穩(wěn)定性和出庫效率兩個方面的多目標(biāo)優(yōu)化數(shù)學(xué)模型，遺傳算法求解和MATLAB仿真分析，結(jié)果表明，該貨位分配優(yōu)化策略可以很大程度上提高雙深式自動化立體倉庫的效益。關(guān)鍵詞：雙深式；自動化立體倉庫；貨位優(yōu)化；多目標(biāo)優(yōu)化；遺傳算法中圖分類號：TP39 文獻(xiàn)標(biāo)志碼：AApplication of genetic algorithm in double deep shelf automated stora

2、ge and retrieval system goods lacation distribution Abstract：The double deep shelf automated storage and retrieval system(AS/RS) in improving land utilization at the same time puts forward higher requirements on goods management and distribution, this paper uses two levels location coding way for do

3、uble deep shelf AS/RS to study the distribution of goods, through establishing the multi-objective optimization mathematical model in two aspects of the shelf stability and outbound efficiency,genetic algorithm solution and MATLAB simulation analysis, the results show that this goods distribution op

4、timization strategy can be largely improve the efficiency of the double deep shelf automated storage and retrieval system.Key words：double deep shelf;automated storage and retrieval system (AS/RS);slotting optimization;multiobjec-tive optimization;genetic algorithm(GA)0 引言隨著土地資源的日益緊缺和成本的增大，傳統(tǒng)的自動化立體倉

5、庫已經(jīng)不能滿足物流產(chǎn)業(yè)的效益最大化。為了克服和突破當(dāng)下物流產(chǎn)業(yè)的這種“瓶勁”狀態(tài)，有學(xué)者提出了雙深式自動化立體倉庫1-2。但由于這種立庫最大的特點(diǎn)是一個堆垛機(jī)對應(yīng)四排貨架（每側(cè)各兩排貨架），這無疑減少了巷道和堆垛機(jī)的數(shù)量，但同時也增加了貨位管理的復(fù)雜程度。因此，如何更好地實現(xiàn)貨位優(yōu)化成為了提高雙深式自動化立體倉庫整體出庫效率、改善物流產(chǎn)業(yè)的關(guān)鍵所在。貨位優(yōu)化是在特定的貨物存儲方式下，有效掌握貨物和貨位的變化情況，按照貨物的周轉(zhuǎn)率、質(zhì)量和相關(guān)性等方面對貨位進(jìn)行實時分配。雙深式自動化立體倉庫的雙排貨架增加了臨時周轉(zhuǎn)單元，在進(jìn)行出入庫和倒庫操作時可以起到很好的貨物暫存作用，有效提高了貨物優(yōu)化的效率。

6、1 貨位配置優(yōu)化問題數(shù)學(xué)模型雙深式自動化立體倉庫和傳統(tǒng)的自動化立體倉庫在貨位優(yōu)化時需要實現(xiàn)的目標(biāo)都是一樣的，都要滿足貨架的重心最低以提高貨架穩(wěn)定性、出入庫時間最短以提高出庫效率等目標(biāo)。本文將貨架穩(wěn)定性和出庫效率作為具體的優(yōu)化目標(biāo)，但這兩個目標(biāo)之間本身又是相互矛盾的，一個目標(biāo)的實現(xiàn)總是以犧牲一個目標(biāo)為代價，這就需要建立一個多目標(biāo)優(yōu)化的數(shù)學(xué)模型3-6。2.1 問題描述與基本假設(shè)本文以某物流公司的雙深式自動化立體倉庫為研究對象，將涉及的具體問題和參數(shù)描述如下：共有n組雙排貨架，將靠近巷道的一排貨架規(guī)定為內(nèi)側(cè)，而遠(yuǎn)離巷道的一排貨架則規(guī)定為外側(cè)。則內(nèi)側(cè)貨架可編碼為2n-1，外側(cè)貨架編碼可為2n，如圖1所

7、示。所示每排貨架有p列q層，將靠近出庫臺位置雙排貨架的內(nèi)側(cè)排為第1排，靠近出庫臺位置的列記為第1列，將最底層定義為第1層。則第x排y列z層貨位的坐標(biāo)記為（x,y,x）（x=1,2,.,2n;y=1,2,.,p;z=1,2,.,q）。圖1 雙深式自動化立體倉庫結(jié)構(gòu)圖Fig.1 The structure of the double shelf automated storage and retrieval system同時采用固定貨位分配策略，也就是每個貨位只能放同一種貨物，不能放多種貨物。另外假設(shè)立庫內(nèi)（x,y,z）貨位處的貨物出庫頻率為fxyz，貨物質(zhì)量為mxyz，貨位單元格的長寬高相等均為

8、L。為了便于計算，不考慮出庫貨物耗費(fèi)的時間，只研究揀選所耗費(fèi)的時間。2.2 目標(biāo)函數(shù)及約束條件 （1）貨架穩(wěn)定性分析要想使貨架的穩(wěn)定性足夠好，就必須遵循上輕下重的原則，保證貨架上貨物的整體重心足夠低。假設(shè)將質(zhì)量為mxyz的貨物放在貨位(x,y,z)上，為了使貨物的總重心最低，從而保證貨架的穩(wěn)定，就要使貨位(x,y,z)所在的層數(shù)z和貨物質(zhì)量mxyz的乘積最小，因此有滿足貨架穩(wěn)定性最好的目標(biāo)函數(shù)S如下：（1）（2）出庫效率分析提高雙深式自動化立體倉庫的整體出庫效率的本質(zhì)就是縮短出庫貨物所用的時間，但由于堆垛機(jī)的速度是一定的，那么減小出庫貨物堆垛機(jī)的行走路程才是縮短出庫貨物時間的關(guān)鍵。由于雙深式自

9、動化立體倉庫的貨架是雙排的，因此對外側(cè)貨架上的貨物進(jìn)行出庫操作時，需要考慮內(nèi)側(cè)的貨架上是否存放有貨物。如果沒有貨物時就直接進(jìn)行出庫操作，如果放置有貨物時需要進(jìn)行周轉(zhuǎn)操作。在將內(nèi)側(cè)貨架上的貨物取出之前，先要將外側(cè)貨架上的貨物轉(zhuǎn)移到臨時周轉(zhuǎn)單元。假設(shè)某貨位的坐標(biāo)為（x,y,z），出庫臺的坐標(biāo)為（0,0,0），vy和vz分別代表堆垛機(jī)在水平方向和垂直方向的運(yùn)行速度，而vx則代表將貨物從貨架出口送到出庫臺的運(yùn)輸機(jī)的速度。由此可以得出將貨位（x,y,z）處的貨物送至出庫臺實際所耗費(fèi)的時間為：（2）其中，flag代表周轉(zhuǎn)標(biāo)識。當(dāng)flag=0時，表示內(nèi)側(cè)貨架上沒有貨物，不需要進(jìn)行貨物周轉(zhuǎn)操作；當(dāng)flag=1

10、時，表示內(nèi)側(cè)貨架上放有貨物，需要進(jìn)行貨物周轉(zhuǎn)操作。表示需要臨時周轉(zhuǎn)操作時堆垛機(jī)與取貨貨位點(diǎn)（x,y,z）對應(yīng)的內(nèi)側(cè)貨位點(diǎn)單程運(yùn)行時間。實現(xiàn)貨位優(yōu)化，實際就是要減小出庫頻率高的貨物的出庫時間，使其實際耗費(fèi)時間最少，因此滿足出庫效率最高目標(biāo)的目標(biāo)函數(shù)E如下：(3)式中表示不大于的最大整數(shù)，而表示取兩者之間的較大值。（3）約束條件根據(jù)本文假設(shè)的倉庫模型，共有n組雙排貨架，即2n排貨架，每排貨架有貨位p列q層，x、y、z分別表示貨架的排、列、層。因此，可以得到貨位優(yōu)化問題的空間約束條件為：其中，x、y、z均為正整數(shù)2.3 建立多目標(biāo)數(shù)學(xué)模型在滿足貨位空間約束條件的同時，使貨物出庫的耗費(fèi)時間最少、貨物的

11、總重心最低，建立了貨物優(yōu)化的兩個目標(biāo)函數(shù)，這些目標(biāo)函數(shù)需要同時得到優(yōu)化，因此得到本文雙深式立庫貨位分配的基本數(shù)學(xué)模型。(4)s.t.且x,y,z均為正整數(shù)3 求解貨位分配優(yōu)化問題的遺傳算法本文采用遺傳算法來研究雙深式立庫的貨位優(yōu)化問題，結(jié)合隨機(jī)權(quán)重系數(shù)法，對各個子群體分別用不同的權(quán)重系數(shù)在不同方向上搜索得到最優(yōu)解7-9。3.1 隨機(jī)權(quán)重系數(shù)法假設(shè)多目標(biāo)問題有k個目標(biāo)函數(shù)，并且需要得到它們的最小值，給每個目標(biāo)函數(shù)fi(x)(i=1,2,.,k)賦予相應(yīng)的代表其重要程度的權(quán)重wi(i=1,2,.,k)，那么該多目標(biāo)優(yōu)化問題可以表示為： (5)其中，,i=1,2,.,k且均為有3.2 適應(yīng)度函數(shù)確定

12、于算子設(shè)計（1） 適應(yīng)度函數(shù) 遺傳算法中的適應(yīng)度主要用來評價個體的優(yōu)劣程度，適應(yīng)度越大個體越好，適應(yīng)度越小個體越差。對個體進(jìn)行選擇時主要根據(jù)適應(yīng)度的大小，適應(yīng)度大的個體良好基因更容易進(jìn)入下一代，使得個體的優(yōu)良特性得以遺傳。而遺傳算法要求適應(yīng)度函數(shù)值必須是非負(fù)數(shù)，并且最大值。本文貨位分配優(yōu)化的目標(biāo)函數(shù)是非負(fù)數(shù)，且是最小值。為了構(gòu)建本文的適應(yīng)度函數(shù)，取目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，為了防止數(shù)據(jù)溢出，在目標(biāo)函數(shù)的基礎(chǔ)上加1。經(jīng)過這種轉(zhuǎn)換就得到了對應(yīng)的適應(yīng)度函數(shù)如下：(6)（2） 選擇算子設(shè)計確定每個個體的選擇概率psel，是選擇出理想的R/2對父本進(jìn)行交叉和變異操作，產(chǎn)生新個體的第一步。結(jié)合他們的權(quán)

13、重值wi，由式（5）得到相應(yīng)的適應(yīng)度，進(jìn)而就可以得到選擇概率如下： （7）其中，M代表種群規(guī)模，fmin代表當(dāng)前種群中最小適應(yīng)度值。（3） 交叉算子設(shè)計本文設(shè)計的交叉算子為二進(jìn)制交叉算子，為了保留性能更優(yōu)的個體，不是所有的父代都參加交叉操作，而是以pc的概率進(jìn)行交叉的，剩下的直接進(jìn)入下一代。由父代個體和交叉產(chǎn)生子代個體和的過程如下：首先隨機(jī)選擇一個數(shù)，計算出的值，即：父代產(chǎn)生子代的交叉運(yùn)算如下：（4） 變異算子設(shè)計本文變異算子采用多項式變異算子，父代個體以pv的概率進(jìn)行變異，產(chǎn)生性能更優(yōu)的子代個體。父代個體變異產(chǎn)生子代個體的具體操作如下：首先隨機(jī)選擇一個數(shù)，計算出的值，即：父代個體變異產(chǎn)生自帶

14、個體的計算如下：3.3 遺傳算法的實現(xiàn)流程編碼：本文采用整數(shù)排列編碼方式對染色體進(jìn)行編碼，基因位置表示固定貨位上的貨物編號，每段基因表示要存儲貨物的貨位坐標(biāo)(排、列、層)。（1） 采用隨機(jī)方法產(chǎn)生規(guī)模為M=40的初始種群；（2） 評價當(dāng)前每個個體的適應(yīng)度，選取Me個非受支配解，放入暫定集合；（3） 按照式（5）確定權(quán)重值，按照式（7）確定選擇算子，依次選擇出（M-Me）對父代個體；（4） 將步驟(3)選取的(M-Me)對父代個體進(jìn)行交叉操作后得到(M-Me)個新個體，并對它們進(jìn)行變異操作；（5） 將新得到的(M-Me)個解與暫定集合中的Me個非受支配解放到一起，進(jìn)行局部搜索得到M個新解作為新種

15、群；（6） 若遺傳次數(shù)達(dá)到規(guī)定上限100，終止運(yùn)算，否則轉(zhuǎn)到步驟(2)。4 實驗仿真及結(jié)果分析本文選取某物流公司的雙深式自動化立體倉庫進(jìn)行貨位分配優(yōu)化問題的研究，利用MATLAB進(jìn)行優(yōu)化仿真10-12，規(guī)定基本參數(shù)如下：表1 優(yōu)化仿真的基本參數(shù)Table.1 The basic parameters of optimization and simulation優(yōu)化參數(shù)取值優(yōu)化參數(shù)取值X方向移動速度vx1m/s貨架的層數(shù)6Y方向移動速度vy1m/s遺傳算法迭代次數(shù)100Z方向移動速度vz0.5m/s初始種群個體M40貨架單位長度L1m交叉概率pc0.7貨架的排數(shù)8變異概率pv0.1貨架的列數(shù)20

16、在基本參數(shù)確定以后，結(jié)合貨物信息的和雙深式自動化立體倉庫的貨位信息，進(jìn)行了大量的數(shù)據(jù)運(yùn)算和試驗仿真，得到了目標(biāo)函數(shù)值隨迭代次數(shù)在解和種群均值兩個方面的結(jié)果追蹤如圖2所示。圖2 解和種群均值追蹤結(jié)果Fig.2 The tracking results of solution and population mean value同時，將貨物信息和貨位信息分別帶入兩個目標(biāo)函數(shù)中，求出貨位優(yōu)化前后目標(biāo)函數(shù)的值，并對比如下表：表2 優(yōu)化前后目標(biāo)函數(shù)值對比Table.2 The comparison of the objective function value before and after optim

17、ization目標(biāo)函數(shù)優(yōu)化前優(yōu)化后降低值降低率（%）S2.89621.31571.580554.57150749E60.5333.1227.4145.28333058從表2中可以看出，經(jīng)過貨位分配優(yōu)化之后，本文所要優(yōu)化的貨架穩(wěn)定性和貨物出庫效率都得到很大的改善，兩個目標(biāo)的降低率分別為：54.57%、45.28%。5 結(jié)論本文采用遺傳算法完成了對多目標(biāo)優(yōu)化問題的研究，借助MATLAB軟件工具，以某物流公司雙深式自動化立體倉庫為研究對象，對其貨位分配問題進(jìn)行了優(yōu)化求解和仿真分析，有效改進(jìn)了當(dāng)前的貨位分配。對文中建立的模型試驗仿真結(jié)果表明，經(jīng)過貨位分配優(yōu)化之后，貨架的穩(wěn)定性和出庫有效率得到了很大的改

18、善，這大大降低了雙深式立庫運(yùn)營過程中的成本以及貨架的后期維護(hù)費(fèi)用，從根本上解決了物流產(chǎn)業(yè)成本高昂的現(xiàn)狀，同時也為管理人員做出科學(xué)合理的決策提供了強(qiáng)有力的理論支撐。參考文獻(xiàn)1 黃楊波,劉萬軍,劉卉.雙伸位堆垛機(jī)系統(tǒng)調(diào)度的優(yōu)化設(shè)計J.計算機(jī)工程,2010,36(1): 260-2642 赫隆譽(yù).雙伸位堆垛機(jī)的設(shè)計J. 物流技術(shù)與應(yīng)用, 2007, 12(1):98-99.3 李梅娟,陳雪波. Pareto遺傳算法在貨位配置中的應(yīng)用研究J.控制工程, 2006, 13(2): 138-141.4 田國會, 張攀, 尹建芹, 等. 基于混合遺傳算法的固定貨架揀選優(yōu)化問題研究J. 機(jī)械工程學(xué)報, 2004, 40(2): 141-144.5 吳婷.基于遺傳算法的倉儲系統(tǒng)多目標(biāo)貨位優(yōu) 化的研究D.武漢:武漢理工大學(xué), 2011.6 別文群,李擁軍.遺傳算法在立體倉庫貨位優(yōu)化分配中的研究J.計算機(jī)工程與應(yīng)用,2009,45(29):211-219.7 Lins Isis Didier, Droguett Enrique López. Redu -ndancy allocationproblems considering syste -ms with imperfect