基于改進(jìn)蟻群算法的線纜路徑規(guī)劃技術(shù)研究

吳保勝，郭 宇，王發(fā)麟，宋 倩

南京航空航天大學(xué) 機(jī)電學(xué)院，南京 210016

1 引言

隨著以航空、航天、船舶、電子、兵工等大型電氣系統(tǒng)的飛速發(fā)展，現(xiàn)代電氣系統(tǒng)日益復(fù)雜化、集成化。大量的電氣設(shè)備密集于系統(tǒng)平臺(tái)上，用于各設(shè)備和部件連接的線纜所傳送的信號(hào)越來越多，頻率越來越高，消耗的功率也越來越大，對(duì)線纜的敷設(shè)提出了更高的要求和挑戰(zhàn)。線纜敷設(shè)路徑規(guī)劃是一類特殊的帶性能約束的布局問題，其中待定參數(shù)多、可行空間復(fù)雜，線纜的布局合理性和裝配質(zhì)量直接關(guān)系到產(chǎn)品最終的整機(jī)性能和可靠性[1-2]。美國通用電器公司分析歸納飛機(jī)發(fā)動(dòng)機(jī)發(fā)生故障的原因，其中因?yàn)榫€纜管路損壞或失效而產(chǎn)生故障的比例達(dá)到了50%[3]。傳統(tǒng)的線纜模裝試驗(yàn)方法需要大量的人工干預(yù)，大大影響了線纜裝配的效率。虛擬環(huán)境下的線纜布線設(shè)計(jì)的出現(xiàn)，能夠?qū)崿F(xiàn)線纜自動(dòng)避障，生成滿足工程規(guī)則的布線路徑，為解決線纜裝配的布線不合理、效率低下等問題提供了一條有效的解決途徑[4]。

線纜自動(dòng)敷設(shè)的核心是路徑搜索算法。使用智能算法完成線纜路徑的自動(dòng)求解具有效率高等特點(diǎn)，是當(dāng)前的研究熱點(diǎn)。國內(nèi)外的學(xué)者對(duì)此進(jìn)行了相關(guān)的研究，如Park等[5]在1992年提出了基于Agent的線纜二維設(shè)計(jì)方法。CONRU等[6]將并行工程的方法應(yīng)用到線纜的自動(dòng)布局設(shè)計(jì)中，并使用遺傳算法進(jìn)行全局最優(yōu)路徑的搜索。ILKNUR等[7]針對(duì)復(fù)雜環(huán)境下線纜的布局問題，提出了一種布線路徑的搜索算法，該算法進(jìn)行約束采樣，然后利用隨機(jī)路徑圖法計(jì)算出初始路徑，再采用動(dòng)力學(xué)法對(duì)布線路徑進(jìn)行優(yōu)化，取得了良好的計(jì)算效果。韓明晶[8]將A*算法應(yīng)用到電子制造裝備的三維路徑搜索中，開發(fā)了基于UG的布線模塊。白曉蘭等[9]提出了基于工程規(guī)則和離散空間的航空發(fā)動(dòng)機(jī)管路布局方法。蔡毅等[10]提出了“按面自動(dòng)布線”和“貼壁干涉自動(dòng)調(diào)整”的方法，但由于布線路徑多、路徑空間交匯復(fù)雜等原因，結(jié)果仍存在干涉、算法耗時(shí)較高等問題。王成恩等[11]提出了一種基于計(jì)算幾何、微分幾何和智能優(yōu)化等思想，實(shí)現(xiàn)了對(duì)管系的敷設(shè)順序與管路路徑的自動(dòng)求解，取得了較好的效果。徐聯(lián)杰等[12]提出了一種基于障礙物碰撞檢測的RRT算法，利用基于碰撞信息進(jìn)行節(jié)點(diǎn)擴(kuò)展策略和快速繞障，有效解決了復(fù)雜結(jié)構(gòu)條件下沿結(jié)構(gòu)件表面的管路自動(dòng)布局問題。吳宏超等[13]提出了一種基于改進(jìn)A*算法的管路自動(dòng)布局方法，將工程規(guī)則作為約束條件，分別添加在路徑搜索和路徑優(yōu)化兩個(gè)階段，能較快地獲得一條滿足工程約束的路徑，但是仍未考慮管路之間的相互影響。

