面向智能制造的不規(guī)則零件排樣優(yōu)化算法

高 勃，張紅艷，朱明皓

(1.北京交通大學(xué) 計算機(jī)與信息技術(shù)學(xué)院，北京 100044;2.北京交通大學(xué) 經(jīng)濟(jì)管理學(xué)院，北京 100044)

0 引言

二維零件排樣是實(shí)際應(yīng)用中最常見的排樣問題，廣泛應(yīng)用在機(jī)械制造、輕工、服裝和印刷業(yè)等行業(yè)中。排樣就是在給定原材料區(qū)域內(nèi)將多個零件按照一定的工藝需求以恰當(dāng)?shù)姆绞竭M(jìn)行排列，最終使得原材料獲得較高的利用率，并且要求排樣零件之間不能交叉或重疊。排樣問題主要分為規(guī)則件排樣和不規(guī)則零件排樣兩類。在規(guī)則件排樣中，矩形件排樣是排樣問題的基礎(chǔ)，研究最為廣泛，由于矩形件形狀簡單，可以較快地進(jìn)行碰撞檢測，并且排樣方式只有橫排或豎排兩種，規(guī)則零件排樣計算復(fù)雜度較低，實(shí)現(xiàn)起來相對容易。而不規(guī)則零件邊數(shù)為多邊形，零件凹凸性不定且形狀復(fù)雜，并且可以任意角度旋轉(zhuǎn)，因此，在零件定位以及零件之間碰撞檢測判斷方面時間復(fù)雜度較高。隨著工業(yè)生產(chǎn)規(guī)模的不斷擴(kuò)大，針對不規(guī)則零件排樣問題，綜合考慮板材利用率以及耗時情況找到有效的解決方法，對企業(yè)尤為重要。另一方面，由于排樣問題屬于典型的NP完全問題，不規(guī)則零件排樣問題求解的重點(diǎn)和難點(diǎn)在于如何在盡量短的時間內(nèi)找到使得原材料利用率盡可能高的排樣結(jié)果，設(shè)計和研究更加高效的不規(guī)則零件排樣算法具有非常重要的理論研究意義和實(shí)際應(yīng)用價值。

在研究初期，由于不規(guī)則件的復(fù)雜性，為了化簡問題的復(fù)雜度，一部分學(xué)者針對零件形狀進(jìn)行優(yōu)化處理，根據(jù)自身的幾何特點(diǎn)對其進(jìn)行包絡(luò)矩形，三角形，以及梯形等預(yù)處理，將不規(guī)則多邊形首先轉(zhuǎn)換成包絡(luò)矩形[1]，然后進(jìn)行組合[2]排樣，雖然這種轉(zhuǎn)變大大降低了問題的復(fù)雜度，但造成了空間的嚴(yán)重浪費(fèi)，不符合實(shí)際生產(chǎn)需求。之后，在包絡(luò)矩形的方法上加以改進(jìn)，研究者提出利用臨界多邊形的方法進(jìn)行求解[3-4]。臨界多邊形可以較好地保留不規(guī)則零件的形狀信息，不需要將零件進(jìn)行規(guī)則化擬合和離散化，但隨著不規(guī)則件數(shù)量的增加，會大大增加耗時，嚴(yán)重影響排樣效率。而后，隨著計算機(jī)的發(fā)展，智能優(yōu)化算法在排樣問題中得到了廣泛應(yīng)用。梁利東等[5-6]利用混合智能排樣優(yōu)化算法以及粒子群算法進(jìn)行排樣；韓偉等[7]提出基于模擬退火的貫通約束方法進(jìn)行排樣；史俊友等[8]利用神經(jīng)網(wǎng)絡(luò)混合優(yōu)化算法優(yōu)化排樣；梁利東等[9]基于遺傳算法的不規(guī)則件優(yōu)化排樣研究；王靜靜等[10-11]改進(jìn)遺傳算法針對不規(guī)則圖形排樣，李敬花等[12]結(jié)合遺傳和模擬退火兩種智能算法來求解不規(guī)則件排樣問題，楊衛(wèi)波等[13]基于實(shí)數(shù)編碼量子方法解決不規(guī)則排樣問題。雖然智能算法的應(yīng)用使得板材利用率有所提高，但算法計算開銷較大，計算過程較復(fù)雜。

