船舶進(jìn)離港行為捕獲算法設(shè)計(jì)與實(shí)現(xiàn)

王永明 饒全成 姚萍

摘要：

針對(duì)在設(shè)計(jì)船舶進(jìn)離港行為捕獲算法時(shí)存在港口范圍難定義、AIS數(shù)據(jù)的經(jīng)緯度誤差造成船舶頻繁進(jìn)出港區(qū)邊界等問題，將全球AIS數(shù)據(jù)與港口數(shù)據(jù)相結(jié)合，設(shè)計(jì)船舶進(jìn)離港行為捕獲算法。根據(jù)船舶速度、位置、運(yùn)動(dòng)特性等信息，實(shí)現(xiàn)對(duì)船舶進(jìn)離港、停泊等行為的判斷。利用緯度分桶法、網(wǎng)格法和Kd樹法實(shí)現(xiàn)基于船舶位置的港口匹配。實(shí)際數(shù)據(jù)測(cè)試表明，網(wǎng)格法的港口匹配時(shí)效性最好，每秒可處理約16萬條AIS數(shù)據(jù)。隨機(jī)選取30艘船對(duì)算法進(jìn)行驗(yàn)證，結(jié)果表明船舶軌跡與捕獲到的船舶進(jìn)離港事件相符。

關(guān)鍵詞：

船舶行為; 自動(dòng)識(shí)別系統(tǒng)（AIS）; 港口匹配; 進(jìn)離港

中圖分類號(hào)： U697.1

文獻(xiàn)標(biāo)志碼： A

Design and implementation of capturing algorithm

for ship entering and leaving port behavior

WANG Yongming1， RAO Quancheng2， YAO Ping2

（1. Navigation College， Dalian Maritime University， Dalian 116026， Liaoning， China;

2. Institute of Computing Technology， Chinese Academy of Sciences， Beijing 100190， China）

Abstract：

In the design process of capturing algorithm for ship entering and leaving port behavior， it is difficult to define port scope， and ships go in and out of port boundary frequently due to latitude and longitude errors of AIS data. To solve these problems， global AIS data and port data are combined to design an algorithm for capturing ship entering and leaving port behavior. The velocity， position and motion characteristics of ships are used to identify ship behaviors such as entering and leaving port， mooring. The latitude point barrel method， the grid method and the Kd tree method are used to realize port match based on ship position. The real data test shows that the grid method is optimal in time and effect for port match， and it can handle about 160 000 messages in 1 s. Thirty ships are selected randomly to verify the algorithm， and the result shows that the ship tracks accord with the events of entering and leaving port of captured ships.

Key words：

ship behavior; automatic identification system （AIS）; port match; entering and leaving port

收稿日期： 2017-05-22

修回日期： 2017-09-20

基金項(xiàng)目： 國(guó)家自然科學(xué)基金（51309044）

作者簡(jiǎn)介：

王永明（1973—）， 男， 安徽壽縣人，高級(jí)工程師，博士，研究方向?yàn)楹竭\(yùn)信息化，（E-mail）wangyongming@cttic.cn

0 引 言

船舶軌跡數(shù)據(jù)是一種典型的時(shí)空大數(shù)據(jù)，各種船舶監(jiān)測(cè)系統(tǒng)（LRIT，VMS，VDR和AIS [1]等）所獲取的船舶軌跡數(shù)據(jù)記錄了船舶及海上交通的時(shí)空變化過程，蘊(yùn)含了豐富的語義信息。對(duì)船舶軌跡數(shù)據(jù)進(jìn)行挖掘可發(fā)現(xiàn)船舶群體活動(dòng)的時(shí)空特征及演化規(guī)律[2]、船舶主航跡帶及其成因等。掌握船舶進(jìn)離港的規(guī)律，對(duì)于船舶軌跡的分析[3]具有重要意義。

港口是船舶航行中的關(guān)鍵節(jié)點(diǎn)，也是整個(gè)船舶航行過程中語義信息最豐富的環(huán)節(jié)。在港船舶會(huì)產(chǎn)生包括接受引航、等待、卸貨、裝載、理貨、報(bào)關(guān)等諸多行為。狹義的船舶進(jìn)離港就是進(jìn)港和出港航行，廣義的則是包括船舶進(jìn)入港區(qū)、接受引航、在錨區(qū)停留等待、在泊位作業(yè)、離開泊位出航、機(jī)動(dòng)航行等的全部過程。對(duì)舶舶進(jìn)離港行為的精細(xì)判斷，對(duì)于優(yōu)化港區(qū)引航調(diào)度、提升港口作業(yè)效率具有重大的意義[4]。

