基于自動導(dǎo)引車單向?qū)б窂骄W(wǎng)絡(luò)的智能車間設(shè)備布局規(guī)劃

王 闖,常豐田,高佳佳

(1.西安郵電大學(xué) 物聯(lián)網(wǎng)與兩化融合研究院，陜西 西安 710061; 2.西安交通大學(xué) 機(jī)械制造系統(tǒng)工程國家重點實驗室，陜西 西安 710054; 3.西安交通大學(xué) 機(jī)械工程學(xué)院，陜西 西安 710049)

0 引言

生產(chǎn)車間設(shè)備布局設(shè)計是將加工設(shè)備、物料輸送設(shè)備、工作單元和通道走廊等布局物體合理地放置在一個有限的生產(chǎn)空間內(nèi)的過程[1]?；谧詣訉?dǎo)引車(Automated Guided Vehicle, AGV)的生產(chǎn)設(shè)備布局是整個智能車間布局規(guī)劃的核心問題之一。傳統(tǒng)車間生產(chǎn)設(shè)備布局設(shè)計規(guī)劃方法是基于生產(chǎn)車間物流量最小目標(biāo)建立設(shè)備布局模型，在考慮約束條件下，通過各種優(yōu)化算法得到最終布局方案[2]。錢駿等[3]應(yīng)用單元生產(chǎn)分析的方法，以某機(jī)加工車間轉(zhuǎn)子的整個加工流程為研究對象，通過對該轉(zhuǎn)子零件的加工流程分析，設(shè)備布局分析以及在制品分析，提出轉(zhuǎn)子加工的改善方案。周娜等[4]在設(shè)備混合布局問題研究中，提出了“田”分形理論，并通過總運(yùn)輸成本和布局占用面積最小化為優(yōu)化目標(biāo)，實現(xiàn)對車間設(shè)備的布局設(shè)計。丁祥海等[5]研究了U型生產(chǎn)單元重構(gòu)設(shè)施布局問題，構(gòu)建了具有預(yù)算約束的單元物料搬運(yùn)成本、單元重構(gòu)成本、生產(chǎn)時間損失成本的重構(gòu)設(shè)施布局模型。熊佳瑋等[6]利用MATLAB和Python語言對仿真生產(chǎn)實驗平臺設(shè)備布局系統(tǒng)進(jìn)行設(shè)計與開發(fā)，采用GA-Lyaout算法進(jìn)行優(yōu)化，并且對Python、Flexsim等軟件開放接口，降低了重構(gòu)車間布局的設(shè)計難度，增強(qiáng)了可操作性及便利性。陳春鵬等[7]根據(jù)機(jī)床數(shù)量以及型號進(jìn)行功能區(qū)劃分和功能區(qū)布局，以物流時間最短為目標(biāo)進(jìn)行總體布局。何坤等[8]以某航天所某零件的加工車間為例，使用模擬退火遺傳算法對該車間進(jìn)行布局評價。楊挺等[9]結(jié)合多行多區(qū)域車間的特點，通過定義包含設(shè)備位置點、通道位置點和轉(zhuǎn)向位置點的網(wǎng)絡(luò)節(jié)點以及鄰接矩陣，構(gòu)建設(shè)備布局網(wǎng)絡(luò)模型，給出了設(shè)備之間最短物流路徑的求取方法與步驟。在生產(chǎn)設(shè)備布局設(shè)計規(guī)劃問題中，工程界主要針對具體生產(chǎn)場景和需求進(jìn)行研究[10-12]，而學(xué)術(shù)界開始將各種優(yōu)化算法應(yīng)用到最優(yōu)布局的求解中[13-16]。鄭永前等[17]設(shè)計了基于結(jié)構(gòu)化編碼的動態(tài)多種群粒子群優(yōu)化算法，對單元構(gòu)建與單元布局同時進(jìn)行描述求解。Palomo-Romero等[18]在不等面積設(shè)施布局問題上引進(jìn)了島模型遺傳算法。左興權(quán)等[19]雙行設(shè)備布局問題，提出一種結(jié)合多目標(biāo)免疫算法和線性規(guī)劃的雙行設(shè)備布局方法，同時實現(xiàn)優(yōu)化物流成本和布局面積兩個目標(biāo)。

