3.4 操控工业机械

在现代制造业中，像钻孔、装配这样的重复性工作常常由机械设备完成。以此为背景产生了很多TSP应用题。

3.4.1 印制电路板钻孔

常见电子设备中都含有印制电路板（printed circuit board，又称印刷电路板，简称PCB）。印制电路板上面经常有大量小孔，用来装载计算机芯片或者导通各层之间的电气连接。制作过程中，自动钻孔机在特定位置之间移动，从而依次打出这些小孔，找出钻头总移动时间最短的路线就是TSP的一大经典应用。Gerhard Reinelt的TSPLIB是旅行商问题的实验数据库，收集的案例中包括一些电路板钻孔类的题目，其中一道题对应的印制电路板如图3-7所示。

图3-7　有411个孔的印制电路板（Martin Grötschel供图）

应用TSP算法可以使电路板生产线的总生产量提高10%左右。¹这一类TSP题目的规模一般为几百至几千座城市。

_{1. Grötschel, M., M. Jünger, G. Reinelt. 1991. Zeit. Op. Res. 35, 61–84.}

3.4.2 印制电路板焊锡

德国电子工程师Wladimir Nickel在文章中介绍说，他在电路板焊锡步骤中借助了Concorde程序。 焊锡（solder）是印制电路板生产过程的一步后续处理，目的是把贴片元件焊接到电路板表面。Nickel使用一台装有锡膏点胶机的数控（计算机数字控制，简称CNC）机械，将锡膏涂布于电路板表面的特定位置。图3-8展示了他使用的数控机械。照片上他制作的电路板有256处位点需要点涂锡膏。Concorde程序帮他解出了这道TSP题目的最优路线，也就提供了点胶机走完所有位点的最快方式。

图3-8　印制电路板涂布锡膏（Wladimir Nickel供图）

3.4.3 黄铜雕刻

人们使用黄铜冲压模具制作浮雕图案，比如巧克力包装盒上凸起的装饰图。黄铜模具以前都是手工制作的，但现在一般由重型数控铣床铣削雕刻而成。数控铣床刻完一个字母或者其他设计元素之后，主轴升高，铣头移动，准备刻下一个字母或设计元素。由于每个设计元素都不只是单个小点，因此铣头移动到整个元素上方的任意一点都可以，这就引入了灵活变通的可能。2008年，数控雕刻师Bartosz Wucke写道，如果模具图案有大量字母或者是大量点纹组成的抽象图案，则应用TSP模型可以使加工时间减半。

3.4.4 定制计算机芯片

20世纪80年代中期，在贝尔实验室的研究工作中，涌现出了类似的TSP应用，不过这次的空间尺度要小得多。贝尔实验室的研究人员发展了一种快速生产定制计算机芯片的技术。生产原料是一块原始的芯片，一些称为逻辑门（logic gate）的简单组件在芯片上形成了网络。然后研究人员用激光切割网络中的部分位点，把这些逻辑门组件划分成各组逻辑门电路，分别实现指定的芯片功能。这里需要引领激光经过各切割位点，也就转化成为TSP题目。Johnson提出了更快的TSP启发式算法，使一般情况下的激光定向时间降低到原来的一半以下，实现了生产过程的大提速。

这项应用同样在TSP光荣榜上占有一席之地，因为创纪录的85 900座城市的TSP（见图1-7）就来源于此。

3.4.5 清理硅晶片缺陷

在激光切割步骤之前，计算机芯片生产过程中还会出现另一种TSP应用。硅晶片形状为圆形，面积比较大，由硅组成，而且必须不含任何杂质。设计的标准芯片要蚀刻到硅晶片上。纳米制造技术企业美国应用材料公司（Applied Materials）有一项清理硅晶片缺陷的技术。为了操控机器在各个缺陷之间移动，他们也用到了Concorde程序。