快速、準(zhǔn)確地挖掘出船舶進(jìn)離港的行為是對(duì)船舶進(jìn)離港行為捕獲算法的要求。本文將算法分為兩個(gè)階段：船舶停泊檢測(cè)階段和船舶進(jìn)離港檢測(cè)階段。在船舶停泊檢測(cè)階段對(duì)船舶的航行與停泊特征進(jìn)行區(qū)分。在船舶進(jìn)離港檢測(cè)階段通過對(duì)速度、航向、活動(dòng)范圍等因素的綜合考慮，捕獲船舶進(jìn)離港事件。本文采用緯度分桶法、網(wǎng)格法和Kd樹法解決船舶進(jìn)離港行為捕獲算法中的核心問題：快速找到距離當(dāng)前船舶最近的港口。通過對(duì)港口位置的先驗(yàn)知識(shí)的利用，結(jié)合相關(guān)的數(shù)據(jù)結(jié)構(gòu)，不斷提高算法效率。最終發(fā)現(xiàn)，用網(wǎng)格法每秒可處理約16萬條數(shù)據(jù)（目前系統(tǒng)接收的實(shí)時(shí)AIS數(shù)據(jù)每秒約3 000條），滿足實(shí)時(shí)處理的需求。

1 基于AIS數(shù)據(jù)的船舶進(jìn)離港

目前，很少看到有關(guān)船舶進(jìn)離港行為捕獲算法的文獻(xiàn)。在一些根據(jù)船舶進(jìn)離港數(shù)據(jù)進(jìn)行研究的文獻(xiàn)[5-6]中，船舶進(jìn)離港行為捕獲算法非常粗糙，且沒有清晰地展現(xiàn)計(jì)算過程。這一方面是因?yàn)槟壳按斑M(jìn)離港行為判斷算法只在一些航運(yùn)網(wǎng)站（如國(guó)內(nèi)的寶船網(wǎng)、船訊網(wǎng)，國(guó)外的Marine Traffic）上使用，另一方面是因?yàn)榇斑M(jìn)離港行為判斷算法有自身的一些難點(diǎn)需要解決。

首先，AIS的航次信息中含有ETA及目的地這兩個(gè)字段，即預(yù)計(jì)到達(dá)時(shí)間和目的港。最簡(jiǎn)單的船舶進(jìn)離港行為可直接根據(jù)其靜態(tài)信息（船名、船舶呼號(hào)、MMSI、IMO編號(hào)等）得到。然而，靜態(tài)信息是在設(shè)備安裝時(shí)由專業(yè)技術(shù)人員根據(jù)船舶國(guó)籍證書輸入的，而有些工程師在安裝時(shí)沒有嚴(yán)格按照相關(guān)規(guī)則設(shè)置靜態(tài)信息，各類船舶的操作員均未按規(guī)定操作AIS設(shè)備，從而造成AIS靜態(tài)信息錯(cuò)誤，無法直接使用。比如，對(duì)一張含有635 055條數(shù)據(jù)的靜態(tài)表進(jìn)行分析發(fā)現(xiàn)，船舶MMSI不正常的有27 186條（占4%），呼號(hào)不可用的有287 167條（占45%），目的港不可用的有459 998條（占72%），ETA不可用的有507 481條（占80%）。因此，直接根據(jù)靜態(tài)信息判斷船舶進(jìn)離港是不可取的。

其次，港口區(qū)域較難定義。有的港口比較小，適合用基于港區(qū)的位置和大小設(shè)置的圓表示。有的港口，如上海港，范圍非常大，包含幾百個(gè)泊位和錨區(qū)，很難用一個(gè)簡(jiǎn)單的幾何圖形來描述，則可用自定義的不規(guī)則區(qū)域來描述。

再次，每新獲取一條AIS數(shù)據(jù)，算法都會(huì)對(duì)所有的港口進(jìn)行遍歷，現(xiàn)階段算法還能勉強(qiáng)滿足系統(tǒng)需要，而一旦有更多的港口數(shù)據(jù)，用該算法遍歷港口所需要的時(shí)間就會(huì)增加，難以滿足在線處理的實(shí)時(shí)性要求。

最后，有些船的AIS信息發(fā)送不正常。比如，檢測(cè)到某船t1時(shí)刻在港口A，t2時(shí)刻在港口B，但由于該船主動(dòng)關(guān)閉了AIS，所以其出港口A未被檢測(cè)到。這

會(huì)對(duì)后續(xù)利用進(jìn)離港事件進(jìn)行分析的其他應(yīng)用產(chǎn)生影響。本文采取的做法是將此前出港口A事件補(bǔ)全，并給出異常等級(jí)參考。

1.1 基于AIS的船舶進(jìn)離港定義

