考慮風浪流影響的船舶路徑規劃及算法

謝新連，王余寬,2，何 傲，潘 偉，許小衛

(1. 大連海事大學 綜合運輸研究所，遼寧 大連 116026； 2. 武漢理工大學 航運學院，湖北 武漢 430063)

0 引 言

人工智能技術日益進步，船舶業也向著智能化方向發展，2016年中國船級社頒布的《智能船舶規范》中將航線規劃技術列為船舶智能化的一項重要途徑。為船舶規劃航線，尤其當面臨海上搜救、海上緝私等對時間要求緊迫的任務時，為巡邏船或執法船等規劃出航行耗時短的路徑是必要的。另外，海洋氣象環境會造成船舶失速，此時考慮海洋氣象環境的影響智能規劃航行路徑，則更能提高船舶航行效率，提升船舶智能化水平。

目前，國內外已有大量的船舶路徑規劃研究，主要集中于不考慮海洋氣象環境的研究上。蔣美芝等[1]考慮海上礙航區和船舶經濟效益設計船舶航線，基于柵格環境建模和蟻群算法求解路徑；SONG Rui等[2]針對A*算法求解無人水面艇避障路徑不光滑的問題，對A*算法進行改進并求解獲取了平滑程度較高的路徑；謝新連等[3]將航行經驗轉化為船舶航行規則，利用強化學習和A*算法為受限水域內船舶規劃全局避碰航線；S.M.LEE等[4]考慮船舶排放法規的約束，以航速優化為目標求解不同航段的航法；XIE Lei等[5]設計了一種全局多方向的A*算法，對海上風電場內工作的船舶規劃航線；LIU Yuanchang等[6]應用改進隨機樹算法，以距離最短為目標為船舶設計了平滑性較大的航線；Y. SINGH等[7]考慮了動態礙航物和水流對船舶航行的影響，設計了一種改進A*算法求解船舶避障路徑；H.KIM等[8]針對無人水面艇在風浪流環境中避障航行設計航線，其獲取的路徑轉向點較多不適用于轉向慢或回轉半徑大的船舶。

多數研究未考慮海洋氣象環境或僅考慮海流對船舶航行的影響，綜合考慮風、波浪及水流影響對船舶路徑進行規劃的研究尚少。但實際上，船舶受到風、波浪和水流的干擾后，會出現明顯的失速現象，因此，為船舶規劃能夠避障航行且耗時最短的航線時，考慮風、波浪及水流的影響是必要的。

筆者從3個方面設計船舶路徑優化方案：①分析海洋環境對船舶航行帶來的干擾，設計了考慮風、波浪、水流及安全水深影響的路徑規劃方案；②為提高算法收斂精度和效率，設計了交叉變異算子自適應的改進遺傳算法；③為優化算法運行耗時，對改進的遺傳算法設計主從并行化模型實現模式。通過方案設計和算法優化求解，以提高船舶路徑智能規劃的有效性。

1 風浪流影響

1.1 風浪流干擾力

船舶航行時，風、波浪和水流作用于船體產生阻力，使得船速和航向發生改變。通常，將船舶所受海洋環境阻力分為風力、波浪力和水流作用力，由于實際海況中風和波浪存在的不確定性[9]，船舶受力公式一般通過模擬試驗獲得，即在風洞和水池條件下模擬風浪流環境，計算船舶航行過程受到風浪流的干擾力。

用τwind和τcurrent分別表示船舶所受風和水流的干擾力矢量，二者計算方法為式(1)[10]～式(2)[11]：

(1)

(2)

式中：ρa和ρw分別為空氣和海水密度;AFw和ALw分別為水面以上風的正投影和側投影面積;CXw和CYw分別為X方向和Y方向的風力負荷系數;γrw為風向與船艏的夾角;Vrw為風對船舶的相對速度;AFc和ALc分別為水面以下水流的正投影和側投影面積;CXc和CYc分別為水流作用力沿X方向和Y方向的負荷系數;γrc為水流向與船艏的夾角;Vrc為水流對船舶的相對速度。

實際應用中計算船舶所受X方向和Y方向的風力合力和水流合力，結合式(1)和式(2)計算得式(3)：

(3)

