陳艷平，李 紅，儲正陽

（合肥學院 網(wǎng)絡與智能信息處理重點實驗室，合肥 230601）

0 引言

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

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

1 火焰切割問題描述

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

圖1 排樣后的零件排列圖

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

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

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

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

2.1 構(gòu)建連通圖

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

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

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

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

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

Step3：算法結(jié)束。

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

2.2 構(gòu)建歐拉圖

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

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

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

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

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

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

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

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

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

Step3：當遇到連接點vi_x，則選擇連接線，到達下一個多邊形G(i+1)的連接點vi+1_y。

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

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

Step6：當所有的非連接線的邊都遍歷后（回到起點位置），算法停止。

3 實驗結(jié)果與分析

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

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

表1 排樣圖1的切割實驗比較

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

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

表2 排樣圖1的切割實驗比較

表3 排樣圖1的切割實驗比較

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

4 結(jié)論

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

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

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

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

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

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

[6] 卜月華.圖論及其應用[M].南京:東南大學出版社,2002.