羅 煥，閆富乾，宋小欣，張 劍

（西南交通大學(xué) 先進(jìn)設(shè)計(jì)與制造技術(shù)研究所，成都 610000）

0 引言

隨著經(jīng)濟(jì)環(huán)境和相關(guān)政策的影響，全球倉儲業(yè)的效率和管理水平得到迅速提高并穩(wěn)步發(fā)展。各倉儲企業(yè)不斷追求倉儲的自動化與無人化，以釋放勞動力、提高倉儲作業(yè)運(yùn)轉(zhuǎn)效率等，促使自動化立體倉庫的貨位優(yōu)化成為研究熱點(diǎn)[1]。

焦玉玲等[2]針對自動化立體倉庫的工作效率和安全性要求，以出入庫作業(yè)時(shí)間、整體貨架的等效重心和相關(guān)產(chǎn)品的相對積累程度為多目標(biāo)函數(shù)，建立了多目標(biāo)貨位分配優(yōu)化的數(shù)學(xué)模型，提出了多種群遺傳算法進(jìn)行求解；唐文獻(xiàn)等[3]提出自動化立體倉庫分區(qū)存放策略，以多巷道貨架為對象，開展貨位優(yōu)化研究。蔡錦文等[4]在傳統(tǒng)的以存儲頻率為中心的存儲分配策略的基礎(chǔ)上，考慮了工作負(fù)載平衡問題，提出了兩種新的自動化倉庫存儲分配策略；楊瑋等[5]以出庫效率和貨物重量為目標(biāo)將倉庫進(jìn)行分區(qū)，然后對比HPSO、GA、PSO三種算法的求解效果；宋賀騰等[6]以堆垛機(jī)的立體倉庫貨架重心最低和總?cè)∝洉r(shí)間最短為目標(biāo)，同時(shí)保證調(diào)整時(shí)間最短，采用改進(jìn)自適應(yīng)遺傳算法進(jìn)行求解。

綜上所述，目前國內(nèi)外學(xué)者在構(gòu)建貨位優(yōu)化模型時(shí)，多以出入庫效率為首選目標(biāo)，再進(jìn)行目標(biāo)和約束擴(kuò)展，而現(xiàn)有文獻(xiàn)往往忽略了同類貨物在倉庫中的分布情況以及各條巷道堆垛機(jī)工作量均衡問題，導(dǎo)致倉庫作業(yè)過于集中和不平衡，容易造成通道堵塞[7]。為此，本文以出入庫效率、貨架穩(wěn)定性、同類貨物就近存放和堆垛機(jī)工作量均衡創(chuàng)建多目標(biāo)優(yōu)化數(shù)學(xué)模型，提出一種變鄰域NSGA-Ⅱ算法對遺傳操作后的部分個(gè)體進(jìn)行變鄰域操作，以增強(qiáng)算法的求解搜索能力，并通過實(shí)例驗(yàn)證了算法的有效性。

1 貨位分配模型

1.1 問題描述

自動化立體倉庫由貨架、堆垛機(jī)、傳送帶組成如圖1所示。貨位分配優(yōu)化問題可以描述為：已知一系列貨物的類型、重量和出入庫頻率等相關(guān)屬性，按照一定的貨位分配原則，通過傳送帶和巷道堆垛機(jī)將這些貨物放置在第x排y列z層的貨位上，以實(shí)現(xiàn)同類貨物在各巷道兩側(cè)的貨架上分布均勻，各巷道堆垛機(jī)工作量均衡，同類貨物就近存放，提高貨架整體穩(wěn)定性和貨物出入庫效率。

圖1 自動化立體倉庫示意圖

貨位分配過程滿足如下假設(shè)：每個(gè)貨位只存放一個(gè)貨物；堆垛機(jī)和傳送帶以平均速度運(yùn)行，不考慮啟動和停止時(shí)間且可存取巷道左右兩排貨架上的一個(gè)貨物；不考慮貨架自身、貨箱以及托盤的重量，且貨物重量不影響存取時(shí)間，貨位重心位于該貨位的幾何中心；巷道為單向出口，出入庫口位置坐標(biāo)為（0,0,0）。

1.2 符號說明

模型中相關(guān)參數(shù)說明：

x：倉庫第x排貨架，x={1,2,3….X}；

y：倉庫第y列貨架，y={1,2,3….Y}；

z：倉庫第z層貨架，z={1,2,3….Z}；

vx：傳送帶沿水平方向的平均速度；

vy：堆垛機(jī)沿巷道方向的平均速度；

vz：堆垛機(jī)沿豎直方向的平均速度；

pji：i類貨物中第j個(gè)貨物的出入庫頻率；

mji：i類貨物中第j個(gè)貨物的重量；

L：貨位的寬度；

L0：巷道寬度；

J：第i類貨物的總數(shù)；j={1,2,3….J}；

h：巷道序號，h={1,2,3….H}；

H：巷道總數(shù)；

G（x）max：第x排貨架的最大承重；

