一種基于AIS數據的船舶航線自動規劃方法

石 浩， 喬繼潘， 季 盛

(上海船舶運輸科學研究所 航運技術與安全國家重點實驗室，上海 200135)

0 引 言

近年來，隨著大數據、物聯網等概念的提出和快速發展,船舶智能化和無人化發展逐漸成為造船業和航運業研究的熱點，得到了世界各國的廣泛關注[1]。航線自動規劃技術作為智能船舶和無人駕駛船舶最關鍵的技術之一，在保證船舶安全航行和提高船舶營運效率等方面有著重要作用。船舶航線自動規劃是指自動為船舶規劃從始發地到目的地的航線，在航線和航行時間最短等特定條件下，結合安全性和能源消耗要求，找到一條最優航行路徑，使船舶在航行過程中能安全可靠地避開所有障礙物[2]。

當前國內外已有很多學者對航線自動規劃方法進行研究。例如：童幫裕等[3]基于電子海圖建立冰區航道環境柵格模型，結合人工勢場法對蟻群算法進行改進；潘明陽等[4]根據內河水網航道通航條件，基于有向航路網絡拓撲法構建航行環境模型，通過改進的A*算法求解最優航線；金建海等[5]提出一種改進的無人艇航線規劃方法，在粒子群優化算法的基礎上引入人工勢場法的思想，通過量子粒子群優化算法求解最優航線，提高全局搜索能力；謝新連等[6]針對海上施工水域，利用Maklink航線網絡構建航路網絡，利用Dijkstra算法求解初始航線，并基于蟻群算法對該航線進行優化；姚肖肖等[7]通過對船舶自動識別系統(Automatic Identification System，AIS)軌跡數據進行聚類提取關鍵轉向點，結合電子海圖相關數據構建無向航路網絡，根據船舶航路的通航頻率設置蟻群算法的初始信息素濃度，求解以總航程最短為優化目標的安全、經濟的最優航線；吳澤亮[8]提出一種改進的蟻群算法，采用Adadelta算法改變蟻群算法的信息素更新規則，動態調整信息素揮發系數，提高蟻群算法的隨機性，從而極大地改善蟻群算法的性能；陳曉等[9]基于海圖上的Maklink圖論，結合無向航路網絡拓撲法構建航行環境模型，通過蟻群算法對采用Dijkstra算法生成的最短航行路徑進行優化；范云生等[10]提出一種依據電子海圖，結合柵格法建立航行環境模型，通過遺傳算法求解最優航線的航線自動規劃方法；SONG[11]針對水面無人艇的全局路徑規劃，采用柵格法建立航行環境模型，采用改進的蟻群算法求解最優航線；SZLAPCZYNSKI[12]根據路徑規劃理論設計最優航線。目前相關研究還存在以下問題：

1)現有的航線自動規劃算法采用的數據大部分為電子海圖上的信息數據，動態地更新這些數據需花費大量的經濟成本和時間成本；

2)無論是基于電子海圖還是基于AIS數據構建航路網絡拓撲結構，考慮的航行限制因素都比較多，附加工作量比較大，部分研究試驗環境單一，缺少實例驗證，需在盡可能降低時間成本和減少附加工作量的情況下充分研究復雜航行環境，找到能符合實際情況的航線自動規劃算法；

3)絕大多數航線規劃算法都只能計算出局部最優航線，不具備全局搜索能力。

對此，以國內外已有研究為基礎，針對其中存在的問題，對海上航行環境和航線規劃方法進行分析，探索出一種無需依靠電子海圖信息數據進行環境建模，性能優良，能在復雜航行環境下便捷、準確地完成全局最優航線自動規劃的航線自動規劃方法至關重要。本文主要在上述研究的基礎上，結合海量AIS軌跡數據、柵格法和蟻群算法構建基于AIS數據中的可通航點的柵格環境模型，結合蟻群算法規劃出一條經濟、便捷的船舶航線，并通過實例驗證說明該方法在全局最優航線自動規劃方面的應用效果和可行性。

1 航線自動規劃方法和主要流程

本文所述航線自動規劃方法主要基于海量AIS數據確定航行區域內的可通航點，對航行區域地圖進行柵格劃分和矩陣化處理，根據AIS數據中的可通航點確定柵格網格的矩陣值，定義可通航柵格。結合全球經緯度距離公式，利用鄰接矩陣對各可通航柵格網格進行距離計算?；谙伻核惴ê陀嬎愕玫降泥徑泳仃噷ふ覐钠鹗键c至終點的最優距離，并輸出規劃航線。由于初始航線是基于柵格網格得到的，輸出的轉向點較多，可在此基礎上根據船員在規劃航線時的習慣做法規劃出符合船舶實際航行習慣的航線。

