过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，打孔机主要用于在制造印刷线路板流程中的打孔作业。

目前，实际采用的打孔机普遍是单钻头作业，即一个钻头进行打孔。

本问题旨在解决某类打孔机的生产效能问题。

打孔机的生产效能主要取决于：（1）单个过孔的钻孔作业时间，由生产工艺决定；（2）打孔机加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。

某种钻头装有8种刀具，8种刀具的顺序固定，不能调换。

加工作业时，一种刀具使用完毕后，可转换使用另一种刀具。

相邻两刀具的转换时间是18 s。

作业时，可顺时针旋转转换刀具，如刀具a→刀具b；也可逆时针旋转转换刀具，如刀具a→刀具h。

将任两个刀具转换，所需时间是相应转换时间的累加。

假定钻头的行进速度相同，为180 mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。

刀具行进过程中可同时转换刀具，但相应费用不减。

不同的刀具加工不同的孔型，有的只需一种刀具来完成，有的需要多种刀具及规定的加工次序来完成。

表1为10种孔型所需加工刀具及加工次序（*表示该孔型不限制加工次序）。

表1：10种孔型所需加工刀具及加工次序同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用多种刀具加工的过孔，只要保证所需刀具加工次序正确即可。

建立相应的数学模型，并完成以下问题：（1）由附件1提供的某块印刷线路板过孔中心坐标的数据，请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。

（2）为提高打孔机效能，现在设计一种双钻头的打孔机（钻头形状与单钻头相同），两钻头可以同时作业，也可一个钻头打孔，另一个钻头行进或转换刀具。

为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm的合作间距。

（i）针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？（ii）研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。

2.1 问题1分析：本问题可看作为动态规划与图论的组合问题，即求取由起始状态到终点状态的最优单向路径问题，主要是运用运筹学的排序理论、图论中的Hamilton 路径的相关理论知识解决问题。

经分析，1T —钻头的行进时间、2T —加工不同孔型的刀具的转换时间，是本题的目标规划量。

行进速度u 恒定，故目标规划量可转化为等效最短路径。

首先，由分析，异型孔中最远两点距离ij d 小于等效换刀距离ij l ，故我们建立换刀、路线分立优化原则，邻近换刀原则。

在该两个原则下，我们确定了运用工序优化算法总体优化换刀次序，同型孔中计算路径最优的问题的思路，将问题分成两部分进行求解。

其次，为解决在同型孔中求解最优路径，由优化的最邻近算法我们求解出初始的Hamilton 回路，通过二边逐次修正算法对其进行优化，而后删去虚拟点得最优单向路径。

最后，通过与最小生成树计算所得下界进行比较，对结果进行验证。

2.2 问题2分析问题二中，双钻头12,J J 对孔群进行加工的互相干扰，使本问题的时序性更突出，故不能简单使用求Hamilton 回路法，即使用动态规划的思想，该问题这也是个典型的NP-难问题，故我们将采用改进的蚁群算法进行近似求解。

我们将采取建立于蚁群算法的蚁对群算法，全局搜索出两条最短路径，以达到目标时间最短，使生产效能最高。

对于（i ），由于其他条件不变，故决定性条件仍为换刀时间1T ，对此我们沿用问题一的两个原则。

为使目标时间最小，基于两刀加工时间12,J J T T 的一致性，对总换刀次数1221,J J N N N k k +=+=+∈Z ，令1N N =+，并使两钻头换刀次数12,J J N N 尽可能相同。

在优化问题上，由于存在合作间距3cm ε≥的约束条件，问题变为在连续时间内，时刻加入两钻孔12,J J 间距离12(,)3d J J cm <的判断。

对于（ii ），将在统一模型算法下，通过改变合作间距ε，定量研究其对生产效能的影响。

在模型验证中，将所求的路径与基于最小生成树的路径做误差分析。

同时，单纯对于提高生产效能而言，与问题一结果相较，若单孔作业总时间s d T T ≈，d T 为双孔作业时间，则该模型的建立是失败的。

三、 模型假设1. 忽略钻头的形状、材料、加工工艺等因素对钻孔作业的影响，将钻头视为质点；2. 忽略所打孔的大小，将孔视为质点，以圆心坐标表示；3. 假定打孔机8种刀具单独钻孔作业时间相同；4. 假定对于同一孔型钻孔作业时间都是相同的；5. 在问题一中，假定所有孔型的钻孔作业时间相同，经查阅资料，取该时间为0.4s ；6. 在问题二的(i)中，假定合作距离为3cm 。

四、 符号说明五、 模型准备5.1 Hamilton 路径（回路）与TSP 问题1. 定义 在无向图G =<V,E >中，穿程于G 的每个节点依次且仅一次的路径称为Hamilton 路径。

穿程于G 的每个节点依次且仅一次的回路称为Hamilton 回路。

2. TSP(旅行商问题)有n 个城市12,n v v v ，其相互间距离121323,,,v v v ,为已知，求合理的路线使得每个城市都被经过一次，且总路径为最短。

