基于圖論的共邊切割方法研究

基于圖論的共邊切割方法研究

1切割路徑優(yōu)化在優(yōu)化零件排列后，應(yīng)設(shè)計零件的切割路徑。一般來說，基于一定的切割順序，零件必須首先切下，并移動到切割點(diǎn)停車，以去除凸面所需的空間，然后通過引入線沿零件的形狀運(yùn)行一周，以分離零件。不斷重復(fù)上述動作,直至切割出所有的零件為止。然而對于有很多公共邊的零件,仍然按照這種常規(guī)方法切割工件勢必會造成時間、行程、能量等的極大浪費(fèi)。為了避免這些浪費(fèi),我們采用共邊切割的方法能夠有效地優(yōu)化切割路徑。共邊切割就是在優(yōu)化排樣時按照一定規(guī)則將具有長邊的零件盡可能以長邊對長邊的方式排列在一起,在生成切割指令時對這些零件外輪廓的公共邊部分只進(jìn)行一次切割。共邊切割已被認(rèn)為是提高切割效率、節(jié)省切割成本的重要措施,然而目前有關(guān)共邊切割的方法研究還不太深入,共邊切割方法對于切割路徑的優(yōu)化效果還沒有完全發(fā)揮出來?？蒲泄ぷ髡哐芯苛藬?shù)控切割機(jī)共用割縫的應(yīng)用,通過采用自動和手工編程方法相結(jié)合,實(shí)現(xiàn)共用割縫,以達(dá)到省工、省時、省料的目的。一些科研工作者研究了基于激光切割的共邊排樣件的路徑優(yōu)化,提出了滿足激光切割工藝要求的3個切割路徑優(yōu)化算法:用于求解理想情況下共邊切割路徑優(yōu)化問題的一個新的歐拉回路算法;基于奇度頂點(diǎn)完全圖最小權(quán)最大匹配算法來求解一般情況下共邊切割路徑優(yōu)化問題的算法;利用廢料區(qū)域進(jìn)一步減少打孔點(diǎn)的處理策略與求解算法。盡管已有不少研究者對共邊切割的方法進(jìn)行了研究,但在優(yōu)化性能和通用性上還不太完善。2切割方法的選擇需要采用更多的方法進(jìn)行切割優(yōu)化板材的切割路徑優(yōu)化主要涉及割嘴的空行程數(shù)和打孔點(diǎn)數(shù)。空行程越少則切割時間越少;打孔點(diǎn)數(shù)越少,不但能夠減少切割時間還能夠提高切割質(zhì)量。比較好的共邊切割方法對于板材的切割優(yōu)化能夠起到到很好的效果。提出了基于圖論理論的“一筆畫”共邊切割方法和針對陣列矩形的“階梯形”共邊切割方法,并與常規(guī)的共邊切割方法進(jìn)行了比較。通過比較,提出的方法在切割路徑上有了很大的優(yōu)化。3聯(lián)合切割法3.1常規(guī)共邊切割方法設(shè)共邊排料圖有n個零件組成,已經(jīng)按最短路徑的原則排好切割順序,每個零件記為P1,P2,..Pn。常規(guī)共邊切割方法步驟如下:(1)首先切割P1,并找出P1與P2的公共邊E12;(2)以零件P1和零件P2的公共邊E12的兩個端點(diǎn)中任一個端點(diǎn)為起點(diǎn),進(jìn)行切割零件P2。然后找出P2和P3的公共邊E23;(3)重復(fù)以上類似的步驟,直到切割完最后一個零件Pn為止。簡單且容易算法實(shí)現(xiàn),如圖1所示。3.2“鋼筆”的整體切割3.2.1圖g的結(jié)論集合如圖2所示,是一些具有公共邊的零件組成的共邊排樣圖,這是個典型的共邊排樣。我們不難發(fā)現(xiàn)共邊排樣件圖形非常適合于用圖論來表達(dá),而且通常情況下我們都是用圖論的有關(guān)技術(shù)來解決鈑材切割的路徑優(yōu)化問題的。所謂圖G是一個三元組,記作G=<V(G),E(G),φ(G)>,其中,(1)V(G)={v1,v2,v3,…vn},V(G)≠?,稱為圖G的結(jié)點(diǎn)集合(vertexset)。(2)E(G)={e1,e2,e3,…en}是G的邊集合(edgeset),E中的每一個元素ek(即V中某兩元素vi,vj的無序?qū)?記為ek=(vi,vj),被稱為該圖的一條邊。(3)φ(G):E→V×V稱為關(guān)聯(lián)函數(shù)(incidencefunction)。設(shè)G是任意圖,vi為G的任一結(jié)點(diǎn),與結(jié)點(diǎn)vi關(guān)聯(lián)的邊數(shù)稱為vi的度數(shù)(degree),記作deg(vi)。利用上面有關(guān)圖論的定義,我們很容易給出共邊排樣圖的圖論表達(dá),如圖2所示。3.2.2種不解決共邊切割的結(jié)論圖論中有一種特殊的圖—?dú)W拉圖,它有一條很重要的性質(zhì),從歐拉圖的任一頂點(diǎn)出發(fā)都能求得一條歐拉回路,即可無重復(fù)邊一筆繪出。其中,如果圖G(V,E)中各頂點(diǎn)的度數(shù)均為偶數(shù),則G圖一定是個歐拉圖。另外如果G圖中除兩個頂點(diǎn)vi,vj的度數(shù)為奇數(shù)外,其他頂點(diǎn)的度數(shù)均為偶數(shù),則一定存在從vi到vj的一條路徑,它經(jīng)過了G各邊一次且無重復(fù)邊,條路徑稱為歐拉通路。這個問題不難理解,連接vi,vj補(bǔ)加一條新邊,則此時G圖變成各頂點(diǎn)的度數(shù)都是偶數(shù),即構(gòu)成了歐拉回路,求得歐拉回路后,再去掉vi與vj間補(bǔ)加邊即得到vi到vj的歐拉通路。顯然歐拉通路也僅需一個打孔點(diǎn)且一次切割中無空行程。因此我們可以利用歐拉圖的原理對共邊排樣零件進(jìn)行共邊切割,對于歐拉圖由于割嘴只需打一次孔,所以對這種方法的共邊切割簡稱“一筆畫”共邊切割。如圖3所示,是一個歐拉圖。它可以無重復(fù)邊一筆繪出,其遍歷軌跡為:1→2→3→4→2→5→3→6→7→4→1。如圖4所示,為一個簡單的非歐拉圖添加虛邊的過程。提出一種能滿足共邊切割的歐拉回路的求解方法。設(shè)歐拉圖為G(V,E),則歐拉圖G的歐拉回路的求解步驟如下:STEP1:求出歐拉圖G的外圍封閉路徑C,接著把C刪去,得G1,則G1=G-E(C)。其中,G1可由連通分支G11,G12,G13,…,G1n來表達(dá),即G1=G11∪G12∪G13…∪G1n。STEP2:設(shè)C1j(j=1,2,..n)是G1j的切割軌跡,則C1j與C到少有一個公共點(diǎn),設(shè)其中之一為VC(j)。對于G1j的求法為:若E∪G1j∪-E∪C1j∪=?,則C1j就是沿著G1j圖形外圍周長的封閉路徑;若E∪G1j∪-E∪C1j∪≠?,則要先求出G1j圖形外圍周長的封閉路徑G′1j,仿照求G的思路如此繼續(xù)下去,經(jīng)過有限次即可得到G1j的切割軌跡G1j。STEP3:由C中的某個頂點(diǎn)V1出發(fā)沿C前進(jìn),每行到一個公共點(diǎn)VC(j)就要先走完G1j再回到VC(j),繼續(xù)沿C前進(jìn),這樣就可以遍歷圖中的每一條邊并回到出發(fā)點(diǎn)V1。根據(jù)步驟,給定一個歐位圖G,如圖5(a)所示,很容易求出符合切割工藝的歐拉回路:1→2→5→4→2→3→4→7→9→6→7→8→9→10→6→5→1,如圖5(b)所示。3.3“梯子形狀”的共邊切割方法3.3.1未切割的零件設(shè)矩形陣列為m行n列,則共有m×n個矩形零件,第i行第j列的零件可表示為Pij(i=1,2…m;j=1,2,...n),如圖6所示。如果零件Pij有任一個邊被切割,則記C(Pij)=1,否則C(Pij)=0,未切割狀態(tài)下所有零件C(Pij)等于0。實(shí)現(xiàn)的目標(biāo)為切割完m×n個零件所需要的切割次數(shù)小于等于m×n,且越小越好。3.3.2剩余零件的切割步驟1:第一次打孔首先切割掉零件P11,則與零件P11有公共邊的零件P12和P21都有一條邊被切割,因此記C(P12)=1,C(P21)=1。記m×n個矩形零件的集合為A,切割的零件集合記為B,則剩余的零件集合為C=A-B。步驟2:在剩余的零件集合C中找出C(Pij)=1的所有零件,記為集合T。步驟3:在集合T中選出零件下標(biāo)列序號最小的零件Pij,以零件Pij的頂點(diǎn)為起點(diǎn),按照階梯形的軌跡把T中的所有零件確保打一次孔切割完畢。步驟4:重復(fù)步驟2和步驟3直到剩余集合C中的零件為空?，F(xiàn)在給出一個實(shí)例,如圖7所示,這是一些矩形的陣列排列組成的共邊排樣圖,按照算法步驟,我們可得到最終切割軌跡為:4使用示例4.1鉆孔點(diǎn)個數(shù)優(yōu)化如圖8所示,為6種零件。共32個零件組成的共邊排樣圖,分別用常規(guī)的共邊切割方法和提出的“一筆畫”共邊方法求解。常規(guī)共邊切割方法求解出的最終切割軌跡,如圖9所示。這種方法在打孔點(diǎn)的個數(shù)優(yōu)化上并沒有提高,32個零件仍然需要32個打孔點(diǎn),也就是有31個空行程。所以說這種共邊切割方法總體優(yōu)化效果并不太理想。如圖10所示,為共邊排樣圖基于“一筆畫”共邊切割方法的最終切割軌跡。由圖7可知,“一筆畫”共邊切割方法與常規(guī)共邊切割方法相比,不僅在切割長度上有很大減少,而且在打孔點(diǎn)個數(shù)也有很大的優(yōu)化。利用“一筆畫”共邊切割方法,32個零件總共只需要打孔11次就可以全部切割完,并且只有10次空行程,其空行程的總長度也很短。實(shí)例結(jié)果證明了提出的基于“一筆畫”共邊切割方法的可行性和優(yōu)越性。4.2切割方法對比如圖11所示,為陣列矩形的共邊排樣圖。常規(guī)共邊切割方法和“階梯形”共邊切割方法來求解。由常規(guī)共邊切割方法求解的最終切割軌跡,如圖12、圖13所示,為“階梯形”共邊切割方法求解的最終切割軌跡。5改進(jìn)共邊切割方法共邊切割已被認(rèn)為是提高切割效率、節(jié)省切割成本的重要措施,然而目前有關(guān)共邊切割方法的研究還不太深入,共邊切割方法對于切割路徑的優(yōu)化效果還沒有完全發(fā)揮出來。以共邊切割的路徑為優(yōu)化目標(biāo),提出了針對普通共邊排樣件