周 波，劉殿海，趙宇輝，田同同，趙吉賓

（1.中國(guó)科學(xué)院沈陽(yáng)自動(dòng)化研究所，沈陽(yáng) 110016；2.中國(guó)科學(xué)院機(jī)器人與智能制造創(chuàng)新研究院，沈陽(yáng) 110169）

三維點(diǎn)陣結(jié)構(gòu)是近年興起的一種新型輕質(zhì)結(jié)構(gòu)，不僅具有良好的力學(xué)性能，而且能很好地滿足對(duì)結(jié)構(gòu)功能一體化的需求[1]。因點(diǎn)陣結(jié)構(gòu)通常是具有質(zhì)量輕、剛度大、優(yōu)良的抗沖擊性能及散熱性能等多功能特性的輕質(zhì)結(jié)構(gòu)，被廣泛地用于工藝品設(shè)計(jì)（圖1（a））、高速運(yùn)載工具、運(yùn)動(dòng)裝備（圖1（b）[2]）及建筑（圖1（c）[3]）。此外，在軍工領(lǐng)域還用于艦船潛艇及航空航天飛行器的外殼結(jié)構(gòu)等[4–5]。目前，從空間衛(wèi)星的大跨度支撐結(jié)構(gòu)件到飛機(jī)發(fā)動(dòng)機(jī)組件，增材制造無(wú)疑是制造領(lǐng)域的研究熱點(diǎn)與技術(shù)聚焦點(diǎn)，相對(duì)于傳統(tǒng)的減材制造如數(shù)控加工技術(shù)，增材制造是一個(gè)逐層累加的過(guò)程，被定位于傳統(tǒng)制造技術(shù)無(wú)法實(shí)現(xiàn)的一體化先進(jìn)制造方式，具有材料利用率高、復(fù)雜結(jié)構(gòu)制造能力強(qiáng)、滿足個(gè)性化小批量生產(chǎn)需求等技術(shù)優(yōu)勢(shì)[6]。

點(diǎn)陣結(jié)構(gòu)的命名源于晶體結(jié)構(gòu)，晶體的基本特征是其內(nèi)部結(jié)構(gòu)具有周期的重復(fù)性，把分子空間排列與空間的網(wǎng)點(diǎn)陣列聯(lián)系起來(lái)，就是晶體的點(diǎn)陣結(jié)構(gòu)，如圖2（a）為某種晶體結(jié)構(gòu)。此外，自然界也廣泛存在這種類(lèi)似的結(jié)構(gòu)，如海綿及其他動(dòng)物骨骼以及植物纖維（圖2（b））?，F(xiàn)代的材料和機(jī)械學(xué)科，借用這個(gè)名詞，將滿足這種具有大量的連接桿及節(jié)點(diǎn)部件的模型統(tǒng)稱(chēng)為三維點(diǎn)陣結(jié)構(gòu)。目前，三維點(diǎn)陣結(jié)構(gòu)的設(shè)計(jì)多采用算法完成，如圖2（c）所示的某周期性點(diǎn)陣結(jié)構(gòu)，其某些相同的結(jié)構(gòu)層具有周期重復(fù)的特性。研究人員在追求輕質(zhì)的同時(shí)要求結(jié)構(gòu)滿足彈塑性、空氣動(dòng)力學(xué)及高散熱等物理特性。

