蔡安江,葉 康,郭師虹,龐飛彪,于海濱

(1.西安建筑科技大學(xué) 機(jī)電工程學(xué)院，陜西 西安 710055；2.西安建筑科技大學(xué) 土木工程學(xué)院，陜西 西安 710055；3.德州海天機(jī)電科技有限公司，山東 德州 253000)

0 引言

貨物分配作為制造業(yè)倉儲運(yùn)輸環(huán)節(jié)的重要組成部分，對貨物的進(jìn)/出庫效率起著決定性作用[1]。合理的貨位分配方法可以有效地縮短工作時(shí)間，提高工作效率，延長貨架的使用壽命，減少企業(yè)的運(yùn)行成本，與企業(yè)的效益密不可分[2-3]。但隨著企業(yè)規(guī)模的擴(kuò)大和倉庫存儲需求的提高，雙向式布局的倉庫在貨物存儲能力及效率方面明顯優(yōu)于單向式倉庫，因此對雙向式立體倉庫貨位分配的研究具有重要意義。

對于現(xiàn)代制造模式下立體倉庫的貨位分配研究，國內(nèi)外學(xué)者已經(jīng)進(jìn)行了較為深入的研究。湯洪濤等[4]和WANG等[5]均以堆垛機(jī)揀選效率為目標(biāo)函數(shù)，分別提出K-Medoids聚類的粒子群優(yōu)化算法和蟻群聚類算法，雖然算法有效地提高了倉庫揀選效率和貨物分配方式，但在其優(yōu)化過程中均沒有考慮貨架的穩(wěn)定性這一要素，無法保證貨物擺放時(shí)貨架的平穩(wěn)安全；李鵬飛等[6]針對貨架穩(wěn)定性和貨物出入庫效率建立數(shù)學(xué)模型，采用病毒協(xié)同遺傳算法進(jìn)行優(yōu)化，取得良好效果，但在建模時(shí)沒有考慮貨物的關(guān)聯(lián)性原則，不適用于同類貨物的存儲優(yōu)化。以上研究均在建立貨物分配模型時(shí)進(jìn)行，建模的原則考慮不周。張貴軍等[7]和焦玉玲等[8]均以貨架重心、堆垛機(jī)運(yùn)行時(shí)間和貨物關(guān)聯(lián)性等為參考因素，分別提出了精英多策略和多種群遺傳算法進(jìn)行優(yōu)化，取得了良好效果；李小笠等[9]以堆垛機(jī)能耗、貨架穩(wěn)定性和運(yùn)輸效率為目標(biāo)，將多目標(biāo)轉(zhuǎn)化為單目標(biāo)函數(shù)，并利用嵌套分區(qū)算法優(yōu)化，有效解決了倉庫的貨位分配問題。上述研究方法可以有效優(yōu)化單向式倉庫貨位分配的問題，但由于雙向式立體倉庫出入口的不確定性導(dǎo)致堆垛機(jī)搬運(yùn)貨物時(shí)對出/入口選擇的不同，影響堆垛機(jī)的運(yùn)行時(shí)間，因此此類建模方法不適用于雙出/入口布局模式下的立體倉庫。鄂曉征等[10]建立了以堆垛機(jī)揀選效率和貨架穩(wěn)定性為分配原則的數(shù)學(xué)模型，采用遺傳算法進(jìn)行貨位優(yōu)化，取得了一定成效，但遺傳算法易陷入局部最優(yōu)，且收斂速度較慢，當(dāng)存取貨物較多時(shí)無法找到全局最優(yōu)解；BOTTANI等[11]和ATMACA等[12]均以自動化立體倉庫貨位分配原則為前提，建立了貨位分配模型，并采用遺傳算法、模擬退火算法對模型進(jìn)行優(yōu)化求解，驗(yàn)證了所建模型的正確性和智能算法的適用性。上述研究采用的多為標(biāo)準(zhǔn)的智能算法，雖有一定成效，但易陷入“早熟”，魯棒性較差。

