考慮AGV路徑規(guī)劃的智能制造流水線車間布局研究

畢 娜

(浙江工業(yè)大學(xué) 機(jī)械工程學(xué)院,浙江 杭州 310023)

制造業(yè)是國(guó)民經(jīng)濟(jì)的主體,在當(dāng)前信息技術(shù)高速發(fā)展的有利條件下,將制造業(yè)向智能化轉(zhuǎn)型是制造業(yè)發(fā)展的迫切需求。智能制造是新一輪工業(yè)革命的核心技術(shù),是“中國(guó)制造2025”的主攻方向[1]。在智能化支撐下的制造業(yè),其生產(chǎn)環(huán)境將會(huì)發(fā)生一系列變化。如大量采用了機(jī)器人、立庫(kù)和AGV等智能技術(shù)后,其制造全過(guò)程的調(diào)度需求無(wú)疑發(fā)生了全方位的改變。因此,新環(huán)境下生產(chǎn)系統(tǒng)的車間布置研究變得尤為迫切,通過(guò)計(jì)算機(jī)智能方法對(duì)其進(jìn)行研究,促進(jìn)智能制造的進(jìn)一步發(fā)展。通過(guò)智慧感知獲取環(huán)境信息和資源狀態(tài),實(shí)現(xiàn)人、機(jī)和物三者的互聯(lián)互通[2]。在智能制造中,傳統(tǒng)的人工叉車搬運(yùn)物料將逐步被智能化的物料運(yùn)輸方式所代替,如采用AGV進(jìn)行車間物料運(yùn)輸。全面應(yīng)用AGV能夠大大提高企業(yè)的生產(chǎn)效率以及制造系統(tǒng)的靈活性與柔性,從而實(shí)現(xiàn)智能制造車間的自動(dòng)化。因此,制造業(yè)從傳統(tǒng)模式往數(shù)字化、智能化轉(zhuǎn)型的過(guò)程中,在新廠建成布局時(shí)就應(yīng)該考慮AGV的最優(yōu)路徑。

有關(guān)車間布局的研究已趨于成熟,Hosseini等[3]在設(shè)施布局規(guī)劃時(shí)考慮了生產(chǎn)周期和生產(chǎn)率;Suhardini等[4]在設(shè)施布局過(guò)程中,除了考慮到物流成本最小因素,還考慮了不同作業(yè)單位間密切程度的最大化約束;馮定忠等[5]基于U型布局構(gòu)建了單元制造系統(tǒng);陳勇等[6]提出了針對(duì)一類多態(tài)性作業(yè)車間的低熵化布局評(píng)價(jià)指標(biāo);陳勇等[7]針對(duì)注塑車間建立了單元系統(tǒng)布局與關(guān)聯(lián)優(yōu)化集成模型;葛曉梅等[8]、馬玉瑩等[9]以及韓昉等[10]通過(guò)改進(jìn)算法來(lái)優(yōu)化加工車間布局。在現(xiàn)有的研究中,一并考慮AGV最優(yōu)路徑的車間布局研究則相對(duì)較少。何永樂(lè)[11]在確定設(shè)備布局的同時(shí)考慮AGV的路徑規(guī)劃對(duì)系統(tǒng)總運(yùn)輸量的影響,采用禁忌搜索算法對(duì)初始解進(jìn)行優(yōu)化以確定回路的最終布局順序;侯魯洋[12]構(gòu)建了涵蓋AGV系統(tǒng)多個(gè)子問(wèn)題的綜合設(shè)計(jì)數(shù)學(xué)模型;劉莊成[13]研究了車間布局與AGV系統(tǒng)的協(xié)同設(shè)計(jì)問(wèn)題,給出了車間布局與AGV系統(tǒng)整體設(shè)計(jì)方案;葛華輝等[14]建立了智能制造數(shù)字化車間布局和AGV路徑規(guī)劃集成優(yōu)化模型,并提出了一種改進(jìn)的帶精英策略的快速非支配排序遺傳算法。不同產(chǎn)品類型的布置方式在考慮使用AGV時(shí)所采用的建模方法和求解方式不同,需要做不同的研究。筆者研究適合產(chǎn)品品種較少但數(shù)量較大的生產(chǎn)方式,即帶有AGV路徑優(yōu)化的流水線車間布局。流水線車間的各條流水線相對(duì)獨(dú)立,各流水線最后一道工序后續(xù)又有一起加工的要求,因此,不能將各流水線進(jìn)行簡(jiǎn)單地串聯(lián),且每條流水線又無(wú)法形成閉環(huán),導(dǎo)致AGV空行程多,研究考慮AGV規(guī)劃的流水線車間布局以提高車間生產(chǎn)效率。