這一熱點(diǎn)問(wèn)題吸引商業(yè)軟件開(kāi)發(fā)了相關(guān)控件，綁定在軟件上配合用戶使用。2018年，著名的三維造型軟件Rhino就在其平臺(tái)下運(yùn)行采用程序算法生成模型的插件（Grasshopper），用于創(chuàng)建輕量的內(nèi)部結(jié)構(gòu)，共提供了10余種單元晶格體，用戶可根據(jù)不同需求將單元晶格體填充于設(shè)計(jì)空間內(nèi)[7]，充分滿足研究人員對(duì)開(kāi)發(fā)增材制造路徑算法的初步要求，圖3為在模型上調(diào)用該控件生成的點(diǎn)陣結(jié)構(gòu)部件。此外，法國(guó)洛林大學(xué)的學(xué)者受Voronoi開(kāi)孔泡沫成型過(guò)程的啟發(fā)，研究了一種非周期性的微觀結(jié)構(gòu)[8]，該方法可以針對(duì)目標(biāo)對(duì)象及其表面內(nèi)的泡沫幾何形狀及其機(jī)械性能進(jìn)行分級(jí)，不需要全局優(yōu)化過(guò)程，而是直接生成微結(jié)構(gòu)以顯示特定的彈性行為，如圖1（a）所示。

點(diǎn)陣結(jié)構(gòu)部件因結(jié)構(gòu)復(fù)雜，不能采用傳統(tǒng)的減材制造加工方式進(jìn)行加工。而采用增材制造，其加工效率一直是亟待解決的難題，其制造總時(shí)間主要集中于切片后多邊形的填充時(shí)間及從當(dāng)前多邊形移動(dòng)到下一待加工多邊形的機(jī)構(gòu)執(zhí)行非填充加工（連接路徑）的時(shí)間。

點(diǎn)陣結(jié)構(gòu)雖然切片后多邊形數(shù)量眾多，但是其填充算法仍需采用填充其他種類(lèi)部件的填充路徑，包括：傳統(tǒng)的主要基于等距輪廓偏置填充算法（CPO）或者往復(fù)填充算法（Zig–Zag），以及這兩種方案的混合路徑，如圖4所示。而效率更高的路徑如螺旋軌跡[8]以及適用于薄壁結(jié)構(gòu)增材制造的直骨架[9]方法，往往僅適用于特殊幾何特征的多邊形的填充，前者適用于外形輪廓圓潤(rùn)的區(qū)域而后者適用于具有狹長(zhǎng)幾何特征的區(qū)域。傳統(tǒng)方式雖然填充效率相對(duì)低，但是在保證多邊形輪廓邊界精度以及對(duì)形狀繁雜的多邊形輪廓適用性上，是效率高的路徑無(wú)法比擬的。因此，本文在采用傳統(tǒng)方式作為填充方式的基礎(chǔ)上，重點(diǎn)討論連接路徑的規(guī)劃問(wèn)題。

圖1 點(diǎn)陣結(jié)構(gòu)應(yīng)用Fig.1 Applications of lattice structure

圖2 自然界中點(diǎn)陣結(jié)構(gòu)及周期性點(diǎn)陣結(jié)構(gòu)Fig.2 Lattice structures in nature and periodic lattice structure

圖3 Grasshopper生成點(diǎn)陣結(jié)構(gòu)Fig.3 Lattice structure generated by Grasshopper

圖4 傳統(tǒng)輪廓掃描路徑類(lèi)型Fig.4 Conventional scanning paths

針對(duì)點(diǎn)陣模型的加工，若采用現(xiàn)有的連接路徑，將存在嚴(yán)重的制造效率問(wèn)題。因點(diǎn)陣模型的切片輪廓過(guò)于復(fù)雜且數(shù)量巨大，而切片過(guò)程是根據(jù)面片順序決定的，在填充階段仍然遵循這一順序，致使填充過(guò)程中大量行程是浪費(fèi)的，極大影響了加工效率?；诖?，本文提出下述軌跡連接算法，見(jiàn)圖5的算法流程圖。

相關(guān)研究工作

