基于多種群空間映射遺傳算法的立體倉庫儲位優(yōu)化

隋 振, 張?zhí)煨? 吳 濤, 陳華銳

(吉林大學 通信工程學院, 長春 130012)

貨物在流通過程中, 會有大量的庫存積壓, 從而產(chǎn)生儲位分配模式混亂的問題, 對囤積的貨物進行合理的擺放是物流業(yè)中的重要環(huán)節(jié). 一旦倉儲環(huán)節(jié)存在問題, 則后續(xù)的生產(chǎn)和流通都將無法對接, 運輸系統(tǒng)將發(fā)生混亂.

目前, 對儲位優(yōu)化問題已有大量研究, 在系統(tǒng)模型方面, Park等[1]提出了物品關聯(lián)度的數(shù)學模型, 并設計了一種啟發(fā)式算法, 再結合傳統(tǒng)遺傳算法解決問題； Muppani等[2]用物品的臨界值指數(shù)(COI)值作為檢測貨物擺放優(yōu)劣的一種指標； 李小笠等[3]改進了貨位分配模型, 加入了貨物分區(qū)的概念； 蔡安江等[4]不僅研究了分離式倉庫優(yōu)化問題, 還對堆垛機的調度方案進行了探究, 將其視為一個旅行商問題； 張鵬[5]對倉儲系統(tǒng)用Flexsim設計了一種仿真軟件, 上述幾種不同的改進方法, 都將儲位優(yōu)化問題引入到約束條件中, 使數(shù)學模型更復雜.

對于優(yōu)化算法的研究, Poulos等[6]選擇遺傳算法解決此問題, 用交叉算子的方法改進了原有算法, 最終得到較好的結果, 也證明了啟發(fā)式算法對組合優(yōu)化問題有較大幫助； Deng[7]也通過遺傳算法進行尋優(yōu), 計算涉及到3個實際的優(yōu)化方向, 進一步靠近工業(yè)領域； 李鵬飛等[8]提出了一種病毒協(xié)同遺傳算法, 解決了多目標優(yōu)化模型； 焦玉玲等[9]也對傳統(tǒng)遺傳算法進行了改進. 算法的不斷更新使求解的效率逐步提升. 但針對不同類型的倉庫, 當存取任務不斷改變時, 儲位分配的方式也應隨著變化的需求進行相應地調整. 在算法方面, 多數(shù)啟發(fā)式算法在尋優(yōu)過程中易陷入局部最優(yōu), 性能還可以提升.

為解決上述問題, 本文構建一個帶權重的多目標組合優(yōu)化模型, 同時提出一種改進的遺傳算法, 從編碼方式、 種群構成和交叉算子等方面對儲位分配問題進行改進, 使其具有較強的針對性, 仿真實驗結果表明, 該算法易跳出局部最優(yōu), 尋優(yōu)能力更好, 并分析了算法的適用范圍.

1 模型構建

1.1 運行環(huán)境及優(yōu)化目標的選擇

本文以分離式貨架結構為系統(tǒng)的運行環(huán)境, 如圖1和圖2所示, 其中z軸為倉庫高度,y軸為倉庫行數(shù),x軸為倉庫列數(shù), 每個貨格H都有一個靜態(tài)坐標(a,b,c)與其對應, 對于單個貨格, 其長、 寬、 高分別用dx,dy,dz表示,Wx為巷道寬度,Wy為起始寬度,x軸方向上所有y=0的點皆為入庫起點.

若用靜態(tài)坐標(a,b,c)找到實際空間位置, 即動態(tài)坐標(xk,yk,zk), 有如下變換公式：

約束條件為

(4)

其中Nx,Ny,Nz分別表示貨架的總列數(shù)、 總行數(shù)和總層數(shù), 使用約束條件一是為避免因為忽略了巷道寬度對實際距離的影響, 二是為可在隨意更改Wx和Wy的條件下不用修改(a,b,c), 降低了重復計算次數(shù), 為后續(xù)算法計算和仿真實驗奠定基礎.

在實際運行過程中, 有任務T={S1,S2,…,Sn}, 其中S1,S2,…,Sn為貨物, 每個貨物Si都有下屬信息{P,M,K},P為貨物周轉率,M為貨物質量,K為貨物類別.儲位分配方式應滿足以下要求： 周轉率大的貨物更靠近出口, 貨架的整體重心要盡可能低, 盡量縮短同類物品的擺放距離[10].因此, 本文根據(jù)P,M,K分別構建相應的目標函數(shù), 使其與動態(tài)坐標(xk,yk,zk)相聯(lián)系, 并進行組合優(yōu)化.

