摘要：為提升智能船舶航線自動設計方案的合理性，考慮船舶通航環境因素的影響，提出一種考慮水深、潮高、風、浪、流的智能船舶航線規劃算法。基于Delaunay三角剖分算法，提出一種環境建模方法，利用船舶航行安全水深理論在環境模型中搜索禁航區。利用切線圖法建立可航網絡。基于船舶力學原理對船舶干擾力進行建模，提出一種在環境干擾力影響下的可航網絡權值修正方法。將提出的智能船舶航線規劃算法用于對浙江舟山衢山島北部水域的實例分析。仿真結果表明，該算法能夠為不同環境下的不同尺度船舶規劃出合適的航線，也能夠為相同船舶給出適應不同環境的規劃結果，從而證明該算法的有效性。

　　關鍵詞： 智能船舶; 航線規劃; 環境因素; Delaunay三角剖分; 切線圖法

　　引 言

　　船舶在航行過程中的航線規劃受到各種環境因素的影響，是船舶安全、經濟運行的基礎。隨著無人船技術的興起，船舶自動航線設計也成為其核心技術之一。電子海圖及相關助航設備已普及，通航環境參數和船舶航行信息的數字化技術已發展成熟。在智能船舶航線規劃算法中，充分考慮環境因素，利用數字化技術及設備進行航線輔助設計，將是智能船舶進行合理航線規劃的基本保障。因此，考慮通航環境因素的智能船舶航線規劃算法研究具有十分重要的意義。

　　近年來，船舶航線規劃算法的研究不斷吸取其他領域在路徑規劃上的成功經驗，逐漸發展成為路徑規劃算法的一個重要分支，取得了較為豐碩的研究成果。張立華等[1]考慮航行水域的水深和礙航物，提出一種基于電子海圖的自動航線設計方法;李源惠等[2]利用電子海圖信息，提出基于動態網格模型的航線規劃算法;TAM等[3]結合交通流數據及環境數據，提出一種考慮船舶會遇狀態的航線規劃算法;曹鴻博等[4]對復雜情形下的航線規劃算法進行優化，提出改進的最短距離航線自動生成算法;NAEEM等[5]考慮《國際海上避碰規則》，

　　提出一種無人船避碰路徑規劃算法;莊佳園等[6]提出一種基于航海雷達的水面無人艇局部路徑規劃算法;王濤等[7]考慮船舶轉向限制，提出一種最短距離航線自動生成算法;向哲等[8]利用海量AIS數據，提取出船舶習慣航路并應用于船舶航線規劃;

　　XU等[9]考慮環境因素影響，提出一種開闊海域的船舶航線規劃算法;謝新連等[10]考慮船舶在繞開礙航區時的避碰問題，提出一種復雜水域船舶避碰路徑規劃算法;SHEN等[11]將粒子群優化算法(particle swarm optimization， PSO)與切線圖法相結合來搜索最優船舶航線;XIE等[12-13]提出改進的多方向A*算法，解決了海上風電場水域的船舶路徑規劃問題;GKEREKOS等[14]提出了一個基于船舶性能和氣象條件的航線規劃框架;WEN等[15]將DBSCAN(density-based spatial clustering of applications with noise)與人工神經網絡相結合，實現了基于港口間AIS數據的船舶航線自動設計;CHEN等[16]提出一種基于Q學習的路徑規劃方法，能夠讓船舶按照該路徑規劃結果進行自主航行。

　　從已有的研究可以發現，船舶航線規劃算法可以分為解析法和智能法。解析法著眼于船舶實際的航行環境和氣象環境，通過對環境進行建模，進而獲得船舶可航水域，完成船舶航線規劃設計;智能法主要對船舶航跡、船舶航行參數等大量相關歷史數據進行挖掘、分析和學習，進而通過智能算法求解可靠的經驗路線。這都為船舶航線自主設計的研究提供了堅實的基礎。然而，針對不同尺度、不同類型的船舶，環境模型通常采用通用模型，難以滿足實際應用過程中的航行安全要求;此外，在考慮環境因素影響的算法中，對多種環境因素的綜合考慮還不充分，并且沒有考慮潮高值對環境建模的影響。