21世紀(jì)初，三維點(diǎn)陣結(jié)構(gòu)最初由哈佛大學(xué) Evans教授、Hutchison教授和劍橋大學(xué)Ashby教授等[10]提出。Deshpande等[11]對(duì)金屬四面體點(diǎn)陣夾芯結(jié)構(gòu)進(jìn)行了彎曲試驗(yàn)，且發(fā)現(xiàn)點(diǎn)陣結(jié)構(gòu)可簡(jiǎn)化為鉸接體系。Li等[12]針對(duì)開(kāi)口式泡沫等多孔材料，提出一種十四面體結(jié)構(gòu)單元作為簡(jiǎn)化計(jì)算模型。其中，三維點(diǎn)陣結(jié)構(gòu)是由面板、桿件等微元件根據(jù)一定規(guī)律排列構(gòu)成的空間桁架結(jié)構(gòu)，見(jiàn)圖6[13]。三維點(diǎn)陣結(jié)構(gòu)具有工程意義和實(shí)際應(yīng)用價(jià)值，因此本文以三維構(gòu)型的點(diǎn)陣結(jié)構(gòu)為研究對(duì)象。

圖5 算法流程圖Fig.5 Flow chart of algorithm

增材制造的路徑規(guī)劃算法，主要包括切片輪廓的路徑填充、連接路徑規(guī)劃等。因增材路徑主要在切片后的平面輪廓內(nèi)進(jìn)行填充，所以路徑填充相對(duì)簡(jiǎn)單，大多選擇前述的CPO或者Zig–Zag方法。為了增加路徑覆蓋效果及材料熔覆強(qiáng)度，可以選擇對(duì)臨近層的填充路徑做角度覆蓋填充，圖7和圖8以Zig–Zag路徑為例，實(shí)現(xiàn)對(duì)邊界區(qū)域的覆蓋填充。通過(guò)上述方法，邊界區(qū)域覆蓋質(zhì)量有了一定的提高。

圖6 三維點(diǎn)陣結(jié)構(gòu)Fig.6 3D lattice structure

圖7 Zig–Zag掃描路徑疊加示意圖Fig.7 Schematic diagram of Zig–Zag overlapped scanning path

針對(duì)增材制造速度相對(duì)緩慢的問(wèn)題，本文專(zhuān)注于點(diǎn)陣模型制造的局限性，提出了高效的軌跡連接方法。在本文中提出了現(xiàn)有增材技術(shù)存在的問(wèn)題，并分析了旅行商問(wèn)題在增材制造點(diǎn)陣結(jié)構(gòu)中的應(yīng)用，進(jìn)行了模擬及打印試驗(yàn)并給出了結(jié)論。

旅行商問(wèn)題規(guī)劃點(diǎn)陣模型填充

復(fù)雜的點(diǎn)陣模型切片后，會(huì)產(chǎn)生大量的多邊形，這些多邊形大多微小且零散。由于切片算法是基于原模型面片的順序執(zhí)行切片的，所以輸出的多邊形次序并沒(méi)有規(guī)律，現(xiàn)有算法沒(méi)有對(duì)這些多邊形進(jìn)行排序方面的研究。而在后續(xù)的填充過(guò)程中，填充順序?qū)⒋蟠笥绊懱畛涞穆窂竭B接距離以及總體填充時(shí)間。

1 分層切片算法

圖9（a）中的八爪魚(yú)模型因具有大量的連桿及節(jié)點(diǎn)構(gòu)造，屬于典型的點(diǎn)陣模型；圖9（b）中大耳狐模型采用樹(shù)形支撐部件以保證在滿足支撐強(qiáng)度的前提下，節(jié)省支撐部件打印材料及打印時(shí)間，因樹(shù)形支撐部件具有復(fù)雜的連桿及節(jié)點(diǎn)構(gòu)造，也屬于本文所述的點(diǎn)陣模型。

通過(guò)查找模型中與給定平面相交的所有三角形，并將相交點(diǎn)依次連接到相應(yīng)的閉合多邊形中，可以獲得每一層的切片軌跡（包括內(nèi)部和外部軌跡）。區(qū)分內(nèi)部和外部軌跡的技術(shù)非常成熟，如文獻(xiàn)[14]中的父子關(guān)系和層次排序算法。通過(guò)分層切片算法，可以獲得圖10模型中各層的多邊形。

圖8 Zig–Zag掃描打印實(shí)例Fig.8 Actual printing samples of Zig–Zag scanning