近年來，蟻群優(yōu)化算法（Ant Colony Optimization，ACO）作為一種啟發(fā)式搜索算法，具有較強(qiáng)的魯棒性，在路徑搜索問題方面獲得了大量的應(yīng)用。但基本蟻群算法在三維環(huán)境下進(jìn)行路徑搜索時(shí)路徑點(diǎn)容易出現(xiàn)發(fā)散現(xiàn)象，為解決該問題，本文提出了一種改進(jìn)的蟻群算法來完成線纜的路徑規(guī)劃，通過引入重力規(guī)則來對(duì)路徑點(diǎn)進(jìn)行約束，讓線纜路徑點(diǎn)滿足貼壁規(guī)則，然后在抽象化的求解空間里，運(yùn)用改進(jìn)的蟻群算法進(jìn)行路徑搜索，從而規(guī)劃出一條合理的布線路徑。為了對(duì)本文算法進(jìn)行測試和驗(yàn)證，通過實(shí)例模型和實(shí)驗(yàn)作了仿真分析。

2 問題描述

布線路徑的求解是線纜布線問題的核心，即在三維環(huán)境中求解出一條連接起始點(diǎn)和終點(diǎn)，并滿足布線規(guī)范的通路。線纜的路徑求解也可以看作碰撞球干涉檢測問題，即在三維環(huán)境中，以路徑離散點(diǎn)為球心，線纜直徑為球直徑，進(jìn)行碰撞球干涉檢測。如果碰撞球在沿路徑進(jìn)行掃掠時(shí)，不與環(huán)境中的障礙物發(fā)生干涉或碰撞，那么這條路徑是安全可靠的。為獲取布線空間的環(huán)境信息，首先需要對(duì)布線空間進(jìn)行環(huán)境建模，建立障礙物和路徑點(diǎn)的抽象模型；為解決基本蟻群算法在三維環(huán)境下進(jìn)行路徑搜索時(shí)路徑點(diǎn)的發(fā)散性，引入重力規(guī)則來對(duì)路徑點(diǎn)進(jìn)行約束，讓線纜路徑點(diǎn)滿足貼壁規(guī)則，然后在抽象化的求解空間里，運(yùn)用改進(jìn)的蟻群算法進(jìn)行路徑搜索，從而規(guī)劃出一條合理的布線路徑。圖1給出了基于改進(jìn)蟻群算法的線纜路徑規(guī)劃技術(shù)總體思路。

圖1 基于改進(jìn)蟻群算法的線纜路徑規(guī)劃技術(shù)總體思路

3 布線空間環(huán)境建模

3.1 分段式空間劃分

在復(fù)雜機(jī)電產(chǎn)品中，由于結(jié)構(gòu)件的種類繁多，大小形狀不一，使得布線空間不規(guī)則，因此需要對(duì)布線環(huán)境進(jìn)行三維空間環(huán)境建模。首先對(duì)布線空間進(jìn)行網(wǎng)格化，將三維空間抽象為包含幾何模型空間位置信息的節(jié)點(diǎn)，這樣可以更有效地描述線路可能經(jīng)過的空間點(diǎn)。需要指出的是，如果對(duì)整個(gè)布線空間進(jìn)行柵格化，當(dāng)空間模型較大時(shí)，將會(huì)占用較大的計(jì)算存儲(chǔ)空間，從而降低計(jì)算效率。因此，為提高算法效率，先對(duì)布線空間進(jìn)行分段式劃分，然后再對(duì)特定的空間區(qū)域進(jìn)行柵格化，而不是對(duì)整個(gè)空間進(jìn)行柵格劃分。

