基于蟻群算法及矩形法的鈑金排樣算法研究

李榮強(qiáng)，吳淑芳，馮梓彤，高 鑫，王靖宇

(1.中北大學(xué)機(jī)械工程學(xué)院，山西 太原 030051) (2.山西省起重機(jī)數(shù)字化設(shè)計(jì)工程技術(shù)研究中心，山西 太原 030051)

鈑金零件在工業(yè)生產(chǎn)中應(yīng)用十分廣泛，研究鈑金排樣策略可以避免鈑金零件切割過程中不必要的材料浪費(fèi)。鈑金排樣對(duì)鈑金件的合理性與經(jīng)濟(jì)性等具有重要影響[1]，因此設(shè)計(jì)有效的鈑金排樣算法具有重要意義。在我國工業(yè)生產(chǎn)中，主要依靠人工經(jīng)驗(yàn)進(jìn)行鈑金排樣，需要經(jīng)過不斷嘗試才能找出較為可行的方案[2]。這種排樣方法主觀性太強(qiáng)，效率較低，并且無法保證排樣結(jié)果為最優(yōu)。

針對(duì)上述問題，國內(nèi)外專家學(xué)者進(jìn)行了諸多研究：文獻(xiàn)[3]將人工排樣經(jīng)驗(yàn)與啟發(fā)思想結(jié)合，提出根據(jù)零件長(zhǎng)寬尺寸定序排樣；文獻(xiàn)[4]針對(duì)板材不限寬度的問題，使用多種智能算法對(duì)實(shí)例進(jìn)行計(jì)算，證明同時(shí)使用多種算法對(duì)得到排樣結(jié)果有促進(jìn)作用；文獻(xiàn)[5]將遺傳算法與模擬退火算法相結(jié)合對(duì)鈑金排樣策略進(jìn)行研究，然后采用填充算法填充剩余部分；文獻(xiàn)[6]針對(duì)二維不規(guī)則排樣問題進(jìn)行了研究；文獻(xiàn)[7]針對(duì)鈑金件展開以及排樣問題，使用AutoCAD進(jìn)行優(yōu)化排樣；文獻(xiàn)[8]對(duì)剩余矩形法進(jìn)行深入研究，并采用遺傳算法對(duì)定序問題進(jìn)行了研究。

目前鈑金排樣研究依然存在一些不足：對(duì)于零件尺寸特征的總結(jié)較為片面，沒有將長(zhǎng)度、寬度、面積等因素綜合考慮；對(duì)定位算法的使用不夠完美，未達(dá)到理想的排布效果；對(duì)于一些可用矩形算法排樣的零件，沒有適合的改進(jìn)措施。因此本文主要針對(duì)排樣算法以及鈑金圖形優(yōu)化兩大方面進(jìn)行研究。

1 排樣問題簡(jiǎn)介

排樣問題是指將需要排樣的零件放置到一塊寬度不變的板材上，且零件之間不能干涉。數(shù)學(xué)模型如下：

假設(shè)參與排樣的第i個(gè)零件為Pi，則在板材B上參與排樣的零件P1，P2，…，Pn必須滿足以下約束條件：1)Pi，Pj互不干涉，i,j=1,2,…,n，且i≠j；2)零件Pi必須完全在板材B內(nèi)；3)必須滿足所需的工藝加工要求，比如板材邊距等參數(shù)。

在鈑金件排樣過程中，需解決鈑金零件的定位問題。首先，用(xi,yi)表示零件位于板材上的位置，其中xi為寬，yi為高,除此之外，需要對(duì)零件進(jìn)行旋轉(zhuǎn)擺放，旋轉(zhuǎn)角度αi順時(shí)針方向?yàn)檎?。因此位置可表示為Mi(xi,yi,αi)。

Di(xi,yi,αi)∩Dj(xj,yj,αj)=?

(1)

0

(2)

0

(3)

式中：Di(xi,yi,αi)為零件屬性。

由于目標(biāo)函數(shù)的分子固定，因此目標(biāo)函數(shù)可簡(jiǎn)化為：在滿足式(1)、(2)、(3) 3個(gè)約束條件的情況下，使WH最小。在排樣中，定義寬度W固定，所以該問題的目標(biāo)為求解高度H的最小值。

2 矩形排樣算法改進(jìn)

2.1 排樣優(yōu)化策略

在剩余矩形法中，當(dāng)排入零件順序不合適時(shí)會(huì)造成空間上的浪費(fèi)，從而產(chǎn)生無法填補(bǔ)的矩形空間，如圖1左圖所示，在3和4兩個(gè)零件中，按排樣效果應(yīng)該優(yōu)先選擇4，如選擇3先行填入就會(huì)得到右圖所示的結(jié)果，造成空間浪費(fèi)。

