TSP改进算法及在PCB数控加工刀具轨迹中的应用
2004年 12月
第 27卷第 12期
重庆大学学报(自然科学版)
Journal of Chongqing University(Natural Science Edition)
Dec．2Oo4
Vo1．27 No．12
文章编号 ：1000—582X(2004)12—0017—03
TSP改进算法及在 PCB数控加工刀具轨迹中的应用
王 英 章 ，李 坚，徐 宗 俊
(重庆大学 机械工程 学院，重庆 400030)
摘 要：电子信息产业的迅猛发展给电子制造技术带来严峻挑战和剧烈的市场竞争。针对电子元
器件 最基础 部件—— 印制 电路 板的孔 位加 工所急 需解 决的效 率 问题 ，提 出了一种 印制 电路 板 焊盘 (孔
位)加工刀具轨迹优化技术，即一种面向工程应用的综合应用贪婪算法和蚁群算法进行问题求解的方
法，以解决由于孔 多、空行程现象严重而带来的加工时间浪 费问题。实际应用效果较好 ，提高加工效率
23．9％ ，取得 了较好 的经济效益 。
关键词：数控加工； P；贪婪算法；蚁群算法；PCB
中图分类号 ：TP391 文献标识码 ：A
印刷电路板(PCB)数控钻铣床是电子信息产业必
不可少的数控加工工艺装备 ，主要用于印制电路板精
密孔位的高速加工。在加工过程 中，刀具 的移动顺序
对加工效率的影响很大。因此 ，在将 CAD数据传递给
机床之前 ，需 要对其 进行 预处理 ，以确定 最佳加 工
顺序。
针对 PCB数控钻铣床进行钻铣加工 时后置处理
软件的实际需要，作者重点研究 了面向工程应用的海
量 焊盘钻孔轨 迹的优化处理技术 。
1 PCB焊盘加工的数学模型
PCB板作为电子元器件 的安装母板 ，在焊装元件
时，需要在 PCB板的对应位置上钻 出焊装用的孔 (又
称焊盘)。一般来说，根据安装元件的数量和种类 的
不 同，PCB板上的焊盘数量和焊盘大小差别较大，从
数量上讲 ，一块复杂的 PCB板上 ，同一尺寸的焊盘可
能有成千上万个。当利用数控钻铣床进行焊盘的加工
时，理想的加工过程如下 ：对某一类给定尺寸的焊盘，
换上对应的刀具后，从下刀点开始 ，沿着使该刀具总的
空行程最短的轨迹，从一个焊盘移动到另一焊盘 ，直到
该类焊盘中的所有对象都被加工完毕 ，再进行下一尺
寸焊盘的加工，如此循环，如图 1所示。
该问题可描述如下 ：
设有 1个换刀点和 n个焊盘，H={ ， ， ，?，
4
图 1 焊 盘加 工过 程
Hn}；已知其中任意两焊盘问的距离 d(Hi，巧)=d(i，
)，0≤ ≤Ⅳ且 ≠ ；现要求得到一个焊盘的排列 R：
Jv
{ ，尺，，R ，?，尺几}；使得min ∑ d(Ri， )，s．t R。
= 为换刀点的位置。
2 TSP问题及改进的贪婪算法
从该问题的处理过程来看 ，这是一个典型的 TSP
问题 ，在这里，钻头充当了旅行商的角色，同孔径的焊
盘充 当着城市 的角色 ，目标为加工过程 中的空行 程
最短 ¨。
P问题是实际应用中出现的复杂问题的集中概
括和简化形式 ，是一个概念简单但求解复杂的问题 ，求
· 收稿 日期：2004—08—12
基金项 目：重庆大学基础及应用基础研究基金(2oo3—27) ．
作者简介：王英章(1969一)，男 ，重庆大学机械工程学院博士研究生，主要研究方向为数控机械加工装备的设计与制造。
维普资讯 http://www.cqvip.com
18 重庆大学学报 (自然科 学版) 2004生
解的任务就是安排一次完整的旅行 ，使得总费用最小，
求解的过程也是一个搜索的过程 ，n个城市的 TSP问
题的搜索空间是 n个城市的所有排列 的集合 ，大小为
n!。TSP问题是一个 NP完备问题 ，一个 1O个城市的
TSP有大约 18 000个可能的解，因此 ，要得到 1O城市
TSP问题 的最短路径 ，最坏的可能是要做 18 000次搜
索 ；而 2O城市 TsP问题 ，最坏可能要做 1O 次搜索 ；
5O个城市 TSP问题 的搜索次数更是一个天文数字。
在 PCB板焊盘数控3H-v过程中，要处理的焊盘可能有
成千上万个 ，因此 ，要 以有限的时空复杂度得到焊盘加
工的最优轨迹实际上不可能实现 ，在工程应用中，大多
采用近似的的方式进行处理。TSP可用的近似解法主
要有 ：近邻法、贪婪法 、最近／最远插人法、启发式方法、
神经 网络法等 。
求解 TSP问题 的最直观的贪婪算法是基于最近
领域的启发式方法 ：随机从某个城市出发，前往最近的
未被访问的城市 ，一直到所有的城市都被访 问过并仅
被访问一次 ，最后返回初始城市 ，这样的路径很难做到
完美 ，通常要为在起始阶段的贪婪的选择付出很大的
代价。图2为一焊盘加工的直接贪婪算法 的运行 结
果 ，从图中可以看出，直接贪婪算法导致的结果是焊盘
加工过程 中的长的空行 程 的出现 。
。 。
。 。 。
。
。
。 o o
o
●
●
o 6 々 o o o
o
o
。 。 。 ：。 。 。
。 。 ● 。 。
。 。
●
● 。 。 口
。 々 口
6 o 0 o
岛 。 。 。
。
。
· o o 。
● ● 0 o o 0
图 2 焊盘加工的直接贪婪算法
为此，提出了一种改进的贪婪算法：
STEPI：建立4个数组(CArray)U、V、W、Z；
STEP2：U={l，2，?，nl，V={0}，W= ，Z= ；
STEP3：len=LENGTH( )；dist=minDIST(i，i)
where：i E U且 i W，J= (1en—1)；
ADD(I， )，DELETE(I， )；
STEP4：size=LENGTH( )，IF(size<6)，转
STEP3；
STEP5：调用蚁群算法得 +V(1en一1)的最优
解 ，将顶点序列存人数组 z中；
STEP6：length=LE NGTH(Z)；k=0，while(k<
length){ADD(Z(k)，V)；DELETE (z(k)，U)；k+
+；}；W= ，Z= ；
STEP7：IF(U= )，结束 ，否则，转 STEP3；
最后得到的数组 中的焊盘序列 即为数控钻铣
床进行焊盘3n-r的近似解。
3 改进算法的程序实现
3．1 蚁群算法原理
蚁群算法是一种新型的模拟进化算法。该算法由
意大利学者 M．Dorigo、V．Maniezzo、A．Colorini等首先
提 出，称 之 为 蚁 群 系 统 (Ant Colony System，简 称
ACS)，并应用该算法求解 P问题 、分配问题 、job—
shop调度问题 ，取得了较好的结果 】。
人工蚁群算法是受到对真实蚁群行为研究的启发
而提出的。蚂蚁在运动过程 中，能够在它所经过的路
径上留下一种称之为外激素(pheromone)的物质进行
信息传递 ，而且蚂蚁在运动过程中能够感知这种物质，
并以此指导 自己的运动方向，因此由大量蚂蚁组成的
蚁群集体行为便表现出一种信息正反馈现象 ：某一路
径上走过的蚂蚁越多，则后来者选择该路径 的概率就
越大 。
3．2 蚁群算法
1)状态转移规则
P ( )表示蚂蚁 由城市 i转移到城市 的转移
概率 。J：
p c ={ √，s隹tabu c )
r (t)为 t时刻在路径 上的信息素量，叩 为城市 间
距离的倒数，tabu( )用以记录蚂蚁 当前所走过的城
市 ，s为下一转移城市， ， 为系数；
2)信息素修正规则
r (t+n)=pr (t)+ar
△r =∑△7- ( )
‘ l
△ ( )：J-- q-,若蚂蚁 走过路径 l
l0
．
else J
Q为常数 ， 为第 只蚂蚁在本次循环 中所走过 的路
径的长度。
维普资讯 http://www.cqvip.com
第 27卷第 12期 王英章 等 ： TSP改进算法及在 PCB数控加工刀具轨迹 中的应用 19
算法的实现流程如图3所示。
l l初始化投组： J I
u ． v． w ， z
】 f
’
寻找致组u中与致组v最末尾
的元素更高最小的结点 m-井
将 m加入敷组 w 中
对敷组 w 中前蛄点调用分支
定界法求最优解．并将有序结
点加入致组 z中
将z中的元素囊序加入致虹V
中．井依次从 U 中删除对应
的蜡点z清空投组 w
I
敷缉 V 中的有序结点为
该问矗的近仁【解
(a)总的流程； (b)蚁群算法流程
图 3 算法实现流程
4 应用实例
某公司是一家长期致力于印制电路板数控工艺装
备研发的企业，改变了我 国在印制板加工设备领域中
长期依赖进口的局面。随着世界和我国电子信息制造
业的蓬勃发展，市场给印制电路板加工工艺装备提出
了更高的要求，其加工的速度和精度已成为数控钻铣
床的生存和发展的主题。数控加工刀具轨迹的优化处
理已成为制约印制电路板海量孔位加工生产效率的瓶
颈环节 。
实例平台：windows2 000研祥工控系统 ；
自主开发的 MT全闭环控制系统 ；
13本松下 A系列驱动系统 ；
台达变频 器 ；
德国上银导轨及 13本 THK丝杠传动系；
WESTWIND主轴系统(转速 100 kprm／min，
可调 )；
x、Y、z向运动速度 40 m／min(可调)；
定位精度 0．005 mm；
下钻频率 300 i~．／min；
加工对象：材料 ：覆铜板
孔数：11 768个；
孔径数：9种( ．25__4 mm)；
表 1 实 验数 据分 析
从实验数据(见表 1)可 以看 出，优化处理后 的路
径明显得到改善 ，提高实际加工效率 23．9％。若是在
大批量、单件孔 数特别多 的情况 下，改进 效 果更 加
明显 。
5 结 论
作者面向工程应用提 出了一种算 法，用 以解决
PCB数控焊盘加工时的轨迹优化问题 ，该算法综合应
用贪婪算法和蚁群算法，实际应用效果较好 ，加工效率
提高 23．9％；但 由于考虑到生产的实际问题 ，这一算
法所得到的结果只是近似的，尚需进一步提高算法的
效率和性能，用以解决海量焊盘加工的轨迹优化问题。
参考文献：
『1] ZBIGNIEW MICHALEWICA，DAVID B FOGEL著．如何求
解问题 一现代启发方法 [M]．北 京 ：中国水利水 电出版
社 ，2003．
[2] 梁吉元．CAM系统中孔加工路径的优化处理 [J]．计算
机集成制造系统 ，20OO，6(2)：3—5．
(下转第 23页)
维普资讯 http://www.cqvip.com
TSP改进算法及在PCB数控加工刀具轨迹中的应用.pdf