本文針對待排件的幾何特征信息，提出將不規(guī)則件進(jìn)行對排或雙排處理，使其盡可能地組合成矩形或近似矩形，然后對其包絡(luò)矩形進(jìn)行處理，這樣在化簡問題復(fù)雜度的同時又降低了板材浪費(fèi)。另一方面，蟻群算法不容易陷入局部最優(yōu)解，能夠?qū)廨^好地進(jìn)行全局搜索，對排樣結(jié)果進(jìn)行進(jìn)一步的優(yōu)化?；诖耍疚睦脝l(fā)式和蟻群學(xué)習(xí)混合算法來進(jìn)行不規(guī)則多邊形零件排樣，而算法之間的結(jié)合可以在不規(guī)則排樣的解空間內(nèi)將最優(yōu)的求解方案搜索出來，綜合考慮板材利用率和算法的耗時情況，并通過仿真實(shí)驗(yàn)結(jié)果表明，該算法取得了較好的結(jié)果。同時，基于最大板材利用率，本文算法還給出了最少需要的板材數(shù)量，以給出企業(yè)合理訂購原材料的方案，減少原材料的積壓，提高企業(yè)的經(jīng)濟(jì)效益。

1 不規(guī)則件排樣問題

1.1 問題描述

二維板材下不規(guī)則件排樣指將若干規(guī)格不一的不規(guī)則零件排列在矩形板材上，并最終使得原材料獲得較高的利用率。排樣過程如圖1所示，不規(guī)則排樣比規(guī)則件排樣要復(fù)雜得多，一方面，由于邊界輪廓的復(fù)雜性，不規(guī)則多邊形的靠接計算需要大量的計算時間；另一方面，不規(guī)則件輪廓具有多樣性，因此不同的放置角度會產(chǎn)生不同的排樣方案，若零件可在全角度范圍內(nèi)旋轉(zhuǎn)，則急劇增加了排樣動作的選擇，大大增加了問題的復(fù)雜度。

在不規(guī)則零件排樣過程中，需要滿足以下約束條件：

(1)不規(guī)則零件ri排列在板材內(nèi)部，不能超過邊界；

(2)不同的零件ri和rj(i≠j)排列不能重疊；

(3)不規(guī)則零件rj可進(jìn)行旋轉(zhuǎn)、翻轉(zhuǎn)等操作。

因此，對于N個零件參與的排樣問題，排樣方案種類可以計算為：

T(N)=N!×(360/θ)N。

(1)

可以看出，當(dāng)零件數(shù)量N增大時，排樣方案種類數(shù)量將呈階乘級數(shù)量增長；另外，θ表示不規(guī)則零件每次旋轉(zhuǎn)的角度變化，θ越小，則零件的選擇動作就越多，排樣方案相應(yīng)地也會增加。

1.2 數(shù)學(xué)模型

在不規(guī)則零件排樣問題的數(shù)學(xué)建模過程中所使用到的變量定義如表1所示。

表1 變量定義表

續(xù)表1

多個不規(guī)則零件排樣，通過定位及定序規(guī)則確定零件的排樣方案，并以最大化板材利用率為目標(biāo)，則不規(guī)則零件排樣問題的數(shù)學(xué)模型定義如下：

(2)

(3)

ri∈A,i=1,2,…,R;

(4)

ri∩rj=?,i,j=1,2,…,R;

(5)

(6)

上述數(shù)學(xué)模型中目標(biāo)函數(shù)式(2)表示以最大化每張板材利用率為目標(biāo)，得到最優(yōu)排樣方案；約束式(3)表示第i張板材上排列零件的總面積；約束式(4)表示不規(guī)則件需要排列在板材區(qū)域內(nèi)部，不能超過邊界；約束式(5)表示零件之間的位置關(guān)系，不能交叉或重疊；約束式(6)表示n個板材裁剪的rj型號的零件總數(shù)為Mrj。

