基于分支定界算法的飞机结构件元特征排序*

南京航天航空大学机电学院 黄玲玲 李迎光 王 伟

中航工业成都飞机工业（集团）有限责任公司 汤立民

随着飞机性能的提高和数控技术的广泛应用，整体结构件的使用量逐渐增多。据统计，整体结构件数控编程时间与加工时间比为10：1，整体结构件的数控编程效率已成为飞机结构件数控加工的瓶颈之一[1]。基于特征的数控加工技术以特征为载体，集成优化的加工工艺知识，实现工艺决策和数控编程的自动化，为提高数控编程效率提供了有效手段。其中，加工特征排序是基于特征的数控加工技术的关键问题之一。

现有飞机结构件加工特征定义对应一个或多个加工操作，加工特征排序结果延伸至加工操作层面，导致大量刀具非切削行程，加工效率低。本文将加工特征分解，使分解结果与单个加工操作一一对应，并定义为元特征。元特征在遵循原加工特征排序满足的刚性工艺约束的基础上，采用最小耗费的分支定界算法进行排序，实现刀具非切削行程最短。本文研究成果已集成在基于CATIAV5平台开发的基于特征的数控编程系统中，并在国内某大型航空制造企业的飞机结构件数控加工中得到应用验证。

1 加工特征定义和排序研究现状

在ISO标准STEP AP224[2]中，加工特征被定义为“为了获得零件最终的几何形状，从原始毛坯中去除的那一部分材料体积”，并分为凸台、槽、孔、台阶、筋等17类，但未给出加工特征对应的操作。高曙明等[3]定义加工特征为“一次装夹中的一个简单的加工操作所去除的那部分连续的体积”；Tseng等[4]定义加工特征为“一个零件的一部分，它具有一些加工语义，能够创建一些具体的加工操作”；Yan X等[5]定义加工特征为“一个工件的具有几何和拓扑属性的特殊对象，并能和一系列的加工操作联系起来”，并将铣加工特征分为5类：孔、槽、开口槽、面和凸台。Kriangkrai等[6]将特征定义为2层，一层主要按照加工机床的种类，另一层为加工时选用的轴数，但未给出加工特征与加工操作的对应关系。

从以上描述可以看出，目前定义的加工特征与加工操作非一一对应，即使存在一一对应关系，仅适用于加工工艺相对简单的通用机加件，不适用于加工工艺复杂的飞机结构件。

Britton等[7]提出了一种基于图的特征排序方法；Wong等[8]提出基于模糊逻辑和遗传算法的混合特征排序方法；Waiyagan等[9]介绍了一种考虑各种可行性约束的情况下，运用蚁群算法解决最佳加工操作序列的全局搜索技术；Deja等[10]着重于优化工艺决策问题，包括制定合理的工艺路线和加工步骤的排序，人工智能中分支定界的方法和基于网络的方法被应用到加工特征的排序中；梁吉元等[11]利用图论中“旅行商问题”的数学模型，对含有大量孔的零件进行了优化处理，使得加工多个特征的走刀路径最短；袁青等[12]提出基于遗传算法的飞机结构件加工特征的排序方法，通过一系列的运算使得加工工序得到优化。

现有的加工特征排序存在的问题有：目前排序方法以原加工特征为最小排序单元，继承该顺序至加工操作排序时会增加刀具的空切削路径；现有的加工特征排序是一个加工特征整体之间的排序，但是每个加工特征中又包含多种操作，也就是加工特征的排序并不能完全代表特征实际加工时的操作顺序。

针对现有加工特征定义和排序存在的问题，本文提出元特征定义和基于最小耗费分支定界算法的飞机结构件元特征排序。

2 元特征的定义

元特征是工件上对应一定加工方法的几何形状，对应的切削体由单一加工操作来完成，是工艺决策的最小单元。定义元特征有以下优点：（1）元特征对应单个加工操作，切削原加工特征的单个加工区域，方便排序。（2）元特征具有良好的扩展性：一方面元特征的种类可以根据实际加工方法不断扩展，另一方面元特征可以根据一定的组合规则组合成各种新的用户自定义特征。

元特征是由加工特征分解而成的，如图1所示，槽加工特征可以分解为粗加工元特征、1个腹板面元特征、1个内型元特征、4个转角面元特征，每个元特征对应一个加工操作。

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

图2 元特征的分类Fig.2 Meta-feature classification

同理，筋特征可以分解成筋顶元特征和筋过渡元特征。综上所述，飞机结构件元特征的分类如图2所示。

3 最小耗费分支定界算法

