基于分支定界算法的飛機結構件元特征排序*

南京航天航空大學機電學院 黃玲玲 李迎光 王 偉

中航工業(yè)成都飛機工業(yè)（集團）有限責任公司 湯立民

隨著飛機性能的提高和數(shù)控技術的廣泛應用，整體結構件的使用量逐漸增多。據(jù)統(tǒng)計，整體結構件數(shù)控編程時間與加工時間比為10：1，整體結構件的數(shù)控編程效率已成為飛機結構件數(shù)控加工的瓶頸之一[1]。基于特征的數(shù)控加工技術以特征為載體，集成優(yōu)化的加工工藝知識，實現(xiàn)工藝決策和數(shù)控編程的自動化，為提高數(shù)控編程效率提供了有效手段。其中，加工特征排序是基于特征的數(shù)控加工技術的關鍵問題之一。

現(xiàn)有飛機結構件加工特征定義對應一個或多個加工操作，加工特征排序結果延伸至加工操作層面，導致大量刀具非切削行程，加工效率低。本文將加工特征分解，使分解結果與單個加工操作一一對應，并定義為元特征。元特征在遵循原加工特征排序滿足的剛性工藝約束的基礎上，采用最小耗費的分支定界算法進行排序，實現(xiàn)刀具非切削行程最短。本文研究成果已集成在基于CATIAV5平臺開發(fā)的基于特征的數(shù)控編程系統(tǒng)中，并在國內(nèi)某大型航空制造企業(yè)的飛機結構件數(shù)控加工中得到應用驗證。

1 加工特征定義和排序研究現(xiàn)狀

在ISO標準STEP AP224[2]中，加工特征被定義為“為了獲得零件最終的幾何形狀，從原始毛坯中去除的那一部分材料體積”，并分為凸臺、槽、孔、臺階、筋等17類，但未給出加工特征對應的操作。高曙明等[3]定義加工特征為“一次裝夾中的一個簡單的加工操作所去除的那部分連續(xù)的體積”；Tseng等[4]定義加工特征為“一個零件的一部分，它具有一些加工語義，能夠創(chuàng)建一些具體的加工操作”；Yan X等[5]定義加工特征為“一個工件的具有幾何和拓撲屬性的特殊對象，并能和一系列的加工操作聯(lián)系起來”，并將銑加工特征分為5類：孔、槽、開口槽、面和凸臺。Kriangkrai等[6]將特征定義為2層，一層主要按照加工機床的種類，另一層為加工時選用的軸數(shù)，但未給出加工特征與加工操作的對應關系。

從以上描述可以看出，目前定義的加工特征與加工操作非一一對應，即使存在一一對應關系，僅適用于加工工藝相對簡單的通用機加件，不適用于加工工藝復雜的飛機結構件。

Britton等[7]提出了一種基于圖的特征排序方法；Wong等[8]提出基于模糊邏輯和遺傳算法的混合特征排序方法；Waiyagan等[9]介紹了一種考慮各種可行性約束的情況下，運用蟻群算法解決最佳加工操作序列的全局搜索技術；Deja等[10]著重于優(yōu)化工藝決策問題，包括制定合理的工藝路線和加工步驟的排序，人工智能中分支定界的方法和基于網(wǎng)絡的方法被應用到加工特征的排序中；梁吉元等[11]利用圖論中“旅行商問題”的數(shù)學模型，對含有大量孔的零件進行了優(yōu)化處理，使得加工多個特征的走刀路徑最短；袁青等[12]提出基于遺傳算法的飛機結構件加工特征的排序方法，通過一系列的運算使得加工工序得到優(yōu)化。

現(xiàn)有的加工特征排序存在的問題有：目前排序方法以原加工特征為最小排序單元，繼承該順序至加工操作排序時會增加刀具的空切削路徑；現(xiàn)有的加工特征排序是一個加工特征整體之間的排序，但是每個加工特征中又包含多種操作，也就是加工特征的排序并不能完全代表特征實際加工時的操作順序。

