夏蔚文，黃廣煒，王軍旗，趙萬生

（上海交通大學(xué)機(jī)械與動(dòng)力工程學(xué)院，機(jī)械系統(tǒng)與振動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，上海200240）

高速電火花小孔加工被普遍用于加工微小孔、群孔、斜孔、深孔等，在航空航天、模具制造等領(lǐng)域廣泛使用[1]。在群孔加工時(shí)，電極從第一個(gè)孔開始，依次移動(dòng)到下一個(gè)孔位放電加工，需頻繁地在孔位之間移動(dòng)，整個(gè)加工任務(wù)中累積的移動(dòng)距離可達(dá)數(shù)米，累積的移動(dòng)時(shí)間也十分可觀，加工的整體效率往往會(huì)因?yàn)椴划?dāng)?shù)穆窂揭?guī)劃而大幅降低。在電火花小孔加工機(jī)床數(shù)控編程時(shí)，大多數(shù)會(huì)通過DXF繪圖文件保存圖形和點(diǎn)位信息。CAM軟件讀取圖中孔位信息后，經(jīng)過路徑規(guī)劃處理，輸出為G代碼或其他格式加工代碼用于加工。但在DXF文件格式中，實(shí)體的排列順序由圖元繪制的先后次序決定，如果整體圖形復(fù)雜，或在繪制過程中出現(xiàn)反復(fù)修改，則加工次序與圖中排列不一致，這是導(dǎo)致加工軌跡過長(zhǎng)的重要原因之一。在機(jī)械鉆孔加工中也存在類似的問題，一些學(xué)者進(jìn)行了討論。朱光宇提出一種基于粒子群優(yōu)化算法的鉆孔路徑規(guī)劃方法，具有全局收斂的特性[2-3]。劉晉飛針對(duì)蜂窩陶瓷模具鉆孔加工問題，基于均勻分布理論開發(fā)了一套CAD/CAM系統(tǒng)，提高了軌跡生成效率[4]。陳戀芳提出了一種基于差分算法的群孔加工路徑優(yōu)化方法，同時(shí)考慮了鉆孔加工中更換刀具的情況[5]。Abbas等針對(duì)矩形陣列群孔，使用蟻群優(yōu)化算法獲得了最優(yōu)解[6]。

本文以有效和實(shí)用為原則，參考旅行商問題近似解法，考慮孔的相對(duì)距離或坐標(biāo)，提出了幾種群孔加工軌跡規(guī)劃的方法，并集成到小孔電火花加工機(jī)床的CAM軟件中。幾種算法的比較測(cè)試結(jié)果表明，規(guī)劃后的加工軌跡長(zhǎng)度比未規(guī)劃時(shí)顯著減少，且各個(gè)算法的時(shí)間復(fù)雜度均可接受。

1 群孔路徑規(guī)劃問題的抽象

設(shè)孔數(shù)為n，構(gòu)成集合V。在加工順序中，任意兩點(diǎn)可相鄰且無先后限制。因此，集合V中可定義一個(gè)二元關(guān)系，表示兩點(diǎn)在加工時(shí)相鄰：

且A為對(duì)稱關(guān)系。A、V構(gòu)成無向完全圖：

給每條邊 a=（vi，vj）賦權(quán)為 w（vi，vj） ，代表任意兩點(diǎn)間的距離，得到無向完全網(wǎng)絡(luò)（G，w）。

群孔加工的最短路徑規(guī)劃要求在此無向網(wǎng)絡(luò)中，以指定的節(jié)點(diǎn)為起點(diǎn)，搜索一條道路經(jīng)過剩余所有節(jié)點(diǎn)一次且僅僅一次，不回到初始節(jié)點(diǎn)，且?guī)?quán)路徑的長(zhǎng)度最小。

此問題類似于旅行商問題 （Traveling Salesman Problem，TSP）。TSP要求在帶權(quán)無向完全網(wǎng)絡(luò)的眾多Hamilton回路中尋找?guī)?quán)長(zhǎng)度最短的一條。該問題在數(shù)學(xué)上屬于非確定多項(xiàng)式 （Non-deterministic Polynomial，NP）完全問題，目前沒有多項(xiàng)式時(shí)間復(fù)雜度的精確解法。在眾多近似解法中，許多學(xué)者研究了遺傳算法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)算法、進(jìn)化算法等[7]。

群孔加工路徑規(guī)劃問題與TSP的區(qū)別在于：①指定了起點(diǎn)；②不必返回起點(diǎn)，形成回路。因而群孔加工路徑規(guī)劃問題獲得最優(yōu)解仍非常困難，但仍可借鑒TSP近似算法達(dá)到良好的效果。下文將在第二節(jié)和第三節(jié)介紹兩種TSP近似算法在群孔路徑規(guī)劃問題中的應(yīng)用，并在第四節(jié)介紹基于坐標(biāo)排序的路徑規(guī)劃算法。

2 最近鄰法

