1、遺傳算法在雙深式自動化立體倉庫貨位分配中的應用研究 摘要：雙深式自動化立體倉庫在提高土地使用率的同時對貨位管理和分配提出了更高的要求，本文采用兩級庫位編碼的方式對雙深式立庫的貨位分配進行研究，通過建立關于貨架穩定性和出庫效率兩個方面的多目標優化數學模型，遺傳算法求解和MATLAB仿真分析，結果表明，該貨位分配優化策略可以很大程度上提高雙深式自動化立體倉庫的效益。關鍵詞：雙深式；自動化立體倉庫；貨位優化；多目標優化；遺傳算法中圖分類號：TP39 文獻標志碼：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 引言隨著土地資源的日益緊缺和成本的增大，傳統的自動化立體倉

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

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

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

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

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

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

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

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

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

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

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

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

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

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