1 模 型

1.1 問(wèn)題描述及相關(guān)假設(shè)

傳統(tǒng)流水生產(chǎn)線布局如圖1所示。圖1中:Mij代表第i條流水線的第j臺(tái)設(shè)備(i=1,2,…,m;j=1,2,…,nm);m代表流水線的條數(shù);ni代表第i條流水線的設(shè)備數(shù)(i=1,2,…,m);Msp代表各流水線的后續(xù)工序。這種布局方式的問(wèn)題在于:設(shè)備之間的物流量都是從前一道工序設(shè)備往后一道工序設(shè)備進(jìn)行搬運(yùn),當(dāng)AGV運(yùn)行到流水線最后一道工序設(shè)備再返回到第一道工序設(shè)備時(shí),第二批物料搬運(yùn)的過(guò)程都是空行程,造成AGV運(yùn)行效率低下。

圖1 傳統(tǒng)流水線布局Fig.1 The layout of flow shop

在按產(chǎn)品布置的流水線智能車間中,為完成一批已知加工順序工件的加工計(jì)劃,需要給出流水線車間設(shè)備合理布局和AGV路徑方案,使車間物料運(yùn)輸總成本最低及AGV路徑最短。同一條流水線的設(shè)備前后順序固定,工序固定;不同流水線的位置及相對(duì)距離可變。

對(duì)智能制造流水線布局作如下假設(shè):1) 有若干條流水線,各生產(chǎn)線的加工順序一定,各流水線之間的相對(duì)布局未知;2) 布局的設(shè)備,不考慮其形狀,假設(shè)均為尺寸大小相同的矩形;3) 設(shè)備間物料搬運(yùn)的優(yōu)先級(jí)相同;4) AGV物料運(yùn)輸路徑只能為水平或垂直方向;5) AGV一次運(yùn)輸一批物料;6) 物料存放在各設(shè)備的中心;7) 該系統(tǒng)的AGV為單一負(fù)載車輛、雙向運(yùn)行。

流水線車間共有m條流水線,每條流水線的設(shè)備數(shù)量不盡相同,用ni表示,i={1,2,…,m},nmax表示各流水線中設(shè)備最多的數(shù)量。智能制造流水線設(shè)備可選位置如圖2所示。圖2中:X軸和Y軸分別代表車間的水平方向和垂直方向;提供m行,nmax列,共m×nmax個(gè)可選位置;Lij代表第i行第j列的位置,其中i={1,2,…,m},j={1,2,…,nmax}。

圖2 智能制造流水線設(shè)備可選位置示意圖Fig.2 The available locations of the equipment

考慮到幾條流水線的后續(xù)工序通常需要把不同流水線的物料集中到一起,應(yīng)建立一個(gè)物料集中區(qū)。根據(jù)m和nmax的數(shù)值特點(diǎn),物料集中區(qū)的位置設(shè)置可分為4種情形,如圖3所示。圖3中的○代表物料集中區(qū),用Mtt表示。當(dāng)m為偶數(shù),nmax為奇數(shù)時(shí),物料集中區(qū)的位置如圖3(a)所示;當(dāng)m為奇數(shù),nmax為偶數(shù)時(shí),物料集中區(qū)的位置如圖3(b)所示;當(dāng)m,nmax均為奇數(shù)時(shí),物料集中區(qū)的位置如圖3(c)所示;當(dāng)m,nmax均為偶數(shù)時(shí),物料集中區(qū)的位置如圖3(d)所示。各設(shè)備之間及設(shè)備與物料集中區(qū)之間的距離為X方向及Y方向的坐標(biāo)差值之和。

圖3 物料集中區(qū)Fig.3 The material collection point

1.2 目標(biāo)函數(shù)

考慮按產(chǎn)品分類的流水線布局,其工藝順序既定,則車間總物流量為

(1)

