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

　　關(guān)鍵詞： 智能船舶; 航線規(guī)劃; 環(huán)境因素; Delaunay三角剖分; 切線圖法

　　引 言

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

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

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

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

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

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

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

　　1 基于電子海圖數(shù)據(jù)的航行水域環(huán)境建模

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

　　1.1 電子海圖數(shù)據(jù)的Delaunay三角剖分算法

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

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

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

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

　　1創(chuàng)建包含集合K所有元素的初始三角形t0

　　2創(chuàng)建拆分三角形集合S′

　　3創(chuàng)建重構(gòu)邊集合L，集合元素個數(shù)g

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

　　5for i=1 to n do

　　6 for j=1 to m do

　　7 if ki在tj的外接圓內(nèi)

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

　　9 end if

　　10 end for

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

　　12 for u=1 to g do

　　13 用ki和lu構(gòu)建新三角形tm+1，加入M

　　14 end for

　　15end for

　　16for j=1 to m do

　　17 if tj表達(dá)的是陸地

　　18 將tj從M中刪除

　　19 end if

　　20end for

　　1.2 搜索禁航區(qū)范圍

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

　　HS=HC+HT≥HA+dm

　　(1)

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

　　HS=HC+HT≥dm×110%

　　(2)

　　利用船舶航行安全水深HS，在Delaunay電子海圖模型中進(jìn)行搜索，獲得不滿足船舶航行安全水深的區(qū)域邊界，構(gòu)建禁航區(qū)。采用式(3)利用等深線li的兩端點坐標(biāo)(x1，y1)和(x2，y2)求取安全水深的區(qū)域邊界點坐標(biāo)(xS，yS)，這里k1的數(shù)據(jù)結(jié)構(gòu)為〈(x1，y1)，h1〉，k2的數(shù)據(jù)結(jié)構(gòu)為〈(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的頂點水深數(shù)值，x=1，2，3)

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

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

　　5 end if

　　6end for

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

　　1.3 可航水域無向圖構(gòu)建

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

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

　　}。

　　步驟2 輸入起點和終點，校驗起點和終點是否包含在礙航區(qū)內(nèi)。

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

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

　　步驟5 獲得無向圖網(wǎng)絡(luò)邊界集合{pjpj∈P，j=1，2，…，m}。

　　2 環(huán)境因素對航速影響的量化分析

　　量化環(huán)境因素的影響是實現(xiàn)航線設(shè)計的重要前提。在影響船舶航速的眾多因素中，風(fēng)、浪、流影響較大也較容易被量化[23]。將環(huán)境因素的量化結(jié)果與船舶力學(xué)原理相結(jié)合，計算在環(huán)境因素影響下的船舶航速。利用航速對可航水域無向圖進(jìn)行權(quán)值修正，將環(huán)境因素的影響加入船舶航線設(shè)計中。

　　2.1 船舶阻力模型

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

　　Rt=12ρSCtv2

　　(4)

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

　　Ct=Cf+Cr+ΔCAR

　　(5)

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

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

　　2.2 環(huán)境干擾力模型

　　2.2.1 風(fēng)對船體的作用力

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

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

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

　　(6)

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

　　推薦閱讀：船舶阻力數(shù)值計算研究