港口區(qū)域一般可被定義成圓形或矩形，相應(yīng)圓的半徑或矩形的長(zhǎng)、寬可以根據(jù)港口的大小設(shè)置。由于AIS信息中的經(jīng)緯度有一定的誤差，如果船舶在劃出的港口區(qū)域附近連續(xù)不斷地發(fā)出AIS信息，僅按船舶的位置來匹配港口的位置、計(jì)算進(jìn)離港事件，那么當(dāng)船舶處于區(qū)域邊界時(shí)算法會(huì)判斷出一系列的進(jìn)離港事件，從而可能導(dǎo)致利用進(jìn)離港事件進(jìn)行分析的其他應(yīng)用判斷其為異常點(diǎn)，或者至少會(huì)受到干擾。因此，只有結(jié)合船舶的速度、轉(zhuǎn)向率、航行狀態(tài)等，才能更準(zhǔn)確地判斷船舶進(jìn)離港事件。

很多沿著江河航行的船舶可能實(shí)際進(jìn)入了某港區(qū)水域，但沒有發(fā)生靠離泊位的行為。如每天經(jīng)過新加坡港的船舶數(shù)量龐大，但很多船舶只是過境通航，并沒有進(jìn)出新加坡港。

基于以上考慮，本文對(duì)船舶進(jìn)離港的定義為：船舶以低于2 kn 的速度進(jìn)入港口范圍內(nèi)，且以高于2 kn的速度離開港口范圍，進(jìn)入與離開的時(shí)間間隔不小于30 min，船舶在港期間活動(dòng)范圍不大于1 000 m;在此期間，船舶分別發(fā)生一次進(jìn)港和離港事件。港口范圍一般用港口中心經(jīng)緯度加半徑表示，港口半徑根據(jù)其大小進(jìn)行差異化設(shè)置。形狀不規(guī)則的港口可用矩形或引入JTS開源模塊來表示。（JTS是加拿大的 Vivid Solutions公司做的一套開放源碼的 Java API，它提供了一套空間數(shù)據(jù)操作的核心算法。）

1.2

船舶進(jìn)離港行為時(shí)空分析和意義

通過研究船舶進(jìn)離港行為，可以了解船舶航行規(guī)律和港口運(yùn)作規(guī)律[7-8]?；诖斑M(jìn)離港事件，可以對(duì)船舶和港口進(jìn)行一系列有意義的分析，如統(tǒng)計(jì)港口吞吐量、統(tǒng)計(jì)全球或所關(guān)注港口的船舶進(jìn)出情況、估算港口的運(yùn)作效率等，并為決策者提供一定的參考信息。這對(duì)貨主選擇效率高的航運(yùn)公司和航運(yùn)公司選擇效率高的港口碼頭具有重要參考價(jià)值。

目前船舶進(jìn)離港信息僅掌握在港口經(jīng)營(yíng)人手中，是分散且不對(duì)外公開的。AIS船位信息是可以通過廣播公開獲得的，利用公開信息辨別進(jìn)離港事件，在經(jīng)濟(jì)情報(bào)獲得、安全情報(bào)獲得、適應(yīng)于大數(shù)據(jù)時(shí)代的數(shù)據(jù)素材生成方面具有重大意義。

在經(jīng)濟(jì)情報(bào)獲得方面，通過船舶進(jìn)離港行為將船舶整個(gè)航程進(jìn)行切分，結(jié)合船舶檔案、船型、吃水、靠泊時(shí)間等，能夠?qū)Q(mào)易量做比較精準(zhǔn)的推測(cè)，進(jìn)而掌握大宗貨物的流向，分析宏觀經(jīng)濟(jì)。同時(shí)，通過分析船舶進(jìn)離港行為，挖掘船舶航行規(guī)律，可以評(píng)估航運(yùn)公司、港口運(yùn)營(yíng)效率。

在安全情報(bào)獲得方面，船舶進(jìn)離港行為分析可以推廣到進(jìn)離區(qū)域分析。對(duì)于一些關(guān)鍵區(qū)域、作業(yè)平臺(tái)區(qū)域、敏感對(duì)峙區(qū)域等進(jìn)行進(jìn)離區(qū)域分析，能夠有效地追蹤和甄別潛在的海上犯罪和敵對(duì)力量，包括海上走私、海上賭博、海上販毒、圍攻海上作業(yè)平臺(tái)以及海盜等。

在生成適應(yīng)于大數(shù)據(jù)時(shí)代的數(shù)據(jù)素材方面，可以增加語義、切割航線段。水上交通與陸上交通不同，其語義信息并不豐富，目前在大數(shù)據(jù)時(shí)代也沒有很好的辦法來套用如機(jī)器學(xué)習(xí)、深度學(xué)習(xí)之類的方法。船舶進(jìn)離港事件將航線段進(jìn)一步切分成帶有語義標(biāo)記的航行事件，使得船舶航行不再是一系列軌跡點(diǎn)記錄，而是一系列帶有語義信息的事件，這一系列事件可以作為高階處理方法的素材。

