熊 勇，張 加，余嘉俊，張本任，梁萱卓，朱奇舸

（1.武漢理工大學(xué)航運(yùn)學(xué)院，武漢 430063；2.湖北省內(nèi)河航運(yùn)技術(shù)重點(diǎn)實(shí)驗(yàn)室（武漢理工大學(xué)），武漢 430063；3.國(guó)家水運(yùn)安全工程技術(shù)研究中心（武漢理工大學(xué)），武漢 430063）

（*通信作者電子郵箱1195574893@qq.com）

0 引言

管路布局問題涉及到各個(gè)領(lǐng)域，如化工廠管路、自來水管路、船舶管路、飛機(jī)管路等，管路設(shè)計(jì)是系統(tǒng)設(shè)計(jì)中極為關(guān)鍵的一步，良好的管路布局設(shè)計(jì)，對(duì)于保證系統(tǒng)的可靠性、穩(wěn)定性、安全性等有著至關(guān)重要的意義。

船舶管路具有復(fù)雜龐大、空間有限、規(guī)則約束繁多、連接附件種類多樣等特點(diǎn)，依靠人工敷設(shè)，難度大、耗時(shí)長(zhǎng)且管路布局質(zhì)量難以保證，隨著計(jì)算機(jī)技術(shù)和人工智能算法的不斷發(fā)展，實(shí)現(xiàn)管路自動(dòng)布局成為可能。國(guó)內(nèi)外學(xué)者在管路自動(dòng)布局問題上給出了許多解決方法，主要分為啟發(fā)式搜索算法和非啟發(fā)式搜索算法，啟發(fā)式搜索算法包括遺傳算法［1-2］、蟻群算法［3-4］（Ant Colony，ACO）、粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［5］等，非啟發(fā)式搜索算法包括迷宮算法［6］、逃逸算法［7］、A*算法［8］等，Park［9］采用單元生成法對(duì)船舶管路的布局問題進(jìn)行研究；Guirardello 等［10］提出一種解決化工廠管路布局優(yōu)化方法；Van de Velden 等［11］對(duì)飛機(jī)管路進(jìn)行了研究，建立了搜索空間內(nèi)的三維結(jié)構(gòu)和障礙物網(wǎng)格，獲取滿足相關(guān)規(guī)則和約束的最短路徑；樊江等［12］應(yīng)用迷宮算法對(duì)分支管路端點(diǎn)進(jìn)行串行連接，達(dá)到了一定的效果，卻不能保證最優(yōu)解；Wang 等［13］提出了一種人機(jī)協(xié)作改進(jìn)的蟻群優(yōu)化算法，該算法不僅提高了收斂速度，而且提高了搜索效率；隋海騰等［14］將迷宮算法與遺傳算法相結(jié)合，研究了船舶管路的優(yōu)化設(shè)計(jì)，通過仿真實(shí)驗(yàn)表明方法的可行性；Jiang 等［15］設(shè)計(jì)了基于粒子群和蟻群混合算法的船舶機(jī)艙規(guī)劃方法，該方法考慮設(shè)備布置和管路敷設(shè)兩者之間的耦合作用，從而獲得整體最優(yōu)的設(shè)計(jì)方案；董宗然等［16］提出一種基于最短路徑快速算法的船舶管路自動(dòng)敷設(shè)方法，將網(wǎng)格能量值引入距離松弛函數(shù)，將可以通過網(wǎng)格能量描述的布置約束考慮其中，并分別給出了單管路和分支管路的敷設(shè)方法；柳強(qiáng)等［17］提出基于多目標(biāo)粒子群優(yōu)化（Muti-Objective Partical Swarm Optimization，MOPSO）的航空發(fā)動(dòng)機(jī)分支管路多目標(biāo)布局優(yōu)化方法，給出一種分支管路平滑度計(jì)算方法，結(jié)合非支配排序和網(wǎng)格密度計(jì)算完成個(gè)體多目標(biāo)評(píng)價(jià)?，F(xiàn)有的管路自動(dòng)敷設(shè)方法為船舶管路自動(dòng)敷設(shè)問題做出了十分有益的探索，但船舶管路的自動(dòng)敷設(shè)問題仍有以下問題需要深入研究：1）船舶管路往往復(fù)雜而龐大，當(dāng)障礙物增多時(shí)，容易導(dǎo)致算法陷入局部最優(yōu)解，甚至?xí)霈F(xiàn)無法搜索到路徑的情況，算法的搜索效率和成功率也會(huì)急劇降低，因此，當(dāng)出現(xiàn)多個(gè)障礙物時(shí)，如何能夠獲得最優(yōu)解并且保證算法的搜索效率和成功率仍需要深入研究；2）船舶管路敷設(shè)規(guī)則繁多，并且很多規(guī)則難以進(jìn)行量化，導(dǎo)致管路布局方案無法應(yīng)用于實(shí)際工程，因此，如何獲得滿足工程規(guī)則的最優(yōu)管路布局方案，需要進(jìn)一步深入研究。

