船舶三維管路智能布局優化算法

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

（1.武漢理工大學航運學院，武漢 430063；2.湖北省內河航運技術重點實驗室（武漢理工大學），武漢 430063；3.國家水運安全工程技術研究中心（武漢理工大學），武漢 430063）

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

0 引言

管路布局問題涉及到各個領域，如化工廠管路、自來水管路、船舶管路、飛機管路等，管路設計是系統設計中極為關鍵的一步，良好的管路布局設計，對于保證系統的可靠性、穩定性、安全性等有著至關重要的意義。

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

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

1 問題描述

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

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

1.1 布局空間與敷管規則描述

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

沒有進行標記的空間則為可布管空間。

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

G1：保證管路起點和終點之間的連通性；

G2：不與其他設備發生碰撞；

R1：管道長度盡可能短；

R2：彎頭數量盡可能少；

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

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

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

1）對于規則R1，管路路徑的長度：path_length=，即讓path_length盡量小。

2）對于規則R2，彎頭數量bend_number的計算：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）對于規則R3，管道走直線，若當前點坐標值為(x，y，z)，則下一步可選節點方向的集合：{(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）對于規則R4，管道上任意一節點的能量與障礙物的距離d呈反比，能量函數采用距離，Ei為某一節點能量常數。

1.2 建立優化評價函數

針對上述約束集合，建立求解優化評價函數，path_length、bend_number和分別表示為管路路徑的總長度、彎頭的總數量和總能量值，w1、w2、w3則分別為管道長度、彎頭數量和能量值的權重因子，評價函數Fit如下式所示：

在最優路徑的選擇時，即求解Fit最小時，管路路徑點的集合則加入到最優解集中，再通過循環迭代優化，找到所有滿足目標和約束的最小值Fit所對應的管路路徑節點集合，最后綜合考慮敷管規則，輸出最優布管方案。

2 管路自動敷設算法設計

本文將管路敷設問題分為兩步：第一步，利用RRT 算法在復雜、多維環境下較強的路徑搜索能力，搜索可行路徑，并將其存在可行解集中；第二步，采用蟻群算法對可行解集中的可行路徑進行迭代優化，尋找最優解，并將最優解存儲在最優解集中，通過對路徑不斷的迭代優化，最后找到綜合最優路徑。算法詳細步驟如下：

步驟1 初始化各項參數。

步驟2 判斷是否達到最大迭代次數，若達到，輸出全局最優路徑，結束循環；若沒有達到，進行下一步。

步驟3 確定生長點，更新各生長方向上節點上的信息素濃度。

步驟4 根據各點的信息素濃度計算出各個方向的概率大小，根據概率的大小選擇下一步的生長方向Direction，更新生長點NewPoint=Start+Stepsize*Direction(i)，NewPoint則為新的生長節點，更新NewPoint點的信息素濃度。

步驟5 對新生成的路徑是否與障礙物發生碰撞進行檢測，如果新的路徑發生干涉則返回步驟3，然后重新選擇生長方向，并且把當前生長方向從本次生長要選擇的方向中刪除，避免再次選擇不可行的方向進行生長；如果新的路徑沒有發生干涉，則執行下一步。

步驟6 將新的節點添加至RRTree集合中，并且更新生長點Start。

步驟7 判斷是否到達目標點，若沒有達到，則返回步驟3 繼續尋找路徑；若到達目標點，則說明完成一次路徑搜索，將本次路徑搜索過程中所經歷的節點存在可行解集Path中。

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

步驟9 建立Fit適應度函數，尋找本輪n只螞蟻尋找的n條路徑中最優路徑Bestpath，并更新Bestpath中所有節點的信息素濃度。

步驟10 更新全局信息素濃度的值，并返回步驟2 進行循環迭代優化，直到達到最大迭代次數，輸出全局最優路徑。算法實現偽代碼如下：

算法1 管路自動布局算法。

輸入：管道起點和終點，布局空間C；

輸出：Bestpath最優路徑節點集合。

2.1 路徑搜索算法設計

RRT 算法由Lavalle［20］于1998 年提出，其基本思想是通過隨機選擇生長方向，由初始狀態不斷向外增量式生長，形成新的節點，每個節點代表一個狀態，最后達到目標點或附近。該方法較常用于機器人路徑規劃問題，RRT 算法的優勢在于只要路徑客觀存在，就一定能被找到。

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

Stepsize為RRT 算法向外生長的步長，則新的葉節點xnew的求解如下式所示：

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

2.1.1 方向選擇策略

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

在初始化時，空間內的每個節點都會有一個初始的信息素濃度pheromone，每個方向被選擇的概率大小：

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

2.1.2 避障策略

在生成新的節點時，對于新節點與當前節點的連線需要進行碰撞檢測，當新生成的節點路徑不與障礙物發生干涉，才會被加入到隨機樹中，在仿真環境中對障礙物進行了簡化處理，障礙物形狀主要為長方體。

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

情形一 新生成的節點在障礙物內，則該新生成節點與上一節點的連線必會穿過障礙物；

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

第一步在管路布局空間中所有的障礙物已經經過標記，被標記的障礙物節點值為1，自由空間節點值則為0，因此，可以直接判斷新生成的節點是否在障礙物內。

第二步當新生成的節點不在障礙物內時，此時就需要判斷新生成的節點的連線是否穿過障礙物，將節點連線進行柵格化離散，然后判斷連線上的點是否在障礙物內：若不存在，則新生成節點滿足要求，可加入隨機樹中；若存在節點在障礙物內，則認為新生成路徑與障礙物發生干涉，此次生長失敗，返回重新選擇下一節點。

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

2.1.3 變步長策略

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

當出現以下兩種情況需要對步長進行調節：

1）當前節點與終點間的距離小于設定的初始步長Stepsize；

2）當前節點NowPoint和新生成節點NewPoint連線與障礙物發生干涉。

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

當上述兩種情況同時滿足時，優先考慮繞開障礙物Ob，步長因子。變步長策略確保了在路徑存在的前提下，算法能夠搜索到從起點到達終點的路徑，保證了算法的成功率。

上述路徑搜索算法實現偽代碼如下：

算法2 RRT路徑搜索算法。

輸入：管道起點和終點，布局空間C；

輸出：RRTree路徑節點矩陣。

2.2 路徑優化算法設計

2.1 節利用RRT 算法進行了路徑的搜索，RRT 算法的特點是能夠快速、有效地搜索高維空間，通過增量式的不斷生長，將搜索方向導向空白領域，但RRT 算法搜索得到的路徑并不能保證最優，因此本文將其與蟻群算法進行結合，利用蟻群算法迭代尋優能力，不斷對路徑進行優化，最后得到最優路徑。

2.2.1 選擇概率的計算

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

每一個節點的概率大小計算如式（10）所示：

2.2.2 信息素更新

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

1）局部信息素更新。

假設螞蟻從節點i到節點j，節點i和j兩點之間路徑的信息素更新公式如式（11）所示：

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

2）全局信息素更新。

當算法完成一次迭代，按照公式，對最優路徑信息素濃度進行更新：

2.2.3 停止準則

由于采用的使蟻群和RRT 的混合算法進行最優布管路徑搜索，因此，管路路徑搜索的停止條件包括兩層：1）第一層是由RRT 路徑搜索的停止，當某只螞蟻到達設定的管道連接點時，則完成一次路徑的尋找，停止條件如下式所示；2）第二層是蟻群算法路徑優化的停止，通過設定最大迭代次數使算法停止，當迭代次數大于設定最大迭代次數時，蟻群路徑優化算法停止，停止條件如式（14）～（15）所示：

其中：Nowpoint(i，j，k)為螞蟻實時的位置坐標，goal(m，n，p)為設定的目標連接點坐標，b_number為當前迭代次數，max_number為最大迭代次數。

算法3 蟻群路徑優化算法。

輸入：RRTree路徑節點矩陣；

輸出：最優路徑Bestpath、適應度值Fit。

3 仿真實驗

仿真實驗是在Windows10 系統環境下，采用Matlab R2016a，對上述船舶管路自動敷設方法進行仿真實驗。實驗構建一個對角坐標為(0，0，0)和(100，100，100)的管路布局空間，并將空間離散成100 ×100 ×100 個點，將障礙物簡化成長方體形狀，如圖5 所示為空間及障礙物的三維布局顯示圖，障礙物信息如表1所示。

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

表1 障礙物對角坐標Tab.1 Obstacle diagonal coordinates

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

表2 算法參數Tab.2 Algorithm parameters

如圖6 所示，黑色點為管道連接起始點，圖6（a）為采用RRT 搜索的初始路徑，從圖6（a）可以看出RRT 較強的路徑搜索能力，能夠讓初始種群搜索的路徑涵蓋空間內的大部分區域，為后續蟻群算法路徑優化奠定基礎；圖6（b）為采用蟻群算法優化之后的路徑，從圖6（b）可以看出優化之后的路徑較為符合管路敷設工程規則，因此，該算法能夠得到在復雜約束條件下最優敷管路徑方案。

圖6 路徑優化前后Fig.6 Paths before and after optimization

圖7（a）為ACO與RRT混合算法生成的管道路徑，圖7（b）采用對比文獻［21］的ACO+PSO 方法算法生成的路徑，7（c）采用對比文獻［22］的改進ACO 方法算法生成的路徑，通過兩種算法生成的路徑進行對比，可以看出ACO 與RRT 混合算法生成的路徑更優，且較為符合管路敷設工程規則，

圖7 管路自動布局結果Fig.7 Results of automatic pipeline layout

圖8 為三種方法的適應度值的變化曲線，由于實驗結果存在隨機性，適應度值為多次仿真結果的平均值，采用ACO和RRT結合的算法迭代次數平均在11代，對比文獻［21］中的方法平均迭代次數為27 代，對比文獻［22］中的方法平均迭代次數為18代。

圖8 適應度值變化Fig.8 Changes in fitness values

算法詳細對比分析表如表3所示。

表3 實驗結果對比分析Tab.3 Comparison and analysis of experimental results

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

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

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

4 結語

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