針對現(xiàn)有加工特征定義和排序存在的問題，本文提出元特征定義和基于最小耗費分支定界算法的飛機結構件元特征排序。

2 元特征的定義

元特征是工件上對應一定加工方法的幾何形狀，對應的切削體由單一加工操作來完成，是工藝決策的最小單元。定義元特征有以下優(yōu)點：（1）元特征對應單個加工操作，切削原加工特征的單個加工區(qū)域，方便排序。（2）元特征具有良好的擴展性：一方面元特征的種類可以根據(jù)實際加工方法不斷擴展，另一方面元特征可以根據(jù)一定的組合規(guī)則組合成各種新的用戶自定義特征。

元特征是由加工特征分解而成的，如圖1所示，槽加工特征可以分解為粗加工元特征、1個腹板面元特征、1個內(nèi)型元特征、4個轉(zhuǎn)角面元特征，每個元特征對應一個加工操作。

圖1 槽特征分解成元特征的示意圖Fig.1 Diagram of bottom feature decomposing into meta-features

圖2 元特征的分類Fig.2 Meta-feature classification

同理，筋特征可以分解成筋頂元特征和筋過渡元特征。綜上所述，飛機結構件元特征的分類如圖2所示。

3 最小耗費分支定界算法

元特征的排序問題可以歸納到小規(guī)模的旅行商求解問題。旅行商問題的精確解法有3種：窮舉法、整數(shù)規(guī)劃法、分支定界法?；谧钚『馁M的分支定界法相對于窮舉法來說，不需要找到所有的回路，計算量少，節(jié)省時間；整數(shù)規(guī)劃法主要使用割平面法，由于這種辦法在尋找割平面時需要借助經(jīng)驗，因此，后來很少使用該方法求解[13]；基于最小耗費的分支定界算法，通過預先按照權值的排序，剪掉權值較大的分支，加速了搜索過程，從而找到最優(yōu)解。

采用最小耗費的分支定界法，可以求得精確解。在這種模式中，每個節(jié)點都有1個對應的耗費，即路徑的長度。搜索過程是先將所有的路徑按照權值由小到大排列起來，先取前n條邊（假設頂點的個數(shù)為n），若構成回路則取出，若不構成回路則余下的節(jié)點將最后一個節(jié)點依次替換；若此時構成回路則取出，若不構成回路則從余下節(jié)點中按照從小到大的順序依次選擇兩個節(jié)點將最后兩個節(jié)點替換；若此時構成回路則取出，若不構成回路則依次類推。最小耗費的分支定界法的搜索過程是按照邊由小到大依次搜索，先搜索出的回路比后面的要小，故只要搜索到前幾條回路，找到其中的最小回路即可。

4 元特征排序

4.1 異類型元特征排序

異類型元特征間的排序主要遵循飛機結構件的加工工藝規(guī)則。飛機結構件異類元特征的排序遵循一般工藝原則，如基面先行、先粗后精、先主后次、先面后孔，剛性差的先加工、剛性好的后加工。一次裝夾下，筋頂面元特征的加工排在最前面，其次是腹板面元特征和內(nèi)型元特征，最后是轉(zhuǎn)角元特征。因為飛機結構件的復雜加工工藝，元特征排序還需遵循特定的規(guī)則。

規(guī)則1：如果銑內(nèi)型元特征的刀具半徑大于轉(zhuǎn)角半徑，則需加工轉(zhuǎn)角面元特征；如果銑內(nèi)型元特征的刀具半徑小于等于轉(zhuǎn)角半徑，則不需加工轉(zhuǎn)角面元特征。

規(guī)則2：當一種元特征加工完成，需加工另一種元特征時，應先加工離該種元特征最近的異種元特征，從而減少空走刀，提高加工效率。

規(guī)則3：一般情況下，內(nèi)型元特征是腹板面元特征的后續(xù)加工，但也存在特殊情況，如凸臺的輪廓加工應安排在腹板加工的前面，以防止彈刀或者變形。

4.2 同類型元特征排序