因此，本文以雙向式布局模式下的自動化立體倉庫為研究對象，建立以出入庫效率、物品相關(guān)度和貨架穩(wěn)定性為優(yōu)化原則的數(shù)學(xué)模型，為避免結(jié)果陷入局部最優(yōu)，采用改進(jìn)混合蛙跳算法(Improve Shuffled Frog Leading Algorithm, ISFLA)，解決了雙向式立體倉庫在貨位分配問題上采用“逐層放置”等傳統(tǒng)方式的弊端，優(yōu)化了貨物的擺放位置，從而提高雙向式立體倉庫的運(yùn)行效率。

1 貨位分配模型

1.1 模型基本假設(shè)

雙向式布局模式下的立體倉庫每兩排貨架之間架設(shè)有一條巷道，巷道上有一臺堆垛機(jī)負(fù)責(zé)貨物進(jìn)/出庫的運(yùn)輸，倉庫左右兩端各有一個(gè)進(jìn)出口。貨架的局部俯視圖如圖1所示。

針對雙向式立體倉庫分配遇到的相關(guān)問題和應(yīng)遵循的原則，為了便于模型的建立和問題的研究，僅考慮一組貨架(即兩排)并特別作出如下假設(shè)：

(1)假設(shè)某倉庫有a列，b層，c排貨架，為區(qū)別單向式立體倉庫，定義左端出入庫臺底部為坐標(biāo)原點(diǎn)，貨架第x列、y層、z排的貨物坐標(biāo)可表示為(x,y,z)。

(3)每個(gè)貨位只能儲存一個(gè)貨物，且貨位的長寬高都相等，設(shè)為L。

(4)假設(shè)堆垛機(jī)的運(yùn)行速度恒定，堆垛機(jī)的水平、垂直和叉貨速度分別設(shè)為Vx，Vy，Vz且不互相干涉，忽略堆垛機(jī)啟動和制動的時(shí)間。

1.2 貨位多目標(biāo)分配模型的建立

定義(x,y,z,Pk,Mk,j)為貨架中某一待入庫貨物的信息，其中：(x,y,z)表示該貨物在倉庫中貨架中的位置坐標(biāo)，它決定著貨物分配的最終結(jié)果，屬于決策變量；Pk表示(x,y,z)貨位中貨物的出入庫頻率(也可稱為周轉(zhuǎn)率);Mk表示貨物的質(zhì)量，它們是待入庫貨物本身的固有參數(shù)；j表示貨物出入庫臺的列數(shù)，j=0或j=a+1。其中j=0表示最左端出入庫臺所對應(yīng)列數(shù)，j=a+1表示最右端出入庫臺做對應(yīng)列數(shù)。左出入臺位置可表示為(0,1,0)，右出入臺位置可表示為(a+1,1,0)。

(1)建立以出入庫效率為目標(biāo)的函數(shù)F1

貨物出入庫時(shí)，一方面要盡可能地縮短貨物到貨架的之間的距離，進(jìn)而達(dá)到縮短堆垛機(jī)運(yùn)行時(shí)間的目的，同時(shí)還要考慮貨物的周轉(zhuǎn)頻率。即堆垛機(jī)運(yùn)送貨物到指定貨位的時(shí)間與貨物的周轉(zhuǎn)率乘積最小(將周轉(zhuǎn)率看作頻率系數(shù))，則建立的待優(yōu)化函數(shù)為：

(1)

(2)建立以貨品相關(guān)性為目標(biāo)的函數(shù)F2

同種類型產(chǎn)品盡可能存放在相鄰或相近的貨位，可降低相關(guān)性高的產(chǎn)品的儲存距離，減少堆垛機(jī)的運(yùn)行距離。因此，當(dāng)有一批待入庫的貨物進(jìn)行存放時(shí)，在空余貨位確定一位置為中心貨位，使待存放貨物距離中心貨位的距離盡可能短，這樣可減少堆垛機(jī)存取同類貨物運(yùn)行的時(shí)間。

