基于歷史航跡的船舶任意點到港的航線規(guī)劃算法

段俊利，韓 懿

(中遠海運科技股份有限公司，上海 200135)

0 引 言

近年來,隨著科技的不斷發(fā)展，基于互聯(lián)網(wǎng)和大數(shù)據(jù)的陸地導(dǎo)航技術(shù)得到廣泛應(yīng)用，相關(guān)算法越來越成熟，導(dǎo)航精度越來越高，已能滿足日常出行的導(dǎo)航需求。然而在水路運輸領(lǐng)域，雖然國內(nèi)外已有很多平臺提供船舶自動識別系統(tǒng)(Automatic Identification System，AIS)實時船位和歷史航跡查詢服務(wù)，但基于互聯(lián)網(wǎng)和大數(shù)據(jù)的海上導(dǎo)航技術(shù)應(yīng)用較少。目前，全球的貨物運輸主要依靠船舶完成，海上航路邊界模糊、水文氣象變化頻繁、海難事故頻發(fā)和航行效率低下等問題日漸凸顯。隨著計算機技術(shù)的不斷發(fā)展，航運業(yè)正逐漸朝著智能化方向發(fā)展,而航線規(guī)劃是衡量船舶智能化水平的一項關(guān)鍵指標，對保障船舶安全、經(jīng)濟、快速航行具有重要作用。

在此背景下，為促進航運業(yè)的智能化發(fā)展，采用云部署的方式搭建互聯(lián)網(wǎng)大數(shù)據(jù)平臺，主要面向互聯(lián)網(wǎng)公眾提供航運服務(wù)，包括船位信息、航線信息和大數(shù)據(jù)板塊，其中大數(shù)據(jù)包含船舶動態(tài)監(jiān)控分析、風險監(jiān)控分析和競爭對手分析等。為提供高效的服務(wù)，要求用戶在利用該平臺查詢信息時能得到快速響應(yīng)。目前該平臺已存儲18個月共計65億條AIS軌跡數(shù)據(jù)，同時通過算法尋找港口之間的航線，得到了57 699條真實歷史航線，涵蓋16 512個港口對。本文基于海量的歷史航線數(shù)據(jù)，開展航線規(guī)劃算法的設(shè)計與試驗分析，借鑒海量船舶的航行經(jīng)驗，保證船舶在滿足一定準確性要求的前提下，實時獲取航線規(guī)劃結(jié)果。

1 國內(nèi)外研究現(xiàn)狀

目前，船舶駕駛員通常借助電子海圖顯示與信息系統(tǒng)(Electronic Chart Display and Information System，ECDIS)的輔助航線設(shè)計功能，參考導(dǎo)航庫資料，根據(jù)個人經(jīng)驗進行航線規(guī)劃，存在工作量大、航線的質(zhì)量無法保證等缺點，很難滿足現(xiàn)代航海的要求[1]。

近些年，航線規(guī)劃問題得到了很多學者的關(guān)注。例如：劉敦偉[2]采用動力定位(Dynamic Positioning,DP)算法對大量AIS數(shù)據(jù)進行壓縮之后，采用地理網(wǎng)格技術(shù)挖掘熱點航跡段和典型航線，并基于典型航跡段數(shù)據(jù)庫對任意點與港口之間的航線進行規(guī)劃；姚肖肖等[3]基于DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法對壓縮之后的軌跡點進行聚類，提取航路關(guān)鍵轉(zhuǎn)向點，并構(gòu)建無向網(wǎng)絡(luò)圖，采用蟻群算法求解出港口之間的最優(yōu)安全航線；韓佳彤[4]基于大數(shù)據(jù)分析方法，提出一種船舶智能航線設(shè)計方法，通過基礎(chǔ)電子海圖地理信息數(shù)據(jù)，對船舶歷史航線進行分析，計算出港到港、任意點到港和任意點到任意點的最優(yōu)航線；DUCA等[5]提出一種基于KNN(K-Nearest Neighbor)分類器的航線預(yù)測算法，利用歷史上的AIS信息了解過去的船舶航線，預(yù)測船舶在某一特定時間(包括30 min、45 min和60 min)之后的位置，通過對81艘船舶進行測試，取得了良好的效果；MAO等[6]采用Extreme Learning Machine模型,以某種特定的數(shù)據(jù)集分割方式將數(shù)據(jù)庫中的一段軌跡切分為訓練集和測試集，對給定時間點的軌跡進行預(yù)測，發(fā)現(xiàn)該算法對較短時間段的軌跡預(yù)測有較好的效果。