蟻群算法［18］是一種模擬螞蟻覓食行為的模擬優(yōu)化算法，具有較強(qiáng)的魯棒性和自適應(yīng)性，并且易與其他算法結(jié)合，較適合于解決組合優(yōu)化問題，在解決路徑規(guī)劃問題上有著良好的表現(xiàn)，但蟻群算法也有自身的局限性，在解決大規(guī)模、復(fù)雜約束、障礙物較多的路徑規(guī)劃問題上，易出現(xiàn)無法快速地搜索到最優(yōu)路徑、收斂速度下降、局部最優(yōu)解等情況?？焖贁U(kuò)展隨機(jī)樹算法（Rapidly-exploring Random Tree，RRT）［19］通過對(duì)狀態(tài)空間中的采樣點(diǎn)進(jìn)行碰撞檢測(cè)，避免了對(duì)空間的建模，能夠有效地解決高維空間和復(fù)雜約束的路徑規(guī)劃問題，在含有多個(gè)障礙物的空間內(nèi)也能夠快速有效地搜索到可行路徑。因此，針對(duì)三維管路布局問題，對(duì)蟻群算法和RRT 算法進(jìn)行改進(jìn)并將兩種算法進(jìn)行結(jié)合，利用RRT 算法較強(qiáng)的路徑搜索能力進(jìn)行路徑的搜索，再用蟻群算法進(jìn)行循環(huán)迭代優(yōu)化，在選擇最優(yōu)路徑時(shí)，對(duì)船舶管路敷設(shè)規(guī)則中較為主要的規(guī)則進(jìn)行了量化處理，建立優(yōu)化評(píng)價(jià)函數(shù)，綜合考慮各種管路敷設(shè)的工程規(guī)則，以期得到滿足實(shí)際工程的最優(yōu)管路布局方案。

1 問題描述

船舶三維管路布局問題，實(shí)則是一種三維空間下的多目標(biāo)、多約束路徑規(guī)劃問題。如圖1 所示，空間C為管路布局空間，Ob1、Ob2、Ob3、Ob4、Ob5為布局空間內(nèi)障礙物，Start和Goal分別為管路的起點(diǎn)和終點(diǎn)，布局優(yōu)化問題即為找到連接點(diǎn)Start和點(diǎn)Goal的路徑，并且不與障礙物發(fā)生碰撞，同時(shí)需要滿足路徑短、彎頭少、走直線等要求的路徑規(guī)劃問題。

圖1 管路布局空間Fig.1 Pipe layout space

1.1 布局空間與敷管規(guī)則描述

建立布局空間是將三維實(shí)體進(jìn)行數(shù)學(xué)形式的表達(dá)，采用軸平行包圍盒（Aixe Align Bounding Box，AABB）的方法對(duì)三維實(shí)體進(jìn)行包絡(luò)，實(shí)體的長(zhǎng)寬高分別為l×w×h，定義管路布局空間的大小，管路必須在布局空間內(nèi)，對(duì)管路布局的區(qū)域進(jìn)行限定，則有0 ≤x≤l，0 ≤y≤w，0 ≤z≤h，(x，y，z)為布局空間內(nèi)的任意一點(diǎn)坐標(biāo)，為方便表達(dá)將布局空間進(jìn)行離散化，將其離散化為l×w×h個(gè)點(diǎn)；布局空間分為可布管空間和障礙物空間，對(duì)存在障礙的空間進(jìn)行標(biāo)記，障礙物的標(biāo)記同樣也采用區(qū)域限定的方式，建立障礙物集合如下：

沒有進(jìn)行標(biāo)記的空間則為可布管空間。