當(dāng)有n個(gè)貨位可以提供k類產(chǎn)品儲存時(shí)，定義此時(shí)的組內(nèi)平均坐標(biāo)(中心貨位)為(ak,bk,ck)，其取值根據(jù)實(shí)際訂單決定，則待存放貨品(x,y,z)距離平均坐標(biāo)的距離

(2)

根據(jù)雙向式自動化立體倉庫貨位布局特點(diǎn)，為使所有待存放貨品距離平均坐標(biāo)(中心貨位)距離最短，則優(yōu)化的目標(biāo)函數(shù)為：

(3)

(3)建立以貨架穩(wěn)定性為原則的目標(biāo)函數(shù)F3

貨架應(yīng)該符合上輕下重的原則，盡可能地降低貨架重心，把輕的貨物放在上層，重的貨物放在下層，防止貨架因?yàn)橹匦牟环€(wěn)而導(dǎo)致傾覆，即貨物質(zhì)量與其所在層數(shù)的乘積的和最小。

建立以貨架穩(wěn)定性為原則優(yōu)化的目標(biāo)函數(shù)為：

(4)

顯然，所建立的模型是一個(gè)多目標(biāo)函數(shù)，3個(gè)目標(biāo)函數(shù)之間相互影響。為方便計(jì)算，要將多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)，并根據(jù)倉庫實(shí)際情況確定相關(guān)系數(shù)。

Fmin(x,y,z)=μF1min(x,y,z)+

μ2F2min(x,y,z)+μ3F3min(x,yz)。

(5)

s.t.

0<μ1<1;

0<μ2<1;

0<μ3<1,

μ1+μ2+μ3=1。

2 算法設(shè)計(jì)及驗(yàn)證

2.1 混合蛙跳算法設(shè)計(jì)

混合蛙跳算法(SFLA)是一種新的啟發(fā)式群體優(yōu)化算法，由EUSUFF等[13]于2003年最先提出，主要模擬池塘中青蛙尋找食物路徑的過程，來模擬算法的搜索過程，通過局部搜索和全局搜索來完成[14]。子群中的青蛙通過群內(nèi)的局部信息交流來優(yōu)化個(gè)體，迭代到一定次數(shù)后再進(jìn)行全局的搜索交流。在局部搜索過程中，按照混合蛙跳算法的更新公式，對每一個(gè)子群中表達(dá)最差的蛙Pworse進(jìn)行更新替換，公式如下：

STEP=rand()×(Pbest-Pworse)((Dmin)

≤STEP≤Dmax),

(6)

混合蛙跳算法在尋找最優(yōu)解的過程中，青蛙的移動步長決定著算法的搜索速度和準(zhǔn)確度，步長過大容易跳過最優(yōu)解，過小則使收斂速度過慢。在標(biāo)準(zhǔn)混合蛙跳算法更新公式中，rand()是0～1間的隨機(jī)數(shù)，使得移動步長STEP隨機(jī)更新。這種更新方式容易使結(jié)果陷入局部最優(yōu)，無法充分發(fā)揮算法的優(yōu)越性，因此，設(shè)計(jì)了以余弦函數(shù)為基礎(chǔ)的動態(tài)自適應(yīng)同步因子：

(7)

2.2 ISFLA算法步驟

針對所建立的雙向式立體倉庫模型，采用ISFLA進(jìn)行優(yōu)化，算法具體步驟如下：

步驟1初始化參數(shù)。隨機(jī)生成m(memeplex)個(gè)子群，其中每個(gè)子群有n只青蛙，每只青蛙代表一種貨位分配方式。設(shè)置青蛙最大跳躍的最大步長Dmax，子群內(nèi)青蛙迭代次數(shù)gn，種群最大迭代次數(shù)Gn。

