基于改進(jìn)魚群算法的雙向式立體庫貨位優(yōu)化研究

范賢光,吳俊濤,尹藝玲,許英杰

(廈門大學(xué)航空航天學(xué)院,福建 廈門 361100)

1 引言

據(jù)統(tǒng)計(jì),企業(yè)產(chǎn)品制造過程中,有90%時間消耗在物流倉儲過程中,其成本占用總生產(chǎn)制造成本的10%,因此,對物流倉儲過程的優(yōu)化是提高企業(yè)效益[1]的重要途徑,而物流倉儲的重要環(huán)節(jié)之一便是貨位分配。傳統(tǒng)的貨位分配[2][3]模式往往是簡單的人工進(jìn)行就近放置,對于大信息量或者動態(tài)變化的訂單數(shù)據(jù)時將耗費(fèi)大量人工,增加企業(yè)生產(chǎn)成本?；跀?shù)字化背景下[4]的貨位優(yōu)化,能動態(tài)的根據(jù)貨物的相關(guān)屬性、立體庫內(nèi)資源占用情況、運(yùn)行效率和人工成本等因素實(shí)現(xiàn)最佳的分配,極大降低生產(chǎn)成本提高運(yùn)行效率,進(jìn)而為企業(yè)帶來直接的經(jīng)濟(jì)效益。隨著企業(yè)的規(guī)模擴(kuò)大和對立體庫靈活性要求的提高,多巷道雙向式結(jié)構(gòu)更優(yōu)于傳統(tǒng)的單出入口模式,既能夠靈活配置貨物的出入口又提高了運(yùn)行效率,極具研究意義。

基于數(shù)字化平臺下的貨物倉位分配問題,國內(nèi)外學(xué)者已經(jīng)進(jìn)行了大量的研究,并取得了一定的科研成果。Li[5]和焦玉玲[6]以提高貨物出入庫率、貨架穩(wěn)定性以及關(guān)聯(lián)性貨物就近存儲作為研究目標(biāo),分別采用遺傳模擬退火算法以及層次分析配合遺傳算法進(jìn)行優(yōu)化,Yang[7]考慮以提高出入庫效率以及貨架穩(wěn)定性作為研究目標(biāo),采用蟻群算法進(jìn)行尋優(yōu)計(jì)算,張磊[8]以倉庫利用率最大化和倉庫穩(wěn)定性最優(yōu)化為數(shù)學(xué)模型,采用多種群遺傳算法進(jìn)行計(jì)算,雖然他們的算法取得了較好的結(jié)果,但是在實(shí)際立體倉庫中,會有多排貨架的配置,文章內(nèi)容未提及平衡各巷道工作量的要素,可能會造成系統(tǒng)資源利用率不高的問題;唐文獻(xiàn)[9]和吳炳[10]以提高出庫效率,降低貨架中心以及平衡各巷道工作量作為目標(biāo)函數(shù),分別采用細(xì)菌覓食算法和模擬退火遺傳算法進(jìn)行優(yōu)化,取得了良好效果;馬永杰[11]以庫區(qū)分配、貨位分配以及行使時間作為優(yōu)化目標(biāo),采用遺傳算法進(jìn)行求解,取得一定成效,肖建[12]以物料相關(guān)性及需求頻率為優(yōu)化目標(biāo),采用遺傳算法進(jìn)行尋優(yōu),實(shí)驗(yàn)結(jié)果也符合預(yù)期,上述研究都是基于單出入口的立體倉庫模型,而蔡安江[13]等基于雙向式立體倉庫模型,建立以出入庫效率、貨品相關(guān)性以及貨架穩(wěn)定性為目標(biāo)函數(shù),采用混合蛙跳算法進(jìn)行計(jì)算,取得了良好效果,但對于常見的多巷道系統(tǒng)無法很好適用。

因此,本文將多巷道雙向式的立體倉庫作為研究對象,以提高出入庫效率和平衡各巷道工作量為目標(biāo)函數(shù),采用基于平均距離視野的自適應(yīng)人工魚群算法(Adaptive Artificial Fish-swarm Algorithm1,AAFSA1)進(jìn)行尋優(yōu),優(yōu)化了貨物在立體倉庫內(nèi)的位置分配,解決巷道的工作量不均衡問題,從而提高整套系統(tǒng)的工作效率。

2 立體庫系統(tǒng)描述