船舶管路布局問題與路徑規(guī)劃問題類似，但不盡相同，船舶管路的敷設(shè)需要綜合考慮多種工程規(guī)則，是一個(gè)具有多目標(biāo)、多約束的復(fù)雜路徑規(guī)劃問題，具體的敷管目標(biāo)和約束如下。

G1：保證管路起點(diǎn)和終點(diǎn)之間的連通性；

G2：不與其他設(shè)備發(fā)生碰撞；

R1：管道長(zhǎng)度盡可能短；

R2：彎頭數(shù)量盡可能少；

R3：管道走直線，不走斜線；

R4：管道盡可能貼近障礙物表面或空間內(nèi)壁；

G1和G2構(gòu)成目標(biāo)集合G={G1，G2}，R1、R2、R3、R4構(gòu)成約束集合R={R1，R2，R3，R4}，管路是由一個(gè)個(gè)節(jié)點(diǎn)連成的線段組成，定義起點(diǎn)坐標(biāo)為(x0，y0，z0)，終點(diǎn)坐標(biāo)(xn，yn，zn)，管路節(jié)點(diǎn)集合的數(shù)學(xué)表達(dá)式 ：path_node={(x0，y0，z0)，(x1，y1，z1)，(x2，y2，z2)，(x3，y3，z3)，…，(xi，yi，zi)}，0 ≤i≤n，針對(duì)上述規(guī)則做如下處理。

1）對(duì)于規(guī)則R1，管路路徑的長(zhǎng)度：path_length=，即讓path_length盡量小。

2）對(duì)于規(guī)則R2，彎頭數(shù)量bend_number的計(jì)算：n1=((xi-xi-1)，(yi-yi-1)，(zi-zi-1))，n2=((xi+1-xi)，(yi+1-yi)，(zi+1-zi))，如果n1*n2=0，則bend_number加1，即保證bend_number盡量小。

3）對(duì)于規(guī)則R3，管道走直線，若當(dāng)前點(diǎn)坐標(biāo)值為(x，y，z)，則下一步可選節(jié)點(diǎn)方向的集合：{(x-1，y，z)，(x，y-1，z)，(x，y，z-1)，(x+1，y，z)，(x，y+1，z)，(x，y，z+1)}，即可保證管道走直線不走斜線。

4）對(duì)于規(guī)則R4，管道上任意一節(jié)點(diǎn)的能量與障礙物的距離d呈反比，能量函數(shù)采用距離，Ei為某一節(jié)點(diǎn)能量常數(shù)。

1.2 建立優(yōu)化評(píng)價(jià)函數(shù)

針對(duì)上述約束集合，建立求解優(yōu)化評(píng)價(jià)函數(shù)，path_length、bend_number和分別表示為管路路徑的總長(zhǎng)度、彎頭的總數(shù)量和總能量值，w1、w2、w3則分別為管道長(zhǎng)度、彎頭數(shù)量和能量值的權(quán)重因子，評(píng)價(jià)函數(shù)Fit如下式所示：

在最優(yōu)路徑的選擇時(shí)，即求解Fit最小時(shí)，管路路徑點(diǎn)的集合則加入到最優(yōu)解集中，再通過循環(huán)迭代優(yōu)化，找到所有滿足目標(biāo)和約束的最小值Fit所對(duì)應(yīng)的管路路徑節(jié)點(diǎn)集合，最后綜合考慮敷管規(guī)則，輸出最優(yōu)布管方案。

2 管路自動(dòng)敷設(shè)算法設(shè)計(jì)

本文將管路敷設(shè)問題分為兩步：第一步，利用RRT 算法在復(fù)雜、多維環(huán)境下較強(qiáng)的路徑搜索能力，搜索可行路徑，并將其存在可行解集中；第二步，采用蟻群算法對(duì)可行解集中的可行路徑進(jìn)行迭代優(yōu)化，尋找最優(yōu)解，并將最優(yōu)解存儲(chǔ)在最優(yōu)解集中，通過對(duì)路徑不斷的迭代優(yōu)化，最后找到綜合最優(yōu)路徑。算法詳細(xì)步驟如下：

步驟1 初始化各項(xiàng)參數(shù)。

步驟2 判斷是否達(dá)到最大迭代次數(shù)，若達(dá)到，輸出全局最優(yōu)路徑，結(jié)束循環(huán)；若沒有達(dá)到，進(jìn)行下一步。

步驟3 確定生長(zhǎng)點(diǎn)，更新各生長(zhǎng)方向上節(jié)點(diǎn)上的信息素濃度。