將布線空間劃分為若干個(gè)子空間的并集：A=A1?A2?A3?…,其中A表示整個(gè)布線空間，Ai(i=1,2,3…)為劃分出的各個(gè)子空間，如圖2所示。當(dāng)Ai為線纜布線的固定路徑段時(shí)（如線纜的固定卡槽等），線纜經(jīng)過這段區(qū)域?qū)⒕哂兄苯舆B通性，在進(jìn)行路徑搜索時(shí)可以跳過該區(qū)域。A3作為集線器，當(dāng)線纜經(jīng)過該結(jié)構(gòu)時(shí)，該路徑段可以看作入口端T1和出口端T2的直接連通，在求解S1S2之間的布線路徑時(shí)，無需在此路徑段作過多的算法耗費(fèi)。這樣S1S2之間的路徑搜索可以簡化為S1T1與S2T2兩段的布線路徑搜索，A1?A2便是本文算法的求解空間。通過對(duì)求解空間進(jìn)行柵格化劃分將大大節(jié)約算法的存儲(chǔ)空間。

圖2 布線空間的分段式劃分示意圖

3.2 布線空間柵格化

本文采用文獻(xiàn)[14]提出的空間等分網(wǎng)格法。如圖3所示，首先從產(chǎn)品結(jié)構(gòu)模型中抽象出三維空間模型，將左下角的頂點(diǎn)作為三維空間的坐標(biāo)原點(diǎn)A，在點(diǎn)A中建立三維坐標(biāo)系A(chǔ)-xyz。在該坐標(biāo)系中以A為頂點(diǎn)，沿x軸方向取產(chǎn)品三維結(jié)構(gòu)模型的最大長度AB，沿y軸方向取產(chǎn)品三維結(jié)構(gòu)模型的最大長度AA′，沿z軸方向取產(chǎn)品三維結(jié)構(gòu)模型的最大長度AD，由此構(gòu)造包含產(chǎn)品三維結(jié)構(gòu)模型的立方體區(qū)域ABCD-A′B′C′D′，該區(qū)域即為三維布線路徑的規(guī)劃空間，如圖3（a）所示。為得到抽象環(huán)境模型，需在上述規(guī)劃空間ABCDA′B′C′D′的基礎(chǔ)上進(jìn)行等分操作：沿邊 AB 進(jìn)行 n 等分，得到n+1個(gè)平面Πi(i=0,1,2,…,n)，然后對(duì)這n+1個(gè)平面沿邊AD進(jìn)行m等分，沿邊AA′進(jìn)行l(wèi)等分，并且求解出里面的交點(diǎn)，平面劃分如圖3（b）所示。

圖3 三維空間環(huán)境建模過程

4 基于改進(jìn)蟻群算法的線纜路徑規(guī)劃

4.1 基本蟻群算法

蟻群算法是由Dorigo提出的一種群體智能算法，描述了螞蟻在蟻巢和食物之間尋找出最短路徑的合作行為，螞蟻之間通過信息素的濃度來選擇行駛路徑，該算法具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制、易與其他方法結(jié)合等優(yōu)點(diǎn)[15]。

螞蟻的移動(dòng)方向是根據(jù)各條路徑上信息素的量來決定的，同時(shí)根據(jù)信息素的量和啟發(fā)信息來計(jì)算狀態(tài)轉(zhuǎn)移概率。位于節(jié)點(diǎn)i的螞蟻通過公式（1）給出的規(guī)則選擇下一個(gè)將要移動(dòng)到的節(jié)點(diǎn) j：

其中S根據(jù)公式（2）得到：