(Ai,Bi,Ci)：第i類貨物的中心坐標(biāo)；

(xji,yji,zji)：第i類第j個(gè)貨物的貨位坐標(biāo)；

t(xji,yji,zji)：第i類貨物中第j個(gè)貨物從倉庫出口到貨位的時(shí)間。

1.3 數(shù)學(xué)模型

式(1)為多目標(biāo)函數(shù)集合，表示出入庫效率、貨架整體重心、同類貨物間距離、巷道堆垛機(jī)工作量均衡最小化，其中各部分計(jì)算如式(2)～(5)所示，式(2)表示出入庫效率f1，式(3)表示貨架整體重心f2，式(4)表示同類貨物間距離f3，式(5)表示巷道堆垛機(jī)工作量f4。式(6)表示第i類貨物中j貨物入庫所消耗時(shí)間。

約束條件：

其中：式(7)表示貨架x存放貨物總重量不能超過貨架最大承重；式(8)表示貨物j是否在巷道h中。

2 變鄰域NSGA-II算法

傳統(tǒng)的多目標(biāo)優(yōu)化是將不同的目標(biāo)分配一定的權(quán)重以轉(zhuǎn)化為單目標(biāo)優(yōu)化，而目標(biāo)的權(quán)重系數(shù)往往根據(jù)經(jīng)驗(yàn)或試錯(cuò)法得出，難以適應(yīng)問題的變化和需求，采用NSGA-II可以優(yōu)化出適用多目標(biāo)問題的非支配解種群[8]，其主要思想是對種群中個(gè)體的各個(gè)目標(biāo)函數(shù)值進(jìn)行非支配解分層，同層個(gè)體為非支配關(guān)系，其非支配解更傾向于選擇擁擠度大的個(gè)體以得到目標(biāo)函數(shù)最優(yōu)值。本文提出一種變鄰域NSGA-Ⅱ算法對遺傳操作后的部分個(gè)體進(jìn)行變鄰域操作以增強(qiáng)其搜索能力，其算法流程圖如圖2所示。

圖2 變鄰域NSGA-Ⅱ算法

變鄰域NSGA-Ⅱ算法步驟如下：

1）初始化參數(shù)：設(shè)置種群大小PopSize，交叉概率為Pc，變異概率為Pm，最大迭代次數(shù)為Gmax，最優(yōu)前端個(gè)體系數(shù)PF，鄰域初始種群大小VNSize，變鄰域最大循環(huán)次數(shù)VNS_Gmax。

2）初始化種群：采用實(shí)數(shù)編碼隨機(jī)生成初始種群Initial_Pop。

3）目標(biāo)函數(shù)值的計(jì)算：根據(jù)式(2)～式(5)計(jì)算四個(gè)目標(biāo)函數(shù)值f1、f2、f3、f4。

4）非支配排序和擁擠度計(jì)算：

（1）非支配排序：根據(jù)目標(biāo)函數(shù)值進(jìn)行個(gè)體序值的計(jì)算。

（2）擁擠距離計(jì)算：對四個(gè)目標(biāo)分別計(jì)算相應(yīng)的擁擠距離，再將四個(gè)目標(biāo)函數(shù)的擁擠距離相加得到最后的擁擠距離。

5）遺傳操作：

（1）選擇操作：錦標(biāo)賽選擇。根據(jù)序值和擁擠度進(jìn)行選擇操作，對于種群中的兩個(gè)隨機(jī)個(gè)體，當(dāng)序值不同時(shí)，序值小的個(gè)體將被選中；當(dāng)序值相同時(shí)，擁擠距離大的個(gè)體將被選中。

（2）交叉：單點(diǎn)交叉。并運(yùn)用同位基因的思想進(jìn)行交叉前的處理。

（3）變異：為避免在前兩個(gè)操作中優(yōu)秀基因的丟失，選擇隨機(jī)性更大的對調(diào)基因位的變異方式。

6）變領(lǐng)域操作：從變異后種群中隨機(jī)選部分個(gè)體進(jìn)行變鄰域操作。首先，隨機(jī)選擇一種鄰域結(jié)構(gòu)對初始鄰域種群進(jìn)行鄰域操作，再將變鄰域產(chǎn)生的種群與初始鄰域種群進(jìn)行合并，對合并后的種群進(jìn)行選擇得到新一代鄰域種群。最后，判斷是否滿足鄰域終止條件，滿足則結(jié)束，不滿足則返回再執(zhí)行變鄰域操作直到滿足鄰域終止條件。

7）種群合并：將變領(lǐng)域搜索產(chǎn)生的個(gè)體與變異之后未進(jìn)行變鄰域操作的個(gè)體合并再與初始父種群合并。

8）生成新種群：根據(jù)父代種群規(guī)模對合并后的種群進(jìn)行修剪生成新的父代種群。

9）判斷是否達(dá)到終止條件，若滿足則結(jié)束，否則，轉(zhuǎn)去執(zhí)行步驟5）。