多巷道雙向式的立體庫模型配置多排貨架和巷道,巷道架設(shè)在貨架中間,巷道上運(yùn)行著一臺碼垛機(jī),其作用主要用于貨物的出入庫操作,每條巷道兩端設(shè)置有一個貨物的出入庫臺。企業(yè)可以根據(jù)需求增減貨架和巷道數(shù)量。系統(tǒng)結(jié)構(gòu)俯視圖如圖1所示。

圖1 系統(tǒng)結(jié)構(gòu)俯視圖

為了方便算法研究,做出如下說明:

1)每個倉位放置一個倉盒,碼垛機(jī)在出入庫臺和貨架之間來回運(yùn)輸倉盒。

2)訂單信息與倉盒綁定,當(dāng)訂單信息內(nèi)貨物數(shù)越多,該倉盒就需要頻繁出入庫接收新的貨物。

3)定義系統(tǒng)結(jié)構(gòu)俯視圖貨架右下角底部為位置原點(diǎn),每條訂單在貨架的位置信息可以表示為(x,y,z),其中x表示在貨架第x排,y表示第y列,z表示第z層。

4)貨架有a排,b層,c列,倉位深度為d,寬度為w,高度為h。

5)碼垛機(jī)總是處于勻速運(yùn)行狀態(tài),水平、垂直貨叉速度分別為Vx,Vy,Vz。

在實(shí)際的生產(chǎn)中,出現(xiàn)訂單集中存放、出入庫率高的訂單沒有靠近出入庫臺、個別巷道的工作量繁重,其它巷道的工作量極低甚至沒有工作量的現(xiàn)象。

為了解決上述問題,實(shí)現(xiàn)立體庫運(yùn)行效率最大化,讓各巷道工作量均衡的目的,本文提出如下訂單倉位優(yōu)化和分配原則:

1)提高貨物出入庫效率。在倉位分配時,要考慮出入庫率高的訂單靠近出入庫臺,這樣極大減少碼垛機(jī)的運(yùn)行時間,以提高貨物出入庫率繼而提高整套系統(tǒng)工作效率。

2)均衡各巷道的工作量。大型倉儲系統(tǒng)普遍擁有多條巷道,在倉位分配時,需要充分考慮各巷道的工作情況,合理的將工作量分配到各巷道上,實(shí)現(xiàn)資源利用最大化。

3 倉位分配數(shù)學(xué)模型

每條訂單信息有如下參數(shù)信息:(x,y,z,pxyz,pos),其中:(x,y,z)表示該訂單分配到立體倉庫貨架的位置信息,pxyz表示該訂單在系統(tǒng)內(nèi)的出入庫次數(shù),pos表示該訂單的出入庫口,pos有兩個值:pos=0或者pos=b+1;當(dāng)pos=0時,表示該訂單的出入庫口為巷道的右邊,當(dāng)pos=b+1時,表示訂單的出入庫口為巷道的左邊。

1)提高貨物出入庫效率

將每條訂單盡量安排在靠近出入庫口側(cè),且考慮訂單的出入庫次數(shù),讓出入庫次數(shù)高的更靠近出入庫口,以此減少碼垛機(jī)的運(yùn)行時間,提高工作效率。建立的目標(biāo)函數(shù)是碼垛機(jī)完成一次入庫或者出庫時間與該訂單的出入庫次數(shù)的乘積。碼垛機(jī)在完成入庫或者出庫動作時,水平y(tǒng)與垂直z方向的運(yùn)動是同時的,將倉盒送入貨架內(nèi)是獨(dú)立運(yùn)動,因此,所設(shè)計(jì)目標(biāo)函數(shù)為

F1(x,y,z)=

(1)

2)平衡各巷道工作量

(2)

x,y,z均為正整數(shù)。

3)評價(jià)函數(shù)

所建立的系統(tǒng)模型是一個多目標(biāo)函數(shù),且各自目標(biāo)函數(shù)量綱不同,但又相互影響,所以采用最優(yōu)值法對上述兩個目標(biāo)函數(shù)進(jìn)行處理。首先,對各目標(biāo)單獨(dú)運(yùn)算,求出其收斂后的最優(yōu)值F′(x,y,z),然后根據(jù)實(shí)際值與最優(yōu)值之間的平方差構(gòu)造評價(jià)函數(shù)Fi=[F(x,y,z)-F′(x,y,z)]2。引入比例系數(shù)?i,可將多目標(biāo)函數(shù)轉(zhuǎn)換為評價(jià)函數(shù):

(3)

4 基于平均距離視野的自適應(yīng)人工魚群算法設(shè)計(jì)

