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

李榮強，吳淑芳，馮梓彤，高 鑫，王靖宇

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

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

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

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

1 排樣問題簡介

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

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

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

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

(1)

0

(2)

0

(3)

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

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

2 矩形排樣算法改進

2.1 排樣優化策略

在剩余矩形法中，當排入零件順序不合適時會造成空間上的浪費，從而產生無法填補的矩形空間，如圖1左圖所示，在3和4兩個零件中，按排樣效果應該優先選擇4，如選擇3先行填入就會得到右圖所示的結果，造成空間浪費。

圖1 剩余矩形法造成的空間浪費

本文針對此類情況進行改進，意在避免不合適零件被優先排樣。以圖1為例，在產生剩余空間時，先用空間大小與待排零件的長和寬進行匹配，若匹配成功則優先填入此零件，從而減少板材浪費。優化后的排樣結果如圖2所示。

圖2 優化后剩余矩形算法排樣結果

2.2 改進剩余矩形算法排樣過程

優化后的排樣步驟如下：

1)進入循環，多次排樣,預設hmin(hmin為每次排樣的最小高度，本文設置為零件寬度之和)。

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

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

4)對剩余矩形空間信息與零件信息進行匹配，若長寬相近則將此零件優先排入，并將結果記錄到已排樣信息中。

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

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

2.3 定序問題研究

排樣順序是一個必須要考慮的問題，本文使用蟻群算法對定序問題進行研究。蟻群算法是一種較好的尋優算法，目前蟻群算法使用的啟發式為面積大小，然而只考慮面積這一因素無法全面概括一個矩形零件的全部特性，本文以(yi+xi)表示長寬特性，蟻群算法啟發式ηij為:

ηij=aSi+b(xi+yi)

(4)

式中：a為面積權值；b為長寬特性權值。

為對a,b值進行確定，本文使用2.2節零件定位方式對a,b值進行測試，得到當a=2、b=7時排樣結果較好，因此啟發式確定為：

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

(5)

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

根據上述描述可設定算法步驟如下：

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

2)進入蟻群算法循環，判斷是否達到最大代數,若達到最大代數跳到步驟7)；若沒有執行步驟3)。

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

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

(6)

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

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

(7)

(8)

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

3 鈑金類零件簡化

3.1 矩形鈑金件簡化

因為柜體零件大多為凸形鈑金件，如果將其簡單地定義為矩形，會造成材料的浪費。若按不規則零件排樣，又會增加算法難度，所以本文提出圖3所示的策略來優化此類問題。

圖3 階梯形鈑金示意圖

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

(9)

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

圖4 凸階梯形鈑金簡化圖

3.2 非矩形鈑金件簡化

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

圖5 非矩形鈑金件簡化圖

3.3 實現方法

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

1)在預處理階段，利用3.1節所提到的方法進行簡化，然后建立其關系式。在填入其中一塊時，將所對應的剩余空間加入到原有的剩余空間集合中。

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

4 實例分析

4.1 矩形鈑金件排樣

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

圖6 改進剩余矩形法排樣圖

排樣順序為{-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為以零件面積為蟻群算法的優缺點啟發式和按本文所提蟻群算法啟發式迭代對比圖。

圖7 迭代曲線圖

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

4.2 鈑金類零件排樣

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

表1 結果對比表

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

如圖9所示，排樣順序為{-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 結論

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

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

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

3)針對不規則鈑金件浪費板材問題，進行圖形優化，提出零件自帶剩余空間策略，使用改進剩余矩形算法進行仿真計算，結果證明可以有效解決此類鈑金件排樣問題。