步驟4 根據(jù)各點(diǎn)的信息素濃度計(jì)算出各個(gè)方向的概率大小，根據(jù)概率的大小選擇下一步的生長(zhǎng)方向Direction，更新生長(zhǎng)點(diǎn)NewPoint=Start+Stepsize*Direction(i)，NewPoint則為新的生長(zhǎng)節(jié)點(diǎn)，更新NewPoint點(diǎn)的信息素濃度。

步驟5 對(duì)新生成的路徑是否與障礙物發(fā)生碰撞進(jìn)行檢測(cè)，如果新的路徑發(fā)生干涉則返回步驟3，然后重新選擇生長(zhǎng)方向，并且把當(dāng)前生長(zhǎng)方向從本次生長(zhǎng)要選擇的方向中刪除，避免再次選擇不可行的方向進(jìn)行生長(zhǎng)；如果新的路徑?jīng)]有發(fā)生干涉，則執(zhí)行下一步。

步驟6 將新的節(jié)點(diǎn)添加至RRTree集合中，并且更新生長(zhǎng)點(diǎn)Start。

步驟7 判斷是否到達(dá)目標(biāo)點(diǎn)，若沒有達(dá)到，則返回步驟3 繼續(xù)尋找路徑；若到達(dá)目標(biāo)點(diǎn)，則說明完成一次路徑搜索，將本次路徑搜索過程中所經(jīng)歷的節(jié)點(diǎn)存在可行解集Path中。

步驟8 派出n只螞蟻，重復(fù)上述步驟3～7，得到n條路徑。

步驟9 建立Fit適應(yīng)度函數(shù)，尋找本輪n只螞蟻尋找的n條路徑中最優(yōu)路徑Bestpath，并更新Bestpath中所有節(jié)點(diǎn)的信息素濃度。

步驟10 更新全局信息素濃度的值，并返回步驟2 進(jìn)行循環(huán)迭代優(yōu)化，直到達(dá)到最大迭代次數(shù)，輸出全局最優(yōu)路徑。算法實(shí)現(xiàn)偽代碼如下：

算法1 管路自動(dòng)布局算法。

輸入：管道起點(diǎn)和終點(diǎn)，布局空間C；

輸出：Bestpath最優(yōu)路徑節(jié)點(diǎn)集合。

2.1 路徑搜索算法設(shè)計(jì)

RRT 算法由Lavalle［20］于1998 年提出，其基本思想是通過隨機(jī)選擇生長(zhǎng)方向，由初始狀態(tài)不斷向外增量式生長(zhǎng)，形成新的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)代表一個(gè)狀態(tài)，最后達(dá)到目標(biāo)點(diǎn)或附近。該方法較常用于機(jī)器人路徑規(guī)劃問題，RRT 算法的優(yōu)勢(shì)在于只要路徑客觀存在，就一定能被找到。

如圖2 所示，Sample為樣本空間，xinit為隨機(jī)樹的起始點(diǎn)，xgoal為終點(diǎn)，xrand為樣本空間中隨機(jī)產(chǎn)生的一點(diǎn)。RRT 算法是通過不斷向外增量式擴(kuò)展來完成隨機(jī)樹的生長(zhǎng)，其中RRT 生長(zhǎng)方向的確定是通過在樣本空間中隨機(jī)選取一點(diǎn)xrand，在已有隨機(jī)樹節(jié)點(diǎn)中尋找距xrand最近點(diǎn)xnear，連接點(diǎn)xnear和xrand，則方向向量XnearXrand為隨機(jī)樹的生長(zhǎng)方向，設(shè)：點(diǎn)xnear和xrand的坐標(biāo)分別為xnear=(x1，y1，z1)、xrand=(x2，y2，z2)，則有：

Stepsize為RRT 算法向外生長(zhǎng)的步長(zhǎng)，則新的葉節(jié)點(diǎn)xnew的求解如下式所示：

圖2 RRT算法示意圖Fig.2 Schematic diagram of RRT algorithm

2.1.1 方向選擇策略

