張進(jìn)峰， 朱學(xué)秀， 彭斯楊

(武漢理工大學(xué) a.航運(yùn)學(xué)院； b.國家水運(yùn)安全工程技術(shù)研究中心；c.內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室， 湖北 武漢 430063)

為響應(yīng)“交通運(yùn)輸部辦公廳關(guān)于印發(fā)推進(jìn)智慧交通發(fā)展行動計(jì)劃(2017—2020年)的通知”的要求，確保智能化運(yùn)輸裝備升級改造任務(wù)的順利完成，在航運(yùn)方面，需加快“智能船舶”的研制力度；在船舶導(dǎo)航領(lǐng)域，通過一定的方法對在特定區(qū)域內(nèi)船舶歷史航次信息進(jìn)行分析，得到區(qū)域內(nèi)船舶的典型軌跡，可為船舶自動導(dǎo)航?jīng)Q策系統(tǒng)提供充分滿足航行經(jīng)驗(yàn)和航行需求的航行解決方案，以大大提高智能船舶在導(dǎo)航方面自動感知、自動記憶、自動學(xué)習(xí)、自動決策和自適應(yīng)的能力。同時(shí)，船舶典型軌跡的獲取，可幫助檢測軌跡異常的船舶，有利于提高海事監(jiān)管效率，進(jìn)而更大程度地降低安全事故發(fā)生的可能性，保障智能船舶的航行安全以及海上人員的生命和財(cái)產(chǎn)安全。

獲取船舶運(yùn)動典型軌跡的方法大多基于挖掘技術(shù)下的軌跡聚類[1-2]，其主要研究方向可分為2類：將軌跡作為整體來進(jìn)行[3-4]，該類方法能對軌跡間的相似性進(jìn)行直觀評估，對輸入數(shù)據(jù)的要求不高，但易忽略復(fù)雜軌跡的局部異常信息;借鑒空中交通領(lǐng)域?qū)v史航跡進(jìn)行劃分的方法[5-6]，一般通過軌跡相似度[7-10]識別軌跡特征并劃分軌跡，再根據(jù)相應(yīng)的軌跡片段來進(jìn)行軌跡聚類[11-13]，該方法能更好地識別局部軌跡特征。為優(yōu)化以上算法，牟軍敏等[14]提出一種綜合兩類聚類算法優(yōu)點(diǎn)的快速自適應(yīng)譜聚類算法。但上述通過軌跡聚類獲取的典型軌跡僅能展示出軌跡的形狀，而對典型軌跡在指導(dǎo)船舶航行方面的考慮較少。

為使典型軌跡能對船舶導(dǎo)航系統(tǒng)有更高的指導(dǎo)意義，必須使典型軌跡能與船舶導(dǎo)航的特征相符。本文以海上交通工程為基礎(chǔ)[15]，從為船舶導(dǎo)航服務(wù)的角度出發(fā)，借鑒基于劃分的軌跡聚類的思路，利用在特定生產(chǎn)活動中，船舶起始港和目的港間的歷史航次信息，對船舶產(chǎn)生的航次軌跡進(jìn)行建模，并以遺傳算法(Genetic Algorithm,GA)為基礎(chǔ)[16]，獲取起始港和目的港(將2個港口統(tǒng)稱為目標(biāo)港)間與船舶航次軌跡中船舶位置點(diǎn)分布規(guī)律相符的有向典型軌跡。

1 船舶航行軌跡建模

1.1 航次軌跡數(shù)據(jù)

船舶歷史航次信息是由船舶運(yùn)動的船舶自動識別系統(tǒng)(Automatic Identification System, AIS)數(shù)據(jù)與船舶水運(yùn)生產(chǎn)活動產(chǎn)生的航次信息共同構(gòu)成的一種含有船舶航行時(shí)間信息的軌跡數(shù)據(jù)。其中，船舶在一次生產(chǎn)活動中產(chǎn)生的運(yùn)動軌跡，可稱為航次軌跡，大量航次軌跡構(gòu)成的數(shù)據(jù)集稱為航次軌跡數(shù)據(jù)集。航次軌跡數(shù)據(jù)集中的每一條航次軌跡都包含船舶位置點(diǎn)、位置點(diǎn)的時(shí)間戳、船舶名稱、出發(fā)區(qū)域信息和到達(dá)區(qū)域信息。