波浪可分為規則波和不規則波，后者存在較大不確定性和計算復雜性[12]，模型僅考慮規則波產生的干擾力。規則波干擾力計算方法中較為常用的是Daidola基于水池船模試驗提出的計算方法如式(4):

(4)

式中：ρa為海水密度;ls為船長；κ2為波浪振幅;γw為波向角;λw為波長;Cw為波浪力負荷系數。

1.2 船舶失速

(5)

船舶受海洋氣象環境影響導致航速變化如圖1，結合速度矢量運算得到船舶受環境影響后的航速v′，用式(6)表示為：

圖1 船舶受風浪流影響示意

(6)

2 路徑規劃方案設計

2.1 方案假設

船舶路徑規劃的目標是在保證船舶航行安全的前提下規劃出一條滿足航行要求(如航行距離最短、航行耗時最短等)的路徑。結合船舶駕駛操作要求，路徑規劃應考慮船舶吃水深及礙航區邊界是否規則等因素。另外考慮到海洋環境的復雜性以及船舶本身的特性，建立以下假設：①水域內風和波浪分別為恒風和規則波；②風浪強度在船舶耐受范圍內；③視水域為二維平面環境，船舶運動忽略高度條件；④船舶在路徑轉向點更改航速不占用時間。

2.2 安全航行水域提取

通常，航行水域內礙航區邊界并不規則，采用Graham凸包算法[13]將原始礙航環境處理為凸多邊形，頂點的數量取決于地圖的比例和大小。另外，為保證船舶不與航行空間內的任何障礙物相撞或過于接近，也不會受水深影響發生擱淺，將礙航區的邊界向外延伸hkm，擴展后覆蓋的水域為航行保護區，如圖2，擴展區以外的水域為安全水域，凸包算法和外延操作過程如式(7):

圖2 擴展保護區示意

(7)

式中:Wk為水域中第k個礙航區;hmin為考慮安全水深的影響需要外延至少hmin才可獲取安全水域;Sk為第k個擴展保護區;dr為所有擴展保護區組成的頂點集合中的第r個頂點。

2.3 航行網絡圖構建

2.3.1 構建Maklink圖

在建立航行水域礙航區凸多邊形模型的基礎上，應用Maklink圖論進行航行環境建模，其步驟為：

步驟1障礙物頂點集合D內所有點兩兩相連，所有連線從短到長排序并組成候選鏈接線集合Φ。

步驟2選擇Φ中的最短線段Φmin。

步驟3判斷該線段與障礙區S是否相交，如果相交則轉向步驟8，如果未相交則轉向步驟4。

步驟4判斷該線段與相應凸多邊形頂點產生的兩個外角是否都≤180°，若是則轉向步驟5，若否則轉向步驟6。

步驟5刪除該頂點的其他鏈接線，轉向步驟9。

步驟6檢查該頂點的其他鏈接線是否都≤180°，若是則轉向步驟7；若否則轉向步驟9。

步驟7刪除該頂點的其他候選鏈接線，轉向步驟9。

步驟8從集合Φ中刪除該線段。

步驟9判斷是否遍歷Φ內所有線段，若是則結束，集合Φ內剩余的線段集合則為生成的Maklink線；若否則轉向步驟2。

經過以上步驟得到礙航區環境，圖3給出2個示例，Maklink線集合M={Mj,j=1,2,…,J}。

圖3 航行網絡

2.3.2 路徑轉向點表達

(8)

(9)

式中：θj∈[0,1],j=1,2,…,J。

由式(9)可知，θj任取一個值則相應產生一個路徑點。因此，即使Maklink線是有限的，但路徑可選擇的轉向點是無限的，所以需要建立最優化數學模型以求解最優路徑點。

2.4 初始路徑規劃

在存在J條Maklink線的航行網絡圖中，每條Maklink線上的點均為候選轉向點，利用 Dijkstra 算法在Maklink圖上生成由點序列集合P={pi,i=1,2,…,I}組成的一條初始船舶避碰路徑，I表示初始路徑點共在I條Maklink線上產生，每個點均為其所在Maklink線的中點，此時θj取值為0.5。集合P內點的個數I小于Maklink線的數量J，基于集合P再求解最優路徑將提升求解效率，用式(10)表示Dijkstra 算法的求解操作：

P={pi,i=1,2,…,I}=Ψ(M,θj),θj=0.5,j=1,2,…,J

(10)