然而，傳統(tǒng)的設(shè)備布局設(shè)計規(guī)劃方法采用兩個設(shè)備之間的直線距離或者曼哈頓距離作為優(yōu)化變量，而沒有考慮工件搬運(yùn)設(shè)備在實際物料搬運(yùn)過程中行駛的路線[20]。這必然導(dǎo)致最終選擇的生產(chǎn)設(shè)備布局方案，在物流路徑和物流效率上無法做到最優(yōu)。由于傳統(tǒng)車間的工件搬運(yùn)設(shè)備主要通過人工控制或操作，對物流路徑優(yōu)化和物流效率的要求相對較低。但是智能車間中往往采用AGV作為搬運(yùn)工具，顯然，基于直線距離或者曼哈頓距離的傳統(tǒng)設(shè)備布局方案就具有一定局限性[21-22]。從目前的文獻(xiàn)分析來看，基于AGV的智能車間生產(chǎn)設(shè)備布局設(shè)計規(guī)劃問題還沒有得到深入研究。

本文以缸蓋柔性生產(chǎn)設(shè)備布局為例，針對智能車間設(shè)備布局設(shè)計規(guī)劃問題，采用與AGV路徑優(yōu)化相結(jié)合的方式，提出一種雙層嵌套遺傳算法。外層遺傳算法以物流成本最小為目標(biāo)優(yōu)化車間設(shè)備布局，其物流成本的計算需依賴內(nèi)層遺傳算法優(yōu)化后的路徑得出。將混沌思想引入到遺傳算法中(Chaos Genetic Algorithm，CGA)，以提高優(yōu)化效率，有效地避免簡單遺傳算法早熟與局部收斂問題。

1 問題描述

1.1 傳統(tǒng)車間設(shè)備布局建模

車間設(shè)備布局是指不考慮生產(chǎn)車間設(shè)加工設(shè)備的具體形狀，將其簡化成規(guī)則的矩形，用矩形包絡(luò)加工設(shè)備的最大外形尺寸，將包絡(luò)矩形作為設(shè)備的簡化矩形，在給定的車間范圍內(nèi)，確定每個布局對象在空間的具體位置，傳統(tǒng)設(shè)備布局建立問題模型如圖1所示。圖中：L表示車間長度，H表示車間寬度，(xi,yi)表示設(shè)備i的中心坐標(biāo)，(dij)m表示設(shè)備i和設(shè)備j中心坐標(biāo)之間的曼哈頓距離，(dij)o表示設(shè)備i和設(shè)備j中心坐標(biāo)之間的歐式距離。

常用的布局優(yōu)化目標(biāo)函數(shù)如下：

(1)

1.2 傳統(tǒng)設(shè)備布局規(guī)劃方法優(yōu)缺點

傳統(tǒng)設(shè)備布局通過對物料搬運(yùn)過程中產(chǎn)生的物流成本建模，并進(jìn)行優(yōu)化搜索得到最佳的布局方案。在直線單行布局模式中，搬運(yùn)工具在搬運(yùn)過程中行走的距離，即為兩個設(shè)備之間的直線距離，通過式(1)來表示物流成本是合理可行的。研究表明，在其他布局模式中，如果搬運(yùn)工具在運(yùn)行過程中沒有運(yùn)行軌道及運(yùn)行方向的限制，通過兩個設(shè)備間的曼哈頓距離來表示搬運(yùn)工具的運(yùn)行路線可以有效地避免搬運(yùn)工具之間的來回交叉運(yùn)行，是最合理的。然而，在以AGV作為搬運(yùn)工具的智能生產(chǎn)車間中，單向?qū)б窂骄W(wǎng)絡(luò)具有運(yùn)行效率高等其他導(dǎo)引路徑網(wǎng)絡(luò)無法比擬的優(yōu)勢，因而成為AGV系統(tǒng)的最佳選擇。此時，通過歐式距離和曼哈頓距離來計算物流成本顯然是不合理的。

1.3 智能車間中設(shè)備配置形式及特點