本文使用的歷史航次信息由龍船(北京)科技有限公司提供，其由AIS數(shù)據(jù)以及與AIS數(shù)據(jù)對應(yīng)的航次信息兩個部分組成。

為獲取相應(yīng)港口間的船舶典型軌跡，須將目標(biāo)港間的軌跡數(shù)據(jù)提取出來。提取軌跡數(shù)據(jù)的流程如下：

1)選取本研究中的起始港Pdep及目的港Parr，刪除歷史航次數(shù)據(jù)中起始港及目的港與之不符的航次信息。

2)在航次信息(簡稱數(shù)據(jù)集2)中提取船舶水上移動通信標(biāo)識碼(Maritime Mobile Service Identify,MMSI)碼，找出AIS數(shù)據(jù)(簡稱數(shù)據(jù)集1)中與之對應(yīng)的船舶。

3)在數(shù)據(jù)集1分別提取步驟1)中船舶的離港時(shí)間Ts1和到港時(shí)間Ts2。

4)截取數(shù)據(jù)集1中對應(yīng)船舶Ts1到Ts2間所有位置點(diǎn)作為船舶的一條完整航次軌跡。

5)重復(fù)以上步驟，將所有航次軌跡匯集到一個集合中，記作航次軌跡數(shù)據(jù)集φ。

1.2 時(shí)間歸一化

由于獲取船舶運(yùn)動的典型軌跡僅涉及到軌跡數(shù)據(jù)集的空間維度信息，因此，需通過航次軌跡數(shù)據(jù)集的時(shí)間歸一化處理使后續(xù)操作忽略船舶位置的原始時(shí)間戳。

時(shí)間歸一化將重寫航次軌跡數(shù)據(jù)集中每艘船舶軌跡位置的時(shí)間戳，使船舶從航行開始以來經(jīng)過的時(shí)間與船舶行駛的距離成正比，且船舶的總航行時(shí)間為一個固定值。

對于特定擁有m個船舶位置點(diǎn)的船舶航次軌跡G，時(shí)間戳可按時(shí)間順序?yàn)?/p>

T=[T0，T1，…，Tn-1]

(1)

目標(biāo)港間的固定航程記作D，任意2個相鄰的位置x與y之間的航程為記作voyage(Tx，Ty)，根據(jù)式(2)設(shè)置軌跡G中任意船舶位置點(diǎn)i在時(shí)間歸一化操作后其船舶位置的時(shí)間戳ti為

(2)

式(2)中:length(Pk-1，Pk)為點(diǎn)Pk-1與點(diǎn)Pk間的笛卡爾距離，用于描述兩點(diǎn)間的距離。

1.3 船舶航行軌跡建模

一般情況，目標(biāo)港間的航線可分為多個首尾相連的航路段，首個航路段起點(diǎn)為起始港位置，最后一個航路段終點(diǎn)為目的港位置。各航路段首尾交接的端點(diǎn)為航路點(diǎn)，當(dāng)船舶行駛到航路點(diǎn)時(shí)，會根據(jù)航行需求改變船舶的航行參數(shù)，如航速、航向等。因此，軌跡建?？煽醋髟诤Ｑ蟊砻嫔纤阉饕幌盗械奈灰?，海平面上的每個航路點(diǎn)使用其地理位置的經(jīng)緯度坐標(biāo)(lat，lon)進(jìn)行標(biāo)記。

當(dāng)船舶從航路點(diǎn)P(latP，lonP),航行到航路點(diǎn)Q(latQ，lonQ)，該船舶位移矢量為

w=PQ=(Δlat,Δlon)

(3)

故有m個航路點(diǎn)的船舶航行軌跡R為

R=[w1,w2,…,wn]

(4)

位移矢量的經(jīng)緯度變化設(shè)有相同最大值，以限制每個航路段船舶位移的幅度。

綜上所述，出發(fā)點(diǎn)位于Pdep的軌跡可被描述為從點(diǎn)Pdep出發(fā)的軌跡R，其中：

R=[w1,w2,…,wn]=[(Δlat1,Δlon1),

(Δlat2,Δlon2),…,(Δlatn,Δlonn)]

(5)

航次軌跡數(shù)據(jù)集包含船舶位置所屬的時(shí)間戳信息，因此，為便于對軌跡數(shù)據(jù)集進(jìn)行分割(參見第2.1節(jié))，需為軌跡數(shù)據(jù)集添加時(shí)間信息。