以上研究取得了很多成果，但現(xiàn)有的航線規(guī)劃計算量大，很難做到實時、動態(tài)地完成航線規(guī)劃，無法高效地將其應(yīng)用到互聯(lián)網(wǎng)大數(shù)據(jù)平臺上。

圖1 航線規(guī)劃算法流程圖

2 算法流程設(shè)計

船舶AIS數(shù)據(jù)包含大量航跡信息，凝結(jié)了航海人員多年的航行經(jīng)驗。采用基于AIS動態(tài)數(shù)據(jù)的歷史航線進行航線規(guī)劃具有可行性。

受信號和設(shè)備的影響，AIS數(shù)據(jù)存在數(shù)據(jù)缺失的問題。為更好地利用歷史航線進行航線規(guī)劃，本文首先對原始的航線數(shù)據(jù)進行軌跡插值，并將其存儲到數(shù)據(jù)庫中；對于給定的船位和目的港，從修復(fù)之后的歷史航線中尋找航程最短的航線，作為航線規(guī)劃的結(jié)果；同時，基于當船舶當前的航速和剩余航程，完成抵港時間預(yù)測。航線規(guī)劃算法流程圖見圖1。

2.1 AIS軌跡修復(fù)算法設(shè)計

AIS最基本的信息是由時間和經(jīng)緯度位置組成的時空數(shù)據(jù)，此類數(shù)據(jù)可標記在地圖上形成船舶航行軌跡。但是，受信號傳輸和AIS設(shè)備故障等因素影響，AIS時空數(shù)據(jù)會存在數(shù)據(jù)缺失的問題[7]。本文采用點到點的方式計算當前船位到歷史航線的距離，若航跡存在數(shù)據(jù)缺失的問題，會使計算結(jié)果產(chǎn)生較大的偏差。為解決該問題，需設(shè)計一種AIS軌跡修復(fù)算法。目前，AIS軌跡修復(fù)方法有很多，既可采用聚類算法尋找相似的軌跡進行補全，又可采用插值的方式。本文采用插值的方式，將船舶航速和航向考慮在內(nèi)[8]，首先將AIS數(shù)據(jù)中缺失航段的左右兩端A點和B點的經(jīng)緯度坐標經(jīng)過高斯-克呂格投影轉(zhuǎn)換為高斯坐標(x1,y1)和(x2,y2)。利用A點的AIS動態(tài)信息得到插值點船舶位置的預(yù)測值為

(1)

式(1)中：v1、θ1和t1分別為A點的速度、航行方向和時間。利用B點的AIS動態(tài)信息得到插值點船舶位置的另一個預(yù)測值為

(2)

式(2)中：v2、θ2和t2分別為B點的速度、航行方向和時間。

對通過式(1)和式(2)得到的預(yù)測值(xi1,yi1)和(xi2,yi2)進行加權(quán)平均，權(quán)重根據(jù)A點和B點與插值點的時間差分配，時間差越小，權(quán)重越大，即

(3)

加權(quán)平均之后插值點的坐標為

(4)

對得到的高斯坐標進行高斯投影反算，即得到插值點的經(jīng)緯度坐標。通過查看大量的船舶AIS時空數(shù)據(jù)發(fā)現(xiàn)，相鄰的坐標點一般間隔10 min左右，本文對時間間隔超過20 min的航段采取每間隔10 min進行1次插值的方法，得到修復(fù)之后的完整航跡。

2.2 Hausdorff距離