路徑搜索最為關(guān)鍵的問題是下一個(gè)節(jié)點(diǎn)該如何選擇，如果沒有其他約束，當(dāng)處在三維空間的某一個(gè)節(jié)點(diǎn)時(shí)，下一節(jié)點(diǎn)的選擇理論上有無數(shù)個(gè)，但船舶管路的走向不能是無序、雜亂的，在沒有與障礙物發(fā)生干涉時(shí)，管道應(yīng)沿著當(dāng)前方向或垂直方向布管。如圖3 所示，幾何中心點(diǎn)表示當(dāng)前節(jié)點(diǎn)所在位置，下一節(jié)點(diǎn)可選擇的生長(zhǎng)方向有6個(gè)，生長(zhǎng)方向集合為：

在初始化時(shí)，空間內(nèi)的每個(gè)節(jié)點(diǎn)都會(huì)有一個(gè)初始的信息素濃度pheromone，每個(gè)方向被選擇的概率大小：

圖3 方向選擇示意圖Fig.3 Schematic diagram of direction selection

2.1.2 避障策略

在生成新的節(jié)點(diǎn)時(shí)，對(duì)于新節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的連線需要進(jìn)行碰撞檢測(cè)，當(dāng)新生成的節(jié)點(diǎn)路徑不與障礙物發(fā)生干涉，才會(huì)被加入到隨機(jī)樹中，在仿真環(huán)境中對(duì)障礙物進(jìn)行了簡(jiǎn)化處理，障礙物形狀主要為長(zhǎng)方體。

由圖4繞障示意圖可知，與障礙物發(fā)生干涉有兩種情形：

情形一 新生成的節(jié)點(diǎn)在障礙物內(nèi)，則該新生成節(jié)點(diǎn)與上一節(jié)點(diǎn)的連線必會(huì)穿過障礙物；

情形二 新生成的節(jié)點(diǎn)不在障礙物內(nèi)，則該新生成節(jié)點(diǎn)與上一節(jié)點(diǎn)的連線穿過障礙物，如圖3 黑色虛線段所示。針對(duì)上述兩種情形給出如下避障策略：

第一步在管路布局空間中所有的障礙物已經(jīng)經(jīng)過標(biāo)記，被標(biāo)記的障礙物節(jié)點(diǎn)值為1，自由空間節(jié)點(diǎn)值則為0，因此，可以直接判斷新生成的節(jié)點(diǎn)是否在障礙物內(nèi)。

第二步當(dāng)新生成的節(jié)點(diǎn)不在障礙物內(nèi)時(shí)，此時(shí)就需要判斷新生成的節(jié)點(diǎn)的連線是否穿過障礙物，將節(jié)點(diǎn)連線進(jìn)行柵格化離散，然后判斷連線上的點(diǎn)是否在障礙物內(nèi)：若不存在，則新生成節(jié)點(diǎn)滿足要求，可加入隨機(jī)樹中；若存在節(jié)點(diǎn)在障礙物內(nèi)，則認(rèn)為新生成路徑與障礙物發(fā)生干涉，此次生長(zhǎng)失敗，返回重新選擇下一節(jié)點(diǎn)。

圖4 繞障示意圖Fig.4 Schematic diagram of obstacle avoidance

2.1.3 變步長(zhǎng)策略

在路徑搜索過程中，步長(zhǎng)的選擇往往決定了算法的成功率和搜索效率，在傳統(tǒng)的RRT 算法中，往往采用的是定步長(zhǎng)的方式，定步長(zhǎng)的缺陷在于：1）當(dāng)終點(diǎn)與起始點(diǎn)距離不滿足步長(zhǎng)的整數(shù)倍關(guān)系時(shí)，將無法搜索到終點(diǎn)；2）當(dāng)空間環(huán)境中障礙物較為密集時(shí)，采用定步長(zhǎng)可能出現(xiàn)無法繞開障礙物的情況，導(dǎo)致路徑搜索失敗，因此，本節(jié)采用變步長(zhǎng)的策略對(duì)上述問題進(jìn)行規(guī)避，提高算法的成功率和搜索效率，變步長(zhǎng)策略通過引入步長(zhǎng)因子λ對(duì)步長(zhǎng)進(jìn)行動(dòng)態(tài)調(diào)節(jié)，如式（7）所示：

當(dāng)出現(xiàn)以下兩種情況需要對(duì)步長(zhǎng)進(jìn)行調(diào)節(jié)：

1）當(dāng)前節(jié)點(diǎn)與終點(diǎn)間的距離小于設(shè)定的初始步長(zhǎng)Stepsize；

2）當(dāng)前節(jié)點(diǎn)NowPoint和新生成節(jié)點(diǎn)NewPoint連線與障礙物發(fā)生干涉。

