数学模型 打孔机效率提高 - 图文

福建农林大学计算机与信息学院

（数学类课程）

课程论文报告

课程名称： 课程论文题目： 姓 名：

系： 专 业： 年 级： 学 号： 指导教师： 职 称：

数学模型 打孔机生产效能的提高

2013年 1月7日

福建农林大学计算机与信息学院数学类课程

课程论文结果评定

评定内容 工作态度 论文格式 评定指标 工作努力，遵守纪律；工作作风严谨务实；按期完成规定的任务 格式规范、结构合理、内容完整 假设合理；模型正确；求解准确；表述清晰。立论正确，论述充分，结论严谨合理；实验正确，分析处理科学；文字通顺，技论文质量 术用语准确，符号统一，编号齐全，书写工整规范，图表完备、整洁、正确；论文结果有应用价值； 工作创新 工作量与工作难度 成绩： 指导教师签字： 任务下达日期：2012年12月12日 评定日期：2013年1月15日 工作中有创新意识、有见解；对前人工作有改进或突破，或有独特见解； 工作量饱满，工作难度大 0.1 0.1 0.6 评分权值 0.1 0.1 评定成绩

目录

摘要 ...................................................................... 1 关键词 .................................................................... 1 1 问题重述 ................................................................ 2 2 问题分析 ................................................................ 2 3 模型假设 ................................................................ 3 4 模型准备（模拟退火算法简介） ............................................ 3 5 模型的建立与求解 ........................................................ 4

5.1 模型建立 .......................................................... 4 5.2 模型求解 .......................................................... 6 6 模型分析与评价 ......................................................... 12 参考文献 ................................................................. 13 附录A 单转头优化路线图（部分） ......................................... 14 附录B MATLAB程序代码（部分） ........................................... 16

打孔机生产效能的提高

摘要

过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。因此打孔机效能的提高是降低制板费用的重要途径之一。本文旨通过建立数学模型，实现刀具转换最优顺序的前提下，运用模拟退火算法找到最优线路，及最短距离。使作业成本和行进时间达到最低，以此减少打孔机总打孔成本。

针对单转头的作业方式，先根据刀具转换的约束和孔型的约束，用穷举法得到刀具最优转换顺序，即d-c-b-a-h-g-f-e-d-c，再根据刀具装换方案确定打孔方案，即将孔分成9类，即{D,G}、{E}、{B}、{A,C}、{F,H}、{F,C}、{E,G,F}、{D,I}和{C,I,J}，同一类孔在同一时间段内用同一种刀具进行打孔，没有先后顺序的约束，因此我们对每一类孔都用模拟退火算法进行搜索最优路线，进而得到问题的优化解。经计算得到的结果是：采用单转头加工方式作业成本为95694元，行进时间2小时22分钟。

针对双转头的作业方式，由于两个钻头独立工作，两个钻头可以同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。但为了避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm。所以我们就将线路板根据孔数平均分成两个区域（一个转头负责打一块区域的孔），然后再对每一区域里的孔采用单转头打孔方式找出的优化路线即可得到问题的一个优化解；再验证该解是否符合要求（即是否符合任何时刻两钻头间距都不小于3cm），如果不符合，就再求解（由于模拟退火算法求出的是近似解，所以每次求出的解基本都会不一样），再验证，再求解，再验证??直到找到符合的解为止。经计算得到的结果是：采用双转头加工方式作业成本为98239元，行进时间1小时24分钟，相对于单转头打孔机，效能提高40%左右。

针对打孔机的两钻头合作间距对作业路线和生产效能产生的影响，本文考虑到合作间距太大会影响作业路线；合作间距太小，两转头工作时可能会产生相互影响。因此合作间距控制不合理会浪费资源，降低产品加工质量，进而影响到生产效能。所以，要提高生产效能就得设置一个合理的合作间距。

关键词：穷举法；模拟退火算法；TSP问题

1

1 问题重述

过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，其加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。由于打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间；（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。而目前实际采用的打孔机普遍是单钻头作业。现有某种钻头，上面装有8种刀具a，b，c，… , h，依次排列呈圆环状，而且8种刀具的顺序固定，不能调换。在加工作业时，刀具可以转换，相邻两刀具的转换时间是18 s。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加。为了简化问题，假定钻头的行进速度是相同的，为180 mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。刀具在行进过程中可以同时进行刀具转换，但相应费用不减。

