CNC数控激光切割机床(Laser Cutting Machine,L CM)是典型的机、光、电为一体的技术密集型高科技设备。在工业发达国家,LCM已被看作为“敏捷制造”模式下的一种快速响应

生产的制造设备1近年来,LCM正在被越来越多的国内企业所采用,并在经济发达地区,如深圳、上海、江南一带发展十分迅猛1在数控激光切割技术日趋成熟的情况下,与之配套的专用

CAD/CAM一体化自动编程系统的性能越来越引起用户的关注,因为这种应用软件的性能严重制约了这些先进数控激光加工设备的加工效率与质量1通过我校215KW(CO2)激光切割机床生

产实践发现,在这些性能要求中,激光切割打孔点位置的合理选取与割嘴路径的有效规划A ID1E1D6 ,DNEoS1I5GN&COMPU TER GRAPHICS2082 1,对激光切割这样一个高投入、高消耗、

更高产出的高新设备而言,即使单件节省较少的时间,其效益也是十分可观的1然而从我们接触的国内外几个商品化激光切割自动编程系统中发现,它们在打孔点位置的合理选取及割

嘴路径的确定方面尚存在如下问题:(1)要求人工交互设置切割路径或在图形中补加有关信息;(2)对割嘴随动功能给切割路径带来的不良影响处理不当或没有考虑,导致非切割时间增

长或易产生切割故障;(3)缺乏较好的割嘴路径优化策略与算法1国外学者已对此作过一些研究:Manber等[1]解?1995-2006 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights

reserved.决了一块板上排样多个零件在火焰切割机切割时打孔点的选取与切割顺序的优化(与激光切割类似),但没有考虑被排样的每个零件的内部又包含多个要加工的内部轮廓的

情况;Jackson等[2]考虑了内部轮廓情况且能从已有的CAD系统中自动地确定切割的路径,但需用户在图形上补加引入/引出线等信息确定打孔点,并且切割路径也并未优化;Han等[3]

考虑了排样零件在激光切割过程中切割温度对切割质量的影响,并纳入了切割路径优化的数学模型中1文献[123]皆未涉及割嘴随动功能对切割路径的影响1国内关于激光切割的自动

编程系统的论文很少有系统地研究路径优化或随动功能对切割路径的影响1在单件小批量生产中,尺寸较大且内部包含多个内轮廓特征的这类零件在实际生产中十分常见,而这类零件

只能单件加工(如纺织机械设备、收获机械设备上的钣金零件)1因此,开展这类零件打孔点的选取及割嘴路径的优化的研究,并将其补加到自动编程系统中是十分必要的1图1　钣金零

件轮廓的定义2　割嘴切割路径问题的定义211　钣金零件的几何表达及定义本文研究包含多个内轮廓特征的单个钣金零件,这类零件主要由首尾连接的直线、圆弧、圆等图元构成的

多个封闭轮廓图形组成1我们定义有向有序边首尾相连组成的封闭轮廓为环(Loop),组成环的基本元素称为边(E),边的端点称为顶点(V),环又分为内环与外环1显然,对单件钣金零件

有且只有一个外环,内环可以有多个;边可以是直线、圆弧、圆等,定义直线的顶点是直线的首尾两端点,圆弧的顶点是圆弧的起点与终点1对圆而言,定义一个顶点,这个顶点是圆上的

某一点,这点对切割过程而言既是切割的起点又是切割的终点1本文规定:外环记为Oloop,外环顶点总数记为ω,任一顶点记为O V i(i=1,2,…,ω);任一内环记为loopi,其对应的顶点

总数记为V(i),第k个内环loopk对应的第j个顶点记为Vkj(k=1,2,…,m;j=1,2,V(k)),所有内外环皆按整体逆时针方向从某一顶点开始排列构成,如图1所示1在图1中,环集loop=