智能車間中機(jī)床設(shè)備的配置有互替式、互補(bǔ)式以及混合式等多種形式，以滿足生產(chǎn)過程的柔性和高效率要求[23]。在互替式機(jī)床配置中，各機(jī)床設(shè)備是一種并聯(lián)關(guān)系，其功能可以互相代替，工件可隨機(jī)輸送到任何一臺恰好空閑的機(jī)床上加工，在這種配置形式中，若某臺機(jī)床發(fā)生了故障，系統(tǒng)仍能維持正常的工作，具有較大的工藝柔性和較寬的工藝范圍，但是生產(chǎn)車間的設(shè)備購置成本相對比較高，對車間的布局面積也會有所增加。在互補(bǔ)式機(jī)床配置中，各機(jī)床設(shè)備功能是互相補(bǔ)充的，各自完成特定的加工任務(wù)，工件在一定程度上必須按順序經(jīng)過各臺加工機(jī)床。這種機(jī)床配置形式的特點是具有較高的生產(chǎn)率，能充分發(fā)揮機(jī)床的性能，但由于串聯(lián)配置，降低了系統(tǒng)的可靠性。基于前面兩種配置形式的特點和問題，在實際智能車間的加工設(shè)備配置中較多采用混合式配置，即有些機(jī)床按互替形式布置，有些則按互補(bǔ)形式布置，發(fā)揮各自的優(yōu)點。

2 基于AGV單向?qū)б窂降脑O(shè)備布局建模

2.1 約束條件及前提假設(shè)

為了使模型更具有普適性，本文針對實際生產(chǎn)中較常采用的直線雙行布局進(jìn)行數(shù)學(xué)建模[24]，如圖2所示。并對實際生產(chǎn)場景做以下簡化處理：①每臺設(shè)備尺寸相等；②設(shè)備的上下料點在同一位置。同時，約定以下行和列設(shè)備布局規(guī)則：①行方向的約束條件：一臺設(shè)備只能布置在某一行中，且只能出現(xiàn)一次；同一行內(nèi)，相鄰設(shè)備之間為最小間距約束，即保證兩相鄰設(shè)備之間不能出現(xiàn)干涉或重疊；設(shè)備與車間墻壁之間有最小間距約束。②列方向的約束條件：同一行設(shè)備的縱坐標(biāo)相同；相鄰行之間為最小間距約束，保證設(shè)備在y方向上不出現(xiàn)干涉或重疊。

2.2 數(shù)學(xué)描述

設(shè)從設(shè)備mi到設(shè)備mj的缸蓋搬運(yùn)頻率為fij，則

(2)

以物流成本最小為目標(biāo)函數(shù)，其優(yōu)化目標(biāo)函數(shù)為：

(3)

無向路徑的生成規(guī)則如下：

(1)對每排機(jī)床，連接上下料點產(chǎn)生兩條橫向路徑；

(2)同一排機(jī)床中每兩臺相鄰機(jī)床間產(chǎn)生一條縱向路徑連接兩條橫向路徑；

(3)當(dāng)縱向路徑間距離小于給定值(由計算得出)時路徑合并。

對生成的無向?qū)б窂骄W(wǎng)絡(luò)，以搬運(yùn)矩最小為目標(biāo)確定路徑方向，目標(biāo)函數(shù)為：

(4)

3 基于優(yōu)化路徑的生產(chǎn)設(shè)備布局算法解算

設(shè)備布局問題屬于NP-Hard問題。事實證明，通過傳統(tǒng)最優(yōu)化方法解決此類問題需要較長的時間。而運(yùn)用智能搜索算法往往需要對個體(即每個設(shè)備布局方案)評價，而對設(shè)備布局方案質(zhì)量的評價，需要求解此布局方案下較優(yōu)的單向?qū)б窂骄W(wǎng)絡(luò)，這也屬于NP-Hard問題?；煦鐑?yōu)化方法將問題變量從解空間轉(zhuǎn)換到混沌空間，利用混沌變量隨機(jī)性，遍歷性和規(guī)律性的特點進(jìn)行搜索，從而找到所需解決問題的最優(yōu)解。本文借助混沌優(yōu)化方法的這一特點，將遺傳算法與混沌映射算子相結(jié)合，提出一種混沌遺傳算法來實現(xiàn)對基于優(yōu)化路徑的生產(chǎn)設(shè)備布局算法解算。