现有一种线路板，给定上面孔型所需的加工刀具和刀具加工次序。一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。

请建立相应的数学模型，根据附件给的数据（单位：密尔），完成以下问题： （1）请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。

（2）为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。

（i）给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？

（ii）研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。 2 问题分析

本题是一题优化问题，目标是总费用最少和总时间最少。 1、针对问题一：考虑到：

?总费用?刀具转换费用?刀具行进成本??刀具转换费用?7元/min?1min/60s?18s/次?转换次数?刀具行进成本?0.06元/mm?行进总路程? （2-1）

所以想要总费用最少，就得使刀具转换次数最少和行进总路程最少。 约束条件是：

刀具的转换顺序固定；不同的孔需要不同的刀具。

因此我们先根据不同的孔需要不同的刀具，以刀具转换总次数为目标，先得到刀具的转换方案；

再根据刀具装换方案确定打孔方案，即将孔根据刀具转换方案进行分类，同一类孔在同一时间段内用同一种刀具进行打孔，没有先后顺序的约束，因此我们对每一类孔都

2

用模拟退火算法进行搜索最优路线，进而得到问题的一个解。

2、针对问题二：考虑到双转头，我们就将线路板根据孔横向平均分成两部分，即作一条竖线L1，使两边的孔数差值的绝对值小于或等于1，此时L1称平分分界线。再以1.5cm为距离，在L1两边做平行线L2和L3，若L2、L3之间没有孔，则称L1为最优分界线。若L1不是最优分界线，则适当移动L1使其变成最优分界线。若线路板不存在最优分界线，则以平分分界线L1为界线，将线路板分成两部分，分别用两个转头进行打孔，再利用问题一的方法求出每一部分的优化路线即可得到问题的一个解；再验证L2和L3之间的孔是否符合要求，如果不符合，就再求解（由于模拟退火算法求出的是近似解，所以每次求出的解基本都会不一样），再验证，再求解，再验证??直到找到符合的解为止。而本题给的数据经过计算发现存在最优分界线L1，所以就以L1为界线，将线路板分成两部分，分别用两个转头进行打孔，这样两转头之间的距离在任何时刻都会大于3cm。再利用问题一的方法求出每一部分的优化路线即可得到问题的解。 3 模型假设

1、假设单孔转孔时间都是相同的； 2、假设转头的行进速度是匀速的； 3、假设所有的孔都是一个点； 4 模型准备（模拟退火算法简介）

4.1、模拟退火算法原理：

模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。根据Metropolis规律，如果用粒子的能量定义材料的状态，假设材料在状态i之下的能量为E(i)，那么材料在温度T时从状态i进入状态j就遵循如下规律：

a、如果E(j)?E(i)，接受该状态被转换。

b、如果E(j)?E(i)，则状态转换以如下概率被接受：

E(i)?E(j)eKT （4-1）

其中K是物理学中的波尔兹曼常数，T是材料温度。

用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

3

4.2、模拟退火算法解决TSP问题模型：

TSP问题，即旅行商问题。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。模拟退火算法描述如下：

a、解空间：解空间S可表示为{1,2,?,N}的所有固定的起点和终点的循环排列集合，即：

S?{(?1?2…?N)|(?1?2…?N)为{1,2…N}的一个排列}

（4-2）

其中每一个循环排列表示一种行走方案，?i?j表示第i次到达j城市。 b、目标函数：目标函数为经过所有城市的总路程或称代价函数，我们要求：

minf(?1,?2,…,?N)??d?ii,?i?1 （4-3）

而迭代有下面3步构成：

c、新解的产生(2变换法)：任取序号u，v（u

?1…?u?1?v?v?1…?u?1?u?v?1…?N

（4-4）

d、代价函数差：

?f?(d?u?1,?v?d?u,?v?1)?(d?u?1,?u?d?v,?v?1)

（4-5）

e、接受准则：

?1?p????fT??e?f?0

