基于歐拉回路的數(shù)控火焰切割路徑優(yōu)化研究與實(shí)現(xiàn)

陳艷平，李 紅，儲(chǔ)正陽

（合肥學(xué)院 網(wǎng)絡(luò)與智能信息處理重點(diǎn)實(shí)驗(yàn)室，合肥 230601）

0 引言

由于火焰切割設(shè)備生產(chǎn)投入小，加工厚度大，因此在適合精度要求不高的粗加工行業(yè)得到了廣泛的應(yīng)用。對(duì)于數(shù)控火焰切割設(shè)備來說，切割前必須預(yù)先對(duì)排樣后的零件切割路徑進(jìn)行規(guī)劃，確定引入引出線的長度和位置，并生成切割控制程序。切割路徑的規(guī)劃對(duì)提高設(shè)備的生產(chǎn)效率起著舉足輕重的作用?，F(xiàn)有的絕大多數(shù)路徑規(guī)劃軟件，都采取切割完一個(gè)零件后再切割下一個(gè)零件的方法進(jìn)行路徑規(guī)劃，旨在解決零件的切割順序上做文章，提出了一些優(yōu)化算法，如基于零件外輪廓形心的蟻群算法[1,4]，改進(jìn)的普利姆(Prim) 算法[2,3]等。這些方法在一定程度上縮短了割嘴空程時(shí)間，但不能降低點(diǎn)火、熄火次數(shù)，而對(duì)于火焰切割來說，點(diǎn)火、熄火時(shí)間長（80秒左右），嚴(yán)重影響了切割效率。

歐拉圖(Euler graph)是圖論中一種重要的圖。歐拉回路是通過圖（有向圖或者無向圖）中所有邊一次且僅一次行遍所有頂點(diǎn)的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。它最早源于1736年瑞士數(shù)學(xué)家歐拉（Euler）發(fā)表的論文“哥尼斯堡七橋問題”，并在各行各業(yè)中得到了廣泛的應(yīng)用[6]。因此在零件外輪廓切割問題上提出了一種基于歐拉回路的切割路徑規(guī)劃算法，為切割路徑優(yōu)化問題提供一個(gè)新的思路。先計(jì)算零件外輪廓的最短距離，然后通過搭橋法構(gòu)造歐拉圖，最后求解該歐拉圖的歐拉回路，從而確定整個(gè)樣板的切割路徑。

1 火焰切割問題描述

如圖1所示，某一尺寸為L×S的板材上是通過排樣程序計(jì)算輸出的排樣圖，排樣圖上緊湊的排列著多個(gè)不規(guī)則的圖形，數(shù)控切割任務(wù)是將所有圖形沿輪廓從板材上切割下來。顯然切割得方式有多種，不同的切割路徑不同，行程也將不同。

圖1 排樣后的零件排列圖

在文獻(xiàn)[1]中利用Prim算法產(chǎn)生最小代價(jià)樹，生成切割順序表，按照順序逐個(gè)完成各零件的切割，這種方法在激光或刀片切割時(shí)可取，但不適合用于火焰切割。由于火焰切割時(shí)不但點(diǎn)火熄火時(shí)間長，而且需要在點(diǎn)火熄火位置打孔、設(shè)置引入引出線，大大增加了問題求解的難度，降低了切割效率。在充分考慮火焰切割特點(diǎn)的基礎(chǔ)上，提出火焰切割的目標(biāo)是如何規(guī)劃切割路徑，在點(diǎn)火次數(shù)盡量少的條件下，求解切割軌跡長度最小值，其中切割軌跡為每個(gè)零件的輪廓軌跡與空行程軌跡總和。根據(jù)熱加工的特點(diǎn)，還必須保證每個(gè)零件的輪廓軌跡只切割一次。

2 基于歐拉回路的求解框架

火焰切割中減少點(diǎn)火次數(shù)是路徑優(yōu)化中首要問題。盡量減少點(diǎn)火次數(shù)的問題與“一筆畫問題”非常相似。所謂“一筆畫問題”就是畫一個(gè)圖形，在筆不離紙，每條邊只畫一次而不許重復(fù)的情況下，畫完該圖。“一筆畫問題”的本質(zhì)是一個(gè)無向圖是否存在歐拉回路的問題。如果該圖為歐拉圖，則一定能夠用一筆畫完，并且筆又回到出發(fā)點(diǎn)。因此火焰切割問題可以轉(zhuǎn)化為在現(xiàn)有的排樣圖的基礎(chǔ)上構(gòu)造歐拉圖、求解歐拉圖的一個(gè)歐拉回路。求解思路如圖2所示。