2 船舶進(jìn)離港行為捕獲算法

在船舶靜態(tài)AIS信息不可用的情況下，為快速得到船舶進(jìn)離港事件，可對(duì)船舶動(dòng)態(tài)AIS信息進(jìn)行充分挖掘。綜合考慮船舶的速度、位置、運(yùn)動(dòng)特征等，在線檢測(cè)出全球船舶進(jìn)離港事件。

船舶在到港時(shí)會(huì)低速進(jìn)入港區(qū)，低速到達(dá)錨地，等待有可用的泊位（并持續(xù)一段較長(zhǎng)時(shí)間）。其間，船舶的活動(dòng)范圍有限。本文對(duì)低速閾值、活動(dòng)范圍閾值給出了經(jīng)驗(yàn)值，并依據(jù)此經(jīng)驗(yàn)值檢測(cè)船舶進(jìn)離港事件。

為快速得到船舶所在的港口，先對(duì)全球港口在地理位置上進(jìn)行預(yù)處理，構(gòu)造相關(guān)的數(shù)據(jù)結(jié)構(gòu)，使得查詢船舶所處港口的速度得到大幅提升，從而滿足在線檢測(cè)的需求。

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

AIS信息在傳輸過程中會(huì)出現(xiàn)一定的錯(cuò)誤，因此在

輸入AIS數(shù)據(jù)前，需要對(duì)其進(jìn)行預(yù)處理，刪除明顯錯(cuò)誤的AIS數(shù)據(jù)，如：經(jīng)度的正常范圍為-180°～180°，緯度的正常范圍為-90°～90°，不在此范圍內(nèi)的AIS數(shù)據(jù)都會(huì)被刪除。[9]

2.2 船舶進(jìn)離港行為捕獲算法設(shè)計(jì)

對(duì)某單船的速度進(jìn)行研究，其速度隨時(shí)間的變

化大致如圖1所示。T1時(shí)刻船舶進(jìn)港，T1～T2時(shí)間

圖1 單船速度變化示意圖

圖2 船舶進(jìn)離港行為捕獲

算法流程

內(nèi)船舶低速在港區(qū)內(nèi)移動(dòng)，T2時(shí)刻船舶離港。根據(jù)船舶速度和活動(dòng)范圍可判斷出船舶航行狀態(tài)的變化，再結(jié)合船舶和港口的位置即可對(duì)船舶進(jìn)離港行為作出判斷。

在線船舶進(jìn)離港行為捕獲算法分為兩個(gè)階段：（1）根據(jù)船舶速度、活動(dòng)范圍、軌跡點(diǎn)數(shù)等判斷其是否發(fā)生停泊事件;（2）結(jié)合全球港口信息，檢測(cè)船舶停泊事件是否為船舶進(jìn)離港事件。算法流程見圖2。

根據(jù)上述分析設(shè)計(jì)出船舶停泊事件檢測(cè)的流程，見圖3。

算法維護(hù)每條船的低速軌跡序列，根據(jù)每條實(shí)時(shí)的AIS數(shù)據(jù)：若船舶速度低于給定的閾值，則將該船加入到相應(yīng)的序列;若船舶速度高于閾值，則認(rèn)為該船是從停泊狀態(tài)轉(zhuǎn)到航行狀態(tài)，是一個(gè)可能的停泊結(jié)束事件。若確實(shí)存在該船的低速軌跡點(diǎn)序列，則此軌跡點(diǎn)序列的首尾軌跡點(diǎn)被認(rèn)為是停泊事件的起訖點(diǎn)。為能夠判斷準(zhǔn)確，接著加入平均速度、活動(dòng)范圍等信息進(jìn)行進(jìn)一步確認(rèn)。首先判斷該船的低速軌跡序列的點(diǎn)數(shù)是否大于設(shè)定的閾值，以免低速軌跡序列點(diǎn)數(shù)太少，給停泊事件檢測(cè)造成誤差。若點(diǎn)數(shù)符合要求，則求出軌跡序列平均速度，若平均速度大于等于閾值，則認(rèn)為停泊狀態(tài)可信度不高。最后，求出軌跡點(diǎn)序列的最大、最小經(jīng)緯度，即將該船的活動(dòng)范圍看成一個(gè)矩形，將矩形對(duì)角線的一半作為該船的活動(dòng)半徑。若此活動(dòng)半徑在設(shè)定的閾值范圍內(nèi)，則可判斷這是一個(gè)停泊事件。