1.3 相關(guān)定義

1.3.1 不規(guī)則多邊形面積

在排料之前，一般需要對多邊形零件面積進(jìn)行比較，并在計算板材的利用率時，需要求所有布局在板材上的零件的面積總和。由于不規(guī)則多邊形的面積不易求解，將不規(guī)則多邊形切割成多個三角形進(jìn)行求解。

如圖2所示的三角形的面積求解公式為：

(7)

將不規(guī)則多邊形切割成若干個三角形，如圖3所示。

因此，不規(guī)則多邊形的面積為:

(8)

1.3.2 不規(guī)則多邊形坐標(biāo)

零件排樣過程中，需要記錄零件的質(zhì)心(x,y)以及旋轉(zhuǎn)的角度，來確定零件的排列位置。由于不規(guī)則零件有凹凸兩種，針對凸多邊形，可直接根據(jù)多邊形的坐標(biāo)點(diǎn)求解質(zhì)心，n條邊的凸多邊形的質(zhì)心求解如式(9)所示：

(9)

對于凹多邊形則不能根據(jù)上面的方式進(jìn)行計算，因?yàn)樯鲜龇绞街魂P(guān)注了坐標(biāo)點(diǎn)，而沒考慮組成的圖形。對于凹多邊形，相同的頂點(diǎn)分布，可能組成不同的多邊形，且質(zhì)心相差很大。于凹邊形，可以將它切割成多個三角形，其中每個三角形可以抽象為一個帶質(zhì)量的點(diǎn)p，點(diǎn)的位置為三角形的質(zhì)心，根據(jù)n個點(diǎn)的系統(tǒng)的質(zhì)心求解公式，可得凹邊形質(zhì)心求解公式：

(10)

其中:t1,t2,…,tn為分割的三角形質(zhì)心，s1,s2,…,sn為三角形的面積。

零件在排樣過程中，需要進(jìn)行一定程度的旋轉(zhuǎn)，使得排列更加緊密，因此需要根據(jù)旋轉(zhuǎn)的角度，確定不規(guī)則多邊形的位置坐標(biāo)。多邊形的旋轉(zhuǎn)操作是指將多邊形的各個頂點(diǎn)相對某參考點(diǎn)旋轉(zhuǎn)一定角度后得到新的頂點(diǎn)構(gòu)成新的多邊形。如圖4所示，零件P逆時針旋轉(zhuǎn)角度為θ，求解旋轉(zhuǎn)后的A點(diǎn)坐標(biāo)。

x′=x×cosθ-y×sinθ,

y′=x×sinθ+y×cosθ。

(11)

逆時針旋轉(zhuǎn)時θ>0，順時針旋轉(zhuǎn)時θ<0。

2 不規(guī)則零件排樣優(yōu)化算法

2.1 啟發(fā)式算法預(yù)處理

由于不規(guī)則件輪廓的復(fù)雜性，在排樣之前首先利用啟發(fā)式算法對不規(guī)則多邊形進(jìn)行預(yù)處理。排樣之前零件的預(yù)處理主要是針對不規(guī)則件的幾何特征信息，對零件進(jìn)行組合、填充等操作。本文對零件的預(yù)處理主要根據(jù)零件的幾何特征通過平移和旋轉(zhuǎn)等操作，對其進(jìn)行雙排或?qū)ε挪僮?，使組合后的零件形狀為矩形或近似矩形。零件的預(yù)處理將不規(guī)則件組合為較規(guī)則的件，簡化了排樣的復(fù)雜度，在一定程度上簡化排樣過程中的重疊檢測和碰撞靠接，能夠較好地提高算法的執(zhí)行效率，生產(chǎn)規(guī)模越大，優(yōu)勢越明顯，在實(shí)際工業(yè)大規(guī)模生產(chǎn)中的應(yīng)用是非常重要的。

2.1.1 局部零件組合