為衡量修復(fù)之后的軌跡與原始軌跡的相似度，采用Hausdorff距離作為衡量標準。Hausdorff距離是2個點集之間相似程度的一種量度，設(shè)2個點集A={a1,…,ap}，B={b1,…,bq}，這2個點集之間的Hausdorff距離定義為

H(A,B)=max(h(A,B),h(B,A))

(5)

(6)

2.3 歷史航跡查詢與航線規(guī)劃算法設(shè)計

在對原始的軌跡數(shù)據(jù)進行修復(fù)之后，要根據(jù)當前的船位和目的港選擇合適的航線。由于歷史航線眾多，給定目的港的航線數(shù)據(jù)量較大，實時進行航線預(yù)測有一定的難度。為減少計算量，本文在查詢給定目的地的航線時設(shè)置多個查詢條件，以減少查詢結(jié)果的數(shù)據(jù)量。若存在該船出發(fā)港至目的港的歷史航線，則當前點到目的港的航線從此類航線中產(chǎn)生，否則再查詢給定目的港的歷史航線。給定目的港的歷史航線遍布各個方向，基于當前的船位和目的港，方可大體上確定航線的方向，與該方向偏離較大的航線可忽略。根據(jù)當前的船位設(shè)定一個距離參數(shù)，在該距離形成的矩形范圍內(nèi)篩選航線。

給定距離的矩形范圍，直接獲得四點的經(jīng)緯度，計算式為

(7)

式(7)中：φ和λ為船舶當前的經(jīng)緯度位置；φN為矩形正北緯度；φS為矩形正南緯度；λE為矩形正東經(jīng)度；λW為矩形正西經(jīng)度;R為地球半徑；d為用來尋找歷史航線的矩形范圍距離。

本文設(shè)定10～100 km距離劃定當前船位的矩形范圍，由此進行歷史航跡查詢。若根據(jù)10 km距離劃定的矩形范圍內(nèi)包含歷史航線，則查詢停止，并從獲得的航線中尋找最近航線；若根據(jù)10 km距離劃定的矩形范圍內(nèi)不存在歷史航線，則將距離擴展至20 km，以此類推。該方法只獲取特定范圍內(nèi)的歷史航線，能在較大程度上減少每條航線的軌跡數(shù)量，提高計算速度。

本文設(shè)計的算法的應(yīng)用步驟為：

1)采用Python的pymysql模塊連接數(shù)據(jù)庫。

2)對于給定的船位經(jīng)緯度(lon,lat)和目的港代碼port_code，采用sql語句對附近航線矩形范圍內(nèi)的航跡進行查詢；初始搜索的矩形范圍設(shè)定為10 km，若該范圍內(nèi)存在航線，則查詢停止，否則將搜索范圍擴大至20 km，直至將矩形范圍擴大至100 km或查詢到航跡為止；若100 km范圍內(nèi)航跡數(shù)量為0，則說明未找到航線。

3)為方便計算船位到航線的距離，將上述查詢得到的航線和航跡數(shù)據(jù)轉(zhuǎn)換為Python常用數(shù)據(jù)處理模塊Pandas中的DataFrame(DataFrame是一種類似表格的數(shù)據(jù)清洗常用的數(shù)據(jù)結(jié)構(gòu)，包含一組有序的列，既有行索引，又有列索引)。

4)為計算當前船位到每條航線的距離，按line_ID(航線ID)對航線和航跡數(shù)據(jù)的DataFrame進行分組，新增一列來保存船位與每條航線上的軌跡點之間的距離，并在這些距離中找到最小值，作為當前船位到航線的最短距離。

5)計算距離船位最近的航跡點的剩余航線長度。

6)距離當前船位最近的航線即為要預(yù)測的航線，基于船舶航速和剩余航線的長度完成抵港時間預(yù)測。本文在試驗時采用的航速是當前的航速，可根據(jù)實際情況選擇不同的航速來對抵港時間進行預(yù)測。

3 試驗分析

3.1 軌跡修復(fù)