圖1 剩余矩形法造成的空間浪費(fèi)

本文針對(duì)此類情況進(jìn)行改進(jìn)，意在避免不合適零件被優(yōu)先排樣。以圖1為例，在產(chǎn)生剩余空間時(shí)，先用空間大小與待排零件的長(zhǎng)和寬進(jìn)行匹配，若匹配成功則優(yōu)先填入此零件，從而減少板材浪費(fèi)。優(yōu)化后的排樣結(jié)果如圖2所示。

圖2 優(yōu)化后剩余矩形算法排樣結(jié)果

2.2 改進(jìn)剩余矩形算法排樣過程

優(yōu)化后的排樣步驟如下：

1)進(jìn)入循環(huán)，多次排樣,預(yù)設(shè)hmin(hmin為每次排樣的最小高度，本文設(shè)置為零件寬度之和)。

2)按最左最下的原則，將隨機(jī)選出的第一個(gè)零件排入板材中，計(jì)算剩余矩形空間。

3)在未排樣零件中選取零件，首先挑選符合要求的矩形空間，將面積大小相近以及排入點(diǎn)最低作為判斷要求排入零件，計(jì)算剩余矩形空間，再將零件信息記錄到已排樣信息中。

4)對(duì)剩余矩形空間信息與零件信息進(jìn)行匹配，若長(zhǎng)寬相近則將此零件優(yōu)先排入，并將結(jié)果記錄到已排樣信息中。

5)重復(fù)步驟4)、5)直到所有零件排樣完成為止，記錄排樣高度h。

6)將h與hmin對(duì)比，若h小于hmin則保留此次排樣序列及排樣圖，刪除已有的排樣圖并且令hmin=h，直到循環(huán)結(jié)束，繪制出排樣圖以及利用率曲線圖。

2.3 定序問題研究

排樣順序是一個(gè)必須要考慮的問題，本文使用蟻群算法對(duì)定序問題進(jìn)行研究。蟻群算法是一種較好的尋優(yōu)算法，目前蟻群算法使用的啟發(fā)式為面積大小，然而只考慮面積這一因素?zé)o法全面概括一個(gè)矩形零件的全部特性，本文以(yi+xi)表示長(zhǎng)寬特性，蟻群算法啟發(fā)式ηij為:

ηij=aSi+b(xi+yi)

(4)

式中：a為面積權(quán)值；b為長(zhǎng)寬特性權(quán)值。

為對(duì)a,b值進(jìn)行確定，本文使用2.2節(jié)零件定位方式對(duì)a,b值進(jìn)行測(cè)試，得到當(dāng)a=2、b=7時(shí)排樣結(jié)果較好，因此啟發(fā)式確定為：

ηij=2Si+7(xi+yi)

(5)

2.4 蟻群算法與剩余矩形算法排樣過程

根據(jù)上述描述可設(shè)定算法步驟如下：

1)根據(jù)零件信息計(jì)算式(5)。

2)進(jìn)入蟻群算法循環(huán)，判斷是否達(dá)到最大代數(shù),若達(dá)到最大代數(shù)跳到步驟7)；若沒有執(zhí)行步驟3)。

3)螞蟻開始隨機(jī)選擇零件，判斷是否所有螞蟻都已排樣完成，若完成返回步驟2)。

4)根據(jù)式(6),螞蟻隨機(jī)選擇零件進(jìn)行排樣:

(6)

5)按2.2所示的排樣過程進(jìn)行零件排樣，若觸發(fā)空間匹配則不使用步驟4)進(jìn)行選擇，直接將此零件排入，記錄零件信息，否則重復(fù)步驟4)。

6)判斷零件是否排完，若排完按式(7)更新信息素，返回步驟3)；若未排完繼續(xù)執(zhí)行步驟3)、4)、5)。

(7)

(8)

7)繪制排樣圖，得出迭代次序圖。

3 鈑金類零件簡(jiǎn)化

3.1 矩形鈑金件簡(jiǎn)化

因?yàn)楣耋w零件大多為凸形鈑金件，如果將其簡(jiǎn)單地定義為矩形，會(huì)造成材料的浪費(fèi)。若按不規(guī)則零件排樣，又會(huì)增加算法難度，所以本文提出圖3所示的策略來優(yōu)化此類問題。

圖3 階梯形鈑金示意圖

為減少計(jì)算量，使用式(9)求解λ。

(9)

