段俊利，韓 懿

(中遠(yuǎn)海運(yùn)科技股份有限公司，上海 200135)

0 引 言

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

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

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

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

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

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

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

2 算法流程設(shè)計(jì)

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

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

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

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

(1)

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

(2)

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

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

(3)

加權(quán)平均之后插值點(diǎn)的坐標(biāo)為

(4)

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

2.2 Hausdorff距離

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

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

(5)

(6)

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

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

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

(7)

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

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

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

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

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

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

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

5)計(jì)算距離船位最近的航跡點(diǎn)的剩余航線長(zhǎng)度。

6)距離當(dāng)前船位最近的航線即為要預(yù)測(cè)的航線，基于船舶航速和剩余航線的長(zhǎng)度完成抵港時(shí)間預(yù)測(cè)。本文在試驗(yàn)時(shí)采用的航速是當(dāng)前的航速，可根據(jù)實(shí)際情況選擇不同的航速來(lái)對(duì)抵港時(shí)間進(jìn)行預(yù)測(cè)。

3 試驗(yàn)分析

3.1 軌跡修復(fù)

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

a)原始航線軌跡

b)插值之后的航線軌跡

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

3.2 航線規(guī)劃

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

表1 試驗(yàn)船當(dāng)前船位附近航線

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

圖3 航線預(yù)測(cè)

圖4 試驗(yàn)船實(shí)際航行軌跡

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

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

4 結(jié) 語(yǔ)

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

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