從數(shù)據(jù)庫中提取一條航線的航跡數(shù)據(jù)(見圖2a)，刪除該航段中的20個估計點，采用插值方式進行軌跡修復(fù)，修復(fù)之后的航線見圖2b。

a)原始航線軌跡

b)插值之后的航線軌跡

由圖2可知，航線修復(fù)前后的軌跡基本一致，兩軌跡的Hausdorff距離為1.634 km。這說明本文采用的的插值方式對軌跡修復(fù)有明顯的效果。本文設(shè)定Hausdorff閾值為20 km，超過該閾值則保留原軌跡，否則使用插值之后的軌跡。

3.2 航線規(guī)劃

試驗的運行環(huán)境為：聯(lián)想筆記本；i7處理器；內(nèi)存12 GB；64位操作系統(tǒng)；Win10家庭版。選取在航的水上移動通信業(yè)務(wù)標識碼(Maritime Mobile Service Identify,MMSI)為477077700的集裝箱船為研究對象，其當前的經(jīng)緯度船位為(123.343 417，33.209 000)，出發(fā)港為新加坡港，目的港為天津港。按歷史航跡查詢和選擇算法共查詢出13條航線，詳細信息見表1，其中距離當前船位最近的航線ID是62338，此航線由上海到天津，與試驗船舶的目的港相同。將規(guī)劃的航線呈現(xiàn)在地圖上，結(jié)果見圖3，其中：實線部分為試驗船真實航跡；虛線部分為使用ID為62338的航線預(yù)測的航跡。

表1 試驗船當前船位附近航線

船舶當前的航速為14.3 kn，當前的時間為2020-01-15T16:54:35，根據(jù)當前的航速預(yù)測的抵港時間為2020-01-17T07:55:00。船舶的實際航行路線見圖4。圖4中的黑點位置為該船當時的船位，從該點到天津港的航線與本文預(yù)測的航跡基本上無差異，抵港時間比預(yù)測的時間晚7 h左右，原因是算法所用航速為當前航速，而在實際航行過程中(特別是在進港和靠泊時)，航速會發(fā)生變化，同時會受港口排班因素的影響，因此會產(chǎn)生一定的誤差，該算法還有進一步優(yōu)化的空間。

圖3 航線預(yù)測

圖4 試驗船實際航行軌跡

按照上述算法設(shè)計，從歷史AIS數(shù)據(jù)中隨機抽取10艘船，對已完成的航次進行航線預(yù)測和驗證，結(jié)果見表2。從表2中可看出，根據(jù)當前航速預(yù)測的抵港時間與實際時間存在一定的差異，誤差基本上在1 d以內(nèi)，且整體的運行速度基本上在3 s左右，能滿足大數(shù)據(jù)平臺的實時性要求。由于該算法是在單機環(huán)境下運行的，因此運行速度較慢，在大數(shù)據(jù)平臺下，航線規(guī)劃的速度基本上控制在1 s以內(nèi)。

表2 10條歷史航次的航線預(yù)測

4 結(jié) 語

本文對基于海量的AIS動態(tài)數(shù)據(jù)生成的歷史航線進行了航線預(yù)測。在采用插值算法對原始航線數(shù)據(jù)進行修復(fù)之后，對于給定的當前船位和目的港，從數(shù)據(jù)庫中獲取合適的航線，并選擇距離當前船位最近的航線作為最優(yōu)航線，同時采用當前的航速預(yù)測抵港時間。試驗結(jié)果表明,本文提出的航線規(guī)劃算法能合理地對任意位置的船舶進行航線規(guī)劃和抵港時間預(yù)測，誤差基本上能控制在24 h以內(nèi)，但在當前航速過低或過高的情況下，誤差會偏大。

為避免利用當前的航速進行航線規(guī)劃造成預(yù)測誤差過大，可人工設(shè)定航速參數(shù)值，或?qū)Ａ康腁IS數(shù)據(jù)進行大數(shù)據(jù)分析，得到合理的航速范圍。