該方法的主要流程見圖1，具體步驟如下：

圖1 航線自動規劃方法主要流程

1)對船舶AIS數據進行預處理；

2)將航行區域地圖柵格化，構建航行環境模型；

3)采用蟻群算法求解航線規劃數學模型；

4)輸出初始航線，進一步優化得到最終航線。

2 航行環境模型構建

2.1 船舶AIS數據預處理

針對AIS數據中可能存在離群值、異常值和冗余值的情況，結合其分布復雜的特點，在挖掘應用AIS數據之前需對其進行清洗整理[13]。對于離散船舶軌跡點的處理，主要采用聚類算法，主要有劃分聚類、密度聚類、層次聚類和網格聚類等4種。在選擇聚類算法時，主要考慮以下幾點：

1)所選算法能自動確定類簇的數量；

2)聚類結果中各聚類簇的形狀類似于圓形；

3)聚類簇的尺寸不應太大，且相鄰聚類簇不應太小。

基于以上要求，本文選用DBSCAN密度聚類算法。該算法是一種基于密度的空間聚類算法，其核心是利用密度的概念，按一定的約束條件對需聚類的空間中的數據進行分類，將在指定距離范圍內達到設定密度閾值的數據劃分為簇，達到地理空間分類的目的，去除空間數據中的噪聲點。

對AIS數據進行預處理的流程見圖2，主要步驟如下：

圖2 AIS數據預處理流程

1)清洗AIS數據。保留AIS數據中的經緯度、航速、吃水和航向等字段數據正常點，經度正常數據范圍為-180～180，緯度正常數據范圍為-90～90，航速正常數據范圍為0～50，吃水正常數據范圍為0～50，航向正常數據范圍為0～360。以上字段信號非正常點默認為采集數據錯誤，防止此類錯誤干擾后續可通航柵格網絡的劃分。

2)設置通航條件。以吃水大于5 m、航速大于5 kn為標準，保留符合條件的AIS數據。

3)采用DBSCAN密度聚類算法剔除AIS數據中公共通航區內的離散點，距離范圍設置為2 n mile，包含的點數閾值設置為3，排除AIS數據離散點對航路規劃的干擾，具體AIS數據離散點示意見圖3，其中下方的點即為需排除的離散點。DBSCAN密度聚類算法將AIS數據較為密集的區集合為一個簇，并形成符合主要航道要求的空間聚類。

圖3 AIS數據離散點示意

2.2 可通航柵格環境模型

船舶在指定航行區域內的航行路徑可簡化為船舶在二維平面內兩點間的航行路線。采用柵格法將指定的航行區域地圖柵格化為若干個柵格，設定指定的單位分割度數作為柵格的邊長。根據航行區域地圖中的單個柵格是否可航行，確定可通航柵格(標記為白色)和不可通航柵格(標記為黑色)。采用柵格法將復雜航行環境下的航線規劃問題轉化為在二維柵格中尋找2個柵格中心點之間符合特定條件的最優路徑的問題。

本文基于篩選后的AIS數據，采用柵格劃分法構建航行區域可通航柵格環境模型，組成可通航區域。該模型的簡化模型見圖4，其中1個單元格為1個柵格，船舶以柵格為最小運動單位，航向均為前往下一個柵格的中心點所指的方向，設定航速保持不變，航程計算以柵格中心點為準。

圖4 航行區域可通航柵格環境模型簡化模型

1)對全球范圍內的航行區域進行航線規劃，以0.025°為單位分割度數劃分全球經緯度，剔除高緯度地區(南緯75°至南極點，北緯75°至北極點)，確定全球柵格范圍。

2)根據上一步確定的單位分割度數劃分全球柵格范圍，得到6 000×14 400塊柵格。沿橫軸方向由上向下依次對柵格進行編號，分別為1，2，3，…，直至所有柵格編號完畢。根據篩選后的AIS數據判斷各柵格內是否出現過AIS數據，若出現過AIS數據，則將其確定為可通航柵格。采用DBSCAN密度聚類算法將可通航柵格組成可通航區域，從而剔除可通航離散柵格(圖4中左下角被不可通航柵格包圍的可通航柵格為需剔除的離散柵格)。