圖3 船舶停泊事件檢測(cè)流程

將軌跡點(diǎn)序列起訖點(diǎn)的AIS信息字段中的定位時(shí)間分別設(shè)為停泊事件的起止時(shí)間，并將平均速度、活動(dòng)半徑等參數(shù)記錄到該船停泊事件中。在上述計(jì)算平均速度和活動(dòng)半徑的過程中，為確保準(zhǔn)確性，省略了軌跡點(diǎn)序列前后的部分軌跡點(diǎn)，僅將中間數(shù)據(jù)質(zhì)量更高的軌跡點(diǎn)序列用于計(jì)算，以進(jìn)一步提高船舶停泊事件的可信度。

表1 P0與P1的比較邏輯

當(dāng)?shù)玫酱巴２词录螅Y(jié)合全球港口信息可得到船舶進(jìn)離港事件。船舶停泊檢測(cè)流程輸出的結(jié)果為船舶停泊對(duì)象STOP，屬性包括活動(dòng)半徑、中心經(jīng)緯度、停泊起始時(shí)刻、停泊結(jié)束時(shí)刻等。計(jì)算出此中心與最近的港口P1的距離，且判斷此距離是否小于設(shè)定的閾值（此閾值反映港口區(qū)域的大?。Ｏ到y(tǒng)維護(hù)一張全局在港船舶列表，列表的鍵為船舶MMSI，

值為對(duì)應(yīng)的停泊港口P0。同時(shí)，每個(gè)港口各自維護(hù)一張?jiān)诟鄞傲斜?，列表的鍵為船舶MMSI，值為停泊對(duì)象STOP。比較P0與P1的關(guān)系，可得到船舶的進(jìn)離港事件。比較邏輯如表1所示，其中p0和p1為具體的港口。

當(dāng)P1和P0均為NULL時(shí)，說明船A正處于動(dòng)力航行狀態(tài)。

當(dāng)P1為NULL，P0不為NULL時(shí)，說明船A之前在港口p0內(nèi)，當(dāng)前不在任何港口內(nèi)，表明船A已經(jīng)離開港口p0。

當(dāng)P1不為NULL，P0為NULL時(shí)，說明船A之前未到任何港口，當(dāng)前在港口p1內(nèi)，表明船A已經(jīng)進(jìn)入港口p1。

當(dāng)P1和P0均不為NULL時(shí)，若P1=P0則說明船舶停泊在p1內(nèi)，若P1≠P0則說明船A此刻進(jìn)入p1，之前某一時(shí)刻離開p0。離開p0事件并不是此時(shí)發(fā)生的，而是之前某一時(shí)刻發(fā)生的，但由于該船的AIS信息異常，如該船主動(dòng)關(guān)閉AIS發(fā)射器，所以該船的離港事件未能被及時(shí)檢測(cè)到。若需要區(qū)分此類事件，可對(duì)其做相應(yīng)的異常標(biāo)記。

船舶進(jìn)離港事件檢測(cè)流程見圖4。船舶在港口內(nèi)可能會(huì)在錨地與泊位間移動(dòng)，每次移動(dòng)均會(huì)產(chǎn)生停泊事件，即系統(tǒng)可能會(huì)檢測(cè)到多次停泊事件。對(duì)于這種情況，只需更新當(dāng)前港口內(nèi)對(duì)應(yīng)于該船的STOP對(duì)象的停泊結(jié)束時(shí)間。當(dāng)檢測(cè)到進(jìn)港事件時(shí)，向全局在港船舶列表中增加相對(duì)應(yīng)的船舶與所停泊港口的鍵值對(duì)，同時(shí)向發(fā)生船舶停泊事件的港口所維護(hù)的在港船舶列表中添加船舶與STOP對(duì)象的鍵值對(duì);當(dāng)檢測(cè)到離港事件時(shí)，則需要?jiǎng)h掉相應(yīng)的鍵值對(duì)。

船舶進(jìn)離港行為捕獲算法偽代碼如下：

輸入：船舶STOP對(duì)象數(shù)據(jù)流

輸出：船舶進(jìn)離港事件流

Init HashMap<Ship，PORT>m;//所有在港船舶

Init HashMap<Ship，STOP>s;//每個(gè)港口維護(hù)的在港船舶

For stop in STOP_stream：

Ship ship = new Ship（stop）;

Port P1 = CurInPort（ship）; //當(dāng)前距離最近港口

If （Dist（P1， ship） > DistThreshold） continue;

Port P0 = m.get（ship）; //全局表中所對(duì)應(yīng)港口

if（P1==NULL && P0==NULL） nothing to do;

Else if （P1==NULL && P0！=NULL）

generateEvent（ship， P0， departure）; //離港