假 設(shè)，當(dāng)前節(jié)點(diǎn)NowPoint=(x0，y0，z0) 和下一節(jié)點(diǎn)NewPoint=(xn，yn，zn)連線的方向向量為a=(x0-xn，y0-yn，z0-zn)，當(dāng)前節(jié)點(diǎn)NowPoint和發(fā)生干涉的障礙物距離為Dis，當(dāng)前節(jié)點(diǎn)NowPoint和終點(diǎn)Goal的距離為dis，則步長(zhǎng)因子λ的確定方式如式（8）所示：

當(dāng)上述兩種情況同時(shí)滿足時(shí)，優(yōu)先考慮繞開障礙物Ob，步長(zhǎng)因子。變步長(zhǎng)策略確保了在路徑存在的前提下，算法能夠搜索到從起點(diǎn)到達(dá)終點(diǎn)的路徑，保證了算法的成功率。

上述路徑搜索算法實(shí)現(xiàn)偽代碼如下：

算法2 RRT路徑搜索算法。

輸入：管道起點(diǎn)和終點(diǎn)，布局空間C；

輸出：RRTree路徑節(jié)點(diǎn)矩陣。

2.2 路徑優(yōu)化算法設(shè)計(jì)

2.1 節(jié)利用RRT 算法進(jìn)行了路徑的搜索，RRT 算法的特點(diǎn)是能夠快速、有效地搜索高維空間，通過增量式的不斷生長(zhǎng)，將搜索方向?qū)蚩瞻最I(lǐng)域，但RRT 算法搜索得到的路徑并不能保證最優(yōu)，因此本文將其與蟻群算法進(jìn)行結(jié)合，利用蟻群算法迭代尋優(yōu)能力，不斷對(duì)路徑進(jìn)行優(yōu)化，最后得到最優(yōu)路徑。

2.2.1 選擇概率的計(jì)算

設(shè)螞蟻g當(dāng)前所在位置坐標(biāo)為(x，y，z)，結(jié)合船舶管路三維布局問題，RRT 生長(zhǎng)的方向限定為6 個(gè)，因此，每只螞蟻可選擇的方向有6 個(gè)，在步長(zhǎng)一定的前提下，螞蟻g下一步可選擇的節(jié)點(diǎn)一共有6 個(gè)，如式（9）為下一步可選節(jié)點(diǎn)集合，Stepsize為步長(zhǎng)大?。?/p>

每一個(gè)節(jié)點(diǎn)的概率大小計(jì)算如式（10）所示：

2.2.2 信息素更新

信息素的更新對(duì)于整個(gè)算法的成功率和收斂速度至關(guān)重要，本節(jié)信息素的更新采用局部信息素更新和全局信息素更新相結(jié)合的方式，各條路徑的更新信息素的更新方式如下式所示：

1）局部信息素更新。

假設(shè)螞蟻從節(jié)點(diǎn)i到節(jié)點(diǎn)j，節(jié)點(diǎn)i和j兩點(diǎn)之間路徑的信息素更新公式如式（11）所示：

其中：ξ為局部信息素更新的揮發(fā)率，τ0為信息素的初始值。局部信息素更新可以保證其他路徑被選擇的概率，不至于使某一條路徑上的信息素濃度太大。

2）全局信息素更新。

當(dāng)算法完成一次迭代，按照公式，對(duì)最優(yōu)路徑信息素濃度進(jìn)行更新：

2.2.3 停止準(zhǔn)則

由于采用的使蟻群和RRT 的混合算法進(jìn)行最優(yōu)布管路徑搜索，因此，管路路徑搜索的停止條件包括兩層：1）第一層是由RRT 路徑搜索的停止，當(dāng)某只螞蟻到達(dá)設(shè)定的管道連接點(diǎn)時(shí)，則完成一次路徑的尋找，停止條件如下式所示；2）第二層是蟻群算法路徑優(yōu)化的停止，通過設(shè)定最大迭代次數(shù)使算法停止，當(dāng)?shù)螖?shù)大于設(shè)定最大迭代次數(shù)時(shí)，蟻群路徑優(yōu)化算法停止，停止條件如式（14）～（15）所示：

其中：Nowpoint(i，j，k)為螞蟻實(shí)時(shí)的位置坐標(biāo)，goal(m，n，p)為設(shè)定的目標(biāo)連接點(diǎn)坐標(biāo)，b_number為當(dāng)前迭代次數(shù)，max_number為最大迭代次數(shù)。