3)采用鄰接矩陣算法確定相鄰可通航柵格距離，將柵格編號轉換為經緯度，根據地球上兩點之間距離的計算公式計算兩相鄰可通航柵格之間的距離。

2.3 航線規劃的數學模型

規劃航線的目的是避開障礙物，并使航行路徑最短。因此，結合實際操作需要建立相應的數學模型，需優化的目標函數為

(1)

式(9)中：L為航線距離；fn為第n個航行路徑穿越的網格中心點，n=1,2，…，N；S(fn,fn+1)為點fn與點fn+1之間的直線距離；N為規劃的由初始點到目標點的航線中航路轉向點的個數。船舶航線F由航路點f1，f2，…，fn組成。該模型的目標是求得航線距離L的值最小的路徑，將該路徑作為該條件下的最優航行路徑。

3 基于蟻群算法的航線規劃建模和求解

3.1 蟻群算法的原理

蟻群算法是模擬螞蟻在尋找食物過程中尋求最短路線的行為，并對其進行抽象簡化，得到的一種用來搜索最優路徑的群體智能算法(或稱啟發式算法)，常應用于最短路徑尋優問題的求解中[14]。

假設螞蟻總數為m，航路轉向點總數為n。第k只螞蟻在t時刻由航路轉向點i轉移到航路轉向點j的概率為

(2)

式(2)中：α為信息啟發式因子，表示信息素濃度的重要程度；β為期望啟發式因子，表示航路轉向點之間距離的重要程度；τij(t)為航路轉向點i和航路轉向點j在t時刻的信息素濃度；ηij(t)為啟發函數，表示螞蟻個體由航路轉向點i到航路轉向點j的期望，取值為1/dij，dij為當前航路轉向點i與下一個航路轉向點j之間的歐式距離；allowedk為螞蟻k能選擇的航路轉向點。螞蟻根據路徑上的信息素和距離選擇可能的各種航線。

當所有螞蟻全部完成迭代之后，對路徑上的信息素進行更新，更新公式為

τij(t+n)=(1-ρ)τij(t)+Δτij(t)

(3)

(4)

(5)

3.2 基于蟻群算法的最短航線規劃實施步驟

基于蟻群算法的最短航線規劃流程見圖5，具體實施步驟如下：

圖5 基于蟻群算法的最短航線規劃流程

1)將給定的出發點A(經度φA，緯度αA)和到達點B(經度φB，緯度αB)轉換成全球柵格中的對應柵格位置出發點A(XA,YA)和到達點B(XB,YB)；

2)初始化每個螞蟻種群，設定參數；

3)采用輪盤賭法選擇下一個相鄰可通航柵格，該柵格和兩柵格之間的距離是基于全球可通航柵格網格劃分模型計算得到的；

4)每只螞蟻根據信息素找到路徑，直至到達點B；

5)記錄每只螞蟻的通航路線和總的航行距離；

6)更新螞蟻留下的信息素；

7)判斷是否達到最大種群數；

8)輸出航線最短的解。

4 實例分析及結果

4.1 數據基本情況及處理

本文將2020年5月某批次船舶航行產生的AIS軌跡數據作為原始數據樣本，該數據樣本共包含628艘船舶和對應的23 168個AIS軌跡數據點。作為實例驗證，設定起始點為山東煙臺港，目標點為遼寧大連港。對原始AIS數據進行預處理：

1)清洗AIS數據，保留其中經緯度、航速、吃水和航向等字段數據正常且符合條件的點，經度正常數據范圍為121.12°E～122.02°E，緯度正常數據范圍為37.57°N～38.945°N，航速正常數據范圍為0～50 kn，吃水正常數據范圍為0～50 m，航向正常數據范圍為0°～360°。

2)設置通航條件，以吃水大于5 m、航速大于5 kn為標準，保留符合通航條件的AIS數據。

3)采用DBSCAN密度聚類算法剔除AIS數據中公共通航區內的離散點，排除AIS數據離散點對航路規劃的干擾。在參數設定方面，給定的距離范圍設置為2 n mile，包含的點數不小于給定的閾值3。

經上述處理之后，得到162艘船舶對應的1 963個軌跡數據點，將這些數據作為此次航線規劃方法實例驗證的基礎數據。

4.2 實例分析過程