由于不規(guī)則零件輪廓的復(fù)雜性，根據(jù)零件的特征，對不規(guī)則多邊形零件進(jìn)行雙排或?qū)ε?，即將其中一個零件旋轉(zhuǎn)180°與另一個零件進(jìn)行對排，將兩個零件的互補(bǔ)邊進(jìn)行碰靠檢測，使其排列緊密，如圖5所示。將組合后的零件包絡(luò)成矩形，然后比較兩種組合方式所形成的包絡(luò)矩形的面積，選取面積小的組合方式來作為零件組合排列的方案。

預(yù)處理后的零件如果矩形包絡(luò)較好，可進(jìn)行聯(lián)排，即對單次雙排或?qū)ε潘脧?fù)合零件的形狀再次進(jìn)行普通單排，使零件之間更加緊密。

在預(yù)處理過程中，零件的組合排放需滿足以下約束：

(1)將第i個零件放在第i-1個零件的右邊，使零件緊密貼合；

(2)零件之間不得重疊；

(3)組合零件的最長邊不能超過矩形板材的寬，否則，停止組合。

不規(guī)則零件在預(yù)處理時，可選擇不排列、單排或雙排等組合方式，而組合的目的是為了將不規(guī)則件轉(zhuǎn)成矩形件參與排樣，因此通過比較每種方式的包絡(luò)矩形的面積大小，來選擇相應(yīng)的方式對不規(guī)則件進(jìn)行預(yù)組合。

2.1.2 碰撞檢測

在零件組合排列時需要進(jìn)行零件的定位以及碰撞檢測，為了更好地判斷零件之間的位置，采用已有的經(jīng)典方法——臨界多邊形(NFP)方法[14]，能夠較好地實(shí)現(xiàn)圖形的精準(zhǔn)定位。如圖6所示，對于給定的兩個多邊形A和B，保持多邊形A固定，將多邊形B繞多邊形A旋轉(zhuǎn)一周，并使得多邊形B至少有一點(diǎn)與A接觸但不能重疊，旋轉(zhuǎn)一周后，多邊形B上的參考點(diǎn)所形成的軌跡便是B相對于A的臨界多邊形，記為NFPAB。

根據(jù)構(gòu)建的臨界多邊形NFPAB，在零件排放中便可以較快地判斷兩個多邊形之間的位置關(guān)系：

(1)當(dāng)B的參考點(diǎn)在NFPAB外部時，B和A不相交；

(2)當(dāng)B的參考點(diǎn)在NFPAB內(nèi)部時，B和A重疊相交；

(3)當(dāng)B的參考點(diǎn)在NFPAB上時，B和A剛好接觸。

2.1.3 填充處理

對已排樣零件的孔和零件之間的封閉區(qū)域進(jìn)行檢測，對這部分未利用區(qū)域進(jìn)行填充處理，其中不能填充的區(qū)域稱為廢料，具體來說有兩種情況：比未排的零件中最小的尺寸面積還小的區(qū)域?yàn)閺U料；不能放置未排零件中的任何一個的區(qū)域稱為廢料。填充處理的目的就是降低廢料率，提升板材的利用率。

針對封閉區(qū)域填充零件的具體步驟如下：

(1)計算未利用區(qū)域E的面積S；

(2)搜索所有面積小于或等于S的待處理零件，記作集合Ι，數(shù)量記作K；

(3)計算E和填充零件Ι的形心坐標(biāo)點(diǎn)，然后放置零件Ι與E的形心重合，并將填充零件進(jìn)行旋轉(zhuǎn)，以使得該坐標(biāo)均在填充區(qū)域的內(nèi)部，若可填充則執(zhí)行(5)，否則執(zhí)行(4)；

(4)繼續(xù)查找集合Ι中的零件，若仍存在待填充零件則返回步驟(3)，否則在該區(qū)域內(nèi)不存在合適的零件可填充；

(5)將不規(guī)則零件的坐標(biāo)值存入集合Η。若查找完畢，則執(zhí)行步驟(6)；

(6)比較集合Η中零件的面積大小，選擇面積最大的零件排入?yún)^(qū)域E。

2.2 蟻群學(xué)習(xí)算法排樣