?f?0 （4-6）

如果?f?0，则接受新的路径；否则，以概率e??fT接受新的路径，即若e??fT大于0

到1的随机数则接受。

f、降温：利用降温系数?进行降温，即：T?T?得到新的温度，一般取??0.999。

g、结束条件：用选定的终止温度e(一般取e?10?30)，判断退火过程是否结束。若

T?e，算法结束，输出当前状态。

5 模型的建立与求解 5.1 模型建立

目标函数：

minZ?Z1?Z24

（5-1）

?Z1?k1n ??Z2?k2S （5-2）

其中：Z表示总成本；Z1表示刀具转换总成本；Z2表示转头行进总成本；n为刀具转换总次数；S为转头行进总路程；k1为刀具转换单位次的成本；k2为转头行进单位路程的成本。

所以现在就是要计算n的最少值和S的最少值：即minn和minS。 对于minn，可以这样考虑：

从序列{a,b,?,g,h,a,b,?,g,h,a,b,?}（刀具的转换顺序，也可以全部逆序）中取出一连续子列（刀具的一种转换方案），再任取一种孔型，得到其所需加工刀具的加工次序

(u0,v0)，则子列中至少有一对元素（子列中的两个元素组成有序对(u,v)）的次序与加

工次序(u0,v0)相同（该转换方案可行），则这个子列的元素个数减1就为n。使得n达到最小的子列以下就称最优子列。

用MATLAB进行穷举得到这个最优子列为{d,c,b,a,h,g,f,e,d,c}，有10个元素，所以最少转换次数n=9。得到转换方案及对应打孔的孔型如图2

图2 刀具转换方案及对应加工的孔型

根据刀具的转换方案我们将孔型分成9类即{D,G}，{E}，{B}，{A,C}，{F,H}，{F,C}，{E,G,F}，{D,I}，{C,I,J}。每一类型里面的孔在大的时候是没有分先后顺序的，如{D,G}这一类型中，D孔和G孔打得顺序是无约束的，可以先打D孔也可以先打G孔还可以打了一个D孔再打一个G孔再打一个D孔。

对于minS，可以这样考虑：

98kminS??Sk?1??d

kk?1 （5-3）

NkNk??Sk???di,jei,ji?1j?1,j?i??22s.t?di,j?(xi?xj)?(yi?yj) ?e?{0,1}?i,j?{e}?i,jNk?Nk是使Nk个点能连成一条线 （5-4）

5

其中：Sk表示第k类孔的在给定的一种路线下转头的行进的路程；di,j表示i孔到j

{ei,j}N孔的距离；ei,j?1表示否则不是在最优路线上；（i点?j点）在最优路线上，

k?Nk是

使Nk个点能连成一条线；dk是对于第k类孔的一种优化路径下和第k+1类孔的一种优化路径下，第k类孔的最后一个点到第k+1类孔的第一个点的距离。 5.2 模型求解

5.2.1问题一求解

对于问题一单钻头加工方式，钻孔方式上采用一种刀具钻完对应的全部孔再转换刀具进行下一种刀具对其对应孔型的钻取方式，刀具转换方案考虑到转头的个数不是很多，所以用穷举法，而转头行进路线则用模拟退火算法，通过MATLAB进行数据处理和模型求解。求解步骤：

1、先对数据进行处理，即将各种孔型的坐标分别整理出来；

2、根据模拟退火算法编写相应程序，程序要求是只要给出起始点和各点坐标，就能得到通过这些点的最优路线，和对应的总路程；

3、打印出第一类孔（D孔和G孔）的分布图如图3根据分布图可以看出右上角有一个点与其他点距离较大，所以我们就选这个点为起点（起点选择原则一般就是与其他孔相聚较远的优先考虑，也可以莫测一下可能的最优路线，再根据得到的路线选择起点），我们用MATLAB的图形工具得到其坐标为（3.122e+5,8.982e+5）如图4

图3 D孔和G孔的分布图

6

图4 用MATLAB的图形工具得到右上角的点的坐标

4、运用模拟退火算法得到优化路线如图5

图5 D孔和G孔的优化路线

7