其中q是在[0,1]區(qū)間均勻分布的隨機(jī)數(shù)；q0的大小決定了利用先驗(yàn)知識(shí)與探索新路徑之間的相對(duì)重要性；i、j分別是某一段路徑的起點(diǎn)和終點(diǎn)；ηij=1/dij為能見度，是兩節(jié)點(diǎn)i和 j路徑距離的倒數(shù)；τij(t)為時(shí)間t時(shí)由i到 j的信息素強(qiáng)度；allowedk為尚未訪問過的節(jié)點(diǎn)集合；α,β為兩常數(shù)，分別表示信息素和能見度的加權(quán)值。上述狀態(tài)轉(zhuǎn)移規(guī)則被稱為偽隨機(jī)比例規(guī)則。每只螞蟻在走完一步或者到達(dá)目標(biāo)點(diǎn)之后需要對(duì)信息素進(jìn)行更新，路徑( )i,j上信息素按式（3）和（4）進(jìn)行更新：

其中0＜ρ≤1為信息素的蒸發(fā)率，Δτij為第k只螞蟻在路徑i到 j所留下來的信息素。

4.2 線纜路徑規(guī)劃

線纜作為具有一定質(zhì)量的實(shí)體，在實(shí)際敷設(shè)中，線纜的敷設(shè)路徑不可能出現(xiàn)沒有附著面的懸空現(xiàn)象。線纜的敷設(shè)一般需要依附于一定的實(shí)體表面，即有種“重力趨勢”貼近物體表面。如圖4所示，（1）路徑中出現(xiàn)懸空的路徑段，路徑規(guī)劃不合理；（2）路徑考慮線纜自重，敷設(shè)路徑全程依附于物體表面，符合實(shí)際規(guī)范，為優(yōu)質(zhì)解。故在三維環(huán)境中定義重力吸引規(guī)則（gravity attraction rule），讓線纜路徑規(guī)劃時(shí)的空間姿態(tài)更滿足實(shí)際情況。

圖4 重力規(guī)則示意圖

在對(duì)線纜或者管路自動(dòng)敷設(shè)路徑求解時(shí)，通常的研究方法是先用智能算法求解出線纜起始點(diǎn)至終點(diǎn)的通徑，然后將“貼壁”等諸多規(guī)則作為路徑優(yōu)化的約束條件，以達(dá)到敷設(shè)線纜實(shí)際敷設(shè)規(guī)范的走線路徑，而本文是在研究線纜實(shí)際敷設(shè)時(shí)的空間姿態(tài)基礎(chǔ)上，將“貼壁”以重力約束的形式，直接融合到蟻群算法中，而非將其作為約束條件再對(duì)走線路徑進(jìn)行二次優(yōu)化。

將螞蟻看作有“質(zhì)量”的實(shí)體，則其運(yùn)動(dòng)軌跡必須依附于一定的物體表面或者在地面活動(dòng)，在選擇路徑點(diǎn)時(shí)不僅需要考慮避障，還需考慮路徑點(diǎn)的實(shí)際位置。根據(jù)重力場的概念：其中，mant表示螞蟻的質(zhì)量，m0表示網(wǎng)格點(diǎn)的質(zhì)量，r表示螞蟻與可視域內(nèi)網(wǎng)格點(diǎn)的距離，k、f表示引力系數(shù)。

定義障礙物表面與地面的重力場值為：

將每個(gè)網(wǎng)格點(diǎn)看作單位質(zhì)量的點(diǎn)，則m0=1；將螞蟻看作單位質(zhì)量的螞蟻，則mant=1；當(dāng)網(wǎng)格點(diǎn)位于障礙物表面時(shí)，為了防止出現(xiàn)分母為0的情況，故在分母中加1；則重力可看作為：

引力隨著距離的變化呈現(xiàn)拋物線式的變化，隨著越來越靠近目標(biāo)物體，則引力急劇增加，所以引力場也可以表示為：

其中q=(i , j,k)表示任意路徑點(diǎn)的位置，dobs&gro為當(dāng)前節(jié)點(diǎn)垂直方向上距離最近障礙物或地面的距離，且有：

在建立布線空間的抽象化模型時(shí)，對(duì)障礙物進(jìn)行了“膨化”處理，螞蟻在障礙物表面進(jìn)行路徑搜索時(shí)，布線路徑與障礙物不會(huì)發(fā)生干涉。G的值按以下情況確定：

