海上救援應(yīng)急線路評(píng)估分析算法

楊曉環(huán)， 楊卓超， 揭婉晨

(1.中遠(yuǎn)海運(yùn)科技股份有限公司，上海 200135； 2.舟山海事局，浙江 舟山 310005；3.浙江樹人大學(xué) 管理學(xué)院，杭州 310015)

0 引 言

近年來(lái)，隨著海洋經(jīng)濟(jì)的快速發(fā)展，我國(guó)海上各類型船舶數(shù)量持續(xù)增長(zhǎng)，海洋資源開(kāi)發(fā)等涉海活動(dòng)越來(lái)越多，規(guī)模越來(lái)越大。據(jù)浙江省海上搜救中心統(tǒng)計(jì):與“十二五”末期相比，“十三五”期間轄區(qū)內(nèi)海上險(xiǎn)情、遇險(xiǎn)船舶和遇險(xiǎn)人員數(shù)量均大幅度增加，分別增加16.5%、42.1%和22.2%;2019年，轄區(qū)內(nèi)沿海水域共有227艘次船舶發(fā)生水上交通險(xiǎn)情，遇險(xiǎn)人員2 423人，引發(fā)事故110起，死亡和失蹤45人，沉船39艘，直接經(jīng)濟(jì)損失達(dá)10 342.13萬(wàn)元。在這些事故中，一般等級(jí)和一般等級(jí)以上的事故數(shù)占全國(guó)水上事故總數(shù)的13.9%，死亡失蹤人數(shù)占全國(guó)水上事故導(dǎo)致的死亡失蹤總?cè)藬?shù)的18.9%，沉船數(shù)占全國(guó)沉船總數(shù)的24.3%。涉海業(yè)務(wù)的蓬勃發(fā)展使得我國(guó)的海上搜救任務(wù)日益復(fù)雜、繁重，搜救船舶駕駛員通常需面對(duì)很多環(huán)境方面的復(fù)雜情況。若要成功完成海上搜救任務(wù)，需依靠險(xiǎn)情處置方案進(jìn)行科學(xué)決策：快速定位、尋找失事船舶和落水人員，這是實(shí)施搜救計(jì)劃的基礎(chǔ)；快速抵達(dá)搜救區(qū)域，這是實(shí)施搜救計(jì)劃的關(guān)鍵。但是，在實(shí)際搜救過(guò)程中，由于時(shí)間非常緊迫，需在搜救開(kāi)始之前迅速利用信息系統(tǒng)制訂出安全、準(zhǔn)確、快速的處置方案(包括搜救線路)；同時(shí)，由于搜救目標(biāo)是不斷移動(dòng)的，需能利用信息系統(tǒng)實(shí)時(shí)規(guī)劃最新航線，從而保證搜救力量快速抵達(dá)搜救區(qū)域，大大減輕船舶駕駛員定位和制訂航線計(jì)劃的負(fù)擔(dān)。

圖1 海上救援應(yīng)急線路評(píng)估分析算法流程圖

在設(shè)計(jì)航線時(shí)，一般需根據(jù)電子海圖上的水深、障礙物和船舶參數(shù)等信息，將目標(biāo)區(qū)域劃分為礙航區(qū)域和可航區(qū)域。在可航區(qū)域內(nèi)采用智能搜索算法尋找最優(yōu)路徑，即在己知被搜救船舶的準(zhǔn)確位置和周圍障礙區(qū)域的環(huán)境信息的情況下，尋找一條從起點(diǎn)到終點(diǎn)的滿足要求的盡可能短的航行路徑，使搜救船舶在通行過(guò)程中能安全可靠地避開(kāi)所有障礙物。在對(duì)搜救船舶航行路徑進(jìn)行智能規(guī)劃時(shí),應(yīng)同時(shí)考慮經(jīng)濟(jì)性和安全性。

海上救援應(yīng)急線路評(píng)估分析算法流程圖見(jiàn)圖1。

1 環(huán)境建模

航線設(shè)計(jì)的基本原則是遵守海上通航規(guī)則，充分避開(kāi)礙航物，獲取能耗最少、路徑最短和航行效率最高的航線。影響海上通航的基本要素主要包括初露水面的礁石群、島嶼、海上油田、樁標(biāo)船和燈標(biāo)等。 其他礙航區(qū)影響通航的要素還包括低于船舶凈空高度的空中電纜和橋梁、軍事演習(xí)區(qū)、垃圾傾倒區(qū)、彈藥傾倒區(qū)、拋泥區(qū)和雷區(qū)等。此外，必須遵守內(nèi)河船舶定線制的要求，將礙航區(qū)處理成符合船舶定線規(guī)則的區(qū)域。因此，在設(shè)計(jì)航線時(shí)，首要工作是對(duì)船舶所處的環(huán)境進(jìn)行合理描述，即進(jìn)行環(huán)境建模。