5、考虑到打完最后一个点之后就要进行刀具切换，相邻刀具的转换时间是18s，在这18s内，转头可以行进180mm/s*18s=3240mm，所以下一类孔的起点如果考虑这个范围内，那么时间成本有很大的可能会降低，所以我们就以本类中的最后一个点为圆心，3240mm为半径，画出对应的圆，再把下一类孔的分布图也画出来，然后根据下一类点的分布情况选择起点，尽量考虑在刚才画的圆内，如图6，我们选择(-7.06e+4,4.91e+4)为第二类孔（E孔）的起点。

图6 D孔和G孔优化路线、E孔的分布图及其优化路线的起始点

6、以此类推，将9类孔的优化路线都找出来（具体优化路线见附录），得到的结果绘制成表格（表2）如下：

表2 单转头9类孔对应优化路线的相关信息

刀具种类 d c b a h

加工孔型 DG E B AC FH

最短路程 单位：mm 1.4428e+005 9.5507e+004 2.8660e+005 3.2722e+005 6.6242e+004

起点坐标 单位：mil

(3.122e+005,8.982e+005) (-7.060e+004,4.910e+004) (9.230e+004,8.163e+005) (-9.320e+004,3.264e+005) (8.150e+004,6.070e+004)

终点坐标 单位：mil

(-1.3081e+003, 1.1201e+003) (2.6467e+003, 1.9522e+004) (-1.9355e+003, 8.0213e+003) (2.2555e+003, 4.3993e+003) (2.3444e+003, 2.1262e+004)

8

续表2 单转头9类孔对应优化路线的相关信息

刀具种类 g f e d c

加工孔型 FG EGJ DI 无 CIJ

最短路程 单位：mm 6.1049e+004 1.6314e+005 1.3777e+005

无 2.1903e+005

起点坐标 单位：mil (2.13e+005,8.926e+005) (-3.013e+005,-1.92e+004) (1.690e+005,4.170e+005)

无

(2.359e+005,6.274e+005)

终点坐标 单位：mil

(-7.6530e+003, -487.6800) (4.6582e+003, 6.4890e+003) (6.1112e+003, 1.6822e+004)

无

(-7.3406e+003, 1.7714e+004)

单转头加工方式结果分析：

刀具转换总时间：T?18s/次?9次=162s

刀具转换总成本：Z1?162s?1min/60s?7元/min=18.9元 刀具在各类孔中行进的路程和：?Sk?1.5031?106mm 各类切换路程和：?dk?9.1434?104mm 行进总路程为：S??Sk??dk?1.5946?106mm 行进总成本：Z2?0.06元/mm?S?95675元 总成本：Z?Z1?Z2?95694元

总时间：(?Sk)/180mm/s?T?8.5128?103s?2h22min

5.2.2问题二求解

对于问题二双转头加工方式，我们要先找最优分界线，即在线路板中找到一宽度为3cm的区域，使孔数关于该区域平分且区域内没有孔，则该区域的中线就是最优分界线，再进行求解，具体步骤为：

1、我们先计算总数为2124个；

2、再将孔的横坐标进行排序，得到第1062个和第1063个的横坐标，取其中点横坐标x0，则直线x?x0就是平分分界线，经验证，该直线也是最优分界线，所以就以直线x?x0为分界线，将孔平均分成两部分；

3、每一部分分别用问题一的方法进行求解，即得到问题的解。（加工右边的那个转头编号为1，加工左边的编号为2）求解过程与问题一相似，这里就不再重述了，将得到的结果绘制成表格（表3和表4）如下：

9

表3 双转头转头1加工9类孔对应优化路线的相关信息

刀具种类 d c b a h g f e d c

加工孔型 DG E B AC FH FG EGJ DI 无 CIJ

最短路程 单位：mm 0.7191e+005 0.6838e+005 1.2195e+005 1.8383e+005 0.4481e+005 0.4433e+005 1.1653e+005 0.8351e+005

无 1.4330e+005

起点坐标 单位：mil

(3.122e+005,8.982e+005) (-2.240e+004,4.910e+004) (9.230e+004,8.163e+005) (3.294e+005,-6.52e+004) (0.498e+005,7.569e+005) (1.650e+005,6.130e+004) (1.020e+004,8.000e+005) (1.690e+005,4.170e+005)