　　雖然在求解船舶航線規劃問題時，采用解析法和智能法均可以獲得較好的效果，但是在處理繞開臨時禁航區時，解析法能夠直接將環境數據、氣象數據作為參數代入算法進行航線求解。因此，本文提出一種基于解析法的航線規劃算法。首先提出一種綜合考慮船體參數、水深、潮高值的環境建模算法，

　　用于自動提取船舶禁航區域，并根據實時潮高值和船舶吃水需要給出適應的環境模型;再利用基于船舶參數的航速修正算法對環境模型進行權值修正，通過模型求解為船舶規劃出既安全又高效的航線。

　　1 基于電子海圖數據的航行水域環境建模

　　電子海圖將真實水域資料以數據的形式進行保存和顯示，其中水域水深數據以〈坐標，水深值〉的形式存儲在電子海圖文件中，并能夠以離散點的形式在電子海圖中顯示。Delaunay三角剖分算法是廣泛應用于數值分析(比如有限元分析)以及圖形學的一項重要預處理技術。

　　1.1 電子海圖數據的Delaunay三角剖分算法

　　電子海圖的水深數據集合K可以表示為{kii=1，2，…，n}，其中ki的數據結構為〈(xi，yi)，hi〉，(xi，yi)為坐標點，hi為該點水深值。

　　Delaunay三角剖分算法能夠根據離散的坐標數據構建該區域的Delaunay三角網模型，該模型可以表示為集合{tjtj∈M，j=1，2，…，m}，tj的數據結構為〈l1，l2，l3〉，其中li的數據結構為〈k(i)0，k(i)1〉。根據文獻[17-19]的比較分析結果，采用Marcum提出的基于Delaunay空洞性質的增量法[20]對電子海圖水深數據進行三角模型化處理，僅保留水深數據。其算法偽代碼如下：

　　輸入{kiki∈K，i=1，2，…，n}

　　輸出{tjtj∈M，j=1，2，…，m}

　　1創建包含集合K所有元素的初始三角形t0

　　2創建拆分三角形集合S′

　　3創建重構邊集合L，集合元素個數g

　　4將t0加入集合M，m=1

　　5for i=1 to n do

　　6 for j=1 to m do

　　7 if ki在tj的外接圓內

　　8 將tj從M中刪除并加入S′

　　9 end if

　　10 end for

　　11 刪除S′中元素的公共邊，其余邊加入L

　　12 for u=1 to g do

　　13 用ki和lu構建新三角形tm+1，加入M

　　14 end for

　　15end for

　　16for j=1 to m do

　　17 if tj表達的是陸地

　　18 將tj從M中刪除

　　19 end if

　　20end for

　　1.2 搜索禁航區范圍

　　礙航區除了陸地、島嶼外，水深不滿足船舶吃水要求的區域同樣為礙航區域。為保證船舶航行安全，應選擇水深超過船舶吃水并留有一定安全余量的水域航行[21]。

　　HS=HC+HT≥HA+dm

　　(1)

　　式中：HS為船舶航行安全水深;HA為最小安全富余水深;dm為船舶吃水;HC為電子海圖水深(該點理論最低潮面的水深);HT為潮高。對于船舶富余水深，文獻[21]給出了不同機構對船舶富余水深的規定，綜合考慮船舶安全等因素，取船舶吃水的10%作為最小安全富余水深，式(1)可以轉化為

　　HS=HC+HT≥dm×110%

　　(2)

　　利用船舶航行安全水深HS，在Delaunay電子海圖模型中進行搜索，獲得不滿足船舶航行安全水深的區域邊界，構建禁航區。采用式(3)利用等深線li的兩端點坐標(x1，y1)和(x2，y2)求取安全水深的區域邊界點坐標(xS，yS)，這里k1的數據結構為〈(x1，y1)，h1〉，k2的數據結構為〈(x2，y2)，h2〉。

　　xS=x1+(HS-h1)(x2-x1)h2-h1

　　yS=y1+(HS-h1)(y2-y1)h2-h1

　　(3)

　　等深線搜索算法偽代碼如下，其中RS為等深線集合：

　　輸入{tjtj∈M，j=1，2，…，m}

　　輸出{lili∈RS，i=1，2，…，n}