集合P中p1為路徑起始點，pI為目的點，P′={pi,i=2,…,I-1}為所有轉向點集合，各轉向點順序連接組成的航段集合用L={Lg，g=1,2,…,G}表示。結合式(10)和式(9)得初始路徑點序列的坐標，用式(11)表示:

(11)

式中：i=1,2,…,I。

2.5 路徑優化模型

由式(9)和式(10)知(θ1,θ2,…,θI)可以用來映射一組路徑解的位置信息，基于此，考慮風、波浪、水流對船舶航行的影響時，船舶在不同航段的航速發生改變，此時滿足路徑避障且航行耗時最優要求的模型目標函數可表示為式(12)：

(12)

式中：Λθ={θi,θi∈[0,1],i=1,2,…,I}。

1)f1(Lg)為無避碰規則路徑耗時代價目標函數。風、波浪及水流作用下船舶速度不同于靜水航速，船舶于各個航段上的耗時發生改變，設計船舶于航段Lg航行的耗時代價函數為式(13)：

(13)

2)f2(Lg)為船舶路徑碰撞代價目標函數如式(14)：

(14)

式中：Sk為規劃海域中的第k個礙航區；Lg∩Sk≠?為路徑Lg與Sk有交點，此時碰撞代價無窮大，結合目標函數式(12)相當于此航段耗時代價無窮大；若無交點則不會發生碰撞，此時碰撞代價取值為1，相當于此航段產生的碰撞代價對航段耗時不產生影響。

3 算法設計

船舶路徑規劃模型中，每組路徑解對應一組實數解，求解過程即是在其對應的數值空間上尋找最優值的過程。遺傳算法是一種通過模仿自然選擇和自然遺傳學機理而發展起來的隨機化搜索算法，其實數編碼方式也能夠較好地滿足在數值空間上不斷尋優的目標。標準遺傳算法存在一個缺陷，即迭代尋優過程中不能有效地將上一代的優良信息保留至下一代，為此設計了交叉變異概率自適應的遺傳算法，并采取并行式機制實現遺傳算法，以助于提升算法的求解效率。基于改進遺傳算法優化路徑的算法流程圖如圖4。

圖4 基于并行自適應遺傳算法的路徑優化流程

3.1 基于初始解的遺傳算法

路徑規劃模型求解過程中，標準遺傳算法是隨機生成初始字符串種群，其缺陷是產生大量不可行種群導致種群搜索效率較低。因此，將Dijkstra算法規劃的結果作為遺傳算法的初始種群，使所有種群均在可行解的基礎上進化，以此提升求解效率。

3.1.1 遺傳編碼

圖5 染色體結構

(15)

3.1.2 評估適應度

適應度函數是從目標函數中推導出來的，目標函數是進行適當映射的必要條件，在每一代新生種群上評估所有個體的適應度，適應度函數約為船舶從出發點到目的地航行耗時的倒數，如式(16)：

(16)

3.2 算子選擇概率自適應

遺傳算法在迭代尋優時，染色體之間按照一定概率發生交叉變異來生成新解，一般設置染色體發生交叉和變異的概率為固定值，其缺陷是忽視了染色體之間信息優劣差異，使優勢信息和劣勢信息以相同概率進入到下一代中。因此，設計了交叉和變異概率自適應調整辦法，概率自適應規則為當該個體適應度值小于均值時，個體交叉概率α和變異概率β取較大值，否則按照一定方式求取概率值，這種概率選擇方式提高了優勢信息的進化概率，有助于提升求解質量和效率。概率自適應規則具體如式(17)和式(18)：

(17)

(18)

3.3 AGA算法并行化

算法并行化指利用計算機的不同核心單元同時計算程序的各部分，以此減少程序運行時間。由于遺傳算法一次迭代過程中每個染色體的評估都是獨立的，所以每一代染色體的評估都適合并行化[14]。并行式自適應遺傳算法(parallel adaptive genetic algorithm，PAGA)將各個染色體的適應度評估分配到計算機的各個核心上進行計算，這種并行模式也被稱為主從模型并行機制。

主從模型并行機制的理想加速比計算如式(19)：

(19)

式中：γ為并行部分的核心單元數量；ε為串行運算時適應度值計算一次在程序迭代一次過程中的耗時占比。

4 算例仿真

4.1 仿真結果