1.1 柵格法

柵格法是利用地圖建模的一種方法，用柵格表示環(huán)境。柵格法實(shí)質(zhì)上是對(duì)劃定的地形圖進(jìn)行單元分割，使用大小相等的方塊劃分環(huán)境空間，并用柵格數(shù)組表示環(huán)境，比如用桔色表示障礙物，用淺灰色表示自由空間。對(duì)于混合柵格，根據(jù)自由空間和障礙物的占比將其歸屬于自由空間障礙物空間或自由空間，最短路徑就是通過(guò)在該柵格圖上搜索自由空間得到的。因此，柵格大小的選取是影響規(guī)劃算法性能的一個(gè)很重要的因素。若柵格較小，雖然由柵格地圖表示的環(huán)境信息會(huì)非常清晰，但需存儲(chǔ)的信息較多，存儲(chǔ)空間需求較大，同時(shí)干擾信號(hào)較多，規(guī)劃速度較慢，實(shí)時(shí)性得不到保證；若柵格較大，雖然信息存儲(chǔ)量較少，抗干擾能力較強(qiáng)，規(guī)劃速較快，但環(huán)境信息劃分較為模糊，不利于有效路徑的規(guī)劃。因此，在確定柵格大小時(shí)，存在求解進(jìn)度與時(shí)空開(kāi)銷之間的矛盾。

圖2 柵格數(shù)據(jù)單元分割示例

在處理浙江海域地圖時(shí)，選取120°E～124°E，27°N～31°N的區(qū)域作為研究對(duì)象，采用柵格法進(jìn)行地圖建模。為更清晰地表示環(huán)境信息，將整個(gè)地形圖單元分割成4 800×4 800的地形圖，每個(gè)單元格的長(zhǎng)度最大90 m，從而將整個(gè)地形圖精準(zhǔn)地表示出來(lái)。圖2為柵格數(shù)據(jù)單元分割示例。

采用柵格法建立的浙江海域地形圖見(jiàn)圖3，其水深熱力圖見(jiàn)圖4。

1.2 單元樹法

在采用柵格法存儲(chǔ)數(shù)據(jù)時(shí)，存儲(chǔ)每個(gè)單元格的經(jīng)緯度和水深點(diǎn)信息，存儲(chǔ)文件大小超過(guò)500M。為減少存儲(chǔ)文件，在得到柵格數(shù)據(jù)之后，采用單元樹法對(duì)其進(jìn)行處理，從而可將存儲(chǔ)文件的大小減到4M以內(nèi)。

單元樹法正是為克服柵格法的缺點(diǎn)設(shè)計(jì)的，能有效避免時(shí)空開(kāi)銷與求解精度之間的矛盾。該方法根據(jù)浙江海域的水深將整個(gè)環(huán)境空間分成較大的單元格，即將柵格單元合并成大的單元格，滿足各個(gè)大單元格的水深是相同的，從而將環(huán)境空間劃分成不同大小的單元格。

圖3 浙江海域地形圖

圖4 浙江海域水深熱力圖

在二維空間內(nèi)，單元樹法又稱四叉樹法，其基本思想是將平面拆分為4個(gè)子平面，這些子平面仍可繼續(xù)拆分。拆分得到的每個(gè)單元占用的空間可能是全為海域、全為陸地和混合型區(qū)域(既包含海域，又包含陸地)等3種情況中的1種。對(duì)于混合型區(qū)域，按前面的方法繼續(xù)進(jìn)行拆分，直到整個(gè)區(qū)域都是海域或陸地為止。該方法的優(yōu)點(diǎn)是自適應(yīng)性較好。以某海域數(shù)據(jù)(見(jiàn)圖5)為例，采用單元樹法對(duì)其進(jìn)行分割，結(jié)果見(jiàn)圖6。

圖5 海域數(shù)據(jù)示例

圖6 單元樹法分割示意

2 無(wú)向連通圖構(gòu)建

