英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料

3D打印中喷嘴路径规划的优化方法

摘要---本文提出了3D打印中的喷嘴路径规划的优化方法。喷嘴路径规划问题可以被确切表诉为没有地址的乡村邮递员问题（URPP）。基于URPP在3D打印应用中的独特特性，提出了一种新的优化方法，以缩短传统URPP求解器的处理时间。建议的优化方法的性能用计算机模拟来评估。仿真结果表明，与其他URPP求解器相比，建议的求解器具有更短的处理时间，并且可以提供更短的过渡长度的解决方法。

索引词—增材制造，3D打印，UPRR，最优化。

Ⅰ.引言

在典型的基于熔融沉积模型（FDM）的3D打印方法中，将3D模型的计算机辅助设计（CAD）文件输入到切片软件，并将其分成许多薄层。然后模型的每一层将被分解为打印段，并进一步转换为FDM机器上机械零件的加工运动的控制代码。在大多数现成的FDM机器中，他们的打印喷嘴在打印时沿着打印床移动，挤压机控制丝的流出速率。熔化的塑料丝，通常是ABS或PLA，将通过打印喷嘴被沉积在打印床上，以构建打印段，并逐层构建模型。为了打印打印段，喷嘴移动至打印段的起点并穿越到其终点。同时，挤压机向喷嘴的容器注入塑料丝并产生需要的压力。然后熔化的塑料丝被压出喷嘴，形成打印段。在喷嘴到达层的末端之前，挤压机将逐渐减小压力，以至于没有多余的塑料丝被沉积在当前层的末端。然后喷嘴移动到下一层的起点。重复该过程，直到遍历当前层上的所有打印段。然后打印床下降，下一层的打印过程继续。

模型的总构建时间与打印喷嘴遍历所有打印段（包括打印段和非打印段，也成为过渡段）所需的时间成比例。虽然遍历所有打印段的时间不能减少，但可以通过缩短过渡时间来缩短总构建时间。打印喷嘴的路径可以被表述为无地址的乡村邮递员问题（URPP），在[1]中第一次被Orloff提出来。目的是找到一条时间或距离花费最小的路径，该路径至少能够遍历一次所有需要的边界，其中E是模型中所有打印段的集合。如果，URPP被证明NP困难。

弗雷德克森（Frederickson）的算法是解决URPP的著名方法，该算法有一个等于1.5的近似因子。它类似于克里斯托费德斯（Christofides）在[4]中提出的旨在解决旅行商问题（TSP）的近似算法。在[5]中，Muyldermans等人在一般路径问题（GRP）中使用k-opt算法，其中k-opt最初是TSP的改进算法。它证明GRP解决方案质量的显著提高。Groves和Vuuren在[6]中提出了基于启发式的RPP算法。他们的仿真结果表明，他们的算法可以提供计算复杂度相对较低的相当不错的RPP解决方法。在[7]中，Hertz等人表明，通过对上述Frederickson算法生成的解决方案应用2-opt算法，可以在合理的处理持续时间获得改进的RPP解决方案。最近，Fok等人将喷嘴运动规划问题化为TSP问题，并提出了一种宽松的方案，以缩短处理时间而不会对模型构建时间产生重大影响。

除了喷嘴运动规划之外，还对优化增材制造工艺的其他方面进行了广泛的研究。Cheng等人在[9]中研究了打印模型的方向如何影响FDM工艺的制造精度，制造时间和成本。他们表明，通过优化模型的方向，可以大大减少所需支撑材料的数量，并因此缩短构建时间。

在这项工作中，通过利用打印段的独特特性，提出了一种缩短FDM工艺中喷嘴运动规划处理时间的改善方法。在后面的部分，我们还可以观察到，在提出的改善方法的帮助下可以缩短打印喷嘴所经过的过渡部分的总长度。本文的其余部分安排如下。第二部分提供了问题表述，包括打印喷嘴的运动模型和在最优化过程中使用的目标函数。在第三部分中，简单介绍了Frederickson的算法和k-opt，RPP求解器以及这项工作中采用的相应增强算法。第四部分详细阐述了3D打印的独特特性。第五部分将解释改善过程。使用电脑仿真评估提出的改善方法的性能。仿真设置和相应的结果在第六部分展示。最后，第七部分给出结论。