（1）當(dāng)螞蟻在障礙物表面或者地表上運(yùn)動(dòng)時(shí)，G=0；

（2）當(dāng)螞蟻在自由位置點(diǎn)時(shí)，G=∞。

螞蟻朝目標(biāo)點(diǎn)運(yùn)動(dòng)，也可看作是一種趨向性運(yùn)動(dòng)，故定義目標(biāo)點(diǎn)的引力場為：

其中ddes=‖q- qdes‖,qdes代表目標(biāo)點(diǎn)，ddes即當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的歐氏距離。重力場的吸引可以表示為：

4.2.1 搜索策略

如圖5所示，若當(dāng)前點(diǎn)為 pnow(i , j,k)，而平面α為螞蟻搜索下一路徑點(diǎn)的所在平面，則可供選擇的下一路徑點(diǎn)的集合為：

圖5 允許列表示意圖

根據(jù)每個(gè)網(wǎng)格節(jié)點(diǎn)的信息，選取安全的節(jié)點(diǎn)寫入允許列表allowed中。

在改進(jìn)的蟻群算法中，第k只螞蟻從節(jié)點(diǎn)i轉(zhuǎn)移到下一路徑點(diǎn) j的選擇概率為：

傳統(tǒng)的蟻群算法的啟發(fā)信息ηij為該節(jié)點(diǎn)到目標(biāo)點(diǎn)距離的倒數(shù)，距離目標(biāo)點(diǎn)越近ηij的值越大。而使用G(q)不僅使路徑點(diǎn)的選擇更傾向于地表或障礙物表面，而且還能加強(qiáng)算法在獲取最優(yōu)解時(shí)的收斂性。

4.2.2 信息素的表示及更新策略

布線求解空間是由網(wǎng)格節(jié)點(diǎn)表征的，這些網(wǎng)格節(jié)點(diǎn)即為蟻群算法進(jìn)行路徑搜索的路徑點(diǎn)。如果將各個(gè)離散點(diǎn)間的連接線段作為信息素的連接載體，則會(huì)大大增加算法的空間復(fù)雜度。為避免這種情況，本文使用節(jié)點(diǎn)表示法：將信息素儲(chǔ)存在環(huán)境模型的離散點(diǎn)上，任意點(diǎn)對(duì)應(yīng)一個(gè)信息素值，而信息素量的大小代表了該離散點(diǎn)對(duì)螞蟻的吸引程度。這種信息素的表示方法將大大降低算法的空間復(fù)雜度[16]。信息素的更新采用局部更新和全局更新相結(jié)合的更新規(guī)則。當(dāng)螞蟻選定下一個(gè)路徑點(diǎn)(i , j,k)時(shí)，按公式（15）立即更新該路徑點(diǎn)上的信息素值：

其中，0＜ε＜1，ε為一常數(shù)。τ0為原始信息素值。

當(dāng)一次迭代完成，找出本次迭代所得出的最優(yōu)路徑后，對(duì)該路徑進(jìn)行信息素更新：

lbest為最優(yōu)路徑的長度值。

5 算法測試與仿真

測試時(shí)基于如下運(yùn)行環(huán)境：Intel Core i7-3770，3.40 GHz處理器；內(nèi)存為4 GB；操作系統(tǒng)為Win7；仿真軟件為MATLAB R2012b。

實(shí)驗(yàn)1對(duì)本文所提出的重力吸引規(guī)則進(jìn)行仿真實(shí)驗(yàn)，并和沒有使用該規(guī)則的蟻群算法進(jìn)行了對(duì)比，以驗(yàn)證該方法的有效性和實(shí)用性。

建立兩障礙物的空間模型，中心坐標(biāo)分別為（40，420，75）和（450，40，40）；兩障礙物的長寬高分別為（80，80，150）和（100，80，80）。起始點(diǎn)和終點(diǎn)的位置分別為（0，425，150）和（500，0，80）。表1給出了本次實(shí)驗(yàn)中所使用蟻群算法的主要參數(shù)。