元特征的排序问题可以归纳到小规模的旅行商求解问题。旅行商问题的精确解法有3种：穷举法、整数规划法、分支定界法。基于最小耗费的分支定界法相对于穷举法来说，不需要找到所有的回路，计算量少，节省时间；整数规划法主要使用割平面法，由于这种办法在寻找割平面时需要借助经验，因此，后来很少使用该方法求解[13]；基于最小耗费的分支定界算法，通过预先按照权值的排序，剪掉权值较大的分支，加速了搜索过程，从而找到最优解。

采用最小耗费的分支定界法，可以求得精确解。在这种模式中，每个节点都有1个对应的耗费，即路径的长度。搜索过程是先将所有的路径按照权值由小到大排列起来，先取前n条边（假设顶点的个数为n），若构成回路则取出，若不构成回路则余下的节点将最后一个节点依次替换；若此时构成回路则取出，若不构成回路则从余下节点中按照从小到大的顺序依次选择两个节点将最后两个节点替换；若此时构成回路则取出，若不构成回路则依次类推。最小耗费的分支定界法的搜索过程是按照边由小到大依次搜索，先搜索出的回路比后面的要小，故只要搜索到前几条回路，找到其中的最小回路即可。

4 元特征排序

4.1 异类型元特征排序

异类型元特征间的排序主要遵循飞机结构件的加工工艺规则。飞机结构件异类元特征的排序遵循一般工艺原则，如基面先行、先粗后精、先主后次、先面后孔，刚性差的先加工、刚性好的后加工。一次装夹下，筋顶面元特征的加工排在最前面，其次是腹板面元特征和内型元特征，最后是转角元特征。因为飞机结构件的复杂加工工艺，元特征排序还需遵循特定的规则。

规则1：如果铣内型元特征的刀具半径大于转角半径，则需加工转角面元特征；如果铣内型元特征的刀具半径小于等于转角半径，则不需加工转角面元特征。

规则2：当一种元特征加工完成，需加工另一种元特征时，应先加工离该种元特征最近的异种元特征，从而减少空走刀，提高加工效率。

规则3：一般情况下，内型元特征是腹板面元特征的后续加工，但也存在特殊情况，如凸台的轮廓加工应安排在腹板加工的前面，以防止弹刀或者变形。

4.2 同类型元特征排序

同类型元特征排序简化为元特征的中心点，或者起始点和终止点进行排序。中心点对应到具体的元特征是腹板面元特征的中心点，或者转角面元特征中心轴线和腹板面元特征的交点，或者孔元特征的中心轴线与腹板面元特征的交点，内型元特征的顺序按照腹板面元特征的顺序。其中，转角面元特征的排序体现了元特征的排序与加工特征排序的区别。转角面元特征的排序是把所有加工特征分解得到的元特征混在一起，作为一个整体重新排序，一个加工特征分解可以得到4个或以上的转角面元特征。简化成起始点和终止点进行排序是针对筋顶元特征而言的，将筋顶元特征简化为起始点和终止点，而且起始点和终止点之间的路径必须经过。

具体的算法如下：

（1）得到每个中心点的坐标Vi（xi,yi,zi），设中心点的总个数为n，存放在一维数组V中；筋顶特征则是起始点和终止点存放在一维数组中。

（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）搜索节点，直至找到前4条回路和回路的长度，搜索完毕。

（6）将各个回路去掉最后一条边（也就是最长边），将前4条路径进行比较，选择最小的1条，即得到要找的路径，就是该种元特征的加工顺序。

5 实例

选用如图3所示的框类零件说明腹板面元特征的排序过程，其中BP1～BP5代表腹板面元特征，V1～V5表示腹板面元特征中心点，腹板面元特征排序步骤如下：

（1）识别出零件中所有的腹板面元特征，如图3中的BP1～BP5，计算出腹板面的中心点V1～V5；

图3 腹板元特征排序实例Fig.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 总结

针对现有加工特征定义导致的加工特征排序存在刀具非切削行程过长的问题，本文提出元特征定义和基于最小耗费分支定界算法的元特征排序方法。该方法具有以下优点：

（1）元特征与加工操作一一对应，避免了继承原加工特征排序导致的刀具非切削行程。

（2）针对飞机结构件的加工特点，指定了异类元特征排序遵循的特殊规则。

（3）基于最小耗费分支定界算法对元特征排序实现刀具非切削行程最短，且排序效率高。

[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 系统中孔加工路径的优化处理. 计算机集成制造系统, 2000, 6(1)： 74-76.

[12]袁青, 李迎光, 王伟. 基于遗传算法的飞机结构件加工特征排序. 机械科学与技术, 2011, 30(1)： 86-91.

[13]胡银厚. 求解TSP算法的研究与改进[D]. 郑州：郑州大学,2012.