2.1 染色體編碼

本文針對貨位優(yōu)化設(shè)計(jì)了一種基于貨位和貨物類型順序的編碼方式。貨位由倉庫貨架的排、列、層組成，則每條染色體長度為3N，N為貨物總數(shù)。如圖3 所示，假設(shè)一批貨物分為兩類，第一類貨物總數(shù)為4在貨架上的貨位為(1,2,1)，(2,4,5)，(4,3,1)，(5,4,3)，第二類貨物總數(shù)為3在貨架上的貨位為(1,4,3)，(1,5,3)，(3,4,1)。

圖3 染色體編碼

2.2 變鄰域操作

設(shè)計(jì)三種鄰域結(jié)構(gòu)進(jìn)行變鄰域操作：

1）鄰域1：前插入操作，從染色體基因序列中隨機(jī)選擇兩個(gè)不同的基因位點(diǎn)，在前基因位之前插入后基因，如圖4所示。

圖4 前插入變鄰域操作

2）領(lǐng)域2：后插入操作，從染色體基因序列中隨機(jī)選擇兩個(gè)不同的基因位點(diǎn)，在后基因位之前插入前基因，如圖5所示。

圖5 后插入變鄰域操作

3）領(lǐng)域3：基因片段倒序，從染色體基因序列中隨機(jī)選擇兩個(gè)不同的基因位點(diǎn)，然后將基因片段進(jìn)行倒序操作，如圖6所示。

圖6 基因片段倒序變鄰域操作

3 實(shí)例驗(yàn)證及分析

為了檢驗(yàn)優(yōu)化模型的有效性和變鄰域NSGA-Ⅱ算法的優(yōu)越性，以某車間自動化立體倉庫的實(shí)際數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)分析。

1）數(shù)據(jù)與參數(shù)

自動化立體倉庫共3條巷道和一條傳送帶，即巷道編號h從1到3，堆垛機(jī)工作巷道的寬度為1.5m。倉庫貨架6排6列5層，每個(gè)貨位的長、寬、高都為1m，傳送帶平均速度Vx=1.5m/s，堆垛機(jī)沿巷道方向平均速度Vy=1m/s，堆垛機(jī)沿巷道豎直方向平均速度Vz=0.5m/s。貨架平面布局圖如圖7所示。有5種類型的貨物共100個(gè)需要分配到合適的倉庫位置。貨物基礎(chǔ)信息如表1所示。NSGA-Ⅱ算法和變鄰域NSGA-Ⅱ算法參數(shù)賦值如表2所示。

表1 貨物信息表

表2 變鄰域NSGA-Ⅱ算法參數(shù)賦值及含義

圖7 貨架平面布局圖

2）實(shí)驗(yàn)結(jié)果與分析

通過上文的方法進(jìn)行編碼和求解，先運(yùn)用NSGA-Ⅱ算法求解無巷道堆垛機(jī)工作量平衡目標(biāo)和考慮巷道堆垛機(jī)工作量平衡目標(biāo)，驗(yàn)證模型的有效性；再運(yùn)用變鄰域NSGA-Ⅱ算法求解考慮巷道堆垛機(jī)工作量平衡目標(biāo)，并與NSGA-Ⅱ算法求解結(jié)果進(jìn)行對比，驗(yàn)證算法的優(yōu)越性。應(yīng)用MATLAB R2014a軟件編程實(shí)現(xiàn)算法，分別運(yùn)行10次取運(yùn)行結(jié)果的平均值進(jìn)行比較，如表3所示。

通過表3對比NSGA-Ⅱ算法求解考慮和不考慮巷道堆垛機(jī)工作量均衡目標(biāo)可以得到，出入庫效率、貨架整體重心、同類貨物間距離變化很小，而巷道堆垛機(jī)工作量平衡性提高了13.06%。通過對比變鄰域NSGA-Ⅱ算法與NSGA-Ⅱ算法求解考慮巷道堆垛機(jī)工作量均衡目標(biāo)的計(jì)算結(jié)果可以看出，其他目標(biāo)值變化不大，而巷道堆垛機(jī)工作量平衡性提高了54.39%，得到極大地提高。顯而易見，所提出的變鄰域NSGA-Ⅱ算法優(yōu)化結(jié)果更好。

表3 變鄰域NSGA-Ⅱ與NSGA-Ⅱ計(jì)算結(jié)果對比表

4 結(jié)語

本文基于巷道堆垛機(jī)工作量均衡進(jìn)行貨位分配并創(chuàng)建多目標(biāo)優(yōu)化數(shù)學(xué)模型，采用變鄰域NSGA-Ⅱ算法對遺傳操作后的個(gè)體進(jìn)行變鄰域操作以增強(qiáng)算法搜索能力，實(shí)驗(yàn)結(jié)果表明改進(jìn)算法結(jié)果更優(yōu)，而考慮巷道平衡后各條巷道的堆垛機(jī)工作量更加均衡，各類貨物在各條巷道的分布也更加合理。