最近鄰法是指：從節(jié)點(diǎn)v1出發(fā)，找到其未被標(biāo)記的最鄰近的節(jié)點(diǎn)v2；再?gòu)膙2出發(fā)，尋找最鄰近節(jié)點(diǎn)v3；直到遍歷所有節(jié)點(diǎn)，抵達(dá)vn，從而獲得一條遍歷各點(diǎn)的道路，其流程見圖1。由于需計(jì)算任意兩點(diǎn)間的距離，最近鄰法的時(shí)間復(fù)雜度為 T（n）=O（n2）。

3 插入法

插入法的思路是：從節(jié)點(diǎn)v1出發(fā)，維護(hù)一個(gè)已標(biāo)記的節(jié)點(diǎn)集合T，根據(jù)未標(biāo)記節(jié)點(diǎn)到節(jié)點(diǎn)集合的距離，從中選取一點(diǎn)vj，插入已標(biāo)記的節(jié)點(diǎn)集合中。

其流程可表述如下：所有節(jié)點(diǎn)構(gòu)成無向完全圖G=（V，E），|V|=n；vj表示第 j個(gè)節(jié)點(diǎn)； 每邊的權(quán)為 w（vi，vj）。

圖1 最近鄰規(guī)劃法

（1）初始標(biāo)記節(jié)點(diǎn)集合為T={v1}，初始軌跡記為H=（v1）。

（2）在|T|＜n 時(shí)循環(huán)。

（3）對(duì)所有 vi∈V-T，計(jì)算 vi到 T 的距離，為：

（4）選取待插入節(jié)點(diǎn)vj和插入位置t：

（5）插入集合T和軌跡H：

（6）結(jié)束。

依據(jù)選取插入點(diǎn)和插入方法的不同，插入法又可分為最近插入法和貪心插入法等。

插入法每次循環(huán)時(shí)，需計(jì)算、比較已標(biāo)記節(jié)點(diǎn)中任意一點(diǎn)和未標(biāo)記節(jié)點(diǎn)中任意一點(diǎn)之間的距離，總運(yùn)算次數(shù)為：可得插入法的時(shí)間復(fù)雜度為 T（n）=O（n3）。

3.1 最近插入法

最近插入法選取未標(biāo)記節(jié)點(diǎn)中距離當(dāng)前標(biāo)記節(jié)點(diǎn)集合T最近的節(jié)點(diǎn)：

然后將選取的未標(biāo)記節(jié)點(diǎn)插入t的后面。設(shè)H=（…t1，t，t2…），則插入后得到 H=（…t1，t，vj，t2…）。

3.2 貪心插入法

與最近插入法相同，貪心插入法選取未標(biāo)記節(jié)點(diǎn)中距離當(dāng)前旅行圈T最近的節(jié)點(diǎn)，再采用貪心策略插入當(dāng)前軌跡 H。 設(shè) H=（…t1，t，t2…），若：

即：

則將vj插入t的前面，否則插入t的后面。

由于軌跡中第一節(jié)點(diǎn)被指定為不可更改，如果t恰好為第一節(jié)點(diǎn)，則只能插入t的后面。

4 坐標(biāo)排序規(guī)劃法

考慮到群孔加工時(shí)的點(diǎn)位信息以各點(diǎn)坐標(biāo)表示，對(duì)于群孔排列較密集且按陣列排布的情況，可不計(jì)算各點(diǎn)間距離，而是直接通過坐標(biāo)排序來規(guī)劃路徑。坐標(biāo)排序法的流程如下：

（1）以指定第一點(diǎn)為原點(diǎn)，將剩余各節(jié)點(diǎn)劃分到四個(gè)象限中。落在坐標(biāo)軸上的點(diǎn)，可按需劃入相鄰象限之一，可獲得四個(gè)節(jié)點(diǎn)子集 V1、V2、V3、V4。