當(dāng)比值λ大于1/10時(shí)，則將其視為一個(gè)矩形。如圖4所示，將B部分作為剩余空間區(qū)域進(jìn)行記錄。此區(qū)域與其他空間區(qū)域不存在相容關(guān)系，因此需要提前排入。采用這一方法可以減少資源的浪費(fèi)。

圖4 凸階梯形鈑金簡(jiǎn)化圖

3.2 非矩形鈑金件簡(jiǎn)化

圖5(a)所示為目標(biāo)圖形，以往的處理方案如圖5(b)所示，這種處理方案會(huì)造成上方空間浪費(fèi)，因此要先對(duì)目標(biāo)圖形的角度進(jìn)行比對(duì)，若有相同(或相近)的則先進(jìn)行組合，否則使用式(9)進(jìn)行計(jì)算，若比值大于1/5，按圖5(c)所示的方案進(jìn)行排樣。

圖5 非矩形鈑金件簡(jiǎn)化圖

3.3 實(shí)現(xiàn)方法

綜上，本文采用的解法如下所述：

1)在預(yù)處理階段，利用3.1節(jié)所提到的方法進(jìn)行簡(jiǎn)化，然后建立其關(guān)系式。在填入其中一塊時(shí)，將所對(duì)應(yīng)的剩余空間加入到原有的剩余空間集合中。

2)將鈑金類零件優(yōu)先排入板材，以此保證這些零件所對(duì)應(yīng)的剩余空間能夠優(yōu)先排入鈑金類零件。

4 實(shí)例分析

4.1 矩形鈑金件排樣

本文以文獻(xiàn)[9]中的算例2為例，使用MATLAB進(jìn)行實(shí)例測(cè)試，設(shè)置螞蟻數(shù)量m=30，α=1.6，β=10.2，ρ=0.1，Q=1×106，迭代次數(shù)為100代。得到的排樣結(jié)果如圖6所示。

圖6 改進(jìn)剩余矩形法排樣圖

排樣順序?yàn)閧-30 10 48 12 39 14 20 49 16 54 42 27 18 19 44 7 40 38 43 60 24 15 51 47 28 11 33 13 34 29 23 50 35 55 17 41 -2 57 45 59 3 -56 25 26 -9 1 46 5 21 32 58 22 53 4 31 37 6 52 8 36}，板材占用最大高度為355 mm，材料利用率為94.6%，圖7為以零件面積為蟻群算法的優(yōu)缺點(diǎn)啟發(fā)式和按本文所提蟻群算法啟發(fā)式迭代對(duì)比圖。

圖7 迭代曲線圖

通過表1統(tǒng)計(jì)結(jié)果可知：相比于文獻(xiàn)[9]的算法，本文算法的板材利用率提高了3.5%；相比普通蟻群算法，收斂提前了10代。由此可知本文算法解決矩形排樣問題的效果優(yōu)于其他兩種算法。

4.2 鈑金類零件排樣

以4.1節(jié)中矩形組成幾個(gè)凸形鈑金件為例，用MATLAB進(jìn)行實(shí)例測(cè)試，其步驟為：1)進(jìn)行數(shù)據(jù)輸入；2)按3.3節(jié)所述，將以下幾個(gè)矩形(件10、件20、件30、件39)進(jìn)行切分、排樣，如圖8所示。

表1 結(jié)果對(duì)比表

圖8 階梯形、斜面形鈑金件

如圖9所示，排樣順序?yàn)閧-30 20 39 10 12 29 41 13 28 43 50 -17 25 54 42 15 48 18 16 1 27 33 22 21 14 59 53 35 38 44 34 11 60 19 55 2 26 49 47 7 57 40 23 -56 51 24 9 5 3 -46 4 31 32 58 6 -52 8 -36 -37}，板材占用最大高度為353 mm，材料利用率為94.5%。

圖9 階梯形、斜面形鈑金件排樣圖

5 結(jié)論

本文通過對(duì)蟻群算法以及鈑金零件排樣問題的研究得出以下結(jié)論：

1)用空間匹配原則對(duì)剩余矩形法進(jìn)行改進(jìn)，解決了排樣定位問題，提高了板材利用率。

2)利用蟻群算法對(duì)矩形零件排樣的定序問題進(jìn)行研究，使用面積和長(zhǎng)寬尺寸因素提取零件特征，經(jīng)算例驗(yàn)證，此啟發(fā)式可以有效提高排樣效率和加快蟻群算法的收斂速度。

3)針對(duì)不規(guī)則鈑金件浪費(fèi)板材問題，進(jìn)行圖形優(yōu)化，提出零件自帶剩余空間策略，使用改進(jìn)剩余矩形算法進(jìn)行仿真計(jì)算，結(jié)果證明可以有效解決此類鈑金件排樣問題。