規(guī)則激光切割路徑規(guī)劃研究

規(guī)則激光切割路徑規(guī)劃研究

1切割路徑自動(dòng)編程在線檢測(cè)現(xiàn)在，激光加工技術(shù)越來越受到重視。要充分發(fā)揮激光加工機(jī)的效率，必須使用自動(dòng)駕駛軟件和激光加工編程軟件進(jìn)行。排樣軟件的目的是在給定大小的板材上排列盡可能多的零件或?qū)⒔o出的零件排列在盡可能小的板材上,從而使材料利用率盡可能高。而自動(dòng)編程軟件的目的是根據(jù)排樣的板材圖形來規(guī)劃切割路徑,并自動(dòng)生成數(shù)控加工切割機(jī)床的數(shù)控代碼,保證數(shù)控機(jī)床自動(dòng)完成切割。在實(shí)際生產(chǎn)中,激光切割機(jī)用戶認(rèn)識(shí)到:如果自動(dòng)編程不能保證有效地切割零件、保證部件質(zhì)量及提高產(chǎn)量,排樣軟件在材料效率上獲得的收益將會(huì)喪失。排樣軟件的新發(fā)展趨勢(shì)是充分考慮后續(xù)切割機(jī)床的效率,即采用共邊排樣實(shí)現(xiàn)共邊切割。共邊切割是在優(yōu)化排樣時(shí)按照一定規(guī)則將具有長邊的零件盡可能以長邊對(duì)長邊的方式排列在一起,在生成切割指令時(shí)對(duì)這些零件外輪廓的公共邊部分只進(jìn)行一次切割。共邊切割已被認(rèn)為是提高切割效率、節(jié)省切割成本的重要措施。但現(xiàn)在的數(shù)控切割自動(dòng)編程軟件中,切割路徑的確定仍不能令用戶滿意。絕大多數(shù)自動(dòng)編程系統(tǒng)仍是靠操作者的經(jīng)驗(yàn)在共邊排樣好的板材上交互式地生成切割路徑的順序。由于排樣板材中零件位置分布復(fù)雜,因此手工設(shè)置切割路徑就顯得十分復(fù)雜。另外,即使有少量的能實(shí)現(xiàn)共邊切割路徑自動(dòng)化生成的商品化數(shù)控自動(dòng)編程系統(tǒng),但其切割路徑并不理想,存在著打孔點(diǎn)過多及空行程較長的問題,直接影響切割效率與加工質(zhì)量。本文的研究重點(diǎn)就是在共邊排樣好的板材上,為自動(dòng)編程系統(tǒng)研究出割嘴路徑規(guī)劃的高效處理算法,最大限度提高效率,保證質(zhì)量,降低切割成本。2邊界檢測(cè)路徑的數(shù)學(xué)模型2.1共邊排樣圖形的生成圖1是板材上待切割零件典型的共邊排樣布局圖。共邊排樣件圖形十分適合于用圖論或網(wǎng)絡(luò)圖來表達(dá),而且圖論技術(shù)是解決割嘴路徑優(yōu)化問題的一個(gè)重要理論與方法。很顯然共邊排樣圖形屬于圖論中的無向圖。圖論中無向圖G是一個(gè)非空有限集合V(G)和V(G)中某些元素的無序?qū)Φ募螮(G)構(gòu)成,即G=(V,E),其中V=V(G)={v1,v2,…,vn}仍稱為圖G的頂點(diǎn)集;E=E(G)={e1,e2,…,en}稱為圖G的邊集合,E中的每一個(gè)元素ek(即V中某兩元素vi,vj的無序?qū)?記為ek=(vi,vj)或ek=vivj,或ek=vjvi(k=1,2,…,m),被稱為該圖的一條邊。圖1排樣圖中都是由首尾連接的直線、圓弧等圖元所構(gòu)成,直線、圓弧的端點(diǎn)構(gòu)成圖論表達(dá)中的頂點(diǎn)。為了統(tǒng)一并準(zhǔn)確地用圖論表達(dá)共邊排樣圖形,假設(shè)共邊排樣圖形信息已經(jīng)過如下處理:1)共邊圖形信息中已將共邊的較短邊或等邊的某一零件上重合的一邊的圖形信息刪除,如圖2,圖2(a)中兩單一零件Ⅰ,Ⅱ共邊排樣后形成圖2(b),此時(shí)應(yīng)刪除零件Ⅱ短邊eh。顯而易見,若不刪除,后續(xù)圖形信息處理時(shí),仍會(huì)自動(dòng)讀取到這條邊的信息,不但影響圖論表達(dá)而且后續(xù)數(shù)控加工編程仍對(duì)這一條邊產(chǎn)生加工指令,這樣會(huì)產(chǎn)生雖共邊排樣但這些邊仍會(huì)重復(fù)加工的情況,喪失了共邊排樣共邊切割的本意。2)按圖形系統(tǒng)所記錄的信息,在圖2(b)中頂點(diǎn)e的度數(shù)應(yīng)為1,而不是3。因?yàn)檫卋c是由一條直線一次繪制出來的,即不會(huì)產(chǎn)生頂點(diǎn)e分割邊bc而形成邊be,ec的情況。在本文中為確保排樣圖是一個(gè)連通圖,已采用了一定的算法,能檢測(cè)到頂點(diǎn)e在直線bc上,并將其分割為兩段形成邊be,ec。這樣頂點(diǎn)e的度數(shù)已變成了3而不是1。3)共邊排樣前,每一個(gè)零件都是由首尾連接的直線、圓弧等圖元所構(gòu)成的連通的閉路,共邊排樣后由于任一零件至少有一個(gè)邊與另一零件相重合,這樣再經(jīng)過2)的處理,則排樣構(gòu)成的G圖總是連通的。通過上面的分析,圖1用G=(V,E)來表達(dá)時(shí),V={v1,v2,…,v17},E={e1,e2,…,e27},e1=(v1,v2),e2=(v2,v3),e3=(v3,v4),…,e27=(v16,v17)。2.2切割路徑及尺寸實(shí)際生產(chǎn)中最常見的激光切割機(jī)床一般僅有一個(gè)激光切割頭也就是一個(gè)切割割嘴。按實(shí)際切割工藝,共邊切割路徑規(guī)劃問題是:無論任何順序的路徑都要求G圖中所有邊只能被割嘴切割一次(即遍歷一次),而且不得重復(fù)切割任何邊。這是因?yàn)榘宀囊坏┣虚_會(huì)發(fā)生熱變形和移動(dòng),若再重復(fù)切割則會(huì)影響已加工斷面質(zhì)量。這點(diǎn)與G圖某些問題求解可重復(fù)走G圖中某些邊是不同的。把割嘴遍歷G圖所有邊當(dāng)且僅當(dāng)一次用數(shù)學(xué)模型來表達(dá),則需要一系列路徑G=Ρ1∪Ρ2∪?∪ΡΚ,且?i,jΡi∩Ρj=ΦG=P1∪P2∪?∪PK,且?i,jPi∩Pj=Φ對(duì)激光切割而言,一個(gè)路徑僅需要一個(gè)打孔點(diǎn),而打孔點(diǎn)可選路徑的起點(diǎn)或終點(diǎn)中的任一頂點(diǎn),當(dāng)共邊排樣G圖被分解為不同的切割路徑,激光切割共邊排樣件的過程就很容易描述。對(duì)圖1而言,若切割路徑優(yōu)化分為5條:path1:v6e10v7e11v8e12v10;path2:v2e6v7e14v10e21v14;path3:v3e7v8e15v11e22v15;path4:v4e8v12e23v16;path5:v9e20v14e25v15e26v16e27v17e24v13e19v12e18v11e17v10e16v9e13v6e5v1e1v2e2v3e3v4e4v5e9v13。且打孔點(diǎn)定為:v6,v14,v3,v16,v9,其打孔順序?yàn)?v6,v16,v3,v14,v9。則一個(gè)完整的切割過程可表示為:割嘴快速移動(dòng)到v6(開光打孔)切割→path1→切割path1到v9(關(guān)光)快速直線空移→v16?→快速直線空移v16(開光打孔)切割→path4→切割path4到v4(關(guān)光)快速直線空移→v3(開光打孔)切割→path3到v15(關(guān)光)快速直線空移→v14(開光打孔)切割→path2到v2(關(guān)光)快速直線空移→v9(開光打孔)切割→path5到v13(關(guān)光,切割完成)。從上述切割路線可看出:共邊切割除打孔及開光切割路徑外,切割過程還包括一個(gè)路徑切完后關(guān)光快速直線空移到下一個(gè)切割路徑,這就是所謂切割過程的空行程。這些問題就構(gòu)成了共邊切割的路徑優(yōu)化問題:它要求割嘴路徑不但要滿足單割嘴必須遍歷G圖中所有邊當(dāng)且僅當(dāng)一次,而且要盡量達(dá)到打孔點(diǎn)數(shù)量要少以及切割過程空移行程要短。這個(gè)目標(biāo)正是激光切割機(jī)床用戶所關(guān)心的?？招谐套疃棠軠p少機(jī)床運(yùn)行時(shí)間,降低成本,而打孔點(diǎn)最少更是十分必要,因?yàn)橐话闱闆r下激光打孔的時(shí)間較長,而且打孔點(diǎn)處的質(zhì)量遠(yuǎn)低于連續(xù)切割處的質(zhì)量。通過上述分析,共邊切割路徑優(yōu)化的關(guān)鍵是求打孔點(diǎn)少且空行程要短的G圖的路徑劃分及排序。若不同路徑間空行程用dpj表示,共邊切割路徑優(yōu)化的數(shù)學(xué)模型就可表示為:對(duì)于無向圖G,需求一系列路徑G=Ρ1∪Ρ2∪?∪ΡΚ其中?i,jΡi∩Ρj=Φ且滿足:打孔點(diǎn)最少,minK,空行程最短,minΣdpj(j=1,2,…,K)。3聯(lián)合邊界切割路徑優(yōu)化算法共邊切割路徑優(yōu)化與共邊排樣賦權(quán)無向G圖頂點(diǎn)的度數(shù)性質(zhì)有密切的關(guān)系。3.1共邊切割的求解算法如果G圖中各頂點(diǎn)的度數(shù)均為偶數(shù),則G圖一定是一個(gè)歐拉回路,即可無重復(fù)邊一筆繪出,并且由歐拉回路性質(zhì)可知,從任一點(diǎn)出發(fā)都能求得一歐拉回路。這反映在切割上就是僅有一個(gè)打孔點(diǎn)且G圖中無空行程一次連續(xù)可切割出零件。假若G圖中僅有兩個(gè)頂點(diǎn)vi,vj的度數(shù)為奇數(shù),其某頂點(diǎn)的度數(shù)均為偶數(shù),則一定存在從vi到vj的一條路徑,它經(jīng)過了G各邊一次且無重復(fù)邊,這又稱為歐拉通路。這個(gè)問題不難理解,連接vi,vj補(bǔ)加一條新邊,則此時(shí)G圖變成各頂點(diǎn)的度數(shù)都是偶數(shù),即構(gòu)成了歐拉回路,求得歐拉回路后,再去掉vi與vj間補(bǔ)加邊即得到vi到vj的歐拉通路。顯然歐拉通路也僅需一個(gè)打孔點(diǎn)且一次切割中無空行程。以上兩種情況是最理想的共邊切割情況,而且其解法都與求解歐拉回路有關(guān)。當(dāng)前,求解歐拉回路比較有名的算法是Fleury算法及逐步插入回路算法,然而這些算法都不適應(yīng)用在共邊切割上。因?yàn)樵诠策吳懈顣r(shí)還必須滿足的一個(gè)重要約束條件是每個(gè)零件僅當(dāng)G圖中所有內(nèi)部邊切割完后才能從毛坯板上掉下來,也就是當(dāng)G圖中一個(gè)回路被切割掉時(shí),它的內(nèi)部再無別的以該回路任一頂點(diǎn)為公共頂點(diǎn)而形成的任何回路(零件)。這個(gè)約束的提出是基于對(duì)實(shí)際切割工藝過程的考慮:切割中一旦一個(gè)回路被切割即這部分板料會(huì)因重力而自然下落并使其位置發(fā)生變化。若薄板再受熱變形的影響,其情況更為嚴(yán)重。因此不適應(yīng)以該回路某一公共點(diǎn)在其內(nèi)再進(jìn)行切割。下面提出一種滿足共邊排樣切割的歐拉回路求解算法。算法1(最理想狀態(tài)下共邊切割路徑算法)設(shè)C是共邊排樣歐拉圖中沿著圖形外圍周長的封閉路徑,顯然C是一個(gè)歐拉圖?，F(xiàn)將G中屬于C的邊全刪去,再去除孤立頂點(diǎn)得圖G1,則G1=G-E(C)中各頂點(diǎn)度數(shù)的奇偶性質(zhì)不變。對(duì)于共邊排樣,由于至少有兩個(gè)零件,故E(G)-E(C)≠Φ,所以G1可由連通分支G11,G12,…,G1k來表達(dá),即:G1=G11∪G12∪…∪G1k,而且每個(gè)最大連通分支G1i(i=1,2,…,k,k≥1)仍為歐拉圖,且G1i互不連通。假若G11,G12,…,G1k歐拉環(huán)游已求出,并令C1i是G1i的歐拉環(huán)游,再回到原來的G圖中,由于G連通,所以每個(gè)C1i與C至少有一個(gè)公共頂點(diǎn),設(shè)其中之一為VWi∈V(C)(i=1,2,…,k)。由C中的某個(gè)點(diǎn)V1出發(fā)沿C前進(jìn),每行至一個(gè)頂點(diǎn)VWi就是先走完C1i再回到VWi繼續(xù)沿C前進(jìn),這樣可以遍歷每一條邊一次且僅一次回到出發(fā)點(diǎn)V0,這樣的行走軌跡就是G的一條共邊切割歐拉環(huán)游。對(duì)于C1i的求法,若E(G1i)-E(C1i)=Φ,則C1i就是沿著C1i圖形外圍周長封閉路徑。而E(G1i)-E(C1i)≠Φ,則要先求出沿著G1i圖形外圍周長的封閉路徑,仿照求G的思路,如此繼續(xù)下去,經(jīng)過有限次,即可得到G的歐拉環(huán)游。依據(jù)以上思路,很容易形成一個(gè)遞歸的求解共邊切割路徑的算法。圖3(a)是一個(gè)共邊排樣后形成的無奇度頂點(diǎn)的無向圖G,圖3(b)是算法1所求得的最終切割路徑,其打孔點(diǎn)為圖示左下角圓點(diǎn)上。3.2edmds-bohns一般情況下,G圖既非歐拉回路又不具有歐拉通路,由圖論知:在任何圖G=(V,E)中,奇度頂點(diǎn)的個(gè)數(shù)為偶數(shù),故可設(shè)一般情況下G圖中頂點(diǎn)的個(gè)數(shù)為2K(顯然K>1)。又由歐拉圖性質(zhì)知,在一個(gè)具有2K個(gè)奇度頂點(diǎn)的連通圖中,存在K個(gè)不變子圖,這些子圖包含了圖G的所有邊,且每個(gè)子圖都是一條歐拉通路。這個(gè)性質(zhì)揭示了一般情況下K條路徑是必須的,也是足夠的,最小的。即:G=P1∪P2∪P3∪…∪PK,且對(duì)任意i,j,Pi∩Pj=Φ。也就是說激光切割最少需要K個(gè)打孔點(diǎn),K條切割路徑即可完成共邊切割。由于K條歐拉通路的求解可通過在2K個(gè)奇度點(diǎn)間添加K條邊形成歐拉回路而求解,故現(xiàn)在的問題歸結(jié)為如何求出符合K條歐拉通路間空行程最短的K條添加邊,這就啟發(fā)構(gòu)造一個(gè)以所有奇度頂點(diǎn)集合的賦權(quán)完全圖F=K2k,由空行程含義知F中每條邊vivj上的權(quán)ω就是兩點(diǎn)間的直線距離,即ω=√(vix-vjx)2+(viy-vjy)2。這樣就能保證歐拉通路間空行程最短的K條添加邊的問題就等價(jià)于求F的最小權(quán)完美匹配,即最小權(quán)最大匹配問題。其求解方法可采用當(dāng)前最好的匹配算法Edmonds-Johason算法求解實(shí)現(xiàn)。定義:如果F(V,E,ω)的最大匹配M滿足:ω(M)=min{ω()|是F的最大匹配},則稱M是F的最小權(quán)最大匹配。Edmonds-Johason算法的原理是利用最大權(quán)匹配問題的線性規(guī)劃模型及其與對(duì)偶規(guī)劃問題的關(guān)系,采用原始-對(duì)偶方法來求解G=(V,E,ω)最大權(quán)匹配問題。因此可采用它求出賦權(quán)圖F=(V,E,ω)的最小權(quán)最大匹配。具體做法如下:構(gòu)造賦權(quán)圖F′=(V,E,ω′),其中ω′(e)=K-ω(e),對(duì)一切e∈E,K是足夠大的正常數(shù),可取Κ=Σe∈E|ω(e)|+1。同樣F′中最大權(quán)匹配一定是F的最大匹配,這樣用Edmonds-Johason算法求出F′最大權(quán)匹配就是F的最小權(quán)最大匹配。Edmonds-Johason求解F′最小權(quán)最大匹配算法步驟:STEP0:在賦權(quán)圖F′=(V,E,ω′)中取匹配M=Φ,對(duì)F′的所有頂點(diǎn)vi,令其對(duì)偶變量:yi=12max,對(duì)F′的所有頂點(diǎn)奇集Sm,令其對(duì)偶變量zm=0。并且令k=0。把F′記為。STEP1:在■k中任取一個(gè)yv>0的非人造的非飽和點(diǎn)v,如果不存在這樣的頂點(diǎn),轉(zhuǎn)STEP5;否則令:E*={vivj|vivj∈Ek且yi+yi+Σm:vivj∈Τmzm=■ij},記■*=■k[E*]。應(yīng)用生長種上樹的子程序,在■*中生長以v為根的種上樹。子程序結(jié)束時(shí),必然有下列三種情況之一發(fā)生:(1)得到一條增廣鏈P,轉(zhuǎn)STEP2;(2)得到一個(gè)花朵B,轉(zhuǎn)STEP3;(3)得到一個(gè)匈牙利樹J。如果J不包含人造頂點(diǎn),轉(zhuǎn)STEP4;如果J包含人造頂點(diǎn)vbm,其中vbm是收縮花朵Bm而成的,此時(shí)用vbm標(biāo)號(hào)去標(biāo)記Bm中所有頂點(diǎn),轉(zhuǎn)STEP4。STEP2:置M=M⊕E(P),去掉中所有頂點(diǎn)的標(biāo)號(hào),轉(zhuǎn)STEP1。STEP3:置k=k+1,Bk=B。把Bk收縮成人造頂點(diǎn)vbk,令其對(duì)偶變量zk=0,置M=M/Bk,。并把vbk標(biāo)以“+”(外點(diǎn)),Bk中所有頂點(diǎn)的標(biāo)號(hào)修改為“+”(外點(diǎn)),轉(zhuǎn)STEP1,如果v不包含在Bk中,則以v為根繼續(xù)生長種上樹;如果v包含在Bk中,則以vbk為根繼續(xù)生長種上樹。STEP4:令δ1=min{yi|vi∈V0,且vi為外點(diǎn)},,vi為外點(diǎn),vj未標(biāo)號(hào)},δ3=12min{yi+yj-,vi,vj均為外點(diǎn),且vi,vj不在同一個(gè)人造頂點(diǎn)中},δ4=12min{zm|Sm收縮為人造頂點(diǎn)vbm,且vbm為內(nèi)點(diǎn)},δ=min{δ1,δ2,δ3,δ4}。調(diào)整對(duì)偶變量:(Ⅰ)把V0中的每一個(gè)外點(diǎn)vi對(duì)應(yīng)的對(duì)偶變量yi減去δ;(Ⅱ)把V0中的每一個(gè)內(nèi)點(diǎn)vi對(duì)應(yīng)的對(duì)偶變量yi加上δ;(Ⅲ)把中每個(gè)人造的內(nèi)點(diǎn)vbm對(duì)應(yīng)的對(duì)偶變量zm加上2δ;(Ⅳ)把中每個(gè)人造的外點(diǎn)vbm對(duì)應(yīng)的對(duì)偶變量zm加上2δ。如果δ=δ1,此時(shí)存在一個(gè)頂點(diǎn)vi的對(duì)偶變量yi=0,當(dāng)vi不是J的根,則把從J的根v到vi的M交錯(cuò)鏈找出來,置M=M⊕E(),去掉所有頂點(diǎn)的標(biāo)號(hào),轉(zhuǎn)STEP1;當(dāng)vi是J的根,則去掉所有頂點(diǎn)的標(biāo)號(hào),轉(zhuǎn)STEP1。如果δ=δ4,此時(shí)存在一個(gè)人造頂點(diǎn)vbm,其對(duì)偶變量zm=0,則應(yīng)用展開人造頂點(diǎn)的子程序,把vbm展開為奇圈Bm,得到Bm的一個(gè)最大匹配Mm,置M=M∪Mm,k=k+1,得到新的賦權(quán)圖=(Vk,Ek,ω′),轉(zhuǎn)STEP1,繼續(xù)生長以v為根的種上樹。如果δ=δ2或δ=δ3,轉(zhuǎn)STEP1,此時(shí)E*將擴(kuò)大。STEP5:應(yīng)用展開人造頂點(diǎn)的子程序,按中所有人造頂點(diǎn)的收縮次序的相反次序,把中所有人造頂點(diǎn)展開為奇圈,求出所產(chǎn)生的奇圈上的一個(gè)最大匹配。從而所有奇圈上的最大匹配與M的并集就是F′的最大權(quán)匹配。添加邊問題解決后就容易得到一般情況下求解共邊切割路徑的求解算法。算法2(一般情況下共邊切割路徑算法)STEP1:求出G中任意一對(duì)奇點(diǎn)之間的直線距離dpi,j(i≠j)(i,j=1,2,…,k);STEP2:構(gòu)造完全圖F,F的頂點(diǎn)對(duì)應(yīng)于G的奇點(diǎn),其每條邊的權(quán)ω=dpij;STEP3:調(diào)用Edmonds-Johason算法求出F的最小權(quán)最大匹配M;STEP4:按最小權(quán)最大匹配結(jié)果添加邊到G中去,得歐拉圖G′;STEP5:調(diào)用算法1(共邊切割歐拉圖路徑算法)求出G′閉跡C,則從C中可方便地形成完整的切割路線及順序。圖1中是奇度頂點(diǎn)的有:v2,v3,v6,v4,v9,v12,v13,v14,v15,v16,共10個(gè)。所有這些頂點(diǎn)集合構(gòu)成的賦權(quán)完全圖F=(V,E,ω)經(jīng)Edmonds-Johason算法求得的最小權(quán)完美匹配為M={v2v6,v3v4,v9v14,v12v13,v15v16}。經(jīng)算法2求得的最終優(yōu)化切割路徑為:v14e20v9e16v10e14v6快速直線空移→v2e6v7e11v8e15v11e18v12e12v8e7v3e3v4e8v12e19v13快速直線空移→v12e23v16e26v15e22v11e17v10e21v14e25v15快速直線空移→v16e27v17e24v13e9v5e4v4快速直線空移→v3e2v2e1v1e5v6e13v9切割完成。