圖9 非周期性點(diǎn)陣模型Fig.9 Non–periodic lattice models

圖10 切片效果Fig.10 Slicing effects

將各個(gè)多邊形的重心坐標(biāo)抽象替代各個(gè)多邊形，如圖11（a）所示。若采用現(xiàn)有技術(shù)直接填充這些復(fù)雜的、形狀及尺寸各異的多邊形，獲得填充的路徑連接如圖11（b）所示，可見(jiàn)直接填充的路徑連接基本是隨機(jī)、混亂的，存在多次交叉。在圖11（c）中采用人工的“Z”字形（采用往復(fù)、順序連接）路徑連接，這種連接方式可以保證在人工連接時(shí)無(wú)交叉，大大縮短了連接路徑總長(zhǎng)，無(wú)疑會(huì)提高加工效率。

上述數(shù)據(jù)見(jiàn)表1，可知，相較于默認(rèn)的無(wú)連接規(guī)劃，采用人工連接可以大大縮短路徑連接長(zhǎng)度。但是人工連接不僅耗時(shí)較長(zhǎng)，路徑長(zhǎng)度也難以保證，對(duì)于實(shí)際加工時(shí)每層存在大量多邊形的點(diǎn)陣部件，其連接效率及準(zhǔn)確性難以保證。因此本文提出基于求解旅行商問(wèn)題（Travelling salesman problem,TSP）獲得的自動(dòng)規(guī)劃填充次序的方法，該方法可以快速計(jì)算出無(wú)交叉的連接路徑并保證連接路徑的長(zhǎng)度。

2 旅行商問(wèn)題

旅行商問(wèn)題是這樣一個(gè)問(wèn)題：給定一系列城市和每對(duì)城市之間的距離，求解訪問(wèn)每一座城市一次并回到起始城市的最短回路。它是組合優(yōu)化中的一個(gè)NP困難（Non deterministic ploynomial–hard）問(wèn)題，在運(yùn)籌學(xué)和理論計(jì)算機(jī)科學(xué)中非常重要[15]。

TSP是計(jì)算數(shù)學(xué)中研究最深入的問(wèn)題之一，但對(duì)于一般情況卻沒(méi)有有效的解決方法，最為顯著的問(wèn)題是：隨著點(diǎn)數(shù)的增加，時(shí)間消耗將急劇增加。在這些求解方法中，Uwaterloo大學(xué)研究人員所提出的TSP求解算法雖然具有良好的準(zhǔn)確性但是時(shí)間消耗顯著[16]；而基于Lin–Kernighan算法的Local Search求解TSP的算法[15]具有良好的時(shí)間消耗性，但準(zhǔn)確性欠佳。

本文采用蟻群算法（Ant colony optimization，ACO）來(lái)求解TSP路徑計(jì)算，這是一種用來(lái)尋找優(yōu)化路徑的概率型算法。蟻群算法于1992年由Dorigo在其博士論文中提出，并在文獻(xiàn)[17]中給出系統(tǒng)論述，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為，本質(zhì)上是進(jìn)化算法中的一種啟發(fā)式全局優(yōu)化算法[18]。本文采用蟻群算法解決前述的TSP求解路徑連接問(wèn)題，算法的流程如下（以某一只螞蟻的行走路徑代表一個(gè)可行解，即一個(gè)路徑連接方案）：

圖11 掃描路徑的連接效果Fig.11 Linking effects of scanning path

表1 狐貍某層切片的輪廓軌跡連接數(shù)據(jù)統(tǒng)計(jì)Table 1 Statistics of linking data of fox model

（1）設(shè)定迭代次數(shù)；

（2）確定螞蟻數(shù)n；

①對(duì)每只螞蟻，隨機(jī)選擇一個(gè)抽象點(diǎn)作為起點(diǎn)；

·進(jìn)入循環(huán)選擇后n–1個(gè)抽象點(diǎn)；

·根據(jù)所有與當(dāng)前抽象點(diǎn)相連的路徑上的信息素多少，決定下一步，即選擇信息素最多的路徑；