零件預(yù)處理后，采用群智能算法——蟻群算法[15-17]對處理后的零件進(jìn)行排樣。群智能算法能夠較好地在全局進(jìn)行搜索，以避免較快地陷入局部最優(yōu)解中。該算法的尋優(yōu)過程主要包含兩個階段：①適應(yīng)階段，在該階段信息素會不斷積累，以調(diào)整各個候選解的自身結(jié)構(gòu)，性能好的解，該信息素積累的就越多，而信息素多的解則會有較大的概率被再次選擇；②協(xié)作階段，各個候選解之間進(jìn)行信息的交流，最終使得算法更好地向最優(yōu)解或近優(yōu)解收斂。

2.2.1 信息素初始化

在該算法中，信息素和啟發(fā)式信息會影響螞蟻的行動，螞蟻訪問每個節(jié)點(diǎn)的先后順序?qū)?yīng)著零件的排放順序，而在板材排樣問題中，定序規(guī)則影響最終的排樣布局。因此，如何定義排樣問題中的信息素、啟發(fā)式信息以及信息素的更新規(guī)則，是問題求解的關(guān)鍵及重要內(nèi)容。

在實(shí)際排樣問題中的定序規(guī)則，通常按零件面積從大到小排放，在排樣中產(chǎn)生的空隙用小零件進(jìn)行填充，以提高板材的利用率。另一方面，考慮到零件的形狀，對于長寬比相差大的矩形件對板材空間要求更高，因此可以優(yōu)先排列這樣的零件。因此定義：

ηi=α×(l×w)+β×(l/w)。

(12)

式中：l，w為矩形件i的長和寬;α表示矩形件面積在啟發(fā)信息中所占權(quán)重值;β表示矩形件長寬比值在啟發(fā)信息中所占權(quán)重。

2.2.2 狀態(tài)轉(zhuǎn)移規(guī)則

(13)

式中：τj(t)表示t時刻矩形件j上信息素的強(qiáng)度值；ηj在排樣問題中表示排列矩形件j的啟發(fā)信息值；β為常數(shù)值，表示矩形面積值對螞蟻選擇待排件的影響因子參數(shù)；allowedk={r1,r2,…,rn}表示下一步螞蟻k允許選擇的矩形件，與之對應(yīng)，禁忌表tabuk用于記錄螞蟻k當(dāng)前已選取的矩形，在以后的搜索中該集合的矩形件不能被訪問，在排樣過程中集合allowedk，tabuk會隨著零件的排放進(jìn)行動態(tài)更新。

2.2.3 信息素局部信息更新

在螞蟻運(yùn)動過程中將選中的矩形件參與排樣，同時會更新矩形件上的信息素，但在排樣過程中，螞蟻的訪問順序決定了矩形件排放的順序，而由于排放順序的不同，排樣結(jié)果也不同，則更新的信息素大小也不相同。假設(shè)越早被訪問到的矩形件，則該矩形件上被螞蟻留下的信息素增量就會越大。信息素局部信息更新是指在搜索矩形件排樣的過程中根據(jù)矩形件排放的順序?qū)崟r更新矩形件的信息素濃度，信息素更新規(guī)則定義如下：

τi+1=(1-ψ)×τi+ψ×τ0。

(14)

式中：ψ為初始參數(shù)(0?ψ?1)，τ0為信息素濃度的初始值。

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

隨著不規(guī)則零件逐漸排入板材中，會產(chǎn)生眾多零碎的水平線段以及空隙，則可以選擇合適的零件進(jìn)行填充處理，而在排樣矩形件選擇順序中，將小零件放置在后進(jìn)行排列，可以較好地對余料空隙進(jìn)行填充。另一方面，板材排樣以最大化利用率為目標(biāo)函數(shù)，即排樣零件相對緊密，以使得排樣板材高度最低，因此更小的板材高度代表著更優(yōu)的學(xué)習(xí)效果，而蟻群算法中適應(yīng)度函數(shù)表示期待優(yōu)化的方向?；诖耍x適應(yīng)度函數(shù)如下：

f=Area′/Area+1/hri。

(15)

式中：Area′指已排樣零件的總面積，Area為所生成的排樣圖最大高度以下的板材面積，hri表示當(dāng)前零件排入板材時的最低輪廓線。顯然,適應(yīng)度函數(shù)的數(shù)值越大越好。