1.2 效率最優(yōu)模型構建

周轉率也可表示為貨物出入庫的頻率, 需要多次進出庫的物品離倉庫入口的距離應盡可能小, 這樣會縮短揀選時間, 達到提高分揀速度和效率的要求, 建模方案為

(5)

其中：n為本次任務中入庫貨物的總數(shù)量；Pi為第i個物品的周轉率；Ti為存貨時間,

(6)

(7)

(8)

式中Tiy,Tiz分別表示y軸和z軸方向所需的時間,vy,vz分別表示提升機在y軸和z軸所需的速度, 由于該模型的x軸為入口, 所以不考慮該方向時間, 其中坐標yi,zi的值是經(jīng)過式(2),(3)變換后的值, 故通過式(6)～(8)可得最終的周轉率模型為

(9)

1.3 穩(wěn)定性模型構建

貨物在貨架的擺放過程中, 如果總質量分配不合理, 即重心過于偏向某一側, 會導致貨架傾覆, 因此一個穩(wěn)定的貨架可保證流通的安全性, 因此該目標函數(shù)設計為

(10)

其中Mi為第i個貨物的質量, 單位為kg.求式(10)最小值的目的是使貨架結構在垂直方向(z軸)上達到穩(wěn)定, 即z軸方向數(shù)值較大,f2值越大, 貨物的整體重心越高.

1.4 離散程度模型構建

在處理任務時, 通常是同類物品一起出現(xiàn), 因此縮短彼此的距離可減少堆垛機反復調度的時間.物品中心坐標的計算方法為

(11)

其中(xkm,ykm,zkm)為第k類物品的中心坐標.則物品相對于該點的距離可表示為

Xi=((xki,ykj,zkk)-(xkm,ykm,zkm)),

(12)

(13)

(14)

其中fk為第k類貨物的離散程度,Xi表示距離向量, ‖Xi‖2表示每個貨物與中心坐標的距離差值,kn為類別總數(shù), 由式(12)～(14)可知離散程度模型為

(15)

1.5 組合優(yōu)化模型

在得到上述3個獨立模型的基礎上, 經(jīng)過組合后得到的多目標函數(shù)將不再擁有單方向的最優(yōu)解, 只能得到一個綜合考慮后的可行最優(yōu)解, 整合后的數(shù)學模型為

f(x,y,z)=f1(x,y,z)+f2(x,y,z)+f3(x,y,z).

(16)

若對3個目標有不同的需求, 可在每個獨立函數(shù)前增加權重系數(shù)ω, 最終的優(yōu)化模型為

minf(x,y,z)=ω1f1(x,y,z)+ω2f2(x,y,z)+ω3f3(x,y,z),

(17)

約束目標為

(18)

2 改進遺傳算法尋優(yōu)

遺傳算法在解決組合優(yōu)化問題上效果較好, 其模擬自然界的適者生存法則, 通過生成種群、 染色體的選擇、 交叉、 變異等步驟, 逐代選擇優(yōu)秀個體, 直到滿足終止條件[11].算法的優(yōu)點是其可以給出多目標優(yōu)化問題的可接受解, 但搜索速度較慢, 易陷入局部最優(yōu), 且編碼過程繁瑣, 因此本文提出空間映射編碼, 多種群協(xié)同尋優(yōu), 最后結合爬山算法設計一種改進的遺傳算法.

2.1 空間映射編碼

圖3 空間映射轉換Fig.3 Space mapping transformation

編碼是遺傳算法的起點, 它影響后序所有步驟的計算.當一個任務T到來時, 其包含若干個待處理貨物S1,S2,…,Sn, 每個貨物Si在倉庫模型中都有唯一的靜態(tài)坐標(a,b,c)與其對應.假設貨格總數(shù)為n, 則解集空間就是n個正整數(shù)序列, 每個正整數(shù)對應一個(a,b,c), 映射方式如圖3所示.以z,y,x軸的順序依次進行編碼, 第一個坐標(1,1,1)的編號m=1, 編碼步驟如下：

1)c+1,m+1, 直到c=Nz；

2)c=0,b+1, 返回步驟1), 直到b=Ny;

3)b=0,a+1, 返回步驟1), 直到a=Nx時, 編號結束.

對應關系為

f(a,b,c)=m,m∈[1,Nz·102+Ny·10+Nx], 且m為整數(shù).

(19)