3.1 求解多行設(shè)備布局問題混沌遺傳算法

(1)設(shè)備布局染色體編碼

設(shè)備布局染色體采用實數(shù)編碼的方式來進(jìn)行編碼，將布局方案中各臺加工中心的中心位置的橫縱坐標(biāo)組成的字符串作為染色體，以10臺加工中心為例，該字符串可以表示為[x1,1x1,2x2,1x2,2…xi,1xi,2…x10,1x10,2]。其中：[x1,1x1,2]表示設(shè)備1中心位置的坐標(biāo)，[xi,1xi,2]表示設(shè)備i中心位置的橫縱坐標(biāo)。將混沌思想引入到待優(yōu)化的設(shè)備坐標(biāo)變量中，通過映射的方法得到初始種群。[ai,bi]為設(shè)備布局染色體中第i個變量的取值范圍，當(dāng)i為奇數(shù)時，[ai,bi]為設(shè)備橫標(biāo)在車間長度方向的取值范圍；當(dāng)i為偶數(shù)時，[ai,bi]為寬度方向的取值范圍。種群規(guī)模設(shè)定為100。

通過Logistic映射，可以得到混沌變量的初始種群為：

(5)

式中:i表示混沌變量的序號，i=1，2，…，20；u表示種群序號，u=0,1,…,99；βi表示混沌變量，0≤βi≤1；μi表示吸引因子。

(6)

式中ci和di均為常數(shù)。

通過以上計算得到優(yōu)化變量的染色體及初始種群，即設(shè)備中心位置坐標(biāo)的染色體及初始種群，如下所示：

(7)

(2)隨機(jī)擾動

令

(8)

(3)適應(yīng)度計算

優(yōu)化函數(shù)的適應(yīng)度為：

(9)

式中：K為常數(shù)；F表示生產(chǎn)設(shè)備布局目標(biāo)函數(shù)；P為懲罰項，當(dāng)染色體滿足所有約束條件時，P=0，當(dāng)染色體不滿足所有約束條件時，P為一個值比較大的正整數(shù)。

(4)混沌遺傳操作

1)通過適應(yīng)度函數(shù)，計算每一代個體的適應(yīng)度值。對計算得到的適應(yīng)度值按從大到小的順序進(jìn)行排列。由于當(dāng)某一代群體中適應(yīng)度值差異較小時，會使收斂速度非常慢。經(jīng)過調(diào)整后，種群中染色體的適應(yīng)度值具有明顯差異，對加快收斂速度產(chǎn)生有利的影響。

2)對于排序后的種群，取其適應(yīng)度值最大的10%直接作為下一代種群中的染色體，剩余90%的染色體進(jìn)行遺傳操作以后進(jìn)入下一代。

3)對得到的新的種群，計算其調(diào)整后的適應(yīng)度值，并按適應(yīng)度值從高到低的順序進(jìn)行排列。將該群體中最大適應(yīng)度值與平均適應(yīng)度值進(jìn)行比較，如果小于設(shè)定的差值，則停止尋找最優(yōu)解，否則進(jìn)行下一步操作。

(10)

4)保留種群中適應(yīng)度值較高的10%的染色體，對于適應(yīng)度值較低的90%的染色體，再加一隨機(jī)擾動，將經(jīng)過隨機(jī)擾動后的混沌向量計算調(diào)整后的適應(yīng)度值，如果前后兩次迭代得到的適應(yīng)度的平均值之差小于某一足夠小的正數(shù)ε2，則停止迭代，否則，繼續(xù)迭代。隨著迭代的進(jìn)行，染色體逐漸趨向最優(yōu)解。

(11)

5)對當(dāng)前種群計算適應(yīng)度值，若該種群滿足式10，則尋優(yōu)過程結(jié)束，并將最優(yōu)解輸出，若不滿足，則轉(zhuǎn)第2)步，進(jìn)行下一輪混沌遺傳操作。

4 缸蓋智能生產(chǎn)車間設(shè)備布局規(guī)劃實現(xiàn)