表1 參數(shù)設(shè)置

圖6 實(shí)驗(yàn)1仿真結(jié)果

從圖6的仿真結(jié)果中可以看出，將基本蟻群算法直接應(yīng)用到三維空間的線纜敷設(shè)時(shí)，雖然能搜索出一條連接起始點(diǎn)且不與障礙物發(fā)生干涉的布線路徑，但是路徑點(diǎn)大多處于自由狀態(tài)，這不符合實(shí)際布線的規(guī)范和標(biāo)準(zhǔn)。而結(jié)合重力規(guī)則的蟻群算法所搜索出的路徑始終依附于固定面，布線路徑更加符合線纜敷設(shè)的實(shí)際規(guī)范，路徑規(guī)劃效果較好。

實(shí)驗(yàn)2對(duì)本文所給出的算法進(jìn)行仿真。建立障礙物的包圍盒模型，中心位置和長寬高分別如表2所示，其他參數(shù)設(shè)置參照實(shí)驗(yàn)1中的數(shù)據(jù)。

表2 障礙物模型參數(shù)

圖7（a）、（b）分別從主視圖和俯視圖展示了實(shí)驗(yàn)2仿真的結(jié)果；圖7（c）為算法所對(duì)應(yīng)的適應(yīng)度變化曲線圖。從圖7中可以看出，在多障礙物的環(huán)境模型下，改進(jìn)蟻群算法能較快地搜索出一條安全、合理的布線路徑。三維環(huán)境下重力規(guī)則的應(yīng)用，使得整個(gè)布線路徑都依附于一定的平面，進(jìn)一步驗(yàn)證了改進(jìn)算法的優(yōu)越性。

蟻群算法作為群體智能算法，在路徑點(diǎn)的選取中采用可視域內(nèi)的啟發(fā)式搜索，求解出的不一定是全局最優(yōu)路徑，但卻是符合線纜實(shí)際規(guī)范的可行解。線纜的自動(dòng)敷設(shè)設(shè)計(jì)主要是為線纜的實(shí)際敷設(shè)提供一個(gè)可行、優(yōu)化的敷設(shè)方案，即在特定的應(yīng)用環(huán)境或者工作條件下使線纜滿足敷設(shè)的約束條件，最短路徑不一定就是最優(yōu)路徑。在圖7（b）中綠色虛線表示連接S、T之間的理論最優(yōu)路徑，雖然滿足最短路徑，但是橫跨空間模型的路線，占據(jù)了很大的空間，而且在線纜的實(shí)際敷設(shè)過程中也不方便固定，而采用改進(jìn)算法求解出的圖中紅色路徑雖然犧牲了線纜長度，但更滿足貼壁的約束規(guī)范，有利于卡箍的裝配和線纜的固定等操作。本文算法求解得出的路徑并不是直接作為線纜的實(shí)際敷設(shè)的最終路徑，還應(yīng)對(duì)路徑點(diǎn)進(jìn)行選取，使線纜達(dá)到平滑順直的空間布局姿態(tài)。圖7（d）所示的電器柜模型中線纜實(shí)際走線路徑圖，紅色線纜所表示的路徑2雖然達(dá)到了路徑最短，但是多數(shù)路徑點(diǎn)處于懸空位置，并不符合線纜的空間物理姿態(tài)，而且空間占據(jù)大，不便于設(shè)備的維護(hù)操作。藍(lán)色線纜所表示的路徑1雖然長度較長，但是走線依附于機(jī)柜壁板，這樣有利于后續(xù)卡箍等緊固件的安裝，路徑1的走線方式相比較之下更為合理。

6 結(jié)束語

（1）本文針對(duì)線纜敷設(shè)問題，提出了一種基于改進(jìn)蟻群算法的線纜路徑規(guī)劃方法，通過在算法中引入重力規(guī)則，能夠較好地完成線纜路徑的搜索；對(duì)所提出的方法進(jìn)行了仿真驗(yàn)證，取得了良好的效果。