圖2 路徑優(yōu)化算法流程圖

2.1 構(gòu)建連通圖

已知板上有n個(gè)多邊形形狀，記集合為C= G(1)∪G(2)∪, …, ∪G(n)，G(i)為第i個(gè)多邊形。在圖論中，用頂點(diǎn)和邊的集合來表示一個(gè)圖形，故多邊形可描述為G(i)=(V，E)，其中V(G(i)) ={vi1,vi2, …, vin}稱為圖G(i)的頂點(diǎn)集； E(G(i))= {ei1，ei2，…，ein}稱為圖G(i)的邊集合。其中E中的每一個(gè)元素ei_i =(vi_j,vi_k)表示連接G(i)圖形中vi_j和vi_k節(jié)點(diǎn)的無向邊。

構(gòu)建連通圖的核心是將相鄰形狀用輔助連接線連接起來，構(gòu)成一幅連通圖，保證C中任意兩個(gè)多邊形G(i)之間都有通路可達(dá)。在切割問題中，添加輔助線時(shí)必須滿足兩點(diǎn)：1）該輔助線不能穿越任何形狀；2）盡量保證所有的輔助線長度之和最短。構(gòu)建連通圖問題可以用圖論語言這樣描述，首先將每個(gè)多邊形抽象為一個(gè)節(jié)點(diǎn)，將輔助線抽象為邊，邊的權(quán)值為兩點(diǎn)間的歐式距離，那么通過添加輔助線一定能將多邊形集合轉(zhuǎn)化為完全連通圖。為滿足輔助線添加的兩個(gè)要求，則需要將該完全連通圖轉(zhuǎn)化為具有最小權(quán)值的生成樹。因此構(gòu)建連通圖等價(jià)于求取該完全連通圖的最小生成樹。Prim算法是求解最小生成樹的經(jīng)典算法，改進(jìn)后的算法描述如下：

Step0：初始化已處理形狀列表solved_list為空，未處理形狀列表unsolved_list為C。將unsolved_list的第一個(gè)形狀G(1)加到solved_list中。

Step1：通過改進(jìn)旋轉(zhuǎn)卡殼算法從unsolved_list中搜索與solved_list中最近的形狀G(i)，在距離最近的位置用連接線連接，記錄連接點(diǎn)對(duì)，添加邊ei_i（vi_x，vj_y），將G(i)從unsolved_list中刪除，加入到solved_list。

Step2：unsolved_list不為空，則重復(fù)Step2；為空，則轉(zhuǎn)向step4。

Step3：算法結(jié)束。

通過該算法，生成的連通圖如圖3所示。

2.2 構(gòu)建歐拉圖

定理1：一個(gè)無向連通圖是歐拉圖的充分必要條件是每個(gè)節(jié)點(diǎn)的度為偶數(shù)[6]。

定理2：一個(gè)無向連通圖中奇度節(jié)點(diǎn)的個(gè)數(shù)為偶數(shù)[6]。

根據(jù)定理1、2，對(duì)于給定的連通圖，若該圖中含有2K個(gè)奇度點(diǎn)，構(gòu)建歐拉圖問題歸結(jié)為找到該圖中2K個(gè)奇度點(diǎn)，求出符合K條歐拉通路間空行程最短的K條添加邊[5]。這是最小權(quán)最大匹配問題。在火焰切割問題求解中，要求每個(gè)零件的輪廓軌跡只切割一次，故添加邊只能是連接輔助線。因此根據(jù)先驗(yàn)知識(shí)，首先在C中找到每個(gè)度為奇數(shù)的點(diǎn)，給這些點(diǎn)關(guān)聯(lián)的連接輔助線添加平行邊得C～，C～一定為歐拉圖，如圖4所示。

2.3 求歐拉圖的一條歐拉回路

Fleury算法是求解歐拉圖的歐拉回路的經(jīng)典算法。使用Fleury算法求歐拉通路（回路）時(shí)，每次走一條邊，在可能的情況下不走橋。借鑒Fleury算法思路，在求解上述構(gòu)造的歐拉圖中，每次逆時(shí)針走一條邊，遇到與連接輔助線關(guān)聯(lián)的節(jié)點(diǎn)v則走連接輔助線，簡單的說就是“先走橋后走邊”，從而生成一條能夠遍歷且只遍歷所有的輪廓一次的通路。求解歐拉通路算法描述如下：