基于平均距離視野的自適應(yīng)人工魚群算法是一種新的群智能優(yōu)化算法,該算法最早由李曉磊[14]博士于2002年提出,主要模擬魚在水中的追尾、聚群、覓食以及隨機(jī)行為來實(shí)現(xiàn)尋優(yōu)目的,具有并行性、簡單性、能很快跳出局部極值、尋優(yōu)快的特點(diǎn)。傳統(tǒng)人工魚群(Artificial Fish-swarm Algorithm,AFSA)在追尾、聚群以及覓食[15]的過程中,需要在其感知距離Visual內(nèi)(視野)選擇伙伴,并且通過移動步長Step、擁擠度因子δ來判斷是否向伙伴方向移動。

基于平均距離視野的自適應(yīng)人工魚群算法,減少了Visual、Step以及δ的初始化設(shè)定,通過計(jì)算每條人工魚到其它人工魚的平均距離,作為自身的感知距離Visual;確定視步系數(shù)StepA,將StepA·Visual作為人工魚的最大移動步長Step。

在算法初期,擁有較大的感知距離Visual和移動步長Step,加強(qiáng)全局尋優(yōu)能力,有效克服局部極值,在后期,由于人工魚越來越聚集,使得感知距離Visual和移動步長Step減少,尋優(yōu)精度會越來越高。

本文中,AAFSA1算法參數(shù)定義如下:人工魚群個體數(shù):FishNum;最大迭代次數(shù):Max＿Gen;覓食行為嘗試的最大次數(shù):TryNumber;視步系數(shù):StepA;當(dāng)前迭代次數(shù):NC;當(dāng)前人工魚信息:Xi,i為當(dāng)前代數(shù)。算法具體步驟如下:

步驟1:參數(shù)初始化,設(shè)定FishNum、Max＿Gen、TryNumber、StepA。

步驟2:隨機(jī)生成指定數(shù)量的人工魚,如果待優(yōu)化的訂單數(shù)量為30個,則每條人工魚表示為{x1,x2…x30},x為每條訂單的信息,設(shè)定i=1。

步驟3:對當(dāng)前人工魚Xi執(zhí)行追尾操作,首先計(jì)算當(dāng)前人工魚Xi到其它人工魚的距離平均值,設(shè)定為感知距離Visual,以Visual查找身邊伙伴,并從找到的伙伴中確定最優(yōu)魚Xj,通過適應(yīng)度函數(shù)得到兩條魚的函數(shù)值Yi,Yj;如果Yi>Yj,則以Step=StepA·Visual為步長向其方向移動,否則執(zhí)行覓食行為,最后得到尋優(yōu)后的信息(Xnext1,Ynext1)。

步驟4:對當(dāng)前人工魚Xi執(zhí)行追尾操作,首先計(jì)算當(dāng)前人工魚Xi到其它人工魚的距離平均值,設(shè)定為感知距離Visual,以Visual查找身邊伙伴,并從找到的伙伴中確定中心位置的魚Xc,通過適應(yīng)度函數(shù)得到兩條魚的函數(shù)值Yi,Yc;如果Yi>Yc,則以Step=StepA·Visual為步長向其方向移動,否則執(zhí)行覓食行為,最后得到尋優(yōu)后的信息(Xnext2,Ynext2)。

步驟5:比較Ynext1,Ynext2,若Ynext1

步驟6:判斷i>FishNum,如果滿足,執(zhí)行步驟7,否則i=i+1,執(zhí)行步驟4。

步驟7:NC=NC+1,判斷NC>Max＿Gen,如果滿足,執(zhí)行步驟8,否則執(zhí)行步驟3。

步驟8:確定最優(yōu)值,并輸出結(jié)果。

基于平均距離視野的自適應(yīng)人工魚群算法的流程圖如圖2所示。

圖2 基于平均距離視野的自適應(yīng)人工魚群算法流程圖

5 算法分析

5.1 數(shù)據(jù)信息

以某配件廠為例進(jìn)行訂單倉位分配,立體庫各項(xiàng)數(shù)據(jù)指標(biāo)如表1所示,訂單在立體庫的初始信息如表2所示,該信息主要包含訂單出入庫次數(shù),在立體倉庫的位置信息以及對應(yīng)的出入庫臺。圖3為訂單在立體倉庫內(nèi)的初始位置狀態(tài),紅色塊代表每條訂單,可以看到,訂單在立體倉庫內(nèi)雜亂無章,沒有靠近出入庫臺,且出現(xiàn)了某些巷道無工作量的情況。

表1 立體倉庫各項(xiàng)指標(biāo)

