石 浩， 喬繼潘， 季 盛

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

0 引 言

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

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

1)現(xiàn)有的航線自動規(guī)劃算法采用的數(shù)據(jù)大部分為電子海圖上的信息數(shù)據(jù)，動態(tài)地更新這些數(shù)據(jù)需花費大量的經(jīng)濟成本和時間成本；

2)無論是基于電子海圖還是基于AIS數(shù)據(jù)構(gòu)建航路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，考慮的航行限制因素都比較多，附加工作量比較大，部分研究試驗環(huán)境單一，缺少實例驗證，需在盡可能降低時間成本和減少附加工作量的情況下充分研究復(fù)雜航行環(huán)境，找到能符合實際情況的航線自動規(guī)劃算法；

3)絕大多數(shù)航線規(guī)劃算法都只能計算出局部最優(yōu)航線，不具備全局搜索能力。

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

1 航線自動規(guī)劃方法和主要流程

本文所述航線自動規(guī)劃方法主要基于海量AIS數(shù)據(jù)確定航行區(qū)域內(nèi)的可通航點，對航行區(qū)域地圖進行柵格劃分和矩陣化處理，根據(jù)AIS數(shù)據(jù)中的可通航點確定柵格網(wǎng)格的矩陣值，定義可通航柵格。結(jié)合全球經(jīng)緯度距離公式，利用鄰接矩陣對各可通航柵格網(wǎng)格進行距離計算。基于蟻群算法和計算得到的鄰接矩陣尋找從起始點至終點的最優(yōu)距離，并輸出規(guī)劃航線。由于初始航線是基于柵格網(wǎng)格得到的，輸出的轉(zhuǎn)向點較多，可在此基礎(chǔ)上根據(jù)船員在規(guī)劃航線時的習(xí)慣做法規(guī)劃出符合船舶實際航行習(xí)慣的航線。

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

圖1 航線自動規(guī)劃方法主要流程

1)對船舶AIS數(shù)據(jù)進行預(yù)處理；

2)將航行區(qū)域地圖柵格化，構(gòu)建航行環(huán)境模型；

3)采用蟻群算法求解航線規(guī)劃數(shù)學(xué)模型；

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

2 航行環(huán)境模型構(gòu)建

2.1 船舶AIS數(shù)據(jù)預(yù)處理

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

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

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

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

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

對AIS數(shù)據(jù)進行預(yù)處理的流程見圖2，主要步驟如下：

圖2 AIS數(shù)據(jù)預(yù)處理流程

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

2)設(shè)置通航條件。以吃水大于5 m、航速大于5 kn為標(biāo)準(zhǔn)，保留符合條件的AIS數(shù)據(jù)。

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

圖3 AIS數(shù)據(jù)離散點示意

2.2 可通航柵格環(huán)境模型

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

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

圖4 航行區(qū)域可通航柵格環(huán)境模型簡化模型

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

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

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

2.3 航線規(guī)劃的數(shù)學(xué)模型

規(guī)劃航線的目的是避開障礙物，并使航行路徑最短。因此，結(jié)合實際操作需要建立相應(yīng)的數(shù)學(xué)模型，需優(yōu)化的目標(biāo)函數(shù)為

(1)

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

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

3.1 蟻群算法的原理

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

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

(2)

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

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

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

(3)

(4)

(5)

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

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

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

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

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

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

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

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

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

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

8)輸出航線最短的解。

4 實例分析及結(jié)果

4.1 數(shù)據(jù)基本情況及處理

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

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

2)設(shè)置通航條件，以吃水大于5 m、航速大于5 kn為標(biāo)準(zhǔn)，保留符合通航條件的AIS數(shù)據(jù)。

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

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

4.2 實例分析過程

首先基于篩選處理的AIS數(shù)據(jù)構(gòu)建可通航柵格環(huán)境模型，并將其轉(zhuǎn)化為鄰接矩陣。

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

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

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

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

4.3 實例分析結(jié)果

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

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

5 結(jié) 語

本文通過構(gòu)建基于AIS數(shù)據(jù)的柵格環(huán)境模型，結(jié)合蟻群算法進行了船舶航線自動規(guī)劃。通過在中國沿海港口進行實例驗證，說明了該方法在全局最優(yōu)航線自動規(guī)劃方面具有經(jīng)濟、便捷、安全的應(yīng)用效果。

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

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