該編碼方式將三維空間解集降為一維線性解集處理, 常規(guī)二進制編碼較復雜, 且其在高維空間中易導致無效交換.例如(1,2,3)和(5,2,7), 這兩個貨位如果交換了y軸信息, 則其結果是無效的, 如圖4所示.而對于空間映射編碼, 用唯一整數(shù)去對應靜態(tài)坐標, 避開了對自身內部信息進行交換的問題, 只存在整體交換, 且交換后不存在無效結果, 如圖5所示.在整個算法流程中, 所有數(shù)據(jù)都將以編號的形式參與計算, 可讀性更高.

2.2 初始種群的生成

若任務T中有n個待入庫貨物, 假設種群規(guī)模為m, 則初始種群是一個m×n的矩陣Xa=(m1,m2,…,mm)T,Xa中有m個行向量, 這樣的向量稱為一個染色體, 每個染色體中包含n個元素:

mi=(ai1,ai2,…,ain)1n,

(20)

其中aij為通過上述編碼方式得到的貨格編號.

2.3 適應度函數(shù)

由于本文所求是一個最小值, 所以單個貨物的適應度函數(shù)為

(21)

其中fit(aij)的值越大, 越符合要求.對于一條染色體mi, 其適應度為

(22)

2.4 多種群協(xié)同尋優(yōu)

通過fit(m)已經(jīng)求得種群中每個染色體的適應度, 經(jīng)過概率的歸一化后, 進行優(yōu)質子代的選擇：

(23)

其中Pm為每條染色體被選擇的概率, 通過保留概率PGA, 使得在原種群中, 有一定幾率留下(m×PGA)個優(yōu)秀個體.本次操作后, 得到的種群矩陣稱為父類種群, 表示為Xb=(b1,b2,…,br)T.在父類種群Xb中, 由于概率選擇導致存在多個相同的染色體, 染色體出現(xiàn)次數(shù)越高, 證明適應度越好, 通過選擇機制篩選出了更適應問題的結果.

空間映射編碼雖然減少了無效交換, 但由于不產(chǎn)生初始解集外的新解, 所以也更易陷入局部最優(yōu).為解決該問題, 在Xg生成時, 同時再生成k個父類種群Xbk=(bk1,bk2,…,bkr)T, 該過程相當于增大了種群規(guī)模, 在達成終止條件時, 選出k個種群中的最優(yōu)解.剩下(m-r)個染色體由Xb中兩兩相鄰的染色體進行交叉運算, 若滿足交叉概率Pc,

(24)

圖6 第k個/單個種群的進化演變方式Fig.6 Evolution mode of kth/single population

則進行交叉產(chǎn)生新的子代個體, 本文所用的交叉方式是隨機生成兩個整數(shù)e和s, 在染色體對應的位置上進行兩兩交換, 避開了產(chǎn)生不可行解的可能, 如圖6所示.通過變異概率Pr, 對單個染色體的某個或幾個位置在編號范圍內進行更改, 變異的范圍和產(chǎn)生的新值均為可行解, 組成待選種群Xg.

2.5 爬山算法

對Xg中的每條染色體, 都生成兩個隨機點位e和s, 類似于交叉時的操作, 對點位中所有編號進行倒序排列并重新寫入原染色體, 計算當前的染色體適應度, 若fit(gi)

(25)

爬山算法屬于局部范圍內尋優(yōu), 本文只在鄰域內搜索一次, 即fit(gi)與fit(gj)之間的比較, 在局部解中加強尋優(yōu)效果, 再通過多種群并行求解的方式跳出局部最優(yōu), 二者結合使優(yōu)勢互補.

至此第一次子代生成結束, 同時產(chǎn)生了k個子代種群Xc, 其中每個都包含了r個父代染色體和(m-r)個經(jīng)過交叉變異的優(yōu)秀個體, 若未達到迭代次數(shù)要求, 則將Xck視為下一輪計算中的Xa, 每輪解集的單個種群更新過程如圖6所示.解集的尋優(yōu)可視為一種矩陣拼接過程, 其中虛線表示閾值r.重復上述過程, 若滿足迭代次數(shù), 則根據(jù)式(21)計算出適應度最高的一組解Xfin, 將該解作為最終結果.改進的遺傳算法流程如圖7所示.

圖7 改進的遺傳算法流程Fig.7 Flow chart of improved genetic algorithm

3 仿真實驗與結果分析

3.1 實驗參數(shù)設置