Ⅱ 问题阐述

在这部分，阐述了喷嘴运动规划的最优化问题。在FDM工艺中，3D模型每一层内部的结构由大量打印段构成。打印喷嘴必须遍历所有的打印段，并且在tamen3上面沉积所需数量的熔融塑料丝。打印喷嘴在同一切片上的不连贯的打印段之间移动被视为过渡。打印喷嘴的速度和塑料丝的流动速率会影响打印段的厚度。这使得打印喷嘴遍历所有打印段的总时间几乎恒定。相反，打印喷嘴可以通过达到其最大速度来缩短过渡部分的遍历时间。因此，最优化问题的目的是找到一条遍历模型中所有打印段的快速路径，这条路径也可以看作最小化打印喷嘴遍历过渡部分的时间。

A.无地址的乡村邮递员问题

在这项工作中，最优化问题可以被阐述为无地址的农村邮递员问题（URPP），这是中国邮递员问题（CPP）的替代版本。在CPP中，给定邮递员一张图标，要求其找出一条可以到达图G上所有边缘E至少一次的最短或最快的路线。除了目标是访问所有边缘E而不是顶点V之外，该问题和著名的TSP问题十分相似。在URPP中，要求被放宽了，邮递员只需要至少访问一次图形G上的某些要求的边缘。在URPP问题阐述下，打印段是所需的边缘，而过渡段是剩余的边缘。对于一组打印段，令表示与中的边缘对应的一组顶点，因此可以通过添加一组连接中的每对顶点的额外边缘来构造图形，从而。因此，目的是找到一种至少遍历上所有一次的快速行程。

B.成本函数

因为打印喷嘴遍历模型中所有的打印段所需的总时间是常数，所以在最优化过程中，仅考虑和过渡有关的成本。成本函数代表打印喷嘴从顶点到顶点遍历过渡部分所需的时间。成本函数包括两个部分。

(1)

在此，代表喷嘴遍历过渡区所需的时间，可以使用喷嘴的运动模型获取。第二部分代表挤压机执行缩回操作所需的时间。

1）运动模型：在本部分中，我们采用[8]中的喷嘴运动模型来计算（1）中的)。这种模型考虑了喷嘴的加速和减速，因此允许其速度在遍历边缘时发生变化。对于打印段，在喷嘴的加速和减速过程中，假定沉积塑料丝厚度的一致性是通过挤压机调节其流动速率来控制的。假设打印喷嘴可以精确地停在所指示的坐标处，则可以通过相应的三角速度和梯形速度分布[10]获得打印喷嘴遍历过渡的成本（即时间）。

2）缩回：术语“strings”是指当喷嘴遍历不连续部分时从喷嘴滴落的多余塑料丝。大多数FDM机器可以通过在遍历前缩回（喷嘴）来缓解这种问题，该过程涉及抽出固体丝以便在打印喷嘴内的容器上产生负压。缩回所花费的时间用表示，它是被抽出的塑料丝的数量和相应的抽出速率的函数。

Ⅲ.喷嘴路径规划的最优化

提出的优化方案是一种定制的k-opt算法， 该算法可对使用Frederickson算法获得的解决方案进行操作。在本节中，将详细说明Frederickson算法和k-opt算法。

A.Frederickson算法

Frederickson算法在[3]中首次提出。它是URPP广泛采用的构造算法，与TSP[4]中的Christofin算法具有高度相似性。Frederickson从给定的无向连通图和一组所需的边缘开始。然后构建最小的生成树（MST）连接中的所有边缘。在MST构建过程中引入的那些新边缘组成新集。然后对合集进行最小完美匹配，以连接奇数度的顶点。然后，在匹配过程中添加的额外边缘将形成另一个新的集合。接着可以在总集找到欧拉通路。 通路上连续的边缘（均不在中）被近路替代以进一步优化通路。

B．k-opt算法

