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

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

0 引 言

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

圖1 海上救援應急線路評估分析算法流程圖

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

海上救援應急線路評估分析算法流程圖見圖1。

1 環(huán)境建模

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

1.1 柵格法

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

圖2 柵格數據單元分割示例

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

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

1.2 單元樹法

在采用柵格法存儲數據時，存儲每個單元格的經緯度和水深點信息，存儲文件大小超過500M。為減少存儲文件，在得到柵格數據之后，采用單元樹法對其進行處理，從而可將存儲文件的大小減到4M以內。

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

圖3 浙江海域地形圖

圖4 浙江海域水深熱力圖

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

圖5 海域數據示例

圖6 單元樹法分割示意

2 無向連通圖構建

參照單元樹法，在構建連通網絡時，取每個單元區(qū)域的中心點作為整個連通網絡的頂點。每個單元區(qū)域的中心點都可與其相鄰的單元區(qū)域的中心點相連接，從而完成對整個連通網絡的構建。圖7為單元樹法分割結果；圖8為連通圖構建結果。

圖7 單元樹法分割結果

圖8 連通圖構建結果

將該方法應用于浙江海域，得到該海域連通圖及其局部放大圖，見圖9和圖10。

3 航線設計算法

3.1 基于弧的數學模型

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

圖9 浙江海域連通圖

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

(1)

s.t.

(2)

=0或1， ?(,)∈

(3)

3.2 CH算法

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

3.2.1 預處理

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

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

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

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

收縮并不是完全刪除節(jié)點，在其他收縮過程中可忽略該節(jié)點，因為當看到一條通向C的邊時，知道存在一條捷徑，該路徑可能不是一條最短路徑。無論采用哪種方式，都不需要訪問C。若進行以C開頭或結尾的搜索，仍可找到該節(jié)點。

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

node收縮的順序可用以下指標確定：

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

ED=node_degree-number_of_shortcuts

(4)

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

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

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

3.2.2 尋路過程

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

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

經緯度距離的計算公式為

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

(5)

式(5)中：為經緯度距離；和為2個節(jié)點的緯度；和為2個節(jié)點的經度；為地球半徑。

3.3 平滑處理

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

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

for all 線路頂點 do

if 某個頂點的相鄰2個頂點的直線不經過障礙物

and 2個相鄰頂點之間的距離小于通過該點連接2個相鄰頂點的距離 then

去掉該頂點，生成一條新的線路

end if

end for

end while

經過平滑處理的路徑圖見圖14。擴大生成的浙江海域局部圖中的最短路徑見圖15。

圖13 未經平滑處理的路徑圖

圖14 經過平滑處理的路徑圖

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

4 實際應用效果

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

以保安事件恒利168險情為例，采用柵格法和單元樹法對浙江海域數據進行處理，結果見表1。采用柵格法處理之后，生成14 622 988個格子，每次讀取數據需要25.00 s；采用單元樹法對采用柵格法處理的單元格進行處理之后，生成84 787個格子，每次讀取數據只需要0.38 s，數據存儲數量和讀取時間顯著減少。

表1 2種數據處理方法的數據處理結果對比

為測試CH算法在應急搜集場景下應用時的性能，通過篩選事故點周圍3 n mile范圍內的船舶(共計213艘)，對該算法與傳統(tǒng)的Dijkstra算法的數據讀取時間進行對比，結果見表2。由表2可知，CH算法相比Dijkstra算法在數據讀取時間上的性能顯著提升。

表2 2種算法在應急搜集場景下的數據讀取時間對比

為提高搜救線路的可行性，對算法計算結果進行平滑處理，并將所得結果與平滑處理前的數據相比較，結果見表3。由表3可知，經平滑處理之后，搜救線路途經頂點數量顯著減少，航行距離縮短。

表3 平滑處理對比

平臺運行實測：

1) 確定險情經緯度和船舶基礎信息，發(fā)起算法。

(1) 參數為

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

MarineLineRoutingDTO marineLineRoutingDTO=

algorithmFeignClient.marineRouting(marineLineRoutingRequestDTO)

2) 輸出結果，共包含148個點，具體為

每個點的詳情為

3) 將輸出結果圖形化(見圖16)，并對實際生產進行指導。

圖16 圖形化的算法輸出結果

4) 顯示其他計算路徑，見圖17和圖18。

圖17 顯示的計算路徑1

圖18 顯示的計算路徑2

5 結 語

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