本文使用MATLAB2016a對改進的遺傳算法進行仿真實驗, 為驗證模型和算法的有效性和穩(wěn)定性, 將系統(tǒng)參數(shù)設定為： 巷道寬度和起點寬度分別為2 m和1 m, 倉庫的容量為10×10×4, 共400個固定貨格, 貨格長度為1 m, 堆垛機在x軸和y軸的運行速度分別為1 m/s和0.6 m/s. 遺傳算法的參數(shù)設為： 最大迭代次數(shù)為1 000, 種群規(guī)模為100, 交叉概率為0.8, 變異概率為0.2, 協(xié)同種群數(shù)量為10, 保留概率為0.2. 實驗選用某圖書類倉庫的入庫任務信息列于表1. 其中, No.為貨物編號, 任務T中共有30個待入庫貨物, 容量S=30,P為周轉率,M為質量,K為類別, 這里已用數(shù)字進行了實際含義的替換.

表1 入庫任務信息

3.2 算例分析

3.2.1 算法有效性驗證

在目標函數(shù)(17)中, 每個優(yōu)化方向f1,f2,f3分別可作為驗證模型優(yōu)化程度的3個性能指標[9]. 對表1的數(shù)據(jù)分別用傳統(tǒng)遺傳算法(GA)和多種群空間映射/改進遺傳算法(IGA)進行優(yōu)化求解, 給出三維仿真結果和各項指標的數(shù)值. 圖8為GA優(yōu)化效果, 圖9為IGA優(yōu)化效果. 由圖8和圖9可見, 同顏色為同一類別, 可從物品的擺放位置直觀看出IGA的排列更緊密有序. 表2為目標函數(shù)各項求解結果. 由表2可見, IGA的目標函數(shù)值為98.71, 相比于GA的結果降低27.61%, 各性能指標(出入庫時間, 整體重心, 相關性距離和)結果都較優(yōu), 分別低于GA各項的35.71%,17.64%,27.94%, 驗證了IGA的有效性, 相比于GA, 在本問題上的尋優(yōu)能力更強, 更易跳出局部最優(yōu).

表2 目標函數(shù)各項求解結果

3.2.2 算法穩(wěn)定性驗證

由于遺傳算法(啟發(fā)式算法)每次求解的結果不唯一, 所以為避免出現(xiàn)特殊情況, 需要對算法的穩(wěn)定性進行實驗, 對上述入庫任務進行20次優(yōu)化求解, 每隔5次實驗計算一次f的均值和標準差, 結果列于表3.

表3 兩種算法在不同實驗次數(shù)下的均值和標準差

由表3可見, 經(jīng)過不同次數(shù)的實驗, IGA的標準差增長率為15%～17%, 小于GA, 在完成20次實驗后, IGA的均值小于GA 22.63%, 標準差小于GA 16.67%, 可證明IGA在處理本問題上沒有過多的震蕩, 有足夠的穩(wěn)定性.

3.2.3 算法對不同任務容量的處理能力分析

實驗改變任務容量, 考察優(yōu)化效率隨任務容量S的變化情況.下面以S=10為間隔, 分別對不同容量進行分析討論. 表4列出了不同任務容量下IGA較GA的各項指標提升程度.

表4 不同任務容量下IGA較GA的各項指標提升程度

由表4可見, 各項優(yōu)化指標在IGA的優(yōu)化下總體優(yōu)于GA, 但IGA的優(yōu)化能力隨著S的提升, 逐漸變小, 這種情況當S=80時尤為顯著. 在常規(guī)的立體庫任務分配上, 通常一次任務的容量不超過總容量的10%, 如圖10所示, 當容量比約達到17%時(S=65), 優(yōu)化空間已經(jīng)受限, 目標函數(shù)的優(yōu)化過程不再過分依賴于不同算法.

圖10 IGA優(yōu)化能力隨S的變化趨勢Fig.10 Change trend of IGA optimization capability with S

綜上所述, 本文對自動化立體倉庫中的儲位分配問題進行了研究, 為應對不同的生產(chǎn)需求, 通過建立組合優(yōu)化函數(shù)實現(xiàn)了對貨位的動態(tài)分配, 從而提高了物流運輸效率. 在問題優(yōu)化過程中, 本文提出了一種多種群空間映射遺傳算法. 在算法對比實驗和不同任務容量的處理實驗中, 用三維視圖、 指標數(shù)據(jù)和迭代曲線3個指標驗證了該算法在常規(guī)運行時對貨位分配的能力更好, 3個性能指標均優(yōu)于傳統(tǒng)方案, 但在任務量過大時, 優(yōu)化能力會減弱.