（2）V1中按各點(diǎn)x坐標(biāo)升序排序，然后按x坐標(biāo)分組。設(shè)定分組寬度，記為d，將x坐標(biāo)位于[0，d），[d，2d）…的節(jié)點(diǎn)分別分組。設(shè)V1中最右側(cè)節(jié)點(diǎn)的x坐標(biāo)為xmax，則共得到[xmax/d]+1組，并以x升序從1開始編號(hào)。將編號(hào)為奇數(shù)的組中的節(jié)點(diǎn)，按y坐標(biāo)升序排序；編號(hào)為偶數(shù)的組中的節(jié)點(diǎn)，按y坐標(biāo)降序排序。

（3）V2、V3、V4中的節(jié)點(diǎn)按同樣的分組寬度分組。各組中的節(jié)點(diǎn)也按y坐標(biāo)排序。其中，V2中各組的排序方式與V1相同；V3、V4中的各組以x降序從1開始編號(hào)，且奇數(shù)組內(nèi)按y坐標(biāo)降序排序，偶數(shù)組內(nèi)按y坐標(biāo)升序排序。

（4）按 V1、V4、V3、V2的順序，按各子集中的分組編號(hào)升序，將各組的節(jié)點(diǎn)添加到軌跡中。

在坐標(biāo)排序法中，不需計(jì)算各點(diǎn)間的距離，只需將除第一點(diǎn)外的所有點(diǎn)分別按x和y進(jìn)行排序，且使用快速排序算法。因此，坐標(biāo)排序法的時(shí)間復(fù)雜度為 T（n）=O（nlogn）。

5 方法驗(yàn)證

上述方法被集成到基于LibreCAD開發(fā)的電火花穿孔機(jī)CAM軟件中。實(shí)驗(yàn)選取2個(gè)群孔圖形進(jìn)行路徑規(guī)劃測(cè)試，第1個(gè)圖形為圖2所示的陣列，孔位分別位于圓心處，陣列中有10排10列共計(jì)100個(gè)單元、600個(gè)孔位；第2個(gè)圖形為圖3所示的多邊形陣列，孔位位于頂點(diǎn)處，共有1632個(gè)孔位。

測(cè)試環(huán)境分別為PC機(jī)和嵌入式控制器，參數(shù)見表1。測(cè)試時(shí)，對(duì)相同的圖形分別采用不同的算法進(jìn)行規(guī)劃，記錄算法運(yùn)行時(shí)間和最終獲得的路徑長(zhǎng)度。針對(duì)每種環(huán)境中的每個(gè)圖形，四種算法均運(yùn)行五次，順序隨機(jī)，記錄其運(yùn)行的平均時(shí)間。將不同算法的運(yùn)行時(shí)間進(jìn)行比較，并將各算法得到的路徑長(zhǎng)度與未進(jìn)行路徑規(guī)劃時(shí)的路徑長(zhǎng)度比較，得到的結(jié)果見表2～表5。可看出，采用坐標(biāo)排序法的耗時(shí)最少，只需不到1 ms即可完成規(guī)劃，但規(guī)劃效果不如其他幾種方法。該方法對(duì)于按陣列排列的圖形（圖2），在減少路徑長(zhǎng)度方面的效果較明顯，但對(duì)于復(fù)雜圖形（圖3），其效果較差。采用最近鄰法的耗時(shí)也少，且對(duì)于不同圖形的規(guī)劃效果都十分顯著，可減少運(yùn)動(dòng)路徑30%以上。

圖2 測(cè)試圖形1

圖3 測(cè)試圖形2

表1 測(cè)試環(huán)境

此外，兩種插入法的耗時(shí)都較長(zhǎng)。處理1632個(gè)點(diǎn)位圖形時(shí)，在嵌入式控制器上的運(yùn)行時(shí)間已超過16 s。根據(jù)各算法的時(shí)間復(fù)雜度分析，隨著點(diǎn)位的增加，插入法的耗時(shí)會(huì)急劇增大，且其規(guī)劃效果并沒有顯著優(yōu)于最近鄰法。因此，在四種規(guī)劃算法中，最近鄰法最為實(shí)用和有效，而在處理線性陣列圖形時(shí)，使用坐標(biāo)排序法也未嘗不可。

表2 圖形1路徑規(guī)劃用時(shí)

表3 圖形1路徑規(guī)劃結(jié)果

表4 圖形2路徑規(guī)劃用時(shí)

表5 圖形2路徑規(guī)劃結(jié)果

6 結(jié)束語

針對(duì)電火花群孔加工時(shí)的路徑規(guī)劃問題，根據(jù)各點(diǎn)相對(duì)距離和坐標(biāo)，參考TSP近似解法，提出了幾種有效且實(shí)用的規(guī)劃算法。通過在不同環(huán)境中針對(duì)不同加工圖形的測(cè)試表明，幾種算法均能比不規(guī)劃時(shí)減少電極運(yùn)動(dòng)距離、提高整體效率，且算法運(yùn)行時(shí)間均可接受，其中最近鄰法運(yùn)算耗時(shí)短，規(guī)劃效果好，故最為實(shí)用。

[1] 趙萬生，劉晉春.電火花加工技術(shù)[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2000.

[2] 朱光宇.面向鉆削路徑規(guī)劃問題的微粒群優(yōu)化算法研究[J].信息與控制，2008（1）：103-107，112.

[3] ZHU G Y，ZHANG W B.Drilling path optimization by the particle swarm optimization algorithm with global convergence characteristics[J].International Journal of Production Research，2008，46（8）：2299-2311.

[4] 劉晉飛，姚平喜.基于均布的群孔加工CAD/CAM系統(tǒng)的研究與開發(fā)[J].精密制造與自動(dòng)化，2009（3）：52-54.

[5] 陳戀芳.基于差分算法的群孔加工工藝優(yōu)化 [D].福州：福州大學(xué)，2011.

[6] ABBAS A T，ALY M F，HAMZA K.Optimum drilling path planning for a rectangular matrix of holes using ant colony optimisation[J].International Journal of Production Research，2011，49（19）：5877-5891.

[7] HOFFMAN K L，PADBERG M，RINALDI G.Traveling salesman problem [M].Encyclopedia ofOperations Research and Management Science.Springer US，2013：1573-1578.