无

(-2.780e+004,1.633e+005)

终点坐标 单位：mil (53200,60800) (104200,768600) (278400,5000) (3400,730000) (165000,61300) (173000,8926000) (130600,301400) (22400,54000)

无 (22400,54000)

双转头加工方式转头1结果分析： 刀具转换总时间：Tr?18s/次?9次=162s

刀具转换总成本：Zr1?162s?1min/60s?7元/min=18.9元 刀具在各类孔中行进的路程和：?Sk?8.7856?105mm 各类切换路程和：?dk?1.7664?104mm

行进总路程为：Sr??Sk??dk?8.9622?105mm 行进总成本： Zr2?0.06元/mm?Sr?53773元 总成本：Zr?Zr1?Zr2?53792元

总时间：Tr?(?Sk)/180mm/s?T1?5.0429?103s?1h24min

表4 双转头转头2加工9类孔对应优化路线的相关信息

刀具种类 d c

加工孔型 DG E

最短路程 单位：mm 0.6362e+005 0.4369e+005

起点坐标 单位：mil

(-4.150e+004,4.410e+004) (-2.832e+005,2.886e+005)

10

终点坐标 单位：mil (-257400,168770) (-271900,416500)

续表4 双转头转头2加工9类孔对应优化路线的相关信息

刀具种类 b a h g f e d c

加工孔型 B AC FH FG EGJ DI 无 CIJ

最短路程 单位：mm 1.3949e+005 1.2324e+005 0.1293e+005 0.0878e+005 0.6211e+005 0.5645e+005

无 1.0582e+005

起点坐标 单位：mil

(-2.892e+005,4.340e+005) (-3.098e+005,9.080e+005) (-3.194e+005,4.565e+005) (-3.113e+005,-5.240e+004) (-3.013e+005,6.430e+004) (-2.660e+005,8.690e+005)

无

(-2.960e+005,1.934e+005)

终点坐标 单位：mil (-261000,746400) (-142200,274600) (-311300,-52400) (-301300,64300) (-48400,723800) (-257400,184518)

无

(-257400,184518)

双转头加工方式转头2结果分析： 刀具转换总时间：Tl?18s/次?9次=162s

刀具转换总成本：Zl1?162s?1min/60s?7元/min=18.9元 刀具在各类孔中行进的路程和：?Sk?6.1613?105mm 各类切换路程和：?dk?1.2465?105mm

行进总路程为：Sl??Sk??dk?7.4078?105mm 行进总成本：Zl2?0.06元/mm?Sl?44447元 总成本：Zl?Zl1?Zl2?44466元

总时间：Tl?(?Sk)/180mm/s?Tl?3.5849?103s?1h 双转头加工方式结果分析： 总成本：Z?Zr?Zl?98239元 总时间：T?max(Tr，Tl)?1h24min 两种作业方式比较见表5。

11

表5 两种加工方式成本比较

效能提高 (以单转头为基准)

总成本 总时间

95694元 2h22min

98239元 1h24min

-2.66% +40.85%

加工方式 单转头 双转头

从表五可以看出，采用双转头加工方式虽然成本上有增加，但增加很少，在误差允许范围内可以忽略不计；而在时间上却省下40%，所以双转头方式效能更高，以时间计算，大约提高40%。

5.2.3 研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响

由于打孔机的双钻头合作间距会影响作业路线，合作间距控制不合理会浪费资源，并且会导致两个钻头不同时作业，使加工效率、加工质量降低，增大作业成本，进而影响到生产效能。所以必须选择最合理的合作间距以提高工作效率和工作质量，进而缩短作业成本，以达到提高生产效能目的。路径的最优是缩短钻头的加工路径长度来降低钻头移动时间，其与间距的合理设置密切相关。所以，要提高生产效能，就要设置一个合理的合作间距。 6 模型分析与评价

该模型先得到最优刀具转换顺序，再根据模拟退火算法得到各类孔的最优作业路线，进而得到问题的解。得到的结果和预料的差不多，所以该模型的还是比较可靠的。

该模型的优点：