式中:fijkl為第i條流水線設(shè)備k到第j條流水線設(shè)備l之間的物流量;dijkl為第i條流水線設(shè)備k到第j條流水線設(shè)備l之間的距離;ni為第i條流水線的設(shè)備數(shù);m為流水線的條數(shù)。由于不同生產(chǎn)線之間無(wú)物流量,當(dāng)i≠j時(shí),fijkl=0;同一條流水線中,只有前后工序設(shè)備間有物流量,所以當(dāng)i=j時(shí),l=k+1。當(dāng)diik(k+1)最小,F即最小,車間總物流量最小的目標(biāo)值無(wú)法衡量流水線智能車間的布局是否最優(yōu)。此時(shí),應(yīng)再設(shè)立一個(gè)目標(biāo),即AGV路徑最短。以一條流水線的物流運(yùn)輸使用一臺(tái)AGV為例,AGV運(yùn)行一次的路徑為

(2)

式中:diik(k+1)為某條流水線相鄰工序設(shè)備間的距離;dii1ni為首道工序和末道工序設(shè)備間的距離;dMiniMtt為第i條流水線最后一道工序設(shè)備和物料集中區(qū)的距離;ni為第i條流水線的設(shè)備數(shù);m為流水線的條數(shù)。因?yàn)锳GV運(yùn)行為一整條路線,所以運(yùn)行次數(shù)由該條流水線某相鄰兩道工序間物流量的最大值決定,將這個(gè)值視為該條流水線的物流量,其計(jì)算式為

Fi=max{fiik(k+1)}
i=1,2,…,m;k=1,2,…,ni-1

(3)

式中fiik(k+1)為某條流水線相鄰工序間的物流量。若幾條流水線串聯(lián)成AGV回路,以兩條流水線為例,分別為第p條和第q條流水線,則該AGV回路的路徑為

(4)

該條回路的物流量為

Fp=Fq=max{fppk(k+1),fqqk(k+1)}

(5)

所有AGV的最短路徑,即目標(biāo)函數(shù)為

(6)

1.3 約束條件

因?yàn)閹讞l流水線的后續(xù)工序通常需要把不同流水線的物料集中到一起,所以不同的流水線不能簡(jiǎn)單使用串聯(lián)的方式來(lái)運(yùn)行。為了使Di最小,需要考慮放棄流水線直線布局,改為環(huán)形布局。若各條流水線的物流運(yùn)輸量相對(duì)均衡,且均在單臺(tái)AGV運(yùn)載能力范圍內(nèi),則考慮每一條流水線一臺(tái)AGV。把每條流水線各自布局為環(huán)形,并使各條流水線完成最后一道工序的設(shè)備盡可能靠近物料集中區(qū)。若其中兩條或者多條生產(chǎn)線物流運(yùn)輸量較少,則考慮這幾條流水線串聯(lián)成一條回路,現(xiàn)在只研究單臺(tái)AGV能夠負(fù)荷幾條流水線物流量的情況。

構(gòu)建一個(gè)r×s矩陣,代表r×s個(gè)設(shè)備可選位置,即

其中:r=m;s=nmax。相鄰位置之間的距離記為d,將各條流水線的設(shè)備分配到各個(gè)位置當(dāng)中,并滿足

diik(k+1)=di=1,2,…,m;k=1,2,…,ni-1

(7)

2 改進(jìn)遺傳算法

為了求解智能制造流水線布局問(wèn)題,現(xiàn)將交叉算子和變異算子做一定的改進(jìn),以此來(lái)改進(jìn)遺傳算法。

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

由于流水線車間布局問(wèn)題屬于多條流水線的位置問(wèn)題,采用位置編號(hào)的編碼,長(zhǎng)度為位置的數(shù)量。車間可以提供r行s列的矩陣,共r×s個(gè)位置,每個(gè)位置以所在行和列的數(shù)字表示。如可以提供3×3個(gè)位置,則編碼可以為[11,12,13,21,22,23,31,32,33]。

剩余的數(shù)字則代表該位置為空位。如車間有3條流水線,第1條流水線有3臺(tái)設(shè)備,第2條和第3條均為2臺(tái)設(shè)備。則M11的位置在L11;M12的位置在L12;M13的位置在L13;M21的位置在L21;M22的位置在L22;M31的位置在L23;M32的位置在L31;L32和L33為空位,沒(méi)有設(shè)備。