對于數(shù)據(jù)集中緊鄰的船舶位置點(diǎn)1和船舶位置點(diǎn)2，其所構(gòu)成的段S為

S=(P1,P2)

(6)

船舶在實(shí)際航行中沿該段航行的時(shí)間間隔為

Δts=t2-t1

(7)

與之類似，對于典型軌跡的候選軌跡，可用式(2)求取船舶航行的時(shí)間戳。當(dāng)船舶從出發(fā)點(diǎn)Pdep于t=t0時(shí)出發(fā)，并執(zhí)行相應(yīng)的位移，即可得到船舶典型軌跡的航路段，將其各航路點(diǎn)表示為

[W0,W1,…,Wn]

(8)

任一航路段Si為

Si=(Wi-1,Wi)， 0

(9)

式(9)中：

Wi=(ti,lati,loni),W0=(t0,latdep,londep),

Wn=(tn,latarr,lonarr)

(10)

所有數(shù)據(jù)集中航次軌跡中位置點(diǎn)以及預(yù)設(shè)基準(zhǔn)軌跡和候選軌跡的航路點(diǎn)都以式(10)的形式表示。

據(jù)此，候選軌跡可標(biāo)記為

D=[S0,S1,…,Sn]

(11)

其總長度為

(12)

式(12)中：

length(Si)=length(Wi-1,Wi)=|wi|

(13)

由式(2)可知候選軌跡時(shí)間戳的計(jì)算方法為

(14)

其航行時(shí)間為

ΔtD=tn-t0

(15)

式(15)中：由于出發(fā)點(diǎn)Pdep處的時(shí)間戳t0=0，故ΔtD=tn。

2 軌跡參數(shù)

本文基于GA獲取典型軌跡的過程需通過預(yù)設(shè)基準(zhǔn)軌跡進(jìn)行?；鶞?zhǔn)軌跡是一條出發(fā)點(diǎn)已確定的隨機(jī)軌跡，對起始港A和目的港B而言，當(dāng)預(yù)設(shè)基準(zhǔn)軌跡的出發(fā)點(diǎn)位于A時(shí)，則代表本文獲取的典型軌跡由A指向B。在獲取典型軌跡的過程中，預(yù)設(shè)基準(zhǔn)軌跡會和GA隨機(jī)生成的同類型的初始軌跡，一起作為典型軌跡的候選軌跡參與到進(jìn)化中。因此,基準(zhǔn)軌跡在GA運(yùn)行前指代預(yù)設(shè)基準(zhǔn)軌跡，運(yùn)行后指代典型軌跡的候選軌跡。由于基準(zhǔn)軌跡位移向量的數(shù)量已知，故典型軌跡航路點(diǎn)和航路段的數(shù)量已確定。

基準(zhǔn)軌跡是計(jì)算軌跡參數(shù)的基準(zhǔn)，通過GA進(jìn)行進(jìn)化的每一條候選軌跡都將依次成為計(jì)算軌跡參數(shù)的基準(zhǔn)軌跡，然后用這些軌跡參數(shù)計(jì)算適應(yīng)度函數(shù)值來評判候選軌跡是否是船舶運(yùn)動的典型軌跡。

2.1 船舶位置點(diǎn)到基準(zhǔn)軌跡的平均距離

軌跡數(shù)據(jù)集中所有船舶位置點(diǎn)到含有n個航路點(diǎn)的基準(zhǔn)軌跡的平均距離的求取步驟如下：

1)根據(jù)基準(zhǔn)軌跡數(shù)量，將軌跡數(shù)據(jù)集所有位置點(diǎn)分為n個子集，每個子集中的所有船舶位置作為兩個港口間航線的一個航路段。

2)分別計(jì)算每個航路段內(nèi)各船舶位置到其所在航道段部分基準(zhǔn)軌跡的垂直距離。

3)計(jì)算每個航路段垂直距離的平均值。

4)計(jì)算每個航路段垂直距離平均值的平均值。

步驟1)中軌跡數(shù)據(jù)集的分割基于船舶位置的時(shí)間戳，當(dāng)船舶進(jìn)入航路段后，船舶的航速和航向均保持不變，其航程僅與航行時(shí)間有關(guān)。針對基準(zhǔn)軌跡的航路段Si，對應(yīng)基準(zhǔn)軌跡的航路點(diǎn)Wi-1與航路點(diǎn)Wi間第i個航路段和軌跡數(shù)據(jù)集子集φi，在航路段內(nèi)任意船舶位置點(diǎn)P均滿足以下條件：