1、将复杂问题简单化。原问题是要找到最优作业线路（包括刀具转换方案），本模型就先找到最优刀具转换顺序，再找最优线路；而在找最优线路的时候，又是根据最优刀具转换顺序将孔进行分类，然后再每一类里找最优线路。

2、采用模拟退火算法进行寻找最优线路。模拟退火算法广泛应用于优化领域，从算法原理可以看出，理论上，当降温达到足够缓慢，迭代次数达到足够多，模拟退火算法是可以得到全局最优解的。

该模型也存在许多缺点和不足：

1、先得到刀具最优转换顺序再根据其进行寻找最优线路得到的结果不一定是全局最优的。

2、将孔型进行分类，类与类之间的连接线路在全局上也不一定是最优的。

3、该问题是寻找无回路的最优线路，所以起点选择会影响到解，诶本模型的起点选择是由实验者目测和感觉确定的，所以也不一定是全局最优的。

4、模拟退火算法只是理论上能得到全局最优解，实际上如果迭代次数太大或降温太慢，则搜索时间需要很长，效率很低，因此本模型得到的只是近似最优解，而不是全局最优解。

5、在解决双转头作业方式时，是先得到一个解，再验证，如果不符合，再求解再验证，所以解决的效率很低。

6、在双转头作业方式中，该模型得到的解却出现两个转头作业时间不相等，也就是一个转头在工作，另一个转头却在空闲，所以资源利用率没有达到最高。

12

参考文献

[1] 刘卫国.MATLAB程序设计与应用(第二版).高等教育出版,2006.7(2010重印) [2] 打孔机生产效能的提高(优秀论文).2012年12月27日. http://wenku.http://www.wodefanwen.com//view/e5a4ede8aeaad1f346933f78.html [3] 算法大全.现代优化算法

13

附录A 单转头优化路线图（部分）

图A-1 E孔的优化路线

图A-3 B孔的优化路线

图A-5 A孔和C孔的优化路线

图A-2 E孔优化路线、B孔的分布图及其优化

路线的起始点

图A-4 B孔的优化路线、A孔和C孔的分布图

及其优化路线的起始点

图A-6 A孔和C孔的优化路线、F孔和H孔

的分布图及其优化路线的起始点

14

图A-7 F孔和H孔的优化路线

图A-9 F孔和G孔的优化路线

A-11 E孔和G孔和J孔的优化路线

图A-8 F孔和H孔的优化路线、F孔和G孔

的分布图及其优化路线的起始点

图A-10 F孔和G孔的优化路线，E孔和G孔

和J孔的分布图及其优化路线的起始点

图A-12 E孔和G孔和J孔的优化路线，D孔

和I孔的分布图及其优化路线的起始点

图

15

图A-13 D孔和I孔的优化路线

图A-14 D孔和I孔的优化路线，C孔和I孔

和J孔的分布图及其优化路线的起始点

图A-15 C孔和I孔和J孔的优化路线

附录B MATLAB程序代码（部分） 1.数据处理1：

fin=fopen('C1_data.txt','r'); while(~feof(fin)) fp=fgetl(fin); if(length(fp))

if(fp(1)=='孔')

ülose(fout); switch(fp(5)) case 'A'

fout=fopen('A.txt','w'); case 'B'

fout=fopen('B.txt','w'); case 'C'

fout=fopen('C.txt','w');

16

case 'D'

fout=fopen('D.txt','w'); case 'E'

fout=fopen('E.txt','w'); case 'F'

fout=fopen('F.txt','w'); case 'G'

fout=fopen('G.txt','w'); case 'H'

fout=fopen('H.txt','w'); case 'I'

fout=fopen('I.txt','w'); case 'J'

fout=fopen('J.txt','w'); end else

fprintf(fout,'%s\\r\\n',fp); end end end

fclose(fin); fclose(fout);

2.数据处理2： clear all

fin=fopen('C1_data.txt','r'); fout=fopen('Data.txt','w'); count=1; FP=[]; FPC=[];

while(~feof(fin)) fp=fgetl(fin); if(length(fp))

if(fp(1)=='孔')

ülose(fout); FP=[FP,count]; FPC=[FPC,fp(5)]; else