{Oloop,loop1,…loopm};顶点集V={V 1,V 2,…,Vω,V 11,V 12,…,V 1 V(1),…,V ij,…,V mV(k)}1212　割嘴路径问题数学模型的建立激光切割最终的目的是要切割出所有的内环

与外环而形成工件,切割内环或外环时,首先以一个环上的某一顶点为打孔点,打穿再切割完该环1按实际切割工艺,切割顺序应遵循先内环后外环的原则,其整个切割过程是割嘴从编

程零点(即对刀点)出发,快速行进到某一内环上的打孔点,并开光打孔;再以该打孔点所在的顶点为起点切割完该有向有序的封闭环,即回到开始打孔点;然后关光快速行进到下一个内

环上的打孔点上,重复前面类似过程直到切割完所有内环;再关光快速行进到外环打孔点,开光打孔并切割外环;最后从外环打孔点关光快速返回程序零点1在图1中假定程序零点为P0,

内环loop1打孔点为V 11,loop2打孔点为V 21,loop3打孔点为V31,loop4打孔点为V41,Oloop打孔点为O V 1,则一个完整的切割路径可表示为P0快速空移V 11(开光打孔)切割V 12→V

13→V 14→V 15→V 16→V 17→V 18→V 11(关光)快速空移V 21(开光打孔)切割V 22→V 23→V 24→V 25→V 21(关光)快速空移V 31(开光打孔)切割V 32→V 33→V 34→V 35→V

31(关光)快速空移V 41(开光打孔)切割V 42→V 43→V 44→V 41(关光)快速空移O V 1(开光打孔)切割O V 2→O V 3→O V 4→O V 5→O V 6→O V 7→O V 1(关光)快速空移P01由于

封闭的内外环必须切割,因此无论从何点开始切割,内外环的长度不变,即不存在路径优化问题1这样,割嘴路径规划就是指如何安排切割顺序,使激光切割过程中快速空移的行程的时

间最短1对图1而言,就是从P0出发,如何选择V 11,V 21,V 31,V 41,O V 1及其加工顺序所构成的回路路径最短1很显然,当打孔点一定时,路径优化的问题就是最著名的旅行售货员问

题(Traveling5期刘会霞等:钣金件数控激光切割割嘴路径的优化661?1995-2006 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.Salesman Problem,TSP)1然而,

内外环上的打孔点从切割工艺上讲并不惟一,可以是环上的任一顶点,打孔点在切割路径的优化算法中应被考虑的总顶点数为外环总顶点数ω加上所有内环总顶点数∑Mk=1V(k)个1为

了给出切割路径的数学表达式,本文中把按某种方法确定的内环loopi上的打孔点记为Pi,Oloop上的打孔点记为PE1显然,Pi∈{Vi1,V i2,…,V iV(k)};PE=∈{O V 1,O V 2,…,O

Vω},并设对所有打孔点P={P0,P1,P2,…,PM,PE}的一个访问顺序为T={P0,t1,t2,tM,PE,P0},其中ti∈{P0,P1,P2,…,PM,PE},则切割路径的数学模型为min L={d(p0,t1)+∑M-1i=1d

(ti,ti+1)+d(tM,p E)+d(p E,p0)}1　　在实际切割过程中,切割路径的优化还受到Z轴随动功能的制约1 Z轴随动功能实质上是一种激光焦点自动跟踪功能,它能保证在切割过程中使

激光切割焦点始终保持在工件表面内,且与工件表面的距离恒定,从而避免了因工件变形、表面粘附物等因素影响引起焦点位置变化1 Z轴随动功能会引起下列问题:当一个环切割完

后,割嘴快速空移到下一个环打孔点的过程中,随动功能有可能导致割嘴掉入已切割的板材空洞中而造成割嘴损坏,使机床无法正常切割1如图2所示,当打孔点为ti-1,t i,t i+1时,切