ti-1

(16)

式(16)中：tP為船舶位置點(diǎn)P時(shí)間戳;ti-1和ti分別為基準(zhǔn)軌跡航路點(diǎn)Wi-1和航路點(diǎn)Wi處的時(shí)間戳。故航次軌跡數(shù)據(jù)集φ可被精確分為與基準(zhǔn)軌跡航段數(shù)量n相同，且互不相交n個子集φi(0

軌跡數(shù)據(jù)集分割的分段示例見圖1。

圖1 軌跡數(shù)據(jù)集分割的分段示例

對于船舶位置點(diǎn)P，其到基準(zhǔn)軌跡垂直距離d為點(diǎn)P和經(jīng)過點(diǎn)P且垂直于基準(zhǔn)軌跡航路段的直線與基準(zhǔn)軌跡航路段交點(diǎn)的兩點(diǎn)間的笛卡爾距離。

(17)

2.2 軌跡到目的港的距離

由于典型軌跡的最后一個航路點(diǎn)即第n個航路點(diǎn)為軌跡終點(diǎn)，因此，需評估基準(zhǔn)軌跡到目的港的距離。這項(xiàng)參數(shù)與航次軌跡數(shù)據(jù)無關(guān)，只取決于基準(zhǔn)軌跡末尾的位置。具有n個航路段的基準(zhǔn)軌跡的第n個航路點(diǎn)為Wn，其距固定的目的地Parr的距離為

D=length(Wn,Parr)

(18)

2.3 平均航向變化

船舶在沿軌跡航行時(shí)，可能會在航路點(diǎn)改變其航向。因此，船舶航向變化定義為船舶在航路點(diǎn)前一航路段的航向與后一航路段航向的差值的絕對值。

對于軌跡中任意航路點(diǎn)Wi，其前后兩端航路段分別為Si和Si+1，其航向分別為Ci和Ci+1，則船舶在航路點(diǎn)Wi處的平均航向變化為ΔCi為

ΔCi=|Ci+1-Ci|,0

(19)

由式(19)可知：在航向變化僅受航向改變幅度的影響，而與航向改變的方向無關(guān)。

故n個航路段的軌跡的平均航向變化為

(20)

3 典型軌跡求取

3.1 GA

GA是一種模擬的物種選擇、育種、突變和進(jìn)化過程搜索最優(yōu)解的啟發(fā)式算法。GA的目標(biāo)是在有限的時(shí)間資源的情況下，為個體尋找對環(huán)境的最佳適應(yīng)度。GA流程見圖2。

圖2 GA流程

為從航次軌跡集φ中求得目標(biāo)港間的典型軌跡，將通過GA獲得典型軌跡的船舶候選軌跡作為GA的個體，記作候選軌跡T，T的出發(fā)點(diǎn)全部位于起始港，航路段的數(shù)量相同且與預(yù)設(shè)基準(zhǔn)軌跡的航路段數(shù)量一致，航路段的每個位移向量作為個體的一個基因。

T的集合為GA育種的種群，GA通過計(jì)算每條候選軌跡的軌跡參數(shù)，即可計(jì)算T的適應(yīng)度，并通過選擇過程選擇最優(yōu)個體進(jìn)入下一步。

通過軌跡航道段位移向量的交叉和突變對GA的交叉和突變過程分別進(jìn)行模擬，GA的交叉運(yùn)算被模擬為切割某個航路段兩父輩候選軌跡相同位置的位移向量，然后將兩者交換，組成兩個子輩候選軌跡，其中父輩候選軌跡中含有空心的軌跡部分即為發(fā)生交叉運(yùn)算航路段。候選軌跡的突變是軌跡中某個航路段內(nèi)的位移向量變?yōu)槠渌碾S機(jī)位移向量，從而生成新的子軌跡，其中父輩候選軌跡中含有空心的軌跡部分即為發(fā)生突變運(yùn)算航路段。

3.2 典型軌跡適應(yīng)度函數(shù)

GA中適應(yīng)度即為個體解決問題的能力。因GA優(yōu)選出的個體是適應(yīng)度最大個體，這里將候選軌跡的軌跡參數(shù)加權(quán)就和，并將此值稱為候選軌跡適應(yīng)度函數(shù)的目標(biāo)函數(shù)為