參照單元樹法，在構(gòu)建連通網(wǎng)絡(luò)時(shí)，取每個(gè)單元區(qū)域的中心點(diǎn)作為整個(gè)連通網(wǎng)絡(luò)的頂點(diǎn)。每個(gè)單元區(qū)域的中心點(diǎn)都可與其相鄰的單元區(qū)域的中心點(diǎn)相連接，從而完成對(duì)整個(gè)連通網(wǎng)絡(luò)的構(gòu)建。圖7為單元樹法分割結(jié)果；圖8為連通圖構(gòu)建結(jié)果。

圖7 單元樹法分割結(jié)果

圖8 連通圖構(gòu)建結(jié)果

將該方法應(yīng)用于浙江海域，得到該海域連通圖及其局部放大圖，見(jiàn)圖9和圖10。

3 航線設(shè)計(jì)算法

3.1 基于弧的數(shù)學(xué)模型

在無(wú)向圖=(,)中:為所有點(diǎn)的集合；為網(wǎng)絡(luò)中所有弧的集合。用表示從點(diǎn)到點(diǎn)的距離；用點(diǎn)表示起點(diǎn);用點(diǎn)表示終點(diǎn)。

圖9 浙江海域連通圖

圖10 浙江海域連通圖局部放大圖

(1)

s.t.

(2)

=0或1， ?(,)∈

(3)

3.2 CH算法

CH(Contraction Hierarchies)算法是一種用于查找圖形中最短路徑的加速技術(shù)，可充分利用代表海上網(wǎng)絡(luò)的圖的特性，包括路網(wǎng)預(yù)處理和查詢2個(gè)階段。由于網(wǎng)絡(luò)很少更改，可先進(jìn)行一些計(jì)算(幾秒鐘到幾小時(shí))，再進(jìn)行查詢，查詢時(shí)間可達(dá)到毫秒級(jí)。CH算法依靠“shortcuts”實(shí)現(xiàn)這種加速?！皊hortcuts”線段連接2個(gè)不相鄰的頂點(diǎn)和，其邊權(quán)重是最短-路徑上邊權(quán)重的總和。

3.2.1 預(yù)處理

通過(guò)預(yù)處理能生成一個(gè)多層的結(jié)構(gòu)，每個(gè)點(diǎn)都處在單獨(dú)的一層。事先對(duì)點(diǎn)進(jìn)行優(yōu)先級(jí)排序，排序的好壞直接影響到預(yù)處理的效率和搜索的效率。首先，點(diǎn)的優(yōu)先級(jí)(高低)可根據(jù)問(wèn)題的特性調(diào)整，本文采用將相鄰單元區(qū)域的中心點(diǎn)相連接的方式組建網(wǎng)絡(luò)，鄰接點(diǎn)個(gè)數(shù)最多不超過(guò)8個(gè)，且無(wú)特殊區(qū)域和特殊連接關(guān)系，因此網(wǎng)絡(luò)中邊的權(quán)重根據(jù)中心點(diǎn)之間的球面距離得到，優(yōu)先級(jí)權(quán)重是邊權(quán)重的累加值。其次，根據(jù)優(yōu)先級(jí)由低到高依次選點(diǎn)進(jìn)行收縮，生成“shortcuts”。接著，通過(guò)在預(yù)處理階段創(chuàng)建的“shortcuts”減小搜索空間。最后，在最短路徑查詢中使用這些“shortcuts”跳過(guò)“不重要的”頂點(diǎn)，從而提高搜索效率。為達(dá)到該目標(biāo)，需執(zhí)行迭代式的頂點(diǎn)收縮。通過(guò)1次“收縮”1個(gè)節(jié)點(diǎn)預(yù)處理圖形。為執(zhí)行收縮操作，計(jì)算出節(jié)點(diǎn)之間的最短路徑，并為其插入“shortcuts”，隨后將節(jié)點(diǎn)標(biāo)記為“已處理”。

這里用一個(gè)簡(jiǎn)單的圖形說(shuō)明節(jié)點(diǎn)收縮前后的狀態(tài)，見(jiàn)圖11。為收縮C，插入從A到E和從A到B的“shortcuts”，因?yàn)锳→C→E和A→C→B為最短路徑。不需要插入從B到E的“shortcuts”，因?yàn)锽→C→E不是從B到E的最短路徑，B→D→E較短。

a) 收縮前狀態(tài)

b) 收縮后狀態(tài)