本文以某缸蓋智能生產(chǎn)車間的設(shè)備布局規(guī)劃問題，對以上優(yōu)化模型的實現(xiàn)過程進(jìn)行分析驗證。目前該車間主要生產(chǎn)十幾余種船用發(fā)動機(jī)缸蓋，其主要加工設(shè)備為10臺加工中心：THM6380。根據(jù)每周的平均缸蓋產(chǎn)量，通過式2得到設(shè)備之間的缸蓋搬運(yùn)頻率矩陣如表1所示。

表1 缸蓋搬運(yùn)頻率

續(xù)表1

注：表中m指車間內(nèi)主要加工設(shè)備。

4.1 缸蓋智能生產(chǎn)車間設(shè)備布局嵌套遺傳算法求解與實現(xiàn)

按照直線雙行布局模式，將設(shè)備中心位置橫坐標(biāo)按照從小到大的順序進(jìn)行排列，得到z1,z2,z3,…,z10，設(shè)路徑網(wǎng)絡(luò)各個節(jié)點坐標(biāo)為(pi,qi)，則(pi,qi)的生成方法為：

4.2 基于MATLAB的算法實現(xiàn)

基于優(yōu)化路徑的設(shè)備布局程序在Microsoft Windows 7系統(tǒng)環(huán)境下通過MATLAB進(jìn)行編寫，將本文所提算法與傳統(tǒng)設(shè)備布局中常使用的遺傳—模擬退火算法(GA-SA)和簡單遺傳算法(SGA)收斂曲線進(jìn)行比較，比較結(jié)果如圖3所示。

經(jīng)過20次程序運(yùn)行，將其平均物流成本和平均計算時間與遺傳—模擬退火算法和簡單遺傳算法進(jìn)行比較，如表2所示。

表2 不同布局優(yōu)化算法結(jié)果對比

由圖3的實現(xiàn)結(jié)果，可以看出本文所設(shè)計的混沌遺傳算法在收斂速度和適應(yīng)度值方面均優(yōu)于遺傳—模擬退火算法和簡單遺傳算法，從表2也可以看出，本文所應(yīng)用的混沌遺傳算法可以搜索到的最優(yōu)解在物流成本方面優(yōu)于其他兩種方法。

4.3 基于Plant Simulation的仿真實驗

由于缸蓋生產(chǎn)過程情況比較復(fù)雜，為了進(jìn)一步對本文所提方法及模型的有效性進(jìn)行驗證，此處采用Plant Simulation構(gòu)造缸蓋智能車間生產(chǎn)過程并進(jìn)行仿真實驗，其仿真界面如圖4所示。根據(jù)各臺設(shè)備的坐標(biāo)值確定每臺設(shè)備的位置，其中3種布局優(yōu)化算法得到的布局方案仿真運(yùn)行一周以后，對應(yīng)的6種缸蓋的一周產(chǎn)量結(jié)果如表3所示。從仿真結(jié)果看，本文基于AGV單向?qū)б窂骄W(wǎng)絡(luò)的智能車間生產(chǎn)設(shè)備布局規(guī)劃CGA算法可以進(jìn)一步提高制造車間的生產(chǎn)能力。

表3 基于Plant Simulation的仿真結(jié)果

5 結(jié)束語

以AGV作為搬運(yùn)工具的智能車間在運(yùn)行過程中具有明確的運(yùn)行軌道及運(yùn)行方向，因此通過傳統(tǒng)的歐式距離和曼哈頓距離來計算物流成本，實現(xiàn)生產(chǎn)設(shè)備規(guī)劃顯然不合理。在以混合式機(jī)床設(shè)備配置的智能車間中，采用單向?qū)б窂骄W(wǎng)絡(luò)對AGV的搬運(yùn)頻率、單位距離成本、最短有向距離等參數(shù)進(jìn)行優(yōu)化，建立智能車間設(shè)備布局模型是一種可行的解決方案。本文在此基礎(chǔ)上，將遺傳算法與混沌映射算子相結(jié)合，提出一種混沌遺傳算法來實現(xiàn)對基于優(yōu)化路徑的生產(chǎn)設(shè)備布局模型的解算。通過算法對比研究和平臺仿真，結(jié)果均表明基于AGV單向?qū)б窂骄W(wǎng)絡(luò)的智能車間設(shè)備布局規(guī)劃方法可以得到較為理想的布局方案。