2.2 初始種群的產(chǎn)生

因?yàn)椴季謫?wèn)題的研究對(duì)象是流水線車間,所以不能隨機(jī)產(chǎn)生一個(gè)編碼,降低運(yùn)行效率?？梢酝ㄟ^(guò)將流水線依次排上這種布局方式來(lái)產(chǎn)生初始編碼,雖然這種方法不能對(duì)AGV的路徑加以考慮和規(guī)劃,但是得到的都是可行解。這一部分初始種群可以減小遺傳算法的搜索范圍,使初始種群能夠更廣泛地分布,并且能夠避免改進(jìn)后的遺傳算法過(guò)早陷入局部最優(yōu)。

2.3 適應(yīng)度函數(shù)和選擇操作

選擇操作是基于染色體適應(yīng)度函數(shù)值進(jìn)行的遺傳操作。適應(yīng)度較高的染色體將會(huì)以較大概率被選擇到下一代,適應(yīng)度較低的染色體將以較小的概率被選擇到下一代。根據(jù)問(wèn)題的實(shí)際情況,選擇最優(yōu)保存策略的選擇操作。

記錄當(dāng)前種群中適應(yīng)度最高的染色體Vmin,經(jīng)過(guò)選擇、交叉和變異后,若下一代種群中所有染色體的適應(yīng)度均小于Vmin的適應(yīng)度,則用Vmin取代下一代種群中適應(yīng)度最低的染色體[15]。最優(yōu)保存策略可使得種群中的最優(yōu)染色體不會(huì)由于經(jīng)過(guò)選擇、交叉和變異等遺傳操作而遭到破壞,其適應(yīng)度函數(shù)如式(1,6)所示。

2.4 交叉操作

由于編碼方式的特殊性,因此不能任意選擇兩個(gè)交叉位進(jìn)行交叉。通過(guò)改進(jìn)臨邊重組法,建立鄰接表來(lái)實(shí)現(xiàn)交叉操作。先將編碼[11,12,13,21,22,23,31,32,33]轉(zhuǎn)變?yōu)榫仃?

根據(jù)該矩陣中各數(shù)據(jù)建立鄰接表,表示與某個(gè)基因值相鄰的所有基因。建立的鄰接表如表1所示。由表1可知:從確定第1個(gè)基因值開(kāi)始,更新鄰接表,依次確定各個(gè)基因值。改進(jìn)后的交叉操作能夠較好地保證解的可行性。

表1 鄰接表

2.5 變異操作

因?yàn)榱魉€的特殊性,不能隨機(jī)選取一個(gè)基因,將其基因值插入到另一個(gè)隨機(jī)選取的基因位前,會(huì)使得求解變得沒(méi)有效率。改進(jìn)插入變異法,將整個(gè)基因編碼,按照流水線的數(shù)量,劃分為m+1個(gè)基因串,其中一個(gè)基因串為空位。改進(jìn)后的變異操作只在某個(gè)基因串里進(jìn)行,選擇基因串里的最后一個(gè)基因,將其基因值插入到該基因串第1個(gè)基因位前。如將編碼根據(jù)流水線數(shù)量劃分為[11,12,13,21,22,23,31,32,33],選擇第1個(gè)基因串進(jìn)行變異操作,變異操作后的編碼為[13,11,12,21,22,23,31,32,33]。

3 算 例

3.1 算例1及其優(yōu)化

某車間為流水線車間,共有4條流水線,各流水線分別有5,4,4,3組設(shè)備,設(shè)備之間的物料搬運(yùn)量如表2所示。根據(jù)表2提供的數(shù)據(jù),計(jì)算出各條流水線物流量相對(duì)均衡,采用一條流水線使用一臺(tái)AGV進(jìn)行物料搬運(yùn)的方式。

表2 各設(shè)備之間的物料搬運(yùn)量之情形1

根據(jù)式(3)可計(jì)算出:F1=max{f11k(k+1)}=max{f1112,f1123,f1134,f1145}=50;F2=50;F3=60;F4=70。車間可以提供5×4=20個(gè)位置,相鄰位置之間的距離d設(shè)定為1,則設(shè)備可選的位置和物料集中區(qū)如圖4所示。

圖4 設(shè)備可選位置及物料集中區(qū)Fig.4 The available locations of the equipmentand the material collection point