圖3 構(gòu)造連通圖C

圖4 構(gòu)造歐拉圖C

Step1：取離初始位置最近的點(diǎn)v0∈V(C～)，令P0=v0。

Step2：從P0出發(fā)，遍歷所在多邊形G(i)。

Step3：當(dāng)遇到連接點(diǎn)vi_x，則選擇連接線，到達(dá)下一個(gè)多邊形G(i+1)的連接點(diǎn)vi+1_y。

Step4：逆時(shí)針遍歷與vi+1_y相關(guān)聯(lián)的G(i+1)的邊ei+1_z。

Step5：逆時(shí)針遍歷，遇到連接點(diǎn)，轉(zhuǎn)向Step3。

Step6：當(dāng)所有的非連接線的邊都遍歷后（回到起點(diǎn)位置），算法停止。

3 實(shí)驗(yàn)結(jié)果與分析

將該算法應(yīng)用到數(shù)控火焰切割機(jī)床進(jìn)行實(shí)驗(yàn)，輸入數(shù)據(jù)為排樣圖1，共108個(gè)圖形。在處理外輪廓切割問題上，該算法只需點(diǎn)火一次，與排樣圖中形狀數(shù)量無關(guān)?？傂谐涕L度由形狀的輪廓長度和空行程長度組成，其中空行程長度為連接線長度之和的兩倍。性能上優(yōu)于市場中多種數(shù)控切割產(chǎn)品。

本算法與文獻(xiàn)[1]中基于零件外輪廓形心的蟻群算法對(duì)比數(shù)據(jù)如表1所示。

表1 排樣圖1的切割實(shí)驗(yàn)比較

本算法與文獻(xiàn)[2]中基于改進(jìn)的普利姆算法對(duì)比數(shù)據(jù)如表2所示。

本算法與市場占有率較高的瑞麗軟件對(duì)比數(shù)據(jù)如表3所示。

表2 排樣圖1的切割實(shí)驗(yàn)比較

表3 排樣圖1的切割實(shí)驗(yàn)比較

從切割質(zhì)量上看，本算法為了保證一筆切完，某些形狀是分兩次，有些甚至是三次切割。對(duì)于一個(gè)形狀而言，由于板材熱加工變形收縮，以及機(jī)器臂的漂移等因素影響，導(dǎo)致加工后的部件連接點(diǎn)位置出現(xiàn)部分毛刺。對(duì)于精細(xì)加工工藝而言，可以結(jié)合其他補(bǔ)償方法加以解決。

4 結(jié)論

本文研究了基于歐拉回路的外輪廓數(shù)控火焰切割路徑優(yōu)化算法。先通過計(jì)算外輪廓的距離，充分利用板材空白廢料區(qū)給近鄰的外輪廓添加輔助橋接線（俗稱搭橋），構(gòu)建歐拉圖，并在先驗(yàn)知識(shí)的指導(dǎo)下，求出一條歐拉回路，從而得到了各零件外輪廓的切割路徑。通過在復(fù)雜排樣條件下的比較測(cè)試，本文提出的方法在外輪廓切割上能夠保證一筆切割，空程比例也明顯降低，生產(chǎn)效率得到極大的提高。它不但能很好地解決了數(shù)控火焰切割的路徑優(yōu)化問題，在激光切割，刀片切割等應(yīng)用領(lǐng)域也能夠大大縮短空行程長度。

[1] 朱燈林,陳俊偉,俞潔,董世昌.基于零件形心的數(shù)控火焰切割路徑的規(guī)劃[J].機(jī)械設(shè)計(jì)與制造.2006(09):88-90.

[2] 陳颯,施展.板金加工數(shù)控切割路徑的優(yōu)化計(jì)算[J].上海理工大學(xué)學(xué)報(bào).2003.25(4):376-378.

[3] 劉會(huì)霞,王霄,蔡蘭.鈑金件數(shù)控激光切割割嘴路徑的優(yōu)化[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào).2004.16(1):660-665.

[4] 孫鑫.二維激光切割路徑優(yōu)化研究[M].2012.

[5] 劉會(huì)霞,王霄,周明,蔡蘭.共邊排樣件激光切割路徑的規(guī)劃[J].中國激光,2004.31(10):1269-1274.

[6] 卜月華.圖論及其應(yīng)用[M].南京:東南大學(xué)出版社,2002.