表2 訂單初始信息表

圖3 優(yōu)化前各訂單在立體倉庫內(nèi)的位置圖

本次仿真過程,采用標(biāo)準(zhǔn)遺傳算法GA、AFSA以及AAFSA1分別進(jìn)行優(yōu)化,以此驗(yàn)證AAFSA1的優(yōu)勢和應(yīng)用價(jià)值。各算法的參數(shù)設(shè)置說明如表3所示。

5.2 仿真結(jié)果及分析

當(dāng)只考慮提高出入庫效率為目標(biāo)函數(shù)時,仿真結(jié)果如圖4、圖5所示。當(dāng)只考慮平衡各巷道工作量為目標(biāo)函數(shù)時,結(jié)果如圖6、圖7所示?？梢悦黠@看出,相比圖3,圖4中訂單都被盡量安排到靠近對應(yīng)的出入庫臺側(cè)。這樣,可以極大減少碼垛機(jī)的運(yùn)行時間,達(dá)到提高出入庫效率的目的。圖5中,AAFSA1算法在第220次實(shí)現(xiàn)收斂,函數(shù)值下降到560.975,GA算法在210次實(shí)現(xiàn)收斂,函數(shù)值下降到617.1583,AFSA 算法在第 256 次實(shí)現(xiàn)收斂,函數(shù)值下降到 561.3667。圖6中,每條巷道的工作量基本保持一致,充分利用現(xiàn)有巷道資源,達(dá)到了各巷道負(fù)載均衡的目的。圖7中,AAFSA1算法在第8次實(shí)現(xiàn)收斂,函數(shù)值下降到1.6667,GA算法在235次實(shí)現(xiàn)收斂,函數(shù)值下降到1.6667,AFSA 算法在第 22 次實(shí)現(xiàn)收斂,函數(shù)值下降到 1.6667。從圖5、圖7中的算法迭代圖可以明顯看出,AAFSA1算法較GA、AFSA算法具有更強(qiáng)的尋優(yōu)能力,不易陷入局部最優(yōu)值,且收斂速度更快收斂精度更高。

圖4 提高出入庫效率的訂單位置結(jié)果

圖5 提高出入庫效率的算法迭代過程

圖6 平衡各巷道工作量的訂單位置結(jié)果

圖7 平衡各巷道工作量的算法迭代過程

5.3 雙目標(biāo)的仿真結(jié)果及分析

將上述兩個單目標(biāo)函數(shù)的最優(yōu)值以及比例系數(shù)?1=0.85,?2=0.15帶入式子中,建立評價(jià)函數(shù)如下所示:

F(x,y,z)=

(4)

建立的評價(jià)函數(shù)已經(jīng)消除了各自量綱不同的影響。仿真結(jié)果如圖8、圖9所示。從圖8中,可以明顯看出訂單都被盡量安排到靠近對應(yīng)的出入庫臺側(cè),且每條巷道的工作量基本保持一致。這樣,既減少了碼垛機(jī)運(yùn)行時間,提高了效率,又充分利用現(xiàn)有巷道資源,達(dá)到了各巷道負(fù)載均衡的目的。從圖9中,AAFSA1在第400代實(shí)現(xiàn)了收斂,評價(jià)函數(shù)值由最先的633.2129下降到1.6749,下降了99.7355%,而GA以及AFSA算法在500代內(nèi)還未實(shí)現(xiàn)收斂。

圖8 雙目標(biāo)的訂單位置結(jié)果

圖9 雙目標(biāo)的算法迭代過程

6 結(jié)束語

本文基于多巷道雙向式的大型立體庫貨位優(yōu)化為背景,提出建立提高出入庫效率和平衡各巷道工作量為目標(biāo)函數(shù)的數(shù)學(xué)模型,運(yùn)用最優(yōu)值法將多目標(biāo)函數(shù)轉(zhuǎn)換為評價(jià)函數(shù)。提出AAFSA1算法,減弱了人工設(shè)定參數(shù)對尋優(yōu)過程的影響,并通過GA、AFSA以及改進(jìn)的AAFSA1算法對各自單目標(biāo)函數(shù)和評價(jià)函數(shù)進(jìn)行仿真求解,在自尋優(yōu)過程中可以發(fā)現(xiàn)AAFSA1算法具有更快的收斂速度、更強(qiáng)的尋優(yōu)能力以及更高的精度。優(yōu)化后的值滿足了實(shí)際生產(chǎn)需求,大幅提高了企業(yè)的生產(chǎn)效率。