熊 曄，毛劍琳

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500)

自動(dòng)導(dǎo)引車(chē)(Automated Guided Vechicle，AGV)在柔性制造系統(tǒng)、自動(dòng)化集裝箱碼頭、自動(dòng)化倉(cāng)儲(chǔ)以及物流業(yè)中應(yīng)用廣泛[1]。多載AGV是一種水平作業(yè)設(shè)備，一次搬運(yùn)一件以上的制件，能大幅度提高了作業(yè)效率[2]。在傳統(tǒng)的AGV調(diào)度研究中，大多數(shù)都是假定AGV系統(tǒng)的緩沖區(qū)容量無(wú)限且以單載AGV研究為主，對(duì)多載且緩沖區(qū)容量有限得AGV系統(tǒng)研究甚少。

Azimi等[3]用仿真實(shí)驗(yàn)提出了單載AGV的最優(yōu)調(diào)度策略；Ho等[4]提出了同時(shí)求解多載AGV的負(fù)載選擇和裝載調(diào)度問(wèn)題的多屬性方法；Fazlollahtabar等[5]提出了一種自動(dòng)化集裝箱碼頭最小化多載AGV提前與延遲時(shí)間的綜合啟發(fā)算法；谷寶慧[6]針對(duì)單載AGV載重和運(yùn)送貨箱體積限定問(wèn)題簡(jiǎn)歷AGV路徑優(yōu)化模型，利用改進(jìn)的量子微粒群算法進(jìn)行實(shí)現(xiàn)；杜亞江[7]等建立了復(fù)雜約束的單載AGV多參數(shù)問(wèn)題數(shù)學(xué)模型，采用混合遺傳算法優(yōu)化了調(diào)度時(shí)間。

以上研究大多以緩沖區(qū)容量有限、AGV只能進(jìn)行單載操作為主。在實(shí)際的FMS中，多數(shù)AGV系統(tǒng)加工區(qū)中緩沖區(qū)容量都是有限的，且多載AGV有著節(jié)約運(yùn)輸成本、提高整體系統(tǒng)效率的優(yōu)點(diǎn)。因此，對(duì)柔性制造系統(tǒng)(Flexible Manufacturing System，F(xiàn)MS)中的加工區(qū)緩沖區(qū)容量的多載AGV調(diào)度進(jìn)行研究具有十分重要的理論和應(yīng)用價(jià)值。

本文從提高柔性制造系統(tǒng)AGV作業(yè)效率入手，以加工區(qū)緩沖區(qū)容量、AGV的負(fù)載為約束，建立緩沖區(qū)容量有限的多載AGV調(diào)度模型，使用融合了灰狼優(yōu)化算法思想的混合灰狼遺傳算法求解，并與傳統(tǒng)遺傳算法進(jìn)行對(duì)比，模擬實(shí)驗(yàn)結(jié)果驗(yàn)證了新算法的優(yōu)越性。

1 問(wèn)題描述

一個(gè)典型的柔性制造系統(tǒng)作業(yè)車(chē)間包括AGV小車(chē)、緩沖區(qū)有限的加工區(qū)、導(dǎo)向網(wǎng)絡(luò)和倉(cāng)庫(kù)，其平面構(gòu)造圖如圖1所示。AGV按需求一次可運(yùn)送一個(gè)大制件或者兩個(gè)小制件進(jìn)入FMS中，由倉(cāng)庫(kù)駛出進(jìn)入FMS，經(jīng)過(guò)5個(gè)加工區(qū)的作業(yè)后返回倉(cāng)庫(kù)，即為完成一個(gè)循環(huán)。

圖1 柔性制造系統(tǒng)作業(yè)車(chē)間的構(gòu)造平面圖

一個(gè)特定FMS中有一個(gè)AGV和一個(gè)制件集，目的是最小化所有任務(wù)時(shí)間：計(jì)算出每個(gè)制件在每臺(tái)機(jī)器的加工時(shí)間以及每個(gè)輸入/輸出緩沖區(qū)的時(shí)間，從而確定每個(gè)機(jī)器與機(jī)器之間所走路程的起始和完成時(shí)間。

2 模型建立

在數(shù)學(xué)模型中，符號(hào)定義如下：

M：加工區(qū)集；

W：制件集；

A：搬運(yùn)任務(wù)集；

N：任務(wù)次序集；

G：系統(tǒng)允許的最大制件量；