fprintf(fout,'%s\\r\\n',fp); count=count+1; end end end

count=count-1;

17

fclose(fin); fclose(fout);

[x X y Y]=textread('Data.txt','%c %d %c %d');

3.画出所有孔的分布图1：

[x Ax y Ay]=textread('A.txt','%c %d %c %d'); [x Bx y By]=textread('B.txt','%c %d %c %d'); [x Cx y Cy]=textread('C.txt','%c %d %c %d'); [x Dx y Dy]=textread('D.txt','%c %d %c %d'); [x Ex y Ey]=textread('E.txt','%c %d %c %d'); [x Fx y Fy]=textread('F.txt','%c %d %c %d'); [x Gx y Gy]=textread('G.txt','%c %d %c %d'); [x Hx y Hy]=textread('H.txt','%c %d %c %d'); [x Ix y Iy]=textread('I.txt','%c %d %c %d'); [x Jx y Jy]=textread('J.txt','%c %d %c %d'); plot(Ax,Ay,'b+') grid on hold on

plot(Bx,By,'r+') plot(Cx,Cy,'g+') plot(Dx,Dy,'c+') plot(Ex,Ey,'m+') plot(Fx,Fy,'y+') plot(Gx,Gy,'k+') plot(Hx,Hy,'r.') plot(Ix,Iy,'b.') plot(Jx,Jy,'k.')

legend('A','B','C','D','E','F','G','H','I','J');

3.确定转头顺序;

%顺序穷举法查找============================== clear all

B=[1,3;3,6;4,7;7,6;5 3;6,3]; for k=1:8 %k=1; for l=1:8

A(l)=mod(k+l-2,8)+1; end

for i=1:6