首先基于篩選處理的AIS數據構建可通航柵格環境模型，并將其轉化為鄰接矩陣。

1)以0.025°為單位分割度數劃分經度在120.895°E～122.270°E，緯度在37.570°N～38.945°N的既定經緯度范圍，確定船舶航行區域的柵格范圍。設定起始點的經緯度范圍，經度范圍為121.27°E～121.57°E，緯度范圍為37.67°N～37.85°N；設定目標點的經緯度范圍，經度范圍為121.72°E～122.02°E，緯度范圍為38.765°N～38.945°N。

2)根據上一步驟確定的單位分割度數劃分指定航行區域的柵格范圍，得到將航行區域分割成55×55個單元柵格的柵格環境模型。沿橫軸方向由上向下對柵格依次編號，分別為1，2，3，…，直至所有柵格編號完畢。根據篩選處理之后的AIS數據判斷各柵格內是否出現過AIS數據，若出現過AIS數據，則將其確定為可通航柵格，否則將其確定為不可通航柵格，由此得到此次實例驗證的可通航柵格環境模型(見圖6)。

3)采用鄰接矩陣算法確定兩相鄰可通航柵格之間的距離，將具體柵格編號轉換為經緯度，根據地球上兩點之間距離的計算公式計算兩相鄰可通航柵格之間的距離。

隨后，通過MATLAB軟件實現基于蟻群算法的最短航線求解。設置出發點A(經度為121.495°E，緯度為37.800°N)和到達點B(經度為121.770°E，緯度為38.815°N)，并將其轉換成指定航行區域柵格中的對應柵格位置出發點，設置最大迭代次數Nmax=500次，螞蟻個數m=100個。運行蟻群算法程序，完成最短航線規劃任務。同時，為驗證本文所提方法的航線規劃效果，將采用該方法規劃得出的最短航線與基于AIS數據和A*算法得出的最短航線相對比。

4.3 實例分析結果

基于船舶航行AIS軌跡數據和柵格法構建航行區域可通航柵格環境模型，采用蟻群算法得到的最短航線規劃結果見圖7；基于AIS數據和A*算法得到的最短航線規劃結果見圖8。為觀察蟻群算法在搜索最短航線時的收斂過程，給出采用蟻群算法計算求解最短航線的整個收斂過程(見圖9)。

通過對試驗結果進行對比可知：采用蟻群算法得到的最短航線長度為270.5 km，航路轉向點個數為25個；采用A*算法得到的最短航線長度為279.4 km，航路轉向點個數為29個。2種方法相比，本文所提方法在航線長度上可節省約3%，且初步規劃出的航路轉向點個數更少。2種方法均符合船舶實際航行要求，與傳統的在紙質海圖上繪制航線和在電子海圖上輸入航路轉向點生成航線相比，在便捷性和安全性等方面的表現更優。因此，采用本文所提方法規劃出的航線在經濟性、安全性和便捷高效性等方面具有一定的優勢；此外，與其他航線自動規劃方法相比，在節省時間和經濟成本的同時，提高了全局搜索能力。

5 結 語

本文通過構建基于AIS數據的柵格環境模型，結合蟻群算法進行了船舶航線自動規劃。通過在中國沿海港口進行實例驗證，說明了該方法在全局最優航線自動規劃方面具有經濟、便捷、安全的應用效果。

與其他航線規劃方法相比，本文所提方法的主要優勢和創新之處在于：能在不使用大量電子海圖的情況下對收集的AIS數據進行篩選，從而構建出符合實際應用要求的航線，節省時間成本和經濟成本；能利用實時更新的AIS數據充分研究船舶在復雜航行環境下的航行情況，從而保證船舶安全航行；采用蟻群算法獲得能避免陷入局部最優的最短航線。

另外，本文所提方法仍有一些不足之處有待完善，例如：在實際生產過程中，海洋環境復雜多變，若可航范圍較大，在采用該方法對海洋環境進行柵格化編碼時，柵格過大會導致精度較差,易出現偏差，柵格過小會需要較多的計算資源，所需時間過長，效率較低，需結合實際情況做出評估，確定合適的劃分標準；可結合改進之后的蟻群算法提升原有算法的效率和準確性。由于初始航線是基于柵格網格得到的，輸出的航線轉向點較多，與實際規劃的航線有一定的偏差，因此可根據船員規劃航線的習慣，進一步采用航線平滑處理等方法對航線進行優化，規劃出符合實際航行習慣的航線。