(21)

式(21)中：fp、fD和fc為加權(quán)因數(shù)。參照第2節(jié)軌跡參數(shù)的定義，顯然使適度函數(shù)的目標(biāo)函數(shù)越小的候選軌跡與直達(dá)航次軌跡集內(nèi)所有船舶位置點(diǎn)的分布規(guī)律越相符。因GA選擇出的個體是適應(yīng)度較高的個體，故適應(yīng)度函數(shù)可取F的倒數(shù)為

(22)

4 典型軌跡實(shí)例

本文以上海港—深圳港2015年9月—2016年6月的部分船舶的歷史航次信息數(shù)據(jù)為例，獲取由上海港出發(fā)直達(dá)深圳港的船舶典型軌跡。經(jīng)數(shù)據(jù)處理共獲得了103條上?！钲诘暮酱诬壽E。

出于船舶導(dǎo)航的目的，使用GA求取典型軌跡時(shí)需對航次軌跡進(jìn)行分類，目的是將軌跡數(shù)據(jù)集中的非直達(dá)軌跡與直達(dá)軌跡區(qū)分開來，形成新的軌跡數(shù)據(jù)集作為GA的數(shù)據(jù)訓(xùn)練集，以提高典型軌跡的求取效率和精度。因篇幅有限，這里給出分類的結(jié)果，其中直達(dá)航次軌跡可記作φZ。直達(dá)航次軌跡及非直達(dá)航次軌跡見圖3。

a) 直達(dá)航次軌跡

典型軌跡的求取基于直達(dá)航次軌跡數(shù)據(jù)集，對于GA的適應(yīng)度函數(shù)的目標(biāo)函數(shù)，根據(jù)軌跡參數(shù)的重要程度，將其取為

(23)

GA共產(chǎn)生100代子種群，通過對比運(yùn)行各種不同的交叉概率和突變概率的GA獲取的典型軌跡結(jié)果的，這里將GA的種群的個體數(shù)量設(shè)為500，交叉的概率設(shè)為0.5(50%)，突變概率設(shè)為0.2(20%)。

在多次試驗(yàn)反復(fù)檢驗(yàn)試驗(yàn)后，將預(yù)設(shè)基準(zhǔn)軌跡的航路點(diǎn)定為9個，當(dāng)GA運(yùn)行100代后，可獲得直達(dá)典型軌跡。典型軌跡與船舶位置點(diǎn)的匹配圖見圖4a，典型軌跡的形狀見圖4b。

a) 典型軌跡與船舶位置點(diǎn)的匹配圖

為使GA的優(yōu)化過程更加直觀，適應(yīng)度函數(shù)的目標(biāo)函數(shù)值的變化值見圖5。

根據(jù)軌跡參數(shù)及適應(yīng)度函數(shù)的定義，當(dāng)適應(yīng)度函數(shù)目標(biāo)函數(shù)越小時(shí)，可代表候選軌跡的與船舶位置點(diǎn)的位置誤差越小，候選軌跡的終點(diǎn)距終點(diǎn)更近且形狀更平滑，適應(yīng)度越高。由圖5可知：GA大概在運(yùn)行20代后即可大致獲得最終的典型軌跡，其收斂速度很快，效果較好。

圖5 適應(yīng)度函數(shù)目標(biāo)函數(shù)最優(yōu)值變化趨勢

5 結(jié)束語

本文從為船舶導(dǎo)航服務(wù)的角度出發(fā)，建立船舶運(yùn)動軌跡模型，引入描述軌跡特征的軌跡參數(shù)，提出基于GA獲取船舶運(yùn)動典型軌跡的方法，主要結(jié)論如下：

1)方法能很好地從航次信息中獲得船舶運(yùn)動的有向典型軌跡，典型軌跡獲取的結(jié)果與船舶航次軌跡中船舶位置點(diǎn)分布規(guī)律基本相符。

2)典型軌跡獲取算法的收斂速度快，自動學(xué)習(xí)及自適應(yīng)能力強(qiáng)，具有較高的效率。

3)從典型軌跡的結(jié)果看，還可對航次信息進(jìn)行不同類型劃分，如根據(jù)時(shí)間季節(jié)、航行需求(如船舶行駛過程中掛靠特定港口)等，從而獲得不同類型的典型航行軌跡，從而提高典型軌跡在導(dǎo)航過程中的實(shí)用性。