收縮并不是完全刪除節(jié)點(diǎn)，在其他收縮過(guò)程中可忽略該節(jié)點(diǎn)，因?yàn)楫?dāng)看到一條通向C的邊時(shí)，知道存在一條捷徑，該路徑可能不是一條最短路徑。無(wú)論采用哪種方式，都不需要訪問(wèn)C。若進(jìn)行以C開(kāi)頭或結(jié)尾的搜索，仍可找到該節(jié)點(diǎn)。

CH采用雙向迪杰斯特拉(Dijkstra)算法，在搜索過(guò)程中，只能從級(jí)別低的地方向級(jí)別高的地方搜索，兩邊相遇之后就會(huì)保存途徑路徑。節(jié)點(diǎn)收縮排序的方法是使用優(yōu)先級(jí)隊(duì)列，該隊(duì)列中的最小元素保存為最有收縮潛力的節(jié)點(diǎn)。

node收縮的順序可用以下指標(biāo)確定：

1) 邊的差分(Edge Difference,ED)。ED可認(rèn)為是最重要的node收縮條件，其計(jì)算公式為

ED=node_degree-number_of_shortcuts

(4)

式(4)中：node_degree為連接到節(jié)點(diǎn)的邊的數(shù)量；number_of_shortcuts為刪除節(jié)點(diǎn)之后必須創(chuàng)建的shortcuts數(shù)量。ED值越大，越先收縮。

2) 均勻度(Uniformity)。僅使用ED會(huì)獲得相當(dāng)慢的路徑規(guī)劃速度。應(yīng)以均勻的方式收縮圖中所有位置的節(jié)點(diǎn)，而不是將收縮節(jié)點(diǎn)保持在較小的區(qū)域內(nèi)。

3) 收縮成本(Cost of Contraction)。收縮的一個(gè)耗時(shí)部分是前向最短路徑搜索，用于確定“shortcuts”的必要性。 因此，可將搜索空間大小的總和看作優(yōu)先項(xiàng)。

3.2.2 尋路過(guò)程

在查詢階段，從原始圖上的起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)開(kāi)始雙向搜索(見(jiàn)圖12)，并通過(guò)預(yù)處理階段創(chuàng)建的“shortcuts”進(jìn)行擴(kuò)展。為找到2個(gè)節(jié)點(diǎn)之間的最短路徑，執(zhí)行2次搜索，一次從起始節(jié)點(diǎn)開(kāi)始搜索，一次從結(jié)束節(jié)點(diǎn)開(kāi)始搜索，看二者在哪里相遇。搜索過(guò)程與Djikstra算法相似，但有一項(xiàng)額外的規(guī)則，即僅搜索收縮優(yōu)先級(jí)比當(dāng)前節(jié)點(diǎn)高的節(jié)點(diǎn)。在可視化中，這意味著僅搜索向上傾斜的邊。

圖12 在浙江海域求取的2個(gè)節(jié)點(diǎn)之間的最短路徑示意

經(jīng)緯度距離的計(jì)算公式為

=·arcos[cos·cos·cos(-)+sin·sin]

(5)

式(5)中：為經(jīng)緯度距離；和為2個(gè)節(jié)點(diǎn)的緯度；和為2個(gè)節(jié)點(diǎn)的經(jīng)度；為地球半徑。

3.3 平滑處理

采用上述方法生成的航線會(huì)有很多不平滑的線段，具體見(jiàn)圖13。 需對(duì)該線段進(jìn)行處理，通過(guò)刪除航線上的某些點(diǎn)，判斷新的航線是否成立和距離是否縮短，由此更新航線。平滑處理過(guò)程如下：

While 新的航線比上一個(gè)航線更優(yōu)(即距離更短)do

for all 線路頂點(diǎn) do

if 某個(gè)頂點(diǎn)的相鄰2個(gè)頂點(diǎn)的直線不經(jīng)過(guò)障礙物

and 2個(gè)相鄰頂點(diǎn)之間的距離小于通過(guò)該點(diǎn)連接2個(gè)相鄰頂點(diǎn)的距離 then

去掉該頂點(diǎn)，生成一條新的線路

end if

end for

end while

經(jīng)過(guò)平滑處理的路徑圖見(jiàn)圖14。擴(kuò)大生成的浙江海域局部圖中的最短路徑見(jiàn)圖15。

圖13 未經(jīng)平滑處理的路徑圖

圖14 經(jīng)過(guò)平滑處理的路徑圖

圖15 擴(kuò)大生成的浙江海域局部圖中的最短路徑

4 實(shí)際應(yīng)用效果