·螞蟻有一定概率選擇錯(cuò)誤，即隨機(jī)選擇下一步要走的路徑；

·在選擇的路徑上按照一定規(guī)則留下一定量的信息素；

②螞蟻行走路徑就是本次搜索的軌跡連接路徑；

（3）每群螞蟻結(jié)束后，所有路徑上的信息素進(jìn)行一次衰退，保證越后進(jìn)行的螞蟻的信息素影響越大；

（4）等待迭代結(jié)束。

更新信息素的大小有多種，以下給定其中兩種模型。

設(shè)定更新選擇的路徑上的信息素方式，為式（1）：

設(shè)定全局更新信息素為蟻密系統(tǒng)，見(jiàn)式（2）：

式中，Messageij為從第i個(gè)城市到第j個(gè)城市的路徑上的信息素（初始化為該路徑長(zhǎng)度的倒數(shù)）；u為信息素衰退因子；Q為常數(shù)因子；len為從起始城市遍歷后再次回到起始城市的路徑距離。本文的參數(shù)設(shè)置如表2所示。

算法模擬螞蟻尋找食物的過(guò)程：以螞蟻行走路徑表示連接路徑的可行解，整個(gè)蟻群的所有路徑構(gòu)成最短連接路徑的解空間。螞蟻在選擇路徑時(shí)總是傾向于朝信息素濃度高的方向移動(dòng)，而距離短的路徑上走過(guò)的螞蟻多，留下的信息素也多，后續(xù)螞蟻選擇它的概率也會(huì)越大；其他路徑上的信息素會(huì)隨著時(shí)間的推移不斷揮發(fā)，這樣就形成了一種正反饋機(jī)制，最后整個(gè)蟻群聚集到最短路徑上。

蟻群算法的優(yōu)點(diǎn)在于：（1）采用正反饋機(jī)制，使搜索過(guò)程不斷收斂，不容易陷入局部最優(yōu)，易于獲得全局最優(yōu)解；（2）搜索過(guò)程采用分布式計(jì)算方式，多個(gè)個(gè)體同時(shí)進(jìn)行并行計(jì)算，保證算法的計(jì)算效率和運(yùn)行效率[18]。

表2 蟻群算法參數(shù)設(shè)置數(shù)據(jù)統(tǒng)計(jì)Table 2 Statistics of ACO parameters

3 TSP算法對(duì)比分析

通過(guò)將幾種TSP算法運(yùn)行對(duì)比，以驗(yàn)證本文所提出算法的有效性，這幾種對(duì)比算法在求解TSP的相關(guān)專(zhuān)著[15]中均得到了詳細(xì)的闡述，這里僅做簡(jiǎn)單描述。

首先，本文所述的貪婪算法是針對(duì)無(wú)權(quán)圖的，且每次選擇得到的都是局部最優(yōu)解。選擇的策略必須具備無(wú)后效性，即某個(gè)狀態(tài)以前的過(guò)程不會(huì)影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

針對(duì)TSP問(wèn)題，使用貪心算法求解的過(guò)程為：

（1）從某一個(gè)城市開(kāi)始，每次選擇一個(gè)城市，直到所有的城市被走完。

（2）每次在選擇下一個(gè)城市的時(shí)候，只考慮當(dāng)前情況，保證迄今為止經(jīng)過(guò)的路徑總距離最小。

其次，Boruvka與Quick Boruvka算法均基于帶權(quán)圖的最小支撐樹(shù)（Minimum spanning tree，MST）算法，前者是MST算法中最為古老的算法，后者是前者的優(yōu)化算法。

分別運(yùn)行上述算法，并將軌跡連接效果和統(tǒng)計(jì)數(shù)據(jù)分別列于圖12及表3。