圖7 實(shí)驗(yàn)2仿真結(jié)果

（2）三維空間的網(wǎng)格化建模，存在模型的計(jì)算量和存儲(chǔ)量較大的缺點(diǎn)。網(wǎng)格的劃分越細(xì)則空間的抽象化表示越精確，但數(shù)據(jù)量也會(huì)隨之急劇增大。如何權(quán)衡考慮空間精確化和數(shù)據(jù)量之間的矛盾，是下一步將要進(jìn)行的研究工作。

（3）本文所給出的算法并未考慮到線纜的機(jī)械性能和電氣性能，如何考慮多約束條件下的線纜三維路徑規(guī)劃技術(shù)也是下一步要研究的內(nèi)容。

：

[1]寧汝新，劉檢華，唐承統(tǒng)，等.虛擬裝配技術(shù)及其應(yīng)用[J].國防制造技術(shù)，2009，4（2）：22-29.

[2]尚煒，寧汝新，劉檢華，等.復(fù)雜機(jī)電產(chǎn)品中的柔性線纜裝配過程仿真技術(shù)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2012，24（6）：822-831.

[3]孔瑞蓮.航空發(fā)動(dòng)機(jī)可靠性工程[M].北京：航空工業(yè)出版社，2006.

[4]王發(fā)麟，廖文和，郭宇，等.線纜虛擬裝配關(guān)鍵技術(shù)研究現(xiàn)狀及其發(fā)展[J].中國機(jī)械工程，2016，27（6）：839-851.

[5]Park H，Lee H，Cutkosky M R.Computational support for concurrent engineering of cable harness[C]//Proceedings of the International Computers in Engineering Conference and Exhibit，San Francisco，USA，1992：261-268.

[6]Conru A B.A genetic approach to the cable harness routing problem[C]//Proceedings of the IEEE Conference on Evolutionary Computation，Orlando，USA，1994：200-205.

[7]Ilknur K，Russell G，Ming C，et al.Cable route planning in complex environments using constrained sampling[C]//Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling，2007：395-402.

[8]韓明晶.基于A*算法的電子制造裝備布線研究[D].武漢：華中科技大學(xué)，2009.

[9]白曉蘭，張禹.航空發(fā)動(dòng)機(jī)管路智能布局[J].機(jī)械設(shè)計(jì)與制造，2013（9）：56-59.

[10]蔡毅，王彥偉，黃正東.基于UG的三維電氣自動(dòng)布線技術(shù)研究[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（8）：68-72.

[11]王成恩，柳強(qiáng)，白曉蘭，等.航空發(fā)動(dòng)機(jī)復(fù)雜約束空間內(nèi)管路敷設(shè)技術(shù)[J].計(jì)算機(jī)集成制造系統(tǒng)，2010，16（11）：2327-2332.

[12]徐聯(lián)杰，劉檢華，何永熹，等.一種基于改進(jìn)快速搜索隨機(jī)樹算法的管路自動(dòng)布局方法[J].圖學(xué)學(xué)報(bào)，2016，37（1）：1-10.

[13]吳宏超，劉檢華，唐承統(tǒng)，等.基于改進(jìn)A*算法的管路自動(dòng)布局設(shè)計(jì)與優(yōu)化方法[J].計(jì)算機(jī)集成制造系統(tǒng)，2016，22（4）：945-954.

[14]胡小兵，黃席樾.基于蟻群算法的三維空間機(jī)器人路徑規(guī)劃[J].重慶大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，27（8）：132-135.

[15]Dorigo M，Gambardella L M.Ant colonies for the traveling salesman problem[J].BioSystems，1997，43（2）：73-81.

[16]劉利強(qiáng)，于飛，戴運(yùn)桃.基于蟻群算法的水下潛器三維空間路徑規(guī)劃[J].系統(tǒng)仿真學(xué)報(bào)，2008，20（14）：3712-3716.