m.remove（ship）; //維護(hù)所有在港船舶

P0.s.remove（ship）; //維護(hù)P0的在港船舶

Else if （P1！=NULL && P0==NULL）

generateEvent（ship， P1， In）//進(jìn)港

m.put（ship， P1）;

P1.s.add（ship， stop）;

Else if （P1！=NULL && P0！=NULL）

if （P1==P0） upDateEndTime（P0， stop）;

Else //先離港，再進(jìn)港

generateEvent（ship， P0， departure）;

m.remove（ship）;

P0.s.remove（ship）;

generateEvent（ship， P1， In）;

m.put（ship， P1）;

P1.s.add（ship， stop）;

End

圖4 船舶進(jìn)離港事件檢測(cè)流程

從上述偽代碼可看出，通過系統(tǒng)所維護(hù)的全局在港船舶列表，可以快速找到P0，要得到P1則需要通過實(shí)時(shí)計(jì)算當(dāng)前距船舶最近的港口，因此計(jì)算的快慢決定了算法的效率。提高算法效率的核心在于如何快速找到與當(dāng)前船舶距離最近的港口。

3 基于船舶位置的港口匹配方法

基于當(dāng)前船舶位置，設(shè)計(jì)緯度分桶法、網(wǎng)格法和Kd樹法等3種算法對(duì)港口進(jìn)行快速檢索。這3種算法均利用港口的先驗(yàn)地理信息，將全球港口存儲(chǔ)到特定的數(shù)據(jù)結(jié)構(gòu)中，以加快查詢與當(dāng)前船舶最近的港口的速度。

圖5 緯度分桶法桶編號(hào)示意圖

3.1 算法介紹

緯度分桶法：根據(jù)緯度將全球港口劃分到180個(gè)桶中。算法根據(jù)AIS中的緯度字段快速定位船舶所在的緯度桶，遍歷相鄰的3個(gè)緯度桶。緯度分桶法桶編號(hào)示意圖見圖5。

網(wǎng)格法[10]：在緯度分桶的基礎(chǔ)上，對(duì)經(jīng)度也劃分桶，形成網(wǎng)格，見圖6。將全球港口劃分到1°×1°的網(wǎng)格中。算法根據(jù)AIS中的經(jīng)度、緯度字段快速定位船舶所在網(wǎng)格，遍歷相鄰9個(gè)網(wǎng)格中的所有港口，找到距離當(dāng)前船舶最近的港口。一般1°×1°的網(wǎng)格邊長(zhǎng)約為60 n mile（約110 km），遠(yuǎn)遠(yuǎn)超過港區(qū)大小。因此，其他網(wǎng)格中的港口與該船的距離必然大于設(shè)定距離閾值，不合要求，即其他網(wǎng)格中的港口與該船的距離不用計(jì)算。

圖6 網(wǎng)格法網(wǎng)格編號(hào)示意圖

Kd樹[11-12]法：Kd樹（多維二叉搜索樹）是由Bentley于1975年提出的。通常用Kd樹做數(shù)據(jù)索引和查詢。Kd樹通過把一個(gè)空間劃分成多個(gè)不相交的子空間來組織k維空間中的點(diǎn)集，其中小于等于劃分值的點(diǎn)劃分到左子樹，大于劃分值的點(diǎn)劃分到右子樹。Kd樹本質(zhì)上是一種二元搜索樹，它用超平面把空間劃分成若干子區(qū)間來對(duì)數(shù)據(jù)進(jìn)行搜索，從而可以高效地找到某一點(diǎn)的最近鄰。將全球港口按照經(jīng)緯度劃分存儲(chǔ)到一棵二叉樹中的步驟：首先，將所有港口按經(jīng)度排序，取排在中間的港口作為第1個(gè)節(jié)點(diǎn)插入Kd樹;然后，將余下的港口按緯度排序，取排在中間的港口作為第2個(gè)節(jié)點(diǎn)插入Kd樹;重復(fù)上述步驟，最終所建的二叉樹是一棵高度平衡的二叉樹。找到Kd樹中某船的最近鄰，即距離該船最近的港口。

3.2 算法分析

前述3種算法都利用港口的地理信息預(yù)先構(gòu)建了一張“表”，在實(shí)時(shí)查詢與某船距離最近的港口時(shí)，利用這張“表”加快查詢的速度。因此，港口在“表”中分布得越均勻，查詢的速度越快。目前系統(tǒng)中港口總數(shù)為7 805個(gè)。

用緯度分桶法劃分的桶中的港口數(shù)分布見圖7。由圖7可知：大部分港口集中在小部分緯度桶中;從第120號(hào)到第150號(hào)的桶中的港口總數(shù)為4 904個(gè)，占系統(tǒng)中港口總數(shù)的62.8%。這說明港口在緯度桶中的分布極不均勻。