采用改進(jìn)遺傳算法對(duì)智能制造流水線車間布局問(wèn)題進(jìn)行求解,得出解為[13,12,11,21,22,42,41,31,32,43,44,34,33,14,24,23,15,25,35,45],其最優(yōu)路徑值為1 350。算法收斂曲線如圖5所示,布局圖如圖6所示。

圖5 算法收斂曲線Fig.5 The algorithm convergence curve

圖6 最優(yōu)解位置分布Fig.6 The location distribution of the optimal solution

3.2 算例2及其優(yōu)化

某車間為流水線車間,共有4條流水線,各流水線分別有5,4,4,3組設(shè)備,各設(shè)備間的運(yùn)輸量如表3所示。根據(jù)表3提供的數(shù)據(jù),計(jì)算出各條流水線物流量的差別較大,采用第1條和第2條流水線分別單獨(dú)使用1臺(tái)AGV,第3條和第4條流水線公用1臺(tái)AGV進(jìn)行物料搬運(yùn)的方式。由式(3)可計(jì)算得出:F1=max{f11k(k+1)}=max{f1112,f1123,f1134,f1145}=70,F2=80;由式(5)可計(jì)算得出:F3=F4=max{f33k(k+1),f44k(k+1)}=max{f3312,f3323,f3334,f4412,f4423}=50。車間可以提供5×4=20個(gè)位置,相鄰位置之間的距離d設(shè)為1,設(shè)備可選位置和物料集中區(qū)仍然如圖4所示。采用改進(jìn)遺傳算法對(duì)智能制造流水線車間布局問(wèn)題進(jìn)行求解,得出解為[12,11,21,31,32,13,14,24,23,44,45,35,34,42,43,33,15,25,22,41],其最優(yōu)路徑值為1 630。算法收斂曲線如圖7所示,布局圖如圖8所示。

表3 各設(shè)備之間的物料搬運(yùn)量之情形2

圖7 算法收斂曲線Fig.7 The algorithm convergence curve

圖8 最優(yōu)解位置分布Fig.8 The location distribution of the optimal solution

3.3 方法比較

比較成熟的方法是先對(duì)智能制造流水線車間的設(shè)備布局進(jìn)行規(guī)劃,再對(duì)AGV路徑進(jìn)行優(yōu)化。根據(jù)上述2個(gè)算例,將其與筆者方法進(jìn)行對(duì)比驗(yàn)證。算例1中,首先以物流量最小為優(yōu)化目標(biāo);然后使各流水線最后一道工序盡量靠近下一道工序,得到優(yōu)化的設(shè)備布局為[11,12,13,14,15,42,43,44,45,22,23,24,25,33,34,35,21,31,32,41];最后優(yōu)化AGV路徑,得到路徑值為2 290。算例2中,得到優(yōu)化的設(shè)備布局為[21,22,23,24,25,32,33,34,35,12,13,14,15,43,44,45,11,31,41,42],得到的AGV路徑優(yōu)化值為2 380。經(jīng)對(duì)比,筆者方法可行、有效,能較好地提高運(yùn)輸效率,提升生產(chǎn)效率。同時(shí)發(fā)現(xiàn),各流水線物流量較均衡的情況下,筆者方法可以使AGV運(yùn)行效率提升。

4 結(jié) 論

提出了一種同時(shí)考慮設(shè)備布局與AGV路徑優(yōu)化的智能制造流水線車間模型,并采用改進(jìn)交叉和變異算子的遺傳算法對(duì)其求解。基于流水線車間的特點(diǎn),結(jié)合AGV路徑規(guī)劃的要求,將各流水線布局設(shè)立為環(huán)形布局,并使每條流水線最后一道工序設(shè)備盡可能靠近物料集中區(qū)。改進(jìn)的遺傳算法采用位置編號(hào)的編碼,長(zhǎng)度為位置的數(shù)量,改進(jìn)了交叉算子和變異算子,保證解的可行性。通過(guò)算例分析,驗(yàn)證了筆者方法的可行性和有效性。后續(xù)的研究將重點(diǎn)考慮AGV路徑規(guī)劃的智能制造車間其他生產(chǎn)方式的設(shè)備布局,以適應(yīng)智能制造大環(huán)境下,各類型企業(yè)的不同需求。