步驟2初始化種群。在可行解范圍內(nèi)生成F=m×n只青蛙，代表初始分配方式有m×n種，設(shè)置青蛙的維度S，每只青蛙可以表示為{X1,X1,…,XF}。

步驟3重新劃分子群Z1,Z2,…,Zm。將所有青蛙按計(jì)算適應(yīng)值，記每個(gè)青蛙的適應(yīng)值為f(i)，按照從大到小的順序?qū)⑶嗤芘帕胁凑杖缦乱?guī)則劃分子群：

Zk={X(j)k,f(j)k|X(j)k

=X(k+m(j-1)),f(j)k=f(k+m(j-1))}。

(8)

式中：j=1,2,…,n;k=1,2,…,m。

步驟4記每個(gè)子群中適應(yīng)度最大的青蛙為Pbest，適應(yīng)度最小的青蛙為Pworse。

步驟5記青蛙子群tm=0，表示子群進(jìn)化的數(shù)目;tn=0，用來表示子群內(nèi)局部搜索的迭代數(shù)。

步驟6設(shè)tm=tm+1。

步驟7設(shè)tn=tn1。

步驟8按照式(10)的更新策略，更新子群中表現(xiàn)最差的青蛙。

STEP=φ×(Pbest-Pworse),

Dmin≤STEP≤Dmax,

(9)

步驟9若更新后的青蛙適應(yīng)值優(yōu)于Pworse，則替之；若不如，則用全局最優(yōu)解PB代替Pbest，返回步驟8進(jìn)行重新選擇；若還是不如Pworse，則隨機(jī)生成一只青蛙代替。

步驟10判斷是否tn

步驟11判斷是否tm

步驟12迭代達(dá)到規(guī)定次數(shù)時(shí)，算法結(jié)束。輸出全局最優(yōu)解PB，并輸出對應(yīng)的目標(biāo)函數(shù)值。解碼之后，得到最優(yōu)的貨位分配坐標(biāo)及出入庫臺坐標(biāo)。

改進(jìn)混合蛙跳算法的流程圖，如圖2所示。

2.3 算法驗(yàn)證

為驗(yàn)證改進(jìn)算法的正確性和有效性，選取4個(gè)測試函數(shù)來進(jìn)行實(shí)驗(yàn)仿真驗(yàn)證，通過與改進(jìn)前的標(biāo)準(zhǔn)算法作對比，來說明改進(jìn)算法的有效性和優(yōu)越性。測試函數(shù)的表達(dá)式、維數(shù)、搜索域、最優(yōu)解等如表1所示，表中前兩個(gè)為單峰函數(shù)，后兩個(gè)為多峰函數(shù)。算法所用參數(shù)如表2所示。

表1 測試函數(shù)參數(shù)

表2 測試函數(shù)算法參數(shù)

進(jìn)行算法驗(yàn)證時(shí)，為保證實(shí)驗(yàn)不受偶然因素的影響，每個(gè)函數(shù)分別進(jìn)行20次實(shí)驗(yàn)，取20次實(shí)驗(yàn)的最優(yōu)(BEST)、最差(WORSE)以及平均值(AVERAGE)作為評價(jià)標(biāo)準(zhǔn)，各仿真數(shù)據(jù)如表3所示，函數(shù)迭代圖如圖3所示。

表3 函數(shù)實(shí)驗(yàn)數(shù)據(jù)

由表3可以看出，改進(jìn)后的算法在測試函數(shù)上的表現(xiàn)要明顯優(yōu)于改進(jìn)前。在各個(gè)函數(shù)的表現(xiàn)上，ISFLA的實(shí)際最優(yōu)明顯強(qiáng)于SFLA且無線趨近于理論最優(yōu)值0，說明ISFIL的搜索性能較好。從圖3可以，ISFIL在迭代速率上相比SFIL也明顯更快，且不容易陷入“早熟”，具有較強(qiáng)的魯棒性。仿真結(jié)果表明了ISFIL的有效性和優(yōu)越性。