為驗證路徑規劃方案的有效性，在運行內存為8GB且CPU為Intel core i5-8265u的計算機上仿真。仿真環境以圖3(a)為例，包含5個障礙區，設置水域內風級為5級，水流速為2 m/s，風、波浪和水流方向為北偏東45°，靜水船速為10 m/s，環境負荷參數參照文獻[8]、文獻[10]設置如表1。

表1 算例仿真環境負荷參數

采用并行式自適應遺傳算法為船舶規劃路徑，如圖6可以看出，未對水域內礙航區進行處理時，規劃的路徑穿越可能存在的淺水區等不安全水域，船舶按照此路徑航行可能發生擱淺、觸礁以及與礙航區邊界發生碰撞的情況。經過對水域內礙航區適當處理后獲得安全航行水域，此時規劃的路徑完全避開了可能發生擱淺等危險的水域。

圖6 安全航行水域規劃路徑

圖7中給出考慮與未考慮風浪流干擾情況下規劃的路徑。考慮風浪流后路徑航行里程有所增加，但航行耗時從378.35 s下降到354.80 s，說明優化后的路徑一定程度上規避了環境帶來的干擾。另外，針對考慮風浪流與未考慮風浪流兩種情況下，采用可視圖法、蟻群算法(ant clony optimization，ACO)、標準遺傳算法(genetic algorithm，GA)和自適應遺傳算法(adaptive genetic algorithm，AGA)分別求解，路徑如圖8，航程耗時見表2。

圖7 風浪流干擾下規劃路徑對比

圖8 考慮風浪流后不同算法規劃路徑

考慮風浪流后，利用可視圖法規劃出的路徑航程與未考慮風浪流求解結果均為2 425.2 m，結合路徑結果對比后發現與未考慮風浪流時為同一條路徑，分析其原因在于可視圖法不同于其它3種智能優化算法，可視圖法的可行路徑解集由安全水域的邊界點之間相互連接組成，可供選擇的路徑有限，而海洋環境的影響有時不足以使船舶路徑在有限的可行解中發生改變。

由表2知，相較于未考慮風浪流，考慮風浪流后蟻群算法、標準遺傳算法和自適應遺傳算法求解結果在航程上有所增加，但航行耗時分別減少了5.25%、6.19%和6.22%，這說明考慮風浪流的影響后規劃出的路徑可以幫助船舶縮短航行耗時。另外，自適應遺傳算法規劃路徑航行耗時為354.80 s，在4種算法中求解結果最優，說明了文中對標準遺傳算法進行的交叉變異算子自適應優化是有效的。

表2 不同方法求解結果

4.2 算法耗時分析

在考慮風浪流與未考慮風浪流兩種情況下，保證相同求解質量時，分析不同算法的計算效率，并增加了圖3(b)的環境進行實驗，該環境下實驗結果如圖9。另外，PAGA算法采用八核心并行機制實現，不同方法分別求解20次的運行耗時平均值如表3。

圖9 多障礙區環境路徑規劃結果

表3 不同求解算法運行耗時

當考慮風浪流影響進行船舶路徑規劃時，相較于串行機制，主從并行機制實現遺傳算法的程序運行耗時更短，且多障礙區環境相較于簡單環境更接近并行化機制的理想加速比，這說明主從并行自適應遺傳算法能夠顯著降低算法運行耗時，有效提升了算法效率。

5 結 語

船舶智能化已成為船舶業發展的趨勢，智能船舶的應用優勢逐步顯現，而航線規劃技術是智能船舶的一項重要功能。針對船舶航線規劃研究中較少考慮海洋氣象環境影響的情況，建立了以航行安全為前提、以航行耗時最短為目標的船舶路徑規劃方法。

綜合考慮海上復雜環境因素的影響，考慮航行水域水深限制，計算風、波浪及水流造成的船舶失速，基于Maklink 圖論和改進的自適應算法求解船舶航行路徑，以幫助船舶更安全、快速地到達目的地。與標準遺傳算法和蟻群算法和可視圖法對比，在相同迭代次數下求解航行路徑，改進的自適應遺傳算法所求路徑船舶航行耗時更短。另外，在保證一定求解質量的情況下，將自適應遺傳算法采用主從并行機制實現能夠顯著縮短程序運行耗時，有效地提升了船舶路徑規劃效率。