同類型元特征排序簡化為元特征的中心點，或者起始點和終止點進行排序。中心點對應到具體的元特征是腹板面元特征的中心點，或者轉(zhuǎn)角面元特征中心軸線和腹板面元特征的交點，或者孔元特征的中心軸線與腹板面元特征的交點，內(nèi)型元特征的順序按照腹板面元特征的順序。其中，轉(zhuǎn)角面元特征的排序體現(xiàn)了元特征的排序與加工特征排序的區(qū)別。轉(zhuǎn)角面元特征的排序是把所有加工特征分解得到的元特征混在一起，作為一個整體重新排序，一個加工特征分解可以得到4個或以上的轉(zhuǎn)角面元特征。簡化成起始點和終止點進行排序是針對筋頂元特征而言的，將筋頂元特征簡化為起始點和終止點，而且起始點和終止點之間的路徑必須經(jīng)過。

具體的算法如下：

（1）得到每個中心點的坐標Vi（xi,yi,zi），設中心點的總個數(shù)為n，存放在一維數(shù)組V中；筋頂特征則是起始點和終止點存放在一維數(shù)組中。

（2）計算出每2個中心點之間的距離作為連接這2個點的邊權值，其中i≠j。

（3）將所有的邊a12,a13,a14…an,n-1按照權值由小到大排列，取前n個邊作為分支S；筋頂則先將邊a12,a34,a56…an,n-1取出，剩余的邊按權值由小到大排序，并從中取n/2個邊，與預定的邊組成分支S。

（4）進入迭代階段，若S構成回路，記錄回路的長度值d，若不構成回路則舍去；用剩下未考察的第一組邊作為S，返回（4）。其中迭代的過程如下：若按照權值排序后的邊為b12,b13,b14…bn,n-1先取b12,b13,b14…b1,n，判斷是否為回路，若不是回路，則將b1,n依次替換成b23,b24,b25,…bn,n-1，若有回路則取出；若沒有回路，則將b1,n-1，b1,n依次替換成b23,b24,b25,…bn,n-1中的兩兩組合，若有回路則取出，依次類推。這樣從前往后的搜索，保證了找到的回路是最短的。

（5）搜索節(jié)點，直至找到前4條回路和回路的長度，搜索完畢。

（6）將各個回路去掉最后一條邊（也就是最長邊），將前4條路徑進行比較，選擇最小的1條，即得到要找的路徑，就是該種元特征的加工順序。

5 實例

選用如圖3所示的框類零件說明腹板面元特征的排序過程，其中BP1～BP5代表腹板面元特征，V1～V5表示腹板面元特征中心點，腹板面元特征排序步驟如下：

（1）識別出零件中所有的腹板面元特征，如圖3中的BP1～BP5，計算出腹板面的中心點V1～V5；

圖3 腹板元特征排序?qū)嵗鼺ig.3 Example of bottom meta-feature sequencing

（2）每2點之間連成邊，該例中邊表為a12,a13,a14,a15,a23,a24,a25,a34,a35,a45,其中字母表示邊，下標表示構成這條邊的點且每條邊無向。

（3）計算邊的長度，即構成邊的2點之間的距離：，其 中i≠j，且i

dis(1,2)=51.205mm,dis(1,3)=116.502mm,

dis(1,4)=118.676mm,dis(1,5)=54.524mm,

dis(2,3)=65.309mm,dis(2,4)=77.322mm,

dis(2,5)=57.649mm,dis(3,4)=55.121mm,

dis(3,5)=105.766mm,dis(4,5)=82.785mm。

（4）將所有邊按照長度的大小依次排列，順序如下：a12,a15,a34,a25,a23,a24,a45,a35,a13,a14。

（5）分支定界：

S1：a12,a15,a34,a25,a23，非回路；

S2：a12,a15,a34,a25,a24，非回路；

S3：a12,a15,a34,a25,a35，非回路；

S4：a12,a15,a34,a25,a13，非回路；

S5：a12,a15,a34,a25,a14，非回路；

S6：a12,a15 ,a34,a23,a24，非回路；

S7：a12,a15,a34,a23,a45，回路；

S8：a12,a15,a34,a24,a45，非回路；