m：加工區(qū)編號(hào)，m∈M，Mo表示倉(cāng)庫(kù)；

w：制件編號(hào)，w∈W；

A：任務(wù)編號(hào)，a∈A；

n：任務(wù)執(zhí)行的次序編號(hào)，n∈N；

CIm：加工區(qū)m的輸入緩沖區(qū)容量，CIm>0；

COm：加工區(qū)m的輸出緩沖區(qū)容量，COm=CIm；

CImh：加工區(qū)m的輸入緩沖區(qū)的剩余可容納制件的量；

Im：加工區(qū)m的輸入緩沖區(qū)上的制件個(gè)數(shù)；

COmh：加工區(qū)m的輸出緩沖區(qū)的剩余可容納制件的量；

Cm：加工區(qū)m的輸出緩沖區(qū)上的制件數(shù)。

Um：表示在加工區(qū)m上現(xiàn)有的制件數(shù)；

Twm：制件w在加工區(qū)m上的加工時(shí)間；

Uwm：表示制件w在加工區(qū)m上加工；

Tbm：為制件w在加工區(qū)m上的開(kāi)始加工時(shí)間；

Tem：為制件w在加工區(qū)m上的結(jié)束加工時(shí)間；

Tq：AGV裝載制件的固定時(shí)間；

Tf：AGV卸載制件的固定時(shí)間；

Tba：AGV的搬運(yùn)任務(wù)a的開(kāi)始時(shí)間；

Tea：AGV的搬運(yùn)任務(wù)a的結(jié)束時(shí)間；

Tb(m1,m2)：AGV從加工區(qū)m1移動(dòng)到m2的所用時(shí)間；

Ta：AGV執(zhí)行任務(wù)a所用的時(shí)間；

Cq：任務(wù)q完成操作后AGV容量的占用情況；

C：AGV最大負(fù)荷能力；

D：AGV在任務(wù)q完成后的容量改變情況。

定義決策變量

緩沖區(qū)容量有限的多載AGV調(diào)度問(wèn)題，以最小化多載AGV完成調(diào)度集內(nèi)所有任務(wù)花費(fèi)時(shí)間最短為目標(biāo)，建立數(shù)學(xué)模型，模型的目標(biāo)函數(shù)與約束條件如下

(1)

式(1)表示自動(dòng)導(dǎo)引小車(chē)完成調(diào)度集內(nèi)全部任務(wù)所用最短時(shí)間。自動(dòng)導(dǎo)引小車(chē)每次完成且只完成一個(gè)任務(wù)以式(2)表示。

(2)

搬運(yùn)任務(wù)a的結(jié)束時(shí)間減去開(kāi)始時(shí)間為AGV完成一次搬運(yùn)任務(wù)所耗費(fèi)的時(shí)間

Tea-Tba=xnaTa,?a∈A,n∈N

(3)

后一個(gè)任務(wù)開(kāi)始時(shí)間等于前一個(gè)任務(wù)的結(jié)束時(shí)間，即

x(n+1)kTbk=xnaTea,?a,k∈A∩a≠k,n∈N

(4)

加工區(qū)輸出緩沖區(qū)上有多個(gè)制件，則存在一個(gè)加工區(qū)分配多個(gè)搬運(yùn)任務(wù)時(shí)，在調(diào)度時(shí)段，相同加工區(qū)的任務(wù)只能按分配時(shí)間的先后執(zhí)行

n>1,Cm>1,xnaTbm>xlkTem,?a,k∈A∩a≠k,n,
l∈N∩n≠1

(5)

一個(gè)加工區(qū)一次只能加工一個(gè)制件

bmwj+bmjw=1,?w,j∈W,m∈M

(6)

系統(tǒng)現(xiàn)有制件數(shù)不可超過(guò)系統(tǒng)承受的最大制件數(shù)

(7)

輸入緩沖區(qū)的容量不滿時(shí)，完成一次搬運(yùn)任務(wù)所耗時(shí)等價(jià)于小車(chē)從當(dāng)前位置空載移動(dòng)到目標(biāo)制件所在的加工區(qū)、目標(biāo)制件裝載的時(shí)間、AGV移動(dòng)到目標(biāo)加工區(qū)輸入緩沖區(qū)的時(shí)間、目標(biāo)制件卸載的時(shí)間的總和

xnaTa=Tb(Ya,Xwa)+Tq+Ta(XwaUwm)+Tf,CImh≠0,
?a∈A,w∈W,n∈N