算法3 蟻群路徑優(yōu)化算法。

輸入：RRTree路徑節(jié)點(diǎn)矩陣；

輸出：最優(yōu)路徑Bestpath、適應(yīng)度值Fit。

3 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)是在Windows10 系統(tǒng)環(huán)境下，采用Matlab R2016a，對(duì)上述船舶管路自動(dòng)敷設(shè)方法進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)構(gòu)建一個(gè)對(duì)角坐標(biāo)為(0，0，0)和(100，100，100)的管路布局空間，并將空間離散成100 ×100 ×100 個(gè)點(diǎn)，將障礙物簡(jiǎn)化成長(zhǎng)方體形狀，如圖5 所示為空間及障礙物的三維布局顯示圖，障礙物信息如表1所示。

圖5 空間及障礙物布局Fig.5 Space and obstacle layout

表1 障礙物對(duì)角坐標(biāo)Tab.1 Obstacle diagonal coordinates

初始化管道起點(diǎn)Start(1，1，1)和終點(diǎn)Goal(81，81，81)，對(duì)布管空間100 ×100 ×100 個(gè)空間點(diǎn)進(jìn)行信息濃度初始化，按照對(duì)敷管規(guī)則R4 的處理方法，對(duì)空間各點(diǎn)賦予能量值，利用評(píng)價(jià)函數(shù)對(duì)可行解集中路徑的適應(yīng)度值進(jìn)行計(jì)算，在本次實(shí)驗(yàn)盡可能滿足工程約束，并根據(jù)約束的重要程度來確定式（2）中的權(quán)重因子，以所有權(quán)重總和為1 的原則對(duì)權(quán)重因子進(jìn)行分配，根據(jù)多次仿真的結(jié)果，以及綜合實(shí)際船舶管路敷設(shè)工程經(jīng) 驗(yàn)，式（2）中各權(quán)重因子分配情 況：w1=0.05，w2=0.52，w3=0.43，通常蟻群算法中信息素啟發(fā)因子α∈[0，5]、期望啟發(fā)因子β∈[0，5]、局部信息素?fù)]發(fā)率ξ∈[0.1，0.99]、全局信息素?fù)]發(fā)率ρ∈[0.1，0.99]，關(guān)鍵參數(shù)設(shè)置如表2所示。

表2 算法參數(shù)Tab.2 Algorithm parameters

如圖6 所示，黑色點(diǎn)為管道連接起始點(diǎn)，圖6（a）為采用RRT 搜索的初始路徑，從圖6（a）可以看出RRT 較強(qiáng)的路徑搜索能力，能夠讓初始種群搜索的路徑涵蓋空間內(nèi)的大部分區(qū)域，為后續(xù)蟻群算法路徑優(yōu)化奠定基礎(chǔ)；圖6（b）為采用蟻群算法優(yōu)化之后的路徑，從圖6（b）可以看出優(yōu)化之后的路徑較為符合管路敷設(shè)工程規(guī)則，因此，該算法能夠得到在復(fù)雜約束條件下最優(yōu)敷管路徑方案。

圖6 路徑優(yōu)化前后Fig.6 Paths before and after optimization

圖7（a）為ACO與RRT混合算法生成的管道路徑，圖7（b）采用對(duì)比文獻(xiàn)［21］的ACO+PSO 方法算法生成的路徑，7（c）采用對(duì)比文獻(xiàn)［22］的改進(jìn)ACO 方法算法生成的路徑，通過兩種算法生成的路徑進(jìn)行對(duì)比，可以看出ACO 與RRT 混合算法生成的路徑更優(yōu)，且較為符合管路敷設(shè)工程規(guī)則，

圖7 管路自動(dòng)布局結(jié)果Fig.7 Results of automatic pipeline layout

圖8 為三種方法的適應(yīng)度值的變化曲線，由于實(shí)驗(yàn)結(jié)果存在隨機(jī)性，適應(yīng)度值為多次仿真結(jié)果的平均值，采用ACO和RRT結(jié)合的算法迭代次數(shù)平均在11代，對(duì)比文獻(xiàn)［21］中的方法平均迭代次數(shù)為27 代，對(duì)比文獻(xiàn)［22］中的方法平均迭代次數(shù)為18代。

圖8 適應(yīng)度值變化Fig.8 Changes in fitness values