S9：a12,a15,a34,a24,a35，回路；

……

S55：a12,a34,a25,a45,a13，回路；

……

S58：a12,a34,a25,a35,a14，回路。

找到前4條回路：

S7：a12,a15,a34,a23,a45,d7=308.347；

S9：a12,a15, a34,a24,a35,d9=343.938；

S55：a12,a34,a25,a45,a13,d55=363.262；

S58：a12,a34,a25,a35,a14,d58=388.417。

（6）減去回路中的最長邊，即得到全局刀具最短路徑長度：

S7'：a12,a15,a34,a23,d7'=225.562；

S9'：a12,a15,a34,a24,d9'=238.172；

S55'：a12,a34,a25,a45,d55'=246.76；

S58'：a12,a34,a25,a35,d58'=269.741。

比較路徑的長度可以得到，最短回路為S7'，最短切削路徑為BP5—BP1—BP2—BP3—BP4，如圖 4（b）所示。

圖4 腹板元特征排序Fig.4 Bottom meta-feature sequencing

6 總結

針對現(xiàn)有加工特征定義導致的加工特征排序存在刀具非切削行程過長的問題，本文提出元特征定義和基于最小耗費分支定界算法的元特征排序方法。該方法具有以下優(yōu)點：

（1）元特征與加工操作一一對應，避免了繼承原加工特征排序?qū)е碌牡毒叻乔邢餍谐獭?/p>

（2）針對飛機結構件的加工特點，指定了異類元特征排序遵循的特殊規(guī)則。

（3）基于最小耗費分支定界算法對元特征排序?qū)崿F(xiàn)刀具非切削行程最短，且排序效率高。

[1]Li Y G, Ding Y F, Mou W P, et al. Feature recognition technology for aircraft structural parts based on a holistic attribute adjacency graph.Proceedings of the Institution of Mechanical Engineers, Part B： Journal of Engineering Manufacture, 2010, 224(2)： 271-278.

[2]Industrial automatic systems and integration--Product data representation and exchange-Application protocol ：Mechanical product definition for process planning using machining features. International Standard. ISO10303-224, 2000(E).

[3]Gao S M, Shah J J. Automatic recognition of interacting machining features based on minimal condition subgraph. Computer Aided Design, 1998, 30(9)： 727-739.

[4]Tseng Y J, Joshi S B. Recognition of interacting rotational and prismatic machining features from 3-D mill-turn parts. International Journal of Production Research, 1998, 36(11)： 3147-3165.

[5]Yan X, Yamazaki K, Liu J. Recognition of machining features and feature topologies from NC programs. Computer Aided Design, 2000,32(10)： 605-616.

[6]Waiyagan K, Bohez E L J. Intelligent feature based process planning for five-axis mill-turn parts. Computers in Industry, 2009, 60(5)：296-316.

[7]Britton G, Thimm G, Beng T S. A graph representation scheme for process planning machined parts. International Journal of Advanced Manufacturing Technology, 2002, 20(6)： 429-438.

[8]Wong T N, Chan L C F, Lau H C W. Machining process sequencing With fuzzy expert system and genetic algorithms. Engineering With Computer, 2003, 19(2/3)： 191-202.

[9]Krishna A G, Rao K M. Optimisation of operations sequence in CAPP using an ant colony algorithm. International Journal of Advanced Manufacturing Technology, 2006, 29(1/2)： 159-164.

[10]Deja M, Siemiatkowski M S. Feature-based generation of machining process plans for optimised parts manufacture. Journal of Intelligent Manufacturing, Accepted： 20 February 2012.

[11]梁吉元, 郁鼎文, 張玉峰,等. CAM 系統(tǒng)中孔加工路徑的優(yōu)化處理. 計算機集成制造系統(tǒng), 2000, 6(1)： 74-76.

[12]袁青, 李迎光, 王偉. 基于遺傳算法的飛機結構件加工特征排序. 機械科學與技術, 2011, 30(1)： 86-91.

[13]胡銀厚. 求解TSP算法的研究與改進[D]. 鄭州：鄭州大學,2012.