從列表的數(shù)據(jù)可以看出，（1）除了Uwaterloo大學(xué)及本文所提出的算法，其余算法都存在交叉；（2）雖然Uwaterloo大學(xué)所提出的算法路徑最短，但是計(jì)算時(shí)間顯著較長(zhǎng)，其算法的時(shí)空效果并不好。本文進(jìn)一步比較了時(shí)間消耗和精度的隨機(jī)點(diǎn)（2000點(diǎn)）的計(jì)算結(jié)果，如圖13和表4所示。

圖12 多種連接方法對(duì)比Fig.12 Comparison of multiple linking methods

與連接路徑的長(zhǎng)度相比，本文方法在時(shí)間消耗方面表現(xiàn)出更大的優(yōu)勢(shì)。每層切片的多邊形數(shù)量可能很大，因此建議在處理點(diǎn)陣結(jié)構(gòu)部件的軌跡連接規(guī)劃方法時(shí)，宜使用所提出的蟻群算法來(lái)求解TSP路徑。

數(shù)值模擬與試驗(yàn)分析

為了評(píng)估所提出的TSP連接軌跡規(guī)劃算法，以圖14所示的兩個(gè)點(diǎn)陣模型的分層切片為例。兩者都是典型的具有節(jié)點(diǎn)和連桿的點(diǎn)陣模型，其中圖14（a）屬于典型的周期性點(diǎn)陣結(jié)構(gòu)，為模型1；圖14（b）屬于非周期性點(diǎn)陣結(jié)構(gòu)，為模型2。經(jīng)切片后，各個(gè)切片層均可以獲得多個(gè)零散的多邊形，適合驗(yàn)證本文所提出的算法。在仿真部分，僅測(cè)試示例層的計(jì)算時(shí)間，以驗(yàn)證TSP算法的計(jì)算效率；在打印試驗(yàn)部分，統(tǒng)計(jì)對(duì)比本文方法節(jié)省的實(shí)際打印時(shí)間。本文所提出的算法以C++實(shí)現(xiàn)，并在配置有8 GB RAM的Intel?Core TM i7–4790 CPU 3.6GHz臺(tái)式計(jì)算機(jī)上進(jìn)行了測(cè)量。

1 數(shù)值模擬

采用前述所提出的方法，先將周期性點(diǎn)陣模型的連接結(jié)果顯示于圖15（左側(cè)為原切片后獲得的多邊形；右側(cè)為應(yīng)用本文算法獲得的連接結(jié)果），并將統(tǒng)計(jì)數(shù)據(jù)列于表5。

同樣，調(diào)用本文算法再將非周期性點(diǎn)陣模型的連接結(jié)果顯示于圖16，并將統(tǒng)計(jì)數(shù)據(jù)列于表6。此處需要說(shuō)明的是，給出的兩個(gè)連接方案中，方案2是考慮部分多邊形的抽象點(diǎn)距離遠(yuǎn)，加入了距離聚類(lèi)算法[15]：以點(diǎn)集中抽象點(diǎn)距離的遠(yuǎn)近作為判定依據(jù)，將抽象點(diǎn)集分為兩個(gè)區(qū)域，再分別對(duì)兩個(gè)聚類(lèi)子區(qū)域進(jìn)行TSP路徑規(guī)劃連接的結(jié)果；而方案1并沒(méi)有加入距離聚類(lèi)算法。

圖13 TSP連接隨機(jī)點(diǎn)Fig.13 TSP linking random points

表4 本文算法與Uwaterloo大學(xué)算法的數(shù)據(jù)統(tǒng)計(jì)Table 4 Statistics of algorithms presented by this paper and Uwaterloo University

圖14 兩種點(diǎn)陣模型Fig.14 Two lattice models

表5 模型1仿真結(jié)果統(tǒng)計(jì)Table 5 Statistics of simulation results (Model 1)

圖15 路徑連接實(shí)例 （模型1）Fig.15 Linking example (Model 1)

圖16 路徑連接實(shí)例 （模型2）Fig.16 Linking example (Model 2)