算法詳細(xì)對(duì)比分析表如表3所示。

表3 實(shí)驗(yàn)結(jié)果對(duì)比分析Tab.3 Comparison and analysis of experimental results

從表3中可以看出，在同一布局空間中，ACO和RRT混合算法均能有效搜索到當(dāng)前最優(yōu)路徑，且平均迭代次數(shù)最小，搜索時(shí)間最短：相較于ACO+PSO 算法，本文方法的成功率提升了35 個(gè)百分點(diǎn)，平均運(yùn)行時(shí)間減少94.1%；相較于改進(jìn)ACO算法，本文方法平均運(yùn)行時(shí)間減少78.8%。因此，從實(shí)驗(yàn)結(jié)果來看，基于ACO 和RRT 的混合算法比其他兩種方法具有良好的優(yōu)越性。

圖9 為ACO 和RRT 三維實(shí)體管路布局結(jié)果，在含有多個(gè)障礙物、布管空間有限的情況下，算法能夠搜索到多個(gè)約束條件下的綜合最優(yōu)解，并且算法具有良好的收斂速度和搜索效率，基于ACO 和RRT 的混合算法，能夠很好地求解在多目標(biāo)、多約束下的管路路徑規(guī)劃問題，在實(shí)際工程布管上具有一定的參考作用，但由于仿真建模環(huán)境無法真實(shí)地還原實(shí)際環(huán)境，因此，管路布局結(jié)果與實(shí)際情況仍存在一定偏差。

圖9 三維實(shí)體管路布局Fig.9 3D solid pipeline layout

4 結(jié)語(yǔ)

本文將蟻群算法與快速擴(kuò)展隨機(jī)樹算法進(jìn)行了結(jié)合，提出一種新的船舶管路自動(dòng)敷設(shè)方法，利用快速擴(kuò)展隨機(jī)樹算法在復(fù)雜、多維空間的路徑搜索能力，很好地解決了蟻群算法在多障礙物環(huán)境下，易出現(xiàn)無法搜索到路徑以及容易陷入局部最優(yōu)解等問題，并利用該方法對(duì)單管路自動(dòng)敷設(shè)問題進(jìn)行了仿真實(shí)驗(yàn)，從仿真實(shí)驗(yàn)結(jié)果來看，將兩種算法結(jié)合后，能夠很好地求解多目標(biāo)、多約束的船舶管路路徑規(guī)劃問題，并且算法的收斂速度和成功率有大幅提升。管路敷設(shè)方法同時(shí)考慮了船舶管路敷設(shè)主要的工程規(guī)則，管路自動(dòng)布局結(jié)果能夠?yàn)樵O(shè)計(jì)人員提供多種可行的管路敷設(shè)方案，很好地輔助管路設(shè)計(jì)人員設(shè)計(jì)管路，省去了設(shè)計(jì)人員前期重復(fù)、復(fù)雜的工作步驟。管道布局的理論研究和實(shí)際工程設(shè)計(jì)的主要區(qū)別在于：實(shí)際工程設(shè)計(jì)中，會(huì)給出具體的輸入信息，例如空間大小和障礙物的具體位置，設(shè)計(jì)者會(huì)根據(jù)相關(guān)設(shè)計(jì)手冊(cè)的要求來完成對(duì)應(yīng)管路部分的布局設(shè)計(jì)，通常有約定俗成的設(shè)計(jì)風(fēng)格。但是在理論研究中，由于沒有具體的工程背景，很難實(shí)現(xiàn)量化的真實(shí)案例，且有很多工程約束無法量化成具體形式，因此，仿真環(huán)境中管路自動(dòng)布局結(jié)果與實(shí)際工程要求仍存在偏差，還需要人工經(jīng)驗(yàn)對(duì)布局結(jié)果進(jìn)行修正。后期在此基礎(chǔ)上，可加入專家系統(tǒng)知識(shí)，對(duì)布局結(jié)果進(jìn)行二次評(píng)價(jià)，將專家經(jīng)驗(yàn)知識(shí)融入到管路布局評(píng)價(jià)中，從而實(shí)現(xiàn)船舶管路全智能化布局。該方法也為后續(xù)分支管路和多管路敷設(shè)問題奠定了基礎(chǔ)，同時(shí)，本文方法具有普適性，同樣適應(yīng)于解決類似的路徑規(guī)劃問題，為其提供可供借鑒的思路和方法。