k-opt算法最初被设计用于进一步优化不理想的TSP解决方法[12]。Hertz在[7]中对其修正，以增强URPP的解决方案。在k-opt算法中，给定的路线被分解为k个片段，并使用不同的可行组合进行重新连接。每当发现改进时，这条路线就被更新。重复该过程直到无法实现进一步的改进。K-opt算法有两种常规实现方式。只要发现改进，k-opt₁会立即更新路线并开始新的迭代。K-opt₂会扫描当前迭代中所有可用的组合，并使用具有最佳改进的组合来更新路线。在这项工作中，仿真包含了2-opt的两种实现方式，来研究提出的改进方式的两种不同配置的性能。注意，由于运算复杂度高，未考虑更高阶的k-opt算法。

Ⅳ.3D打印的独特特征

在本节中，将解释URPP在3D打印应用中的一些独特特性，这些特性将为提出的改进方法的发展提供见解。

A.零成本过渡

在公式中，边缘成本表示为，而是边缘长度和打印喷嘴的速度分布函数。因此，连接顶点和且意味着顶点（和相应的打印段）已连接。尽管普通的URPP中很少有成本为0的边，但在上述公式下非常普遍，因为模型中的曲线由于分辨率限制通常由多个短打印段构成。通过在计算中给予较低的优先级，可以大大降低优化过程的计算复杂性。

B.起点和终点

普通URPP的目的是找到快速遍历G中所有必要边缘的欧拉通路，并且路径将回到起点。对3D打印的起点和终点的这种要求不是必须的，因为一旦在当前层中构建了所有打印段，打印喷嘴就可以开始打印下一层。图1中的说明性示例显示，通过不将打印喷嘴返回起始位置，存在进行进一步优化的空间。

图1：（a）通常URPP的最优解决方案和（b）在3D打印中的最有解决方案。

绿点代表开始点，黑线和红线分别代表打印段和过渡部分。

Ⅴ.提出方法

在本文中，通过利用第四节中提到的独特特性，开发了对喷嘴运动规划问题的改进方法。该方法包括两个主要部分。当探索路线的组合时，该方法对k-opt₂引入了一条额外规则。在执行k-opt₂算法之前，将创建给定路线的过渡优先级列表，具有较高成本的过渡具有较高优先级。在执行k-opt₂的搜索操作期间，将首先评估具有较高优先级的过渡。这种设计旨在解决以下事实：模型中的曲线是由大量短打印段和零成本过渡组成的。零成本过渡不太可能被k-opt₂算法中的更好选项所替代。因此，它们的优先级较低。

提出的改进方法的第二部分通过省略返回起始顶点（即起点终点）的要求来更改喷嘴运动规划的顺序。这个方法以给定的打印段T的访问周期开始，该打印段T包括中的所有边缘以及作为打印喷嘴的当前位置的当前层的起始坐标。然后，在最接近的T上的一个顶点处切割该循环，使其变成一条链，其中是链上第i个打印段相对应的顶点。值得注意的是，是C上最接近的顶点。在该过程的第p次迭代中，C被分解为两个子链和。如果和的翻转版（即）的共同成本比原始值低，这条链的顺序就会更新，以至于。否则，C保持不变，并且该过程继续进行下一次迭代，直到评估了所有过渡部分为止。此过程通过迭代执行本地搜索来降低C的相关成本。

Ⅵ.仿真

A.仿真设置

本文进行了仿真以评估提出的改进方法的性能。在[13]中的7个3D模型被选为模拟仿真中的样本模型。使用Cura[14]的默认设置对模型进行切片。撤回动作的垂直高度为0.075mm，撤回长度为4.5mm。填充密度设置为总体积的10%。使用[8]中提出的松弛方案进一步优化了打印规划。尽管如此，处于比较目的，每组仿真中的路径最优化模块都被Frederickson算法，2-opt和提出的改进方案所取代。

使用开源仿真器GCodeAnalysor-1.0[15]对所有产生的打印计划进行了评估。优化器所需的后处理时间是从装有Window8.1，Intel Core i7处理器和16 GB RAM的计算机上执行的30个独立仿真模型获得的平均值。仿真结果展示在表Ⅰ中。

表1 使用不同路径优化器获得的总过渡长度和后处理时间