3 實(shí)例仿真驗(yàn)證

3.1 編碼設(shè)計(jì)

基于任務(wù)編碼是算法求解問題的關(guān)鍵步驟，常用的編碼方式有二進(jìn)制編碼、整數(shù)編碼、符號編碼等，通常需要根據(jù)實(shí)際要解決的問題選擇合適的編碼方式。在用ISFLA進(jìn)行雙向式立體倉庫貨位分配優(yōu)化時(shí)，由于貨位坐標(biāo)的特殊性，采用十進(jìn)制整數(shù)編碼方式，每只青蛙代表一種貨位分配方式。

在初始化種群時(shí)，貨位分配坐標(biāo)隨機(jī)生成。首先對待入庫的貨物進(jìn)行編碼，編碼對應(yīng)周轉(zhuǎn)率、質(zhì)量等信息；其次對貨位進(jìn)行編碼，編碼的長度由待入庫分配貨物的數(shù)量決定，編碼分為若干小段，每段代表著一個(gè)貨位的坐標(biāo)，由于貨位坐標(biāo)是(x,y,z)三維存在的，定義行、列、排分別用x,y,z三個(gè)數(shù)表示，即貨位編碼長度N=3Na。

假設(shè)現(xiàn)有3個(gè)待入庫貨物，則Nα=3，N=9。對其的貨物編號分別為1，2，3。1貨物準(zhǔn)備放入(2，4，7)貨位，2貨物準(zhǔn)備放入(1，3，2)貨位，3貨物準(zhǔn)備放入(3，3，4)貨位，則貨位的編碼為(2，4，7，1，3，2，3，3，4)，具體編碼如圖4所示。

解碼相當(dāng)于是編碼的逆向過程。把算法的解映射到實(shí)際的問題中去，對于雙向式立體倉庫貨位分配問題，把算法得到的最優(yōu)解按照每3個(gè)進(jìn)行劃分，就可得到實(shí)際的貨位坐標(biāo)。

3.2 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)是改進(jìn)混合蛙跳算法(ISFLA)進(jìn)行迭代選擇的依據(jù)[15]。本文貨物分配位置的優(yōu)化，即堆垛機(jī)運(yùn)行時(shí)間最少、貨架重心最低和相關(guān)聯(lián)的貨物之間的距離最小。根據(jù)所建立的目標(biāo)函數(shù)，將適應(yīng)度設(shè)為：

(11)

適應(yīng)度函數(shù)越大，貨架的優(yōu)化程度越好。

3.3 實(shí)例仿真

由于貨位分配的側(cè)重點(diǎn)不同會導(dǎo)致分配結(jié)果的不同，通過層次分析法(Analytic Hierarchy Process, AHP)的計(jì)算以及綜合考慮立體倉庫的實(shí)際情況，取μ1=0.426，μ2=0.283，μ3=0.291。

以某汽車配件廠的雙向式立體倉庫貨位分配任務(wù)為例，采用MATLAB進(jìn)行仿真驗(yàn)證，倉庫的各項(xiàng)參數(shù)如表4所示。

表4 雙向式自動化倉庫基本參數(shù)

現(xiàn)有15件待入庫的貨物，已知各個(gè)貨物的質(zhì)量以及周轉(zhuǎn)率，并按照隨機(jī)分配的方式給出貨位的初始入庫坐標(biāo)和出入臺坐標(biāo)，如5表所示。

表5 優(yōu)化前貨位坐標(biāo)

針對此次貨位分配任務(wù)，采用標(biāo)準(zhǔn)遺傳算法GA、SFLA和ISFLA分別進(jìn)行優(yōu)化。算法的參數(shù)如表6所示。

表6 算法參數(shù)

運(yùn)用所建立的雙向式自動化倉庫貨位分配模型并結(jié)合GA、SFLA及ISFLA對該貨位分配任務(wù)進(jìn)行優(yōu)化仿真求解，其算法優(yōu)化過程適應(yīng)度值變化如圖5所示。