(8)

輸入緩沖區(qū)的剩余容量為零時(shí)，AGV完成一次搬運(yùn)任務(wù)所耗時(shí)等價(jià)于在目標(biāo)加工區(qū)上的制件的結(jié)束加工時(shí)間及目標(biāo)制件卸載的時(shí)耗總和

xnaTa=ymwTem+Tf,CImh=0,ymwj=1,?w,j∈W,
w≠j,a∈A,n∈N

(9)

輸入/輸出緩沖區(qū)的剩余容量為輸入/輸出緩沖區(qū)容量減去輸入/輸出緩沖區(qū)上的制件數(shù)

CImh=CIm-Im,?m∈M

(10)

COmh=COm-Om,?m∈M

(11)

輸入緩沖區(qū)的制件數(shù)、輸出緩存區(qū)上的制件、加工區(qū)上正在加工的制件數(shù)的總和即為加工區(qū)現(xiàn)有的制件數(shù)

Um=Im+Om+ymwj,?w,j∈W,w≠j,m∈M

(12)

加工區(qū)的輸出緩存器剩余容量不為零時(shí)，制件的加工結(jié)束時(shí)間等于制件的加工開(kāi)始時(shí)間加上制件在加工區(qū)上的加工時(shí)間

Tem=Tbm+Twm,?m∈M,w∈W,COmh≠0

(13)

加工區(qū)的輸出緩存器為滿時(shí)，制件加工完畢之后需等候進(jìn)入輸出緩存區(qū)

Tem>Tbm+Twm,?m∈M,w∈W,COmh=0

(14)

AGV相繼完成任務(wù)q、p后AGV的負(fù)載變化如下

zqp(Cq+dp-Cp)=0

(15)

對(duì)AGV負(fù)載的約束為

dq≤Cq≤C

(16)

0≤Cp≤C+dp

(17)

3 多載混合灰狼遺傳算法(MHGWOGA)

灰狼優(yōu)化算法(Gery Wolf Optimization，GWO)是由Mirjalili S等[8]在2014年提出的新算法，通過(guò)模仿自然界灰狼種群領(lǐng)導(dǎo)層級(jí)和以及狼群跟蹤、包圍獵物的狩獵過(guò)程來(lái)實(shí)現(xiàn)優(yōu)化。GWO算法能在解空間中快速找出最優(yōu)解，避免出現(xiàn)局部最優(yōu)[9]。

本文將GWO算法中灰狼社會(huì)等級(jí)、狩獵機(jī)制引入至標(biāo)準(zhǔn)遺傳算法的選擇算子中，克服了傳統(tǒng)的遺傳算法易早熟的缺點(diǎn)，提高了算法全局搜索的效率。

3.1 編碼與解碼

本文研究的是AGV任務(wù)排序問(wèn)題，選擇加工區(qū)的序數(shù)方式進(jìn)行編碼[10]，將搬運(yùn)任務(wù)集內(nèi)的任務(wù)進(jìn)行排序，自動(dòng)導(dǎo)引小車(chē)執(zhí)行的任務(wù)的先后順序從而決定制件去加工區(qū)作業(yè)的順序。同一個(gè)加工區(qū)使用相同的編號(hào)，如圖2所示。

圖2 編碼解釋

解碼按照AGV單載、多載需求開(kāi)始進(jìn)行。針對(duì)同一加工區(qū)的不同任務(wù)，AGV會(huì)根據(jù)任務(wù)工件的大小來(lái)判斷是使用單載AGV還是多載AGV執(zhí)行任務(wù)，執(zhí)行任務(wù)的順序是根據(jù)染色體中出現(xiàn)的同一序號(hào)的順序執(zhí)行：同一個(gè)加工區(qū)發(fā)出的第一個(gè)任務(wù)是染色體基因中出現(xiàn)的第一個(gè)序號(hào)，以此類(lèi)推，即可得出同一加工區(qū)的不同任務(wù)的執(zhí)行順序。

3.2 適應(yīng)度函數(shù)

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

(18)

3.3 選擇

選擇操作是為了避免優(yōu)良基因的損失，使性能好的個(gè)體生存繁殖的概率增大[11]。這里采用輪盤(pán)賭和精英選擇結(jié)合的方法。若不采用精英保留策略，僅是采用輪盤(pán)賭選擇算子，會(huì)造成優(yōu)良的個(gè)體缺失，因此引入灰狼優(yōu)化算法來(lái)化解這個(gè)矛盾。