對(duì)照兩個(gè)方案的結(jié)果，可知在計(jì)算時(shí)間方面，雖然處理的總抽象點(diǎn)數(shù)量相同，但是方案2因?yàn)榫嚯x聚類(lèi)產(chǎn)生了兩個(gè)點(diǎn)集，減少了每個(gè)點(diǎn)集的TSP路徑規(guī)劃的計(jì)算時(shí)間，所以總計(jì)算時(shí)間并沒(méi)有因?yàn)檎{(diào)用聚類(lèi)算法而增大，反而減少了總的TSP路徑規(guī)劃時(shí)間；在連接距離方面，方案2顯著降低，因?yàn)橹唤?jīng)過(guò)一次較大距離的跨越（兩個(gè)子點(diǎn)集之間），而方案1因?yàn)橛袃纱伪容^大距離的點(diǎn)連接，所以路徑顯著增加。

2 打印試驗(yàn)

本文的打印測(cè)試試驗(yàn)是在熔融沉積建模（FDM）3D打印機(jī)上進(jìn)行的，為了驗(yàn)證所述的軌跡連接方法的效率，測(cè)試試驗(yàn)均采用相同的參數(shù)：印刷材料是直徑為2.0mm的PLA（聚乳酸）塑料，噴嘴直徑為0.4mm，將層厚度設(shè)置為0.1mm，最大噴嘴移動(dòng)速度為50mm/s。此外，填充方式均采用Ultimaker Cura軟件提供的等距偏置填充路徑，填充方式及填充行距的設(shè)定值見(jiàn)表7。最終打印效果對(duì)比及數(shù)據(jù)統(tǒng)計(jì)如圖17及表7。

通過(guò)對(duì)比打印效果外觀，因兩種打印方式采用的填充方式及參數(shù)相同，所以打印完的成品件外觀并沒(méi)有明顯差異，局部特征也基本一致；進(jìn)一步，通過(guò)數(shù)據(jù)對(duì)比，兩次打印的成品質(zhì)量相差僅0.3g；考慮外觀和質(zhì)量基本相同，可認(rèn)為這兩種方式的打印結(jié)果沒(méi)有差異。但在總打印時(shí)間消耗及總長(zhǎng)度方面，本文方法均比沒(méi)有進(jìn)行路徑連接規(guī)劃的方法縮短很多：總打印時(shí)間減少17.52%，總連接長(zhǎng)度減少17.38%。因此，本文的方法能夠很高速、準(zhǔn)確地進(jìn)行軌跡連接，大大地縮短了連接軌跡，提高了加工效率。

結(jié)論

本文提出了一種基于蟻群算法解決TSP的增材制造的分層切片數(shù)據(jù)連接方案。通過(guò)將大量的多邊形抽象為重心坐標(biāo)，再將重心坐標(biāo)以TSP方法獲得填充次序和連接路徑。該方法主要解決以下問(wèn)題：

表6 模型2仿真結(jié)果統(tǒng)計(jì)Table 6 Statistics of simulation results (Model 2)

圖17 打印效果（左：Ultimaker Cura軟件；右：本文算法）Fig.17 Printing effects (left: Cura; right：this paper)

表7 打印結(jié)果統(tǒng)計(jì)Table 7 Statistics of simulation results (Model 2)

（1）采用蟻群算法解決了TSP軌跡規(guī)劃方法，對(duì)比多種TSP算法得到的連接路徑長(zhǎng)度和計(jì)算時(shí)間，證明本文提出的算法可以有效保證軌跡連接效率；

（2）通過(guò)比較連接路徑長(zhǎng)度和時(shí)間消耗的結(jié)果，可知如果多邊形數(shù)量相對(duì)較大（超過(guò)2000個(gè)），推薦使用蟻群算法求解TSP；

（3）在規(guī)劃抽象點(diǎn)集中加入距離聚類(lèi)算法，對(duì)聚類(lèi)后的子區(qū)域分別進(jìn)行路徑規(guī)劃，將縮短計(jì)算時(shí)間及路徑規(guī)劃距離。