ISFLA優(yōu)化后的貨位坐標(biāo)及出入庫坐標(biāo)如表7所示。

表7 優(yōu)化后的貨位坐標(biāo)

從圖5可以看出，隨著迭代次數(shù)的增加，目標(biāo)函數(shù)值不斷減少，說明其解逐步逼近最優(yōu)解。相比GA與SFLA，ISFLA明顯收斂速度更快，在140代左右達(dá)到最優(yōu)，此時(shí)函數(shù)值為1.452，SFLA在200代左右達(dá)到最優(yōu)，函數(shù)值為2.132，GA在250代左右達(dá)到最優(yōu)，函數(shù)值為2.433。可見ISFLA相比SFLA與GA的效率分別提高了28.9%與41.6%左右，證明了ISFLA的有效性和優(yōu)越性。

為驗(yàn)證算法對雙向式倉庫不同規(guī)模入庫任務(wù)的實(shí)際作用，增加中型貨物入庫規(guī)模和大型貨物入庫規(guī)模的驗(yàn)證，表4和表6參數(shù)保持不變，入庫貨物的基本參數(shù)如表8和表9所示。

表8 中規(guī)模入庫任務(wù)貨物參數(shù)

表9 大規(guī)模入庫任務(wù)貨物參數(shù)

運(yùn)用所建立的雙向式自動化倉庫貨位分配模型并結(jié)合GA、SFLA及ISFLA對這兩批貨位分配任務(wù)進(jìn)行優(yōu)化仿真求解，其算法優(yōu)化過程如圖6所示。

從圖6可知，ISFLA處理中、大規(guī)模貨物的入庫貨位分配時(shí)，相比于GA和SFLA，在迭代速率和解的質(zhì)量方面都有較大的優(yōu)勢，從而進(jìn)一步驗(yàn)證了ISFLA在處理雙向式布局模式下立體倉庫貨位分配問題時(shí)的有效性和優(yōu)越性。

4 結(jié)束語

本文針對雙向式立體倉庫貨位分配問題，建立了以入庫效率、貨架重心和產(chǎn)品聚集度為優(yōu)化目標(biāo)的數(shù)學(xué)模型，采用ISFLA改變了局部搜索時(shí)的更新策略，減少了堆垛機(jī)取/存貨時(shí)間，提高了貨架的穩(wěn)定性，有效的提升了倉儲管理的效率。

通過對標(biāo)準(zhǔn)蛙跳算法局部搜索策略的改進(jìn)，改變了淘汰最差蛙時(shí)的選擇策略，可以及時(shí)更新最差蛙的位置，使子群內(nèi)青蛙可以充分信息交互，彌補(bǔ)其在解決多目標(biāo)優(yōu)化問題時(shí)易陷入局部最優(yōu)的缺點(diǎn)，增加了算法的搜索速度，并用測試函數(shù)驗(yàn)證了改進(jìn)算法的正確性和有效性，在其解決雙向式立體倉庫的貨位分配優(yōu)化問題時(shí)，效率明顯提升。

相比于GA與SFLA，ISFLA具有更好的收斂性。雙向式立體倉庫貨位分配優(yōu)化時(shí)，可以不斷對貨物位置進(jìn)行更新，避免了GA與SFLA易陷入局部最優(yōu)解且收斂過慢的缺點(diǎn)，有效地提高了迭代速率和解的質(zhì)量。

本文未驗(yàn)證其他布局類型的倉庫是否也可用ISFLA來進(jìn)行優(yōu)化分配，下一步可以據(jù)此展開研究。另外，增加堆垛機(jī)的數(shù)量和出/入口的數(shù)量可以提高倉庫的運(yùn)輸效率，在其數(shù)量上尋找最優(yōu)也是未來建立倉庫模型時(shí)可以考慮和研究的方向。