圖7 用緯度分桶法劃分的桶中港口數(shù)分布

用網(wǎng)格法劃分的網(wǎng)格中的港口數(shù)分布見圖8。由圖8可知，3.4%的網(wǎng)格中的港口總數(shù)占系統(tǒng)中港口總數(shù)的90%。與緯度分桶法一樣，網(wǎng)格中的港口數(shù)分布極不均勻。

圖8 用網(wǎng)格法劃分的網(wǎng)格中的港口數(shù)分布

圖9 Kd樹法劃分效果

Kd樹法的劃分效果見圖9。豎直線為豎直劃分（根據(jù)X坐標(biāo)劃分），水平線為水平劃分（根據(jù)Y坐標(biāo)劃分）。由圖9可知，Kd樹法劃分出的空間并不均勻，地圖下方的空白較多，空間較大，而地圖中部空間小且子空間排列緊密。

現(xiàn)實(shí)世界中的港口分布并不均勻，因此在用緯度分桶法和網(wǎng)格法劃出的桶和網(wǎng)格中的港口分布也不均勻。在極端情況下，所有的港口都聚集在一個(gè)桶或一個(gè)網(wǎng)格中，計(jì)算效率退化為與暴力解法的計(jì)算效率相等。

下面具體分析算法的時(shí)空復(fù)雜度。設(shè)港口數(shù)為M，待計(jì)算AIS信息條數(shù)為N。用緯度分桶法設(shè)置的桶的數(shù)量為D，而用網(wǎng)格法設(shè)置的網(wǎng)格數(shù)為D0·D1。

對(duì)于緯度分桶法和網(wǎng)格法，建“表”的時(shí)間分別花在定位港口所對(duì)應(yīng)的桶和網(wǎng)格上。因此，時(shí)間復(fù)雜度均為O（M），空間復(fù)雜度則除了要存儲(chǔ)每個(gè)港口還要存儲(chǔ)桶或網(wǎng)格，故分別為O（D+M）和

O（D0·D1+M）。對(duì)于Kd樹法，建“表”的插入時(shí)間為log2M，因此總的建表時(shí)間為O（Mlog2M），空間復(fù)雜度則為O（M）。

在查找時(shí)間方面，假定AIS數(shù)據(jù)均勻分布，每個(gè)桶或網(wǎng)格被查找到的概率相等。對(duì)于緯度分桶法，M個(gè)港口均勻分布在D個(gè)桶中，查找時(shí)間復(fù)雜度為O（（1+M/D）·N）。對(duì)于網(wǎng)格法，M個(gè)港口均勻分布在D0·D1個(gè)網(wǎng)格中，查找時(shí)間復(fù)雜度為O（（1+M/（D0·D1））·N）。對(duì)于Kd樹法[13]，平均復(fù)雜度為O（（Mlog2M）·N），在最差的情況下要遍歷到每個(gè)港口，因此，在最差的情況下時(shí)間復(fù)雜度為O（M·N）。

3.3 運(yùn)行效率測(cè)試與分析

為了測(cè)試3種算法在真實(shí)數(shù)據(jù)中的表現(xiàn)，選取全球2015年10—12月的AIS數(shù)據(jù)。在硬件平臺(tái)為Xeon（R） CPU E3-1200（@3.10 GHz），內(nèi)存8 GB，軟件為Windows 7 x64和JRE 1.7.0的試驗(yàn)環(huán)境下

對(duì)3種算法進(jìn)行效率測(cè)試。分別使用1萬條、5萬

條、10萬條、50萬條、100萬條、500萬條、1 000萬條

圖10 系統(tǒng)采用3種算法處理

AIS數(shù)據(jù)所耗費(fèi)的時(shí)間

AIS數(shù)據(jù)作為測(cè)試集，分別記錄系統(tǒng)采用3種算法處理完所有數(shù)據(jù)所耗費(fèi)的時(shí)間（均取3次試驗(yàn)的平均值）。試驗(yàn)結(jié)果見圖10。

從圖10可以看出，3種算法的時(shí)間效率均與AIS數(shù)據(jù)數(shù)量呈線性關(guān)系。從圖10中還可以看出：網(wǎng)格法的效率最高;Kd樹法由于每次進(jìn)行最近鄰查詢都要進(jìn)行多次距離計(jì)算，所以其算法效率較低;緯度分桶法和網(wǎng)格法都天然地減少了待查詢的港口數(shù)量，因此效率都較Kd樹法高。

4 船舶進(jìn)離港行為捕獲算法正確性驗(yàn)證