　　1for j=1 to m do

　　2 if HS-htj(l1)、HS-htj(l2)、HS-htj(l3)異號(htj(lx)為三角形tj的頂點水深數值，x=1，2，3)

　　3 利用式(3)求解等深線端點坐標

　　4 求取等深線li，加入集合RS

　　5 end if

　　6end for

　　遍歷等深線集合RS，通過首尾連接構建礙航區邊界，創建礙航區集合{(o，β)i(o，β)i∈O，i=1，2，…，n}，二元組(o，β)元素包含礙航區邊界數據o和邊界個數β。

　　1.3 可航水域無向圖構建

　　已知礙航區集合后，無法直接進行船舶航線設計，需要將礙航區轉化為可航水域無向圖，英國學者DOYLE等[22]提出了機器人在二維平面上構建無向網絡的切線圖法，并證明最短路徑是由凸多邊形邊界與凸多邊形間的公切線組成的。在通過等深線搜索獲得的Delaunay電子海圖模型中，礙航區形狀不全為凸多邊形，可采用頂角判別算法進行處理。可航水域無向圖的構建步驟如下：

　　步驟1 遍歷礙航物集合{(o，β)i(o，β)i∈O，i=1，2，…，n}，對各礙航區頂點進行校驗，若其夾角小于90°則保留頂點，若其夾角大于等于90°，則刪除該頂點，獲得處理后的礙航區集合{(o，β)i(o，β)i∈Onew，i=1，2，…，n

　　}。

　　步驟2 輸入起點和終點，校驗起點和終點是否包含在礙航區內。

　　步驟3 創建集合O*，連接起點與終點生成探測線，將探測線經過的礙航區加入集合O*;循環遍歷集合O*，以經過起點的礙航區切線、經過終點的礙航區切線作為新的探測線，將經過的礙航區加入集合O*，未穿越的探測線加入集合P，直至集合O*在新一輪遍歷中不再添加新的礙航區。

　　步驟4 遍歷集合O*，求任意兩礙航區的公切線段，以公切線段為探測線，將探測線經過的礙航區加入集合O*，未穿越的探測線加入集合P，直至集合O*在新一輪遍歷中不再添加新的礙航區。

　　步驟5 獲得無向圖網絡邊界集合{pjpj∈P，j=1，2，…，m}。

　　2 環境因素對航速影響的量化分析

　　量化環境因素的影響是實現航線設計的重要前提。在影響船舶航速的眾多因素中，風、浪、流影響較大也較容易被量化[23]。將環境因素的量化結果與船舶力學原理相結合，計算在環境因素影響下的船舶航速。利用航速對可航水域無向圖進行權值修正，將環境因素的影響加入船舶航線設計中。

　　2.1 船舶阻力模型

　　在靜水中航行時，船舶在推力T的作用下克服總阻力Rt前進。這里，推力T可以通過主機有效功率計算，總阻力Rt可以通過估算公式[24]進行計算：

　　Rt=12ρSCtv2

　　(4)

　　式中：S為船舶濕表面面積，可采用文獻[24]的估算圖譜進行估算;Ct為總阻力系數;ρ為水域水密度;v為船舶航行的速度。

　　Ct=Cf+Cr+ΔCAR

　　(5)

　　式中：Cf為摩擦阻力系數，可采用桑海公式[25]估算;Cr為剩余阻力系數，可以采用Lap-Keller圖譜進行估算;

　　ΔCAR為粗糙度補貼系數[26-27]。

　　2.2 環境干擾力模型

　　2.2.1 風對船體的作用力

　　船舶航行時，水線面以上部分受到風的作用力Fwind，沿艏艉方向的分力為Fwind，x，橫向分力為Fwind，y：

　　Fwind，x=12ρaAfv2windCwind，x(αR)

　　Fwind，y=12ρaAsv2windCwind，y(αR)

　　(6)

　　式中：ρa為空氣密度;Af和As分別為水線面以上的正投影面積和側投影面積;vwind為相對風速;αR為風舷角;Cwind，x(αR)和Cwind，y(αR)分別為縱向和橫向風壓力系數，其值可按文獻[28]的經驗公式求取。

　　推薦閱讀：船舶阻力數值計算研究