該算法已在浙江海事海上智控項(xiàng)目中得到應(yīng)用，主要用于完成浙江海域的海上應(yīng)急搜救，在收到參與險(xiǎn)情搜救的指令之后，根據(jù)該算法為每艘應(yīng)急搜救船生成推薦航路。

以保安事件恒利168險(xiǎn)情為例，采用柵格法和單元樹法對(duì)浙江海域數(shù)據(jù)進(jìn)行處理，結(jié)果見(jiàn)表1。采用柵格法處理之后，生成14 622 988個(gè)格子，每次讀取數(shù)據(jù)需要25.00 s；采用單元樹法對(duì)采用柵格法處理的單元格進(jìn)行處理之后，生成84 787個(gè)格子，每次讀取數(shù)據(jù)只需要0.38 s，數(shù)據(jù)存儲(chǔ)數(shù)量和讀取時(shí)間顯著減少。

表1 2種數(shù)據(jù)處理方法的數(shù)據(jù)處理結(jié)果對(duì)比

為測(cè)試CH算法在應(yīng)急搜集場(chǎng)景下應(yīng)用時(shí)的性能，通過(guò)篩選事故點(diǎn)周圍3 n mile范圍內(nèi)的船舶(共計(jì)213艘)，對(duì)該算法與傳統(tǒng)的Dijkstra算法的數(shù)據(jù)讀取時(shí)間進(jìn)行對(duì)比，結(jié)果見(jiàn)表2。由表2可知，CH算法相比Dijkstra算法在數(shù)據(jù)讀取時(shí)間上的性能顯著提升。

表2 2種算法在應(yīng)急搜集場(chǎng)景下的數(shù)據(jù)讀取時(shí)間對(duì)比

為提高搜救線路的可行性，對(duì)算法計(jì)算結(jié)果進(jìn)行平滑處理，并將所得結(jié)果與平滑處理前的數(shù)據(jù)相比較，結(jié)果見(jiàn)表3。由表3可知，經(jīng)平滑處理之后，搜救線路途經(jīng)頂點(diǎn)數(shù)量顯著減少，航行距離縮短。

表3 平滑處理對(duì)比

平臺(tái)運(yùn)行實(shí)測(cè)：

1) 確定險(xiǎn)情經(jīng)緯度和船舶基礎(chǔ)信息，發(fā)起算法。

(1) 參數(shù)為

(2) 發(fā)起的算法為

MarineLineRoutingDTO marineLineRoutingDTO=

algorithmFeignClient.marineRouting(marineLineRoutingRequestDTO)

2) 輸出結(jié)果，共包含148個(gè)點(diǎn)，具體為

每個(gè)點(diǎn)的詳情為

3) 將輸出結(jié)果圖形化(見(jiàn)圖16)，并對(duì)實(shí)際生產(chǎn)進(jìn)行指導(dǎo)。

圖16 圖形化的算法輸出結(jié)果

4) 顯示其他計(jì)算路徑，見(jiàn)圖17和圖18。

圖17 顯示的計(jì)算路徑1

圖18 顯示的計(jì)算路徑2

5 結(jié) 語(yǔ)

本文以浙江海事局轄區(qū)水域?yàn)槔?，采用?shù)學(xué)方法對(duì)海上搜救路線進(jìn)行了分析，設(shè)計(jì)了評(píng)估分析算法，并對(duì)該算法進(jìn)行了實(shí)際應(yīng)用。通過(guò)1個(gè)月的實(shí)踐檢驗(yàn)，證明采用該算法生成的最優(yōu)航路具有較高的參考價(jià)值。該算法雖然已得到實(shí)際應(yīng)用，且證實(shí)對(duì)應(yīng)急險(xiǎn)情具有實(shí)際幫助，但還存在一定的不足，例如有些無(wú)數(shù)據(jù)支撐因素(如漁船網(wǎng)位儀、潮汐)和無(wú)規(guī)律變動(dòng)因素(如風(fēng)速、船長(zhǎng)習(xí)慣航路)沒(méi)有考慮，后續(xù)將根據(jù)數(shù)據(jù)源引入進(jìn)度在模型中逐步疊加相關(guān)因素，針對(duì)無(wú)規(guī)律變動(dòng)因素建立經(jīng)驗(yàn)庫(kù)，引入相關(guān)硬件設(shè)備形成數(shù)據(jù)支撐，最終使推薦的最優(yōu)航路更加精準(zhǔn)。