為驗(yàn)證系統(tǒng)所捕獲到的進(jìn)離港事件的正確性，隨機(jī)選取客船、貨船和漁船各10艘進(jìn)行對(duì)比分析。圖11所示為其中1艘MMSI為235000864的客船的歷史軌跡（數(shù)據(jù)來源于寶船網(wǎng)）。從數(shù)據(jù)庫(kù)中查詢到系統(tǒng)捕獲到的進(jìn)離港事件，見圖12。比較圖11

圖11 某客船的歷史軌跡

圖12 捕獲到的某客船的進(jìn)離港事件

與12可知該客船先后經(jīng)過港口LOCHMADDY，UIG，TARBERT，系統(tǒng)捕獲到了相應(yīng)的進(jìn)離港事件。所選取的其他客船、貨船和漁船的進(jìn)離港事件也均被正確捕獲，這里不再贅述。

隨機(jī)抽取的船舶軌跡與系統(tǒng)捕獲到的船舶進(jìn)離港事件能很好地吻合，表明船舶進(jìn)離港捕獲算法能正確捕獲船舶的進(jìn)離港事件。

5 結(jié)束語

在線船舶進(jìn)離港捕獲算法存在港口范圍難定義、AIS信息中的經(jīng)緯度誤差造成的船舶頻繁進(jìn)出港區(qū)邊界等問題。本文為解決這些問題做了有效嘗試，首次在全球港口數(shù)據(jù)庫(kù)上對(duì)全球AIS數(shù)據(jù)進(jìn)行試驗(yàn)。試驗(yàn)結(jié)果表明，網(wǎng)格法在船舶進(jìn)離港行為捕獲算法中取得了最高的時(shí)間效率，具有實(shí)際應(yīng)用的價(jià)值。由于現(xiàn)實(shí)世界的港口分布并不均勻，未來可以考慮分區(qū)域來劃分網(wǎng)格，以達(dá)到更高的時(shí)間效率。

如果能夠捕獲全球船舶的進(jìn)離港事件，用統(tǒng)一的船舶進(jìn)離港事件格式表示，就能為后續(xù)用更高階的方法來發(fā)現(xiàn)知識(shí)規(guī)律提供極大的便利。

參考文獻(xiàn)：

[1]趙學(xué)俊， 董曉永， 趙麗寧. AIS與船舶航行安全[J]. 世界海運(yùn)， 2003， 26（2）： 24-26.

[2]何時(shí)浩. 基于AIS信息的船舶航跡動(dòng)態(tài)行為分析技術(shù)研究[J]. 科技視界， 2017（1）： 232，238.

[3]朱姣， 劉敬賢， 陳笑， 等. 基于軌跡的內(nèi)河船舶行為模式挖掘[J]. 交通信息與安全， 2017， 35（3）： 107-116.

[4]劉滿娜. 基于AIS的港口監(jiān)控與分析系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 北京： 北京郵電大學(xué)， 2011.

[5]向哲， 施朝健， 胡勤友， 等. 利用AIS數(shù)據(jù)計(jì)算港口間競(jìng)爭(zhēng)度的方法[J]. 上海海事大學(xué)學(xué)報(bào)， 2016， 37（1）： 60-64.DOI：10.13340/j.jsmu.2016.01.011.

[6]劉茹茹， 洪鋒， 劉傳洋. 基于AIS信息的船舶抵離港頻數(shù)的統(tǒng)計(jì)[J]. 電腦知識(shí)與技術(shù)， 2014， 10（13）： 3160-3161.

[7]洪曙東. AIS在港口調(diào)度管理應(yīng)用的研究[J]. 中國(guó)港口， 2010（7）： 51-52.

[8]張建雄. 基于AIS的港口船舶動(dòng)態(tài)統(tǒng)計(jì)系統(tǒng)[J]. 中國(guó)水運(yùn)， 2015（2）： 56-57.

[9]潘家財(cái)， 姜青山， 邵哲平. 船舶會(huì)遇的時(shí)空數(shù)據(jù)挖掘算法及應(yīng)用[J]. 中國(guó)航海， 2010， 33（4）： 57-60.

[10]韓家煒， 坎伯. 數(shù)據(jù)挖掘： 概念與技術(shù)[M]. 北京： 機(jī)械工業(yè)出版社， 2001： 100-103.

[11]BENTLEY J L. Multidimensional binary search trees used for associative searching[J]. Communications of the ACM， 1975， 18（9）： 509-517.

[12]唐寧九， 游洪躍， 朱宏， 等. 數(shù)據(jù)結(jié)構(gòu)與算法分析[M]. 成都： 四川大學(xué)出版社， 2006.

[13]SEDGEWICK R. Algorithms[M]. Chennai Area， India： Pearson Education India， 1988.