割完loopi后,loopi区域内钢板会因重力下落,则割嘴由ti快速空移到ti+1,会掉入loopi形成的空洞中1而当打孔点ti改为t′i时,将不存在此问题1因为加工完loopi后,割嘴由ti-1快

速空移到t′i点,此时loopi还未加工1图2　割嘴掉入切割区域示意图3　打孔点的选择及路径优化当打孔点确定后,路径优化问题相当于一个TSP问题,此时切割路径共有M!条,如考虑

到打孔点的可变化性,切割路径将为M!×ω×∏Mi=1V(k)条1其数目是十分巨大的,即使对于如图1所示这样简单的零件,切割路径也有4!×7×8×5×4×5=134 400条1从形式上看,打

孔点选择及路径优化可被看作一个具有约束的离散变量的优化问题,然而解决这一问题十分复杂1由于TSP问题本身就属于著名的NP问题,因此若再同时考虑打孔点变化及Z轴随动功能

的影响,将使这一问题变得更加复杂1早期人们为了简化这一难题,采用固定打孔点且不考虑Z轴随动功能的影响,这显然很不合理1本文针对这一问题,提出了分级规划的三步方法:先

按改进最近邻算法合理选择打孔点;再按TSP问题进行路径优化;最后再判定空移时是否掉入空洞中,并按一定算法调整路径使之避开空洞,有效地解决了这一难题1311　打孔点的确定

打孔点确定的原则是一个内环或外环仅有一个打孔点,本文按切割工艺采用最近邻算法的一个改进算法确定打孔点1该算法充分考虑了打孔点对割嘴路径优化的影响1算法11打孔点的

确定Step11从编程零点P0出发,令Pk=P0,P={P0}1Step21遍历所有待加工内环loop={loop1,loop2,…,loopM}对应的顶点集V={V 11,V 12,…,V 1 V(1),…,V ij,…,V MV(k)}1找到距

Pk最近的顶点Pi=Vij(对应内环为loop2i),并将Pi加入到打孔点集Q中,Q=P+{Pj};令Pk=Pi,然后在loop集中删除loopi及loopi对应的顶点{Vi1,Vi2,…,ViV(i)}1Step31依次遍历所有

的未访问的内轮廓loop对应的顶点集,找到打孔点,并加入打孔点集Q中,令P=Q1Step41从Pk出发,再遍历外环上的所有顶点集{OV1,OV 2,…,OVω},找到距离最近的一个顶点即打孔点

PE,则所有打孔点P={P0,P1,P2,…,PM,PE}1注意:当环是圆时,按最近邻算法,前一个切割起点与圆上最近点即切割起点,它是前一个切割起点与该圆圆心连线与圆的交点1本文为求解

方便,把圆心定义为虚顶点,以便标识及方便求解圆上的切割起点1312　基于打孔点的路径优化对所有已知的打孔点P={P0,P1,P2,…,PM,PE},由第212节可知路径优化问题等同于著名

的TSP问题1 TSP问题是一个典型的、易于描述却难以处理的NP完全问题1人们针对TSP问题提出了662计算机辅助设计与图形学学报2004年?1995-2006 Tsinghua Tongfang Optical

Disc Co.,Ltd.All rights reserved.Salesman Problem,TSP)1然而,内外环上的打孔点从切割工艺上讲并不惟一,可以是环上的任一顶点,打孔点在切割路径的优化算法中应被考虑

的总顶点数为外环总顶点数ω加上所有内环总顶点数∑Mk=1V(k)个1为了给出切割路径的数学表达式,本文中把按某种方法确定的内环loopi上的打孔点记为Pi,Oloop上的打孔点记为

PE1显然,Pi∈{Vi1,V i2,…,V iV(k)};PE=∈{O V 1,O V 2,…,O Vω},并设对所有打孔点P={P0,P1,P2,…,PM,PE}的一个访问顺序为T={P0,t1,t2,tM,PE,P0},其中ti∈{P0,P1,P2,…

,PM,PE},则切割路径的数学模型为min L={d(p0,t1)+∑M-1i=1d(ti,ti+1)+d(tM,p E)+d(p E,p0)}1　　在实际切割过程中,切割路径的优化还受到Z轴随动功能的制约1 Z轴随动功能