2.2.5 求解算法及步驟

蟻群學(xué)習(xí)進(jìn)行板材排樣的流程如圖7所示，具體步驟如下：

步驟1初始化矩形件排樣的相關(guān)參數(shù)值。

步驟2循環(huán)執(zhí)行以下步驟：

(1)假設(shè)初始有m只螞蟻，首先按一定的策略選擇它們的初始矩形件，并加入到禁忌表tabuk中。

(3)根據(jù)適應(yīng)度值優(yōu)化排樣，生成排樣圖，計算出對應(yīng)排樣圖的板材利用率，得出本次迭代的最優(yōu)排樣方案，保存當(dāng)前矩形件的定序及定位信息。

(4)判斷當(dāng)前解空間中是否存在比目前最優(yōu)解更優(yōu)的解，如果存在則更新最優(yōu)解，更新最優(yōu)排樣方案。

(5)對排樣矩形件進(jìn)行信息素修正。

步驟3定義count值為迭代的次數(shù)，每輪排樣過后count=count+1，如果count小于最大迭代次數(shù)，則重新初始化相關(guān)參數(shù)，轉(zhuǎn)步驟2，進(jìn)行新一輪的搜索排樣；如果迭代次數(shù)達(dá)到最終值，則輸出當(dāng)前的最佳排樣方案，程序結(jié)束。

3 仿真與結(jié)果分析

為驗(yàn)證本算法的優(yōu)越性，在VS2010及MATLAB 2018Ra平臺下進(jìn)行仿真實(shí)驗(yàn)，本文預(yù)處理算法與包絡(luò)矩形算法對不規(guī)則件進(jìn)行排樣對比，采用歐洲排樣問題興趣小組ESICUP提供的基準(zhǔn)問題數(shù)據(jù)以及自定義的一組數(shù)據(jù)作為測試算例。

由表2排樣結(jié)果可得，本文改進(jìn)算法的利用率遠(yuǎn)高于包絡(luò)矩形算法，雖然本文預(yù)處理過程相比于直接包絡(luò)矩形處理復(fù)雜，但耗時并沒有大幅度增加。為直觀地比較兩種算法的排樣結(jié)果，本文給出Trousers數(shù)據(jù)集下的排樣方案，圖8為包絡(luò)矩形算法板材一排樣圖，圖9為包絡(luò)矩形算法板材二排樣圖，圖10為本文算法板材一排樣圖，圖11為本文算法板材二排樣圖。

表2 算法排樣結(jié)果對比

由排樣圖可以看出，包絡(luò)矩形算法不考慮零件的形狀，都統(tǒng)一轉(zhuǎn)化為矩形件進(jìn)行排樣，排樣中產(chǎn)生了較多空隙，嚴(yán)重造成了浪費(fèi)，而本文算法針對不規(guī)則零件進(jìn)行預(yù)處理組合，使得零件排列更加緊密，減少浪費(fèi)，具有較好的排樣效果。

4 結(jié)束語

本文對不規(guī)則零件優(yōu)化排樣進(jìn)行研究，提出了一種基于啟發(fā)式預(yù)處理和蟻群學(xué)習(xí)的混合排樣算法來求解此問題。針對單一算法排樣板材利用率低，處理時間長的缺點(diǎn)，在排樣過程中首先對圖形進(jìn)行預(yù)處理，使其組合為矩形件或近似矩形件，提高了板材排樣利用率。然后利用蟻群學(xué)習(xí)算法，對組合后的零件進(jìn)行排樣。通過實(shí)驗(yàn)驗(yàn)證，板材利用率較高，但是蟻群算法的求解效率在很大程度上受到參數(shù)取值的影響，如何選取適當(dāng)?shù)膮?shù)，使不規(guī)則件優(yōu)化排樣進(jìn)一步取得更優(yōu)的解，還有待繼續(xù)研究和改進(jìn)。另一方面，由于本文處理的不規(guī)則零件形狀輪廓均為直角邊，沒有考慮曲線輪廓，這將是未來研究的工作重點(diǎn)。