在每一次選擇操作的時(shí)候保留α、β、δ3種個(gè)體，形成如圖3所示的灰狼內(nèi)部社會(huì)等級(jí)地位，三者適應(yīng)度關(guān)系滿足式(19)。剩余的個(gè)體即是ω，整個(gè)種群在α、β、δ的領(lǐng)導(dǎo)下向全局最優(yōu)解進(jìn)化。

圖3 灰狼層級(jí)金字塔圖

(19)

灰狼需先判斷獵物位置并進(jìn)行包圍，數(shù)學(xué)表達(dá)式如下

D=|C*Xp(t)-X(t)|

(20)

其中，Xp(t)表示第t代獵物位置向量；X(t)表示第t代時(shí)灰狼位置向量；常數(shù)C為擺動(dòng)因子[12]，由式(21)決定

C=2r1

(21)

r1為[0,1]區(qū)間的隨機(jī)值，對(duì)灰狼位置更新

X(t+1)=Xp(t)-A*D

(22)

其中收斂因子A由式(23)決定

A=2a*r2-a

(23)

其中，r2亦為[0，1]區(qū)間的隨機(jī)值。a在迭代過(guò)程中從2線性下降到0，計(jì)算公式如式(24)所示

(24)

在追捕過(guò)程中，α帶領(lǐng)β、δ狼完成狩獵行為，即由α、β、δ狼距離獵物的位置，判斷獵物的大致位置后，對(duì)獵物進(jìn)行追捕。狼群狩獵的原理[13]如圖4所示。

圖4 灰狼狩獵原理圖

(25)

Dβ=C2*Xβ(t)-X(t)

(26)

Dδ=C3*Xδ(t)-X(t)

(27)

X1=Xα-A1*Dα

(28)

X2=Xβ-A2*Dβ

(29)

X3=Xδ-A3*Dδ

(30)

X(t+1)=(X1+X2+X3)/3

(31)

其中，Xα表示α當(dāng)前位置，Xβ表示β當(dāng)前位置，Xδ表示δ當(dāng)前位置，X(t)為第t代灰狼的位置向量[14]。由式(25)～式(30) 計(jì)算出個(gè)體與α、β、δ之間的距離，然后由式(31)即可定義出獵物的最終方位。

改進(jìn)后的選擇步驟如下：

步驟1初始化隨機(jī)狼群；

步驟2計(jì)算出每頭狼對(duì)應(yīng)的適應(yīng)度值；

步驟3將適應(yīng)度排列前3的灰狼個(gè)體位置分別記為α、β、δ；

步驟4按照式(25)～式(27)計(jì)算其它個(gè)體與α、β、δ的距離，并根據(jù)式(28)～式(30)計(jì)算每個(gè)灰狼個(gè)體的位置；

步驟5更新參數(shù)a、A、C等參數(shù)的值；

步驟6如不滿足結(jié)束條件，跳轉(zhuǎn)至步驟2；

步驟7導(dǎo)出α狼的位置；

步驟8按輪盤(pán)賭規(guī)則選擇個(gè)體復(fù)制到下一代。

3.4 交叉

本文采用了部分映射交叉方式，隨機(jī)產(chǎn)生兩個(gè)隨機(jī)數(shù)p，q∈[2，n-1]，交換兩個(gè)染色體i和j位于p和q之間的基因片段，映射交叉操作如圖5所示[15]。

圖5 部分映射交叉示意圖

3.5 變異

本文中的變異方法采用倒置變異[16]，也就是在染色體上隨機(jī)選擇兩個(gè)位置，然后顛倒兩個(gè)基因序列，如圖6所示。

圖6 倒置變異示意圖

4 數(shù)學(xué)實(shí)驗(yàn)

為驗(yàn)證混合灰狼遺傳算法的有效性，本文以某柔性制造車(chē)間為例，設(shè)計(jì)一組仿真實(shí)驗(yàn)。該FMS中存在5個(gè)加工區(qū)和1個(gè)倉(cāng)庫(kù)。每個(gè)加工區(qū)均配有容量為3的輸入緩沖區(qū)F1和容量為3的輸出緩沖區(qū)F2。制件從倉(cāng)庫(kù)出發(fā)，經(jīng)過(guò)加工區(qū)后運(yùn)回，倉(cāng)庫(kù)加工區(qū)分別用a、b、c、d、e表示，倉(cāng)庫(kù)用0來(lái)表示。