TSP 的数学模型为：1..=11,2mij j s t X i n ==∑， (1)min ij ij i jd X ≠∑ (2)11,1,2miji Xj n ===∑ (3),1,22,{1,2}iji j nXs s n s n ∈≤-≤≤-⊂∑ (4){}0,1,,1,2,ij X i j n i j ∈=≠ (5)式(8)中1ij X =表示旅行商经历i j v v 的路径，0ij X =表示不经过该路径；式(5)(6)要求旅行商经过,i j v v 点有且仅有一次；(8)在任何一个城市的子集中不行成圈。

5.2 最邻近算法定理1 ,,G V E W =<>是n 个顶点的无向完全图，W 为从E 到正实数集的函数，对在V 中任意三点,,i j k v v v ，满足(,)(,)(,)W i j W j k W i k +≤ (6)则可将实际问题转化为求取赋权图上的Hamilton 回路问题。

具体算法如下：1) 在G 中取一点0v V ∈为起始点，找出一个与始点最近的点，形成一条边的初始路径。

2) 设x 表示最新加到这条路径上的点，从不在路径上的所有点中，选一个与x 最邻近的点，把连接x 与此点边加到这条路径中。

重复直至G 中的所有顶点包含在路径中 3) 把始点和最后加入的顶点之间的边放入，即得出一个回路。

5.3 蚁群算法：(1) 状态转移规则[()][()],[()][()]0,ij ik k i ij ik t t j Allowed p t t else αβαβτητη⎧∈⎪=⎨⎪⎩∑若 (7) 式中()k ij P t 一在t 时刻蚂蚁k 由元素i 转移到元素j 的概率；k Allowed ——表示蚂蚁k 下一步允许选择的城市；α——信息启发式因子，表示轨迹的相对重要性；β一期望启发式因子，表示能见度的相对重要性；()ij t η——启发函数，()1/ij ij t d η=；ij τ——残留信息量。

(2) 信息素修正规则()(1)()()ij ij ij t n t t τρττ+=+⨯+∆ (8)1()()mij ij k t t ττ=∆=∆∑ (9),()0,k ij Qk i,j L t else τ⎧⎪∆=⎨⎪⎩若只在本次循环中（）式中,ρ——信息素挥发系数；()ij t τ∆一表示第k 只蚂蚁在本次循环中留在路径(),i j 上的信息量；Q ——信息素强度，设为常数；k L ——第后只蚂蚁在本次循环中所走过的路径的长度。

(3) 禁忌表k tabu 的修改和表Allowed 蚂蚁数后有一个表k tabu 和表Allowed 。

初始时可以把tabu 中的元素都设为0，把的元素都设为l 。

如果蚂蚁第1次选择了城市j ，则把tabu 表中第1元素赋值为j ，并把表Allowed 总第1j -个元素赋值为0，表示此城市已经走过。

算法实现步骤如下：(1) 参数初始化。

令循环次数0c N =，将m 只蚂蚁随机放在n 个元素(城市)上，(),(0)0;ij ij t const ττ==；(2) 循环次数1c c N N =+ (3) 蚂蚁数1k k =+；(4) 对第k 只蚂蚁，根据公式(1)选择城市j ，并前进；(5) 把选择的城市加入到第屉只蚂蚁的表tabu 中，并修改表Allowed ；(6) 对于第k 只蚂蚁若没有游历完所有m 个城市，则转到第4步，若游历完所有城市，则执行第7步；(7) 若蚂蚁数k 小于蚂蚁总数n ，则转到第3步，直到n 只蚂蚁都游历完m 个城市，再执行第8步；(8) 根据式(2)、式(3)更新每条路上的信息量，并找出n 只蚂蚁中，所走的最短路径的值，并保存；(9) 若循环次数未达到最大循环次数，则转到第2步，若满足结束条件则结束循环，并输出计算结果。

5.4 数据处理1. 将10种孔型按所需刀具重新编号H h ，其中,h H 分别代表8种刀具、10种孔型中某一种，故得18类孔（共2814个）如下表。

表格 1 18种新孔分类列表原孔 A B C DEFGHI J 新孔a Ab Ba Cc C*dD *e Dc Ef E*g F*h Fd Gg G f Gh He Ic If Jc J另外，为叙述简便，将新的18种孔型做统一再命名，对应表格如下表格 2 18种新孔识记表新孔a Ab B a Cc C *d D *e D c Ef E *g F *h F d Gg G f Gh H e I c I f Jc J标记 1V 2V 3V 4V 5V 6V 7V 8V 9V 10V 11V 12V 13V 14V 15V 16V 17V 18V同时我们作出了相应的18种新孔的刀具分布情况，如下图。

图 1 18种新型孔的刀具分布情况2. 由公式d ut =，将题目中缩短行进、换刀时间问题，转化为求解最短距离问题。

(1) 首先，将5.3数据处理中所得到的2814个点，12,m v v v ，记作赋权图,G V E <>中点集V ，其中2814m =。

(2) 针对上步中的2814个点，依次求出两点间最短距离ij s ； (3) 不同的孔型需换刀具，两点间的换刀等效距离ij r l t u =⨯ (10)其中18r ij t n =⨯ (11)为两刀具之间所需的换刀时间，ij n 为点i v 与点j v 换刀次数。

六、 模型的建立与求解6.1 两个原则下的单向Hamilton 路径的图论模型6.1.1模型建立6.1.1.1 基于TSP(旅行商问题)的最短路程模型： 1. 最短等效路径：1) 刀具行进路径：从先前位置移动到当前位置的成本。