实质上是一种激光焦点自动跟踪功能,它能保证在切割过程中使激光切割焦点始终保持在工件表面内,且与工件表面的距离恒定,从而避免了因工件变形、表面粘附物等因素影响引起

焦点位置变化1 Z轴随动功能会引起下列问题:当一个环切割完后,割嘴快速空移到下一个环打孔点的过程中,随动功能有可能导致割嘴掉入已切割的板材空洞中而造成割嘴损坏,使机

床无法正常切割1如图2所示,当打孔点为ti-1,t i,t i+1时,切割完loopi后,loopi区域内钢板会因重力下落,则割嘴由ti快速空移到ti+1,会掉入loopi形成的空洞中1而当打孔点ti改

为t′i时,将不存在此问题1因为加工完loopi后,割嘴由ti-1快速空移到t′i点,此时loopi还未加工1图2　割嘴掉入切割区域示意图3　打孔点的选择及路径优化当打孔点确定后,路

径优化问题相当于一个TSP问题,此时切割路径共有M!条,如考虑到打孔点的可变化性,切割路径将为M!×ω×∏Mi=1V(k)条1其数目是十分巨大的,即使对于如图1所示这样简单的零件

,切割路径也有4!×7×8×5×4×5=134 400条1从形式上看,打孔点选择及路径优化可被看作一个具有约束的离散变量的优化问题,然而解决这一问题十分复杂1由于TSP问题本身就属

于著名的NP问题,因此若再同时考虑打孔点变化及Z轴随动功能的影响,将使这一问题变得更加复杂1早期人们为了简化这一难题,采用固定打孔点且不考虑Z轴随动功能的影响,这显然

很不合理1本文针对这一问题,提出了分级规划的三步方法:先按改进最近邻算法合理选择打孔点;再按TSP问题进行路径优化;最后再判定空移时是否掉入空洞中,并按一定算法调整路

径使之避开空洞,有效地解决了这一难题1311　打孔点的确定打孔点确定的原则是一个内环或外环仅有一个打孔点,本文按切割工艺采用最近邻算法的一个改进算法确定打孔点1该算

法充分考虑了打孔点对割嘴路径优化的影响1算法11打孔点的确定Step11从编程零点P0出发,令Pk=P0,P={P0}1Step21遍历所有待加工内环loop={loop1,loop2,…,loopM}对应的顶点

集V={V 11,V 12,…,V 1 V(1),…,V ij,…,V MV(k)}1找到距Pk最近的顶点Pi=Vij(对应内环为loop2i),并将Pi加入到打孔点集Q中,Q=P+{Pj};令Pk=Pi,然后在loop集中删除loopi及

loopi对应的顶点{Vi1,Vi2,…,ViV(i)}1Step31依次遍历所有的未访问的内轮廓loop对应的顶点集,找到打孔点,并加入打孔点集Q中,令P=Q1Step41从Pk出发,再遍历外环上的所有顶

点集{OV1,OV 2,…,OVω},找到距离最近的一个顶点即打孔点PE,则所有打孔点P={P0,P1,P2,…,PM,PE}1注意:当环是圆时,按最近邻算法,前一个切割起点与圆上最近点即切割起点,

它是前一个切割起点与该圆圆心连线与圆的交点1本文为求解方便,把圆心定义为虚顶点,以便标识及方便求解圆上的切割起点1312　基于打孔点的路径优化对所有已知的打孔点P=

{P0,P1,P2,…,PM,PE},由第212节可知路径优化问题等同于著名的TSP问题1 TSP问题是一个典型的、易于描述却难以处理的NP完全问题1人们针对TSP问题提出了662计算机辅助设计

与图