m=min(find(A==B(i,1))); n=max(find(A==B(i,2))); if(n

alen=length(A); aend=A(end);

18

while(A(end)~=B(i,2)) alen=alen+1;

A(alen)=mod(aend,8)+1; aend=A(end); end end end

C(k)=length(A); clear A; end

k=min(find(C==min(C))); for l=1:8

A(l)=mod(k+l-2,8)+1; end

for i=1:6

m=min(find(A==B(i,1))); n=max(find(A==B(i,2))); if(n

alen=length(A); aend=A(end);

while(A(end)~=B(i,2)) alen=alen+1;

A(alen)=mod(aend,8)+1; aend=A(end); end end end A

%逆序穷举法查找============================== clear all

B=[1,3;3,6;4,7;7,6;5 3;6,3]; for k=1:8 %k=5; for l=1:8

A(l)=mod(7+k-l,8)+1; end

for i=1:6

m=min(find(A==B(i,1))); n=max(find(A==B(i,2))); if(n

alen=length(A); aend=A(end);

while(A(end)~=B(i,2)) alen=alen+1;

19

A(alen)=mod(aend-1,8); if(A(end)==0) A(end)=8; end

aend=A(end); end end end

C(k)=length(A); clear A; end

k=min(find(C==min(C))); for l=1:8

A(l)=mod(7+k-l,8)+1; end

for i=1:6

m=min(find(A==B(i,1))); n=max(find(A==B(i,2))); if(n

alen=length(A); aend=A(end);

while(A(end)~=B(i,2)) alen=alen+1;

A(alen)=mod(aend-1,8); if(A(end)==0) A(end)=8; end

aend=A(end); end end end A

4.模拟退火算法程序： 编写sa.m文件：

%%模拟退火算法(simulated annealing) %%[Sum,Path]=sa([x0,y0],[X,Y]) %%[x0,y0]：起点 %%[X,Y]:坐标矩阵 %%Sum:总路程 %%Path:路径

function [Sum,Path]=sa(x0,y0,X,Y) X_mat=[x0;X];

20

Y_mat=[y0;Y];

Num=length(X_mat); MaxTime=9000000; Temper=1;

EndTem=0.1^50; alpha=0.9999; %计算距离矩阵 d=zeros(Num); for i=1:Num-1 for j=i:Num

d(i,j)=sqrt((X_mat(i)-X_mat(j))^2+(Y_mat(i)-Y_mat(j))^2); end end

d=(d+d')*0.0254; %产生初始解 Path=[]; Sum=inf; for i=1:1000

S=[1,1+randperm(Num-1)]; SumTemp=0; for j=1:Num-1

SumTemp=SumTemp+d(S(j),S(j+1)); end

if(SumTemp

Sum=SumTemp; end end

%模拟退火迭代 for i=1:MaxTime

c=sort(2+floor((Num-2)*rand(1,2))); u=c(1);v=c(2);

df=(d(Path(u-1),Path(v))+d(Path(u),Path(v+1)))-(d(Path(u-1),Path(u))+d(Path(v),Path(v+1))); if(df<0)

Path=[Path(1:u-1),Path(v:-1:u),Path(v+1:Num)]; Sum=Sum+df;

elseif(rand(1)

Path=[Path(1:u-1),Path(v:-1:u),Path(v+1:Num)]; Sum=Sum+df; end

Temper=Temper*alpha; if(Temper

21

end end

%画出对应优化线路 hold on; sj1=[];

for k=1:Num

sj1=[sj1;X_mat(Path(k)),Y_mat(Path(k))]; end

plot(sj1(:,1),sj1(:,2),'+-'); hold off; end

5.画圆程序：

编写circle.m文件：

function circle(xCentre,yCentre,radius) seita=0:2*pi/100:2*pi;

x=xCentre+radius*cos(seita); y=yCentre+radius*sin(seita); hold on plot(x,y,'r-') end

6.单转头作业方式，每类孔优化程序（部分）： plot([Dx;Gx],[Dy;Gy],'+');

[sum,path]=sa(3.122e+5,8.982e+5,[Dx;Gx],[Dy;Gy]); sum

path(end) length(Dx)

x1=Dx(path(end)-1); y1=Dy(path(end)-1);

circle(x1,y1,3240/0.0254)

PATH=path; save PATH SUM=sum; save SUM

hold on;

plot([Ex],[Ey],'k+')

[sum,path]=sa(-7.06e+4,4.91e+4,Ex,Ey); sum

path(end) length(Ex)

22

x1=Ex(path(end)-1); y1=Ey(path(end)-1);

circle(x1,y1,3240/0.0254)

hold on;

plot([Bx],[By],'k+')

PATH1=path; save PATH1 SUM1=sum; save SUM1

[sum,path]=sa(9.23e4,8.163e5,Bx,By); sum

path(end) length(Bx)

x1=Bx(path(end)-1); y1=By(path(end)-1);

circle(x1,y1,3240/0.0254)

hold on;

plot([Ax;Cx],[Ay;Cy],'k+')

PATH2=path; save PATH2 SUM2=sum; save SUM2

[sum,path]=sa(-9.32e004,3.264e5,[Ax;Cx],[Ay;Cy]); sum

path(end) length(Ax)

x1=Ax(path(end)-1); y1=Ay(path(end)-1);

circle(x1,y1,3240/0.0254)

hold on;

plot([Fx;Hx],[Fy;Hy],'k+')

PATH3=path; save PATH3 SUM3=sum; save SUM3

23

7.单转头作业方式计算总路程：

load SUM;load SUM1;load SUM2;load SUM3;load SUM4; load SUM5;load SUM6;load SUM7;load SUM8;

SUM,SUM1,SUM2,SUM3,SUM4,SUM5,SUM6,SUM7,SUM8

Sk=SUM+SUM1+SUM2+SUM3+SUM4+SUM5+SUM6+SUM7+SUM8

8.双转头作业方式分界线确定： xsort=sort(X) length(X)

xmid=(xsort(1062)+xsort(1063))/2 minx=xmid-15/0.254 maxx=xmid+15/0.254 ck=[]

for k=1:length(X) if((X(k)>minx) && (X(k)

x11=xmid*ones(1,maxy-miny+1);

x12=(xmid-15/0.254)*ones(1,maxy-miny+1); x13=(xmid+15/0.254)*ones(1,maxy-miny+1); y11=miny:maxy;、 hold on;

plot(x11,y11,'b',x12,y11,'b',x13,y11,'b')

24

本文来源：https://www.bwwdw.com/article/afao.html