AGV的移動(dòng)路徑時(shí)間如表1所示，制件在不同加工區(qū)的加工時(shí)間如表2所示。

表1 AGV的移動(dòng)路徑時(shí)間

表2 制件在不同加工區(qū)加工時(shí)間

通過(guò)MATLAB進(jìn)行實(shí)驗(yàn)仿真，使用傳統(tǒng)的遺傳算法和本文設(shè)計(jì)的混合灰狼遺傳算法對(duì)緩沖區(qū)容量有限的多載AGV調(diào)度模型進(jìn)行求解，得出AGV配送及加工完成所有制件的總時(shí)間。參數(shù)設(shè)置如下：初始種群規(guī)模為50；交叉概率Pc為0.6；變異概率Pm為0.01。在制件數(shù)不同的情況下，仿真結(jié)果如表3所示。HGWOGA最優(yōu)解、GA最優(yōu)解的列表示為分別采用單載AGV模型混合灰狼遺傳算法和單載AGV模型遺傳算法進(jìn)行調(diào)度后AGV配送及加工完成所有制件的總時(shí)間。MHGWOGA最優(yōu)解、MGA最優(yōu)解的列表為分別采用多載AGV模型混合灰狼遺傳算法和多載AGV模型遺傳算法進(jìn)行調(diào)度后，AGV配送及加工完成所有制件的總時(shí)間。

表3 制件數(shù)不同時(shí)4種算法的調(diào)度結(jié)果

上表可看出，當(dāng)制件數(shù)<15時(shí)，4種算法都能得到相同的最優(yōu)解。但是隨著制件數(shù)的增加，當(dāng)制件數(shù)>15時(shí)，MHGWOGA算法的調(diào)度時(shí)間要遠(yuǎn)小于HGWOGA算法的調(diào)度時(shí)間，且當(dāng)制件數(shù)>20時(shí)，單載AGV系統(tǒng)已經(jīng)發(fā)生死鎖，而多載AGV系統(tǒng)仍然能運(yùn)行至22個(gè)制件。這說(shuō)明本文所提出的緩沖區(qū)容量有限的混合灰狼遺傳算法多載AGV調(diào)度模型較單載AGV調(diào)度模型的改進(jìn)策略是有效的。

以1表示小制件，2表示大制件，確定制件從倉(cāng)庫(kù)的運(yùn)出次序。以制件數(shù)分別為15、20為例，設(shè)定制件運(yùn)出次序分別為1，2，1，2，1，1，1，1，2，1，2，1，1，2，2和1，2，2，1，1，2，1，2，1，1，2，1，2，1，1，1，1，2，1，1 ，可得出圖7、圖8兩種算法的進(jìn)化迭代圖。

圖7 制件數(shù)為15兩種算法進(jìn)化過(guò)程對(duì)比

圖8 制件數(shù)為20兩種算法進(jìn)化過(guò)程對(duì)比

從圖中可以看出，當(dāng)制件數(shù)為15時(shí)，MGA算法約在10代收斂，MHGWOGA算法約在3代就已經(jīng)達(dá)到收斂；當(dāng)制件數(shù)為20時(shí)，MGA算法約在90代收斂，而MHGWOGA算法約在10代就已經(jīng)達(dá)到收斂，后者的收斂速度要遠(yuǎn)快于前者的收斂速度，且能得到更好的最優(yōu)解。這也說(shuō)明了MHGWOGA算法的有效性。

5 結(jié)束語(yǔ)

本文針對(duì)FMS中緩沖區(qū)容量有限的多載AGV調(diào)度模型，通過(guò)將灰狼優(yōu)化算法中的社會(huì)等級(jí)、狩獵制度引入傳統(tǒng)的遺傳算法中，提出了一種全新的多載混合灰狼遺傳算法，大幅提升了算法的搜索能力。仿真實(shí)驗(yàn)結(jié)果表明，相對(duì)于傳統(tǒng)的遺傳算法，MHGWOGA算法能有效求解緩沖區(qū)容量有限的多載AGV調(diào)度的問(wèn)題，且具有收斂速度快、得到調(diào)度更優(yōu)解及提升AGV調(diào)度效率的優(yōu)點(diǎn)。但在實(shí)際生產(chǎn)中，存在大量有限緩沖區(qū)的多載AGV情況，仍亟待深入研究。