船舶进离港行为捕获算法设计与实现
王永明 饶全成 姚萍
摘要：
针对在设计船舶进离港行为捕获算法时存在港口范围难定义、AIS数据的经纬度误差造成船舶频繁进出港区边界等问题，将全球AIS数据与港口数据相结合，设计船舶进离港行为捕获算法。根据船舶速度、位置、运动特性等信息，实现对船舶进离港、停泊等行为的判断。利用纬度分桶法、网格法和Kd树法实现基于船舶位置的港口匹配。实际数据测试表明，网格法的港口匹配时效性最好，每秒可处理约16万条AIS数据。随机选取30艘船对算法进行验证，结果表明船舶轨迹与捕获到的船舶进离港事件相符。
关键词：
船舶行为; 自动识别系统（AIS）; 港口匹配; 进离港
中图分类号： U697.1
文献标志码： 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
基金项目： 国家自然科学基金（51309044）
作者简介：
王永明（1973—）， 男， 安徽寿县人，高级工程师，博士，研究方向为航运信息化，（E-mail）wangyongming@cttic.cn
0 引 言
船舶轨迹数据是一种典型的时空大数据，各种船舶监测系统（LRIT，VMS，VDR和AIS [1]等）所獲取的船舶轨迹数据记录了船舶及海上交通的时空变化过程，蕴含了丰富的语义信息。对船舶轨迹数据进行挖掘可发现船舶群体活动的时空特征及演化规律[2]、船舶主航迹带及其成因等。掌握船舶进离港的规律，对于船舶轨迹的分析[3]具有重要意义。
港口是船舶航行中的关键节点，也是整个船舶航行过程中语义信息最丰富的环节。在港船舶会产生包括接受引航、等待、卸货、装载、理货、报关等诸多行为。狭义的船舶进离港就是进港和出港航行，广义的则是包括船舶进入港区、接受引航、在锚区停留等待、在泊位作业、离开泊位出航、机动航行等的全部过程。对舶舶进离港行为的精细判断，对于优化港区引航调度、提升港口作业效率具有重大的意义[4]。
快速、准确地挖掘出船舶进离港的行为是对船舶进离港行为捕获算法的要求。本文将算法分为两个阶段：船舶停泊检测阶段和船舶进离港检测阶段。在船舶停泊检测阶段对船舶的航行与停泊特征进行区分。在船舶进离港检测阶段通过对速度、航向、活动范围等因素的综合考虑，捕获船舶进离港事件。本文采用纬度分桶法、网格法和Kd树法解决船舶进离港行为捕获算法中的核心问题：快速找到距离当前船舶最近的港口。通过对港口位置的先验知识的利用，结合相关的数据结构，不断提高算法效率。最终发现，用网格法每秒可处理约16万条数据（目前系统接收的实时AIS数据每秒约3 000条），满足实时处理的需求。
1 基于AIS数据的船舶进离港
目前，很少看到有关船舶进离港行为捕获算法的文献。在一些根据船舶进离港数据进行研究的文献[5-6]中，船舶进离港行为捕获算法非常粗糙，且没有清晰地展现计算过程。这一方面是因为目前船舶进离港行为判断算法只在一些航运网站（如国内的宝船网、船讯网，国外的Marine Traffic）上使用，另一方面是因为船舶进离港行为判断算法有自身的一些难点需要解决。
首先，AIS的航次信息中含有ETA及目的地这两个字段，即预计到达时间和目的港。最简单的船舶进离港行为可直接根据其静态信息（船名、船舶呼号、MMSI、IMO编号等）得到。然而，静态信息是在设备安装时由专业技术人员根据船舶国籍证书输入的，而有些工程师在安装时没有严格按照相关规则设置静态信息，各类船舶的操作员均未按规定操作AIS设备，从而造成AIS静态信息错误，无法直接使用。比如，对一张含有635 055条数据的静态表进行分析发现，船舶MMSI不正常的有27 186条（占4%），呼号不可用的有287 167条（占45%），目的港不可用的有459 998条（占72%），ETA不可用的有507 481条（占80%）。因此，直接根据静态信息判断船舶进离港是不可取的。
其次，港口区域较难定义。有的港口比较小，适合用基于港区的位置和大小设置的圆表示。有的港口，如上海港，范围非常大，包含几百个泊位和锚区，很难用一个简单的几何图形来描述，则可用自定义的不规则区域来描述。
再次，每新获取一条AIS数据，算法都会对所有的港口进行遍历，现阶段算法还能勉强满足系统需要，而一旦有更多的港口数据，用该算法遍历港口所需要的时间就会增加，难以满足在线处理的实时性要求。
最后，有些船的AIS信息发送不正常。比如，检测到某船t1时刻在港口A，t2时刻在港口B，但由于该船主动关闭了AIS，所以其出港口A未被检测到。这
会对后续利用进离港事件进行分析的其他应用产生影响。本文采取的做法是将此前出港口A事件补全，并给出异常等级参考。
1.1 基于AIS的船舶进离港定义
港口区域一般可被定义成圆形或矩形，相应圆的半径或矩形的长、宽可以根据港口的大小设置。由于AIS信息中的经纬度有一定的误差，如果船舶在划出的港口区域附近连续不断地发出AIS信息，仅按船舶的位置来匹配港口的位置、計算进离港事件，那么当船舶处于区域边界时算法会判断出一系列的进离港事件，从而可能导致利用进离港事件进行分析的其他应用判断其为异常点，或者至少会受到干扰。因此，只有结合船舶的速度、转向率、航行状态等，才能更准确地判断船舶进离港事件。
很多沿着江河航行的船舶可能实际进入了某港区水域，但没有发生靠离泊位的行为。如每天经过新加坡港的船舶数量庞大，但很多船舶只是过境通航，并没有进出新加坡港。
基于以上考虑，本文对船舶进离港的定义为：船舶以低于2 kn 的速度进入港口范围内，且以高于2 kn的速度离开港口范围，进入与离开的时间间隔不小于30 min，船舶在港期间活动范围不大于1 000 m;在此期间，船舶分别发生一次进港和离港事件。港口范围一般用港口中心经纬度加半径表示，港口半径根据其大小进行差异化设置。形状不规则的港口可用矩形或引入JTS开源模块来表示。（JTS是加拿大的 Vivid Solutions公司做的一套开放源码的 Java API，它提供了一套空间数据操作的核心算法。）
1.2
船舶进离港行为时空分析和意义
通过研究船舶进离港行为，可以了解船舶航行规律和港口运作规律[7-8]。基于船舶进离港事件，可以对船舶和港口进行一系列有意义的分析，如统计港口吞吐量、统计全球或所关注港口的船舶进出情况、估算港口的运作效率等，并为决策者提供一定的参考信息。这对货主选择效率高的航运公司和航运公司选择效率高的港口码头具有重要参考价值。
目前船舶进离港信息仅掌握在港口经营人手中，是分散且不对外公开的。AIS船位信息是可以通过广播公开获得的，利用公开信息辨别进离港事件，在经济情报获得、安全情报获得、适应于大数据时代的数据素材生成方面具有重大意义。
在经济情报获得方面，通过船舶进离港行为将船舶整个航程进行切分，结合船舶档案、船型、吃水、靠泊时间等，能够对贸易量做比较精准的推测，进而掌握大宗货物的流向，分析宏观经济。同时，通过分析船舶进离港行为，挖掘船舶航行规律，可以评估航运公司、港口运营效率。
在安全情报获得方面，船舶进离港行为分析可以推广到进离区域分析。对于一些关键区域、作业平台区域、敏感对峙区域等进行进离区域分析，能够有效地追踪和甄别潜在的海上犯罪和敌对力量，包括海上走私、海上赌博、海上贩毒、围攻海上作业平台以及海盗等。
在生成适应于大数据时代的数据素材方面，可以增加语义、切割航线段。水上交通与陆上交通不同，其语义信息并不丰富，目前在大数据时代也没有很好的办法来套用如机器学习、深度学习之类的方法。船舶进离港事件将航线段进一步切分成带有语义标记的航行事件，使得船舶航行不再是一系列轨迹点记录，而是一系列带有语义信息的事件，这一系列事件可以作为高阶处理方法的素材。
2 船舶进离港行为捕获算法
在船舶静态AIS信息不可用的情况下，为快速得到船舶进离港事件，可对船舶动态AIS信息进行充分挖掘。综合考虑船舶的速度、位置、运动特征等，在线检测出全球船舶进离港事件。
船舶在到港时会低速进入港区，低速到达锚地，等待有可用的泊位（并持续一段较长时间）。其间，船舶的活动范围有限。本文对低速阈值、活动范围阈值给出了经验值，并依据此经验值检测船舶进离港事件。
为快速得到船舶所在的港口，先对全球港口在地理位置上进行预处理，构造相关的数据结构，使得查询船舶所处港口的速度得到大幅提升，从而满足在线检测的需求。
2.1 数据预处理
AIS信息在传输过程中会出现一定的错误，因此在
输入AIS数据前，需要对其进行预处理，删除明显错误的AIS数据，如：经度的正常范围为-180°～180°，纬度的正常范围为-90°～90°，不在此范围内的AIS数据都会被删除。[9]
2.2 船舶进离港行为捕获算法设计
对某单船的速度进行研究，其速度随时间的变
化大致如图1所示。T1时刻船舶进港，T1～T2时间
图1 单船速度变化示意图
图2 船舶进离港行为捕获
算法流程
内船舶低速在港区内移动，T2时刻船舶离港。根据船舶速度和活动范围可判断出船舶航行状态的变化，再结合船舶和港口的位置即可对船舶进离港行为作出判断。
在线船舶进离港行为捕获算法分为两个阶段：（1）根据船舶速度、活动范围、轨迹点数等判断其是否发生停泊事件;（2）结合全球港口信息，检测船舶停泊事件是否为船舶进离港事件。算法流程见图2。
根据上述分析设计出船舶停泊事件检测的流程，见图3。
算法维护每条船的低速轨迹序列，根据每条实时的AIS数据：若船舶速度低于给定的阈值，则将该船加入到相应的序列;若船舶速度高于阈值，则认为该船是从停泊状态转到航行状态，是一个可能的停泊结束事件。若确实存在该船的低速轨迹点序列，则此轨迹点序列的首尾轨迹点被认为是停泊事件的起讫点。为能够判断准确，接着加入平均速度、活动范围等信息进行进一步确认。首先判断该船的低速轨迹序列的点数是否大于设定的阈值，以免低速轨迹序列点数太少，给停泊事件检测造成误差。若点数符合要求，则求出轨迹序列平均速度，若平均速度大于等于阈值，则认为停泊状态可信度不高。最后，求出轨迹点序列的最大、最小经纬度，即将该船的活动范围看成一个矩形，将矩形对角线的一半作为该船的活动半径。若此活动半径在设定的阈值范围内，则可判断这是一个停泊事件。
图3 船舶停泊事件检测流程
将轨迹点序列起讫点的AIS信息字段中的定位时间分别设为停泊事件的起止时间，并将平均速度、活动半径等参数记录到该船停泊事件中。在上述计算平均速度和活动半径的过程中，为确保准确性，省略了轨迹点序列前后的部分轨迹点，仅将中间数据质量更高的轨迹点序列用于计算，以进一步提高船舶停泊事件的可信度。
表1 P0与P1的比较逻辑
当得到船舶停泊事件后，结合全球港口信息可得到船舶进离港事件。船舶停泊检测流程输出的结果为船舶停泊对象STOP，属性包括活动半径、中心经纬度、停泊起始时刻、停泊结束时刻等。计算出此中心与最近的港口P1的距离，且判断此距离是否小于设定的阈值（此阈值反映港口区域的大小）。系统维护一张全局在港船舶列表，列表的键为船舶MMSI，
值为对应的停泊港口P0。同时，每个港口各自维护一张在港船舶列表，列表的键为船舶MMSI，值为停泊对象STOP。比较P0与P1的关系，可得到船舶的进离港事件。比较逻辑如表1所示，其中p0和p1为具体的港口。
当P1和P0均为NULL时，说明船A正处于动力航行状态。
当P1为NULL，P0不为NULL时，说明船A之前在港口p0内，当前不在任何港口内，表明船A已经离开港口p0。
當P1不为NULL，P0为NULL时，说明船A之前未到任何港口，当前在港口p1内，表明船A已经进入港口p1。
当P1和P0均不为NULL时，若P1=P0则说明船舶停泊在p1内，若P1≠P0则说明船A此刻进入p1，之前某一时刻离开p0。离开p0事件并不是此时发生的，而是之前某一时刻发生的，但由于该船的AIS信息异常，如该船主动关闭AIS发射器，所以该船的离港事件未能被及时检测到。若需要区分此类事件，可对其做相应的异常标记。
船舶进离港事件检测流程见图4。船舶在港口内可能会在锚地与泊位间移动，每次移动均会产生停泊事件，即系统可能会检测到多次停泊事件。对于这种情况，只需更新当前港口内对应于该船的STOP对象的停泊结束时间。当检测到进港事件时，向全局在港船舶列表中增加相对应的船舶与所停泊港口的键值对，同时向发生船舶停泊事件的港口所维护的在港船舶列表中添加船舶与STOP对象的键值对;当检测到离港事件时，则需要删掉相应的键值对。
船舶进离港行为捕获算法伪代码如下：
输入：船舶STOP对象数据流
输出：船舶进离港事件流
Init HashMap<Ship，PORT>m;//所有在港船舶
Init HashMap<Ship，STOP>s;//每个港口维护的在港船舶
For stop in STOP_stream：
Ship ship = new Ship（stop）;
Port P1 = CurInPort（ship）; //当前距离最近港口
If （Dist（P1， ship） > DistThreshold） continue;
Port P0 = m.get（ship）; //全局表中所对应港口
if（P1==NULL && P0==NULL） nothing to do;
Else if （P1==NULL && P0！=NULL）
generateEvent（ship， P0， departure）; //离港
m.remove（ship）; //维护所有在港船舶
P0.s.remove（ship）; //维护P0的在港船舶
Else if （P1！=NULL && P0==NULL）
generateEvent（ship， P1， In）//进港
m.put（ship， P1）;
P1.s.add（ship， stop）;
Else if （P1！=NULL && P0！=NULL）
if （P1==P0） upDateEndTime（P0， stop）;
Else //先离港，再进港
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 船舶进离港事件检测流程
从上述伪代码可看出，通过系统所维护的全局在港船舶列表，可以快速找到P0，要得到P1则需要通过实时计算当前距船舶最近的港口，因此计算的快慢决定了算法的效率。提高算法效率的核心在于如何快速找到与当前船舶距离最近的港口。
3 基于船舶位置的港口匹配方法
基于當前船舶位置，设计纬度分桶法、网格法和Kd树法等3种算法对港口进行快速检索。这3种算法均利用港口的先验地理信息，将全球港口存储到特定的数据结构中，以加快查询与当前船舶最近的港口的速度。
图5 纬度分桶法桶编号示意图
3.1 算法介绍
纬度分桶法：根据纬度将全球港口划分到180个桶中。算法根据AIS中的纬度字段快速定位船舶所在的纬度桶，遍历相邻的3个纬度桶。纬度分桶法桶编号示意图见图5。
网格法[10]：在纬度分桶的基础上，对经度也划分桶，形成网格，见图6。将全球港口划分到1°×1°的网格中。算法根据AIS中的经度、纬度字段快速定位船舶所在网格，遍历相邻9个网格中的所有港口，找到距离当前船舶最近的港口。一般1°×1°的网格边长约为60 n mile（约110 km），远远超过港区大小。因此，其他网格中的港口与该船的距离必然大于设定距离阈值，不合要求，即其他网格中的港口与该船的距离不用计算。
图6 网格法网格编号示意图
Kd树[11-12]法：Kd树（多维二叉搜索树）是由Bentley于1975年提出的。通常用Kd树做数据索引和查询。Kd树通过把一个空间划分成多个不相交的子空间来组织k维空间中的点集，其中小于等于划分值的点划分到左子树，大于划分值的点划分到右子树。Kd树本质上是一种二元搜索树，它用超平面把空间划分成若干子区间来对数据进行搜索，从而可以高效地找到某一点的最近邻。将全球港口按照经纬度划分存储到一棵二叉树中的步骤：首先，将所有港口按经度排序，取排在中间的港口作为第1个节点插入Kd树;然后，将余下的港口按纬度排序，取排在中间的港口作为第2个节点插入Kd树;重复上述步骤，最终所建的二叉树是一棵高度平衡的二叉树。找到Kd树中某船的最近邻，即距离该船最近的港口。
3.2 算法分析
前述3种算法都利用港口的地理信息预先构建了一张“表”，在实时查询与某船距离最近的港口时，利用这张“表”加快查询的速度。因此，港口在“表”中分布得越均匀，查询的速度越快。目前系统中港口总数为7 805个。
用纬度分桶法划分的桶中的港口数分布见图7。由图7可知：大部分港口集中在小部分纬度桶中;从第120号到第150号的桶中的港口总数为4 904个，占系统中港口总数的62.8%。这说明港口在纬度桶中的分布极不均匀。
图7 用纬度分桶法划分的桶中港口数分布
用网格法划分的网格中的港口数分布见图8。由图8可知，3.4%的网格中的港口总数占系统中港口总数的90%。与纬度分桶法一样，网格中的港口数分布极不均匀。
图8 用网格法划分的网格中的港口数分布
图9 Kd树法划分效果
Kd树法的划分效果见图9。竖直线为竖直划分（根据X坐标划分），水平线为水平划分（根据Y坐标划分）。由图9可知，Kd树法划分出的空间并不均匀，地图下方的空白较多，空间较大，而地图中部空间小且子空间排列紧密。
现实世界中的港口分布并不均匀，因此在用纬度分桶法和网格法划出的桶和网格中的港口分布也不均匀。在极端情况下，所有的港口都聚集在一个桶或一个网格中，计算效率退化为与暴力解法的计算效率相等。
下面具体分析算法的时空复杂度。设港口数为M，待计算AIS信息条数为N。用纬度分桶法设置的桶的数量为D，而用网格法设置的网格数为D0·D1。
对于纬度分桶法和网格法，建“表”的时间分别花在定位港口所对应的桶和网格上。因此，时间复杂度均为O（M），空间复杂度则除了要存储每个港口还要存储桶或网格，故分别为O（D+M）和
O（D0·D1+M）。对于Kd树法，建“表”的插入时间为log2M，因此总的建表时间为O（Mlog2M），空间复杂度则为O（M）。
在查找时间方面，假定AIS数据均匀分布，每个桶或网格被查找到的概率相等。对于纬度分桶法，M个港口均匀分布在D个桶中，查找时间复杂度为O（（1+M/D）·N）。对于网格法，M个港口均匀分布在D0·D1个网格中，查找时间复杂度为O（（1+M/（D0·D1））·N）。对于Kd树法[13]，平均复杂度为O（（Mlog2M）·N），在最差的情况下要遍历到每个港口，因此，在最差的情况下时间复杂度为O（M·N）。
3.3 运行效率测试与分析
为了测试3种算法在真实数据中的表现，选取全球2015年10—12月的AIS数据。在硬件平台为Xeon（R） CPU E3-1200（@3.10 GHz），内存8 GB，软件为Windows 7 x64和JRE 1.7.0的试验环境下
对3种算法进行效率测试。分别使用1万条、5万
条、10万条、50万条、100万条、500万条、1 000万条
图10 系统采用3种算法处理
AIS数据所耗费的时间
AIS数据作为测试集，分别记录系统采用3种算法处理完所有数据所耗费的时间（均取3次试验的平均值）。试验结果见图10。
从图10可以看出，3种算法的时间效率均与AIS数据数量呈线性关系。从图10中还可以看出：网格法的效率最高;Kd树法由于每次进行最近邻查询都要进行多次距离计算，所以其算法效率较低;纬度分桶法和网格法都天然地减少了待查询的港口数量，因此效率都较Kd树法高。
4 船舶进离港行为捕获算法正确性验证
为验证系统所捕获到的进离港事件的正确性，随机选取客船、货船和渔船各10艘进行对比分析。图11所示为其中1艘MMSI为235000864的客船的历史轨迹（数据来源于宝船网）。从数据库中查询到系统捕获到的进离港事件，见图12。比较图11
图11 某客船的历史轨迹
图12 捕获到的某客船的进离港事件
与12可知该客船先后经过港口LOCHMADDY，UIG，TARBERT，系统捕获到了相应的进离港事件。所选取的其他客船、货船和渔船的进离港事件也均被正确捕获，这里不再赘述。
随机抽取的船舶轨迹与系统捕获到的船舶进离港事件能很好地吻合，表明船舶进离港捕获算法能正确捕获船舶的进离港事件。
5 结束语
在线船舶进离港捕获算法存在港口范围难定义、AIS信息中的经纬度误差造成的船舶频繁进出港区边界等问题。本文为解决这些问题做了有效尝试，首次在全球港口数据库上对全球AIS数据进行试验。试验结果表明，网格法在船舶进离港行为捕获算法中取得了最高的时间效率，具有实际应用的价值。由于现实世界的港口分布并不均匀，未来可以考虑分区域来划分网格，以达到更高的时间效率。
如果能够捕获全球船舶的进离港事件，用统一的船舶进离港事件格式表示，就能为后续用更高阶的方法来发现知识规律提供极大的便利。
参考文献：
[1]赵学俊， 董晓永， 赵丽宁. AIS与船舶航行安全[J]. 世界海运， 2003， 26（2）： 24-26.
[2]何时浩. 基于AIS信息的船舶航迹动态行为分析技术研究[J]. 科技视界， 2017（1）： 232，238.
[3]朱姣， 刘敬贤， 陈笑， 等. 基于轨迹的内河船舶行为模式挖掘[J]. 交通信息与安全， 2017， 35（3）： 107-116.
[4]刘满娜. 基于AIS的港口监控与分析系统的设计与实现[D]. 北京： 北京邮电大学， 2011.
[5]向哲， 施朝健， 胡勤友， 等. 利用AIS数据计算港口间竞争度的方法[J]. 上海海事大学学报， 2016， 37（1）： 60-64.DOI：10.13340/j.jsmu.2016.01.011.
[6]刘茹茹， 洪锋， 刘传洋. 基于AIS信息的船舶抵离港频数的统计[J]. 电脑知识与技术， 2014， 10（13）： 3160-3161.
[7]洪曙东. AIS在港口调度管理应用的研究[J]. 中国港口， 2010（7）： 51-52.
[8]张建雄. 基于AIS的港口船舶动态统计系统[J]. 中国水运， 2015（2）： 56-57.
[9]潘家财， 姜青山， 邵哲平. 船舶会遇的时空数据挖掘算法及应用[J]. 中国航海， 2010， 33（4）： 57-60.
[10]韩家炜， 坎伯. 数据挖掘： 概念与技术[M]. 北京： 机械工业出版社， 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]唐寧九， 游洪跃， 朱宏， 等. 数据结构与算法分析[M]. 成都： 四川大学出版社， 2006.
[13]SEDGEWICK R. Algorithms[M]. Chennai Area， India： Pearson Education India， 1988.
摘要：
针对在设计船舶进离港行为捕获算法时存在港口范围难定义、AIS数据的经纬度误差造成船舶频繁进出港区边界等问题，将全球AIS数据与港口数据相结合，设计船舶进离港行为捕获算法。根据船舶速度、位置、运动特性等信息，实现对船舶进离港、停泊等行为的判断。利用纬度分桶法、网格法和Kd树法实现基于船舶位置的港口匹配。实际数据测试表明，网格法的港口匹配时效性最好，每秒可处理约16万条AIS数据。随机选取30艘船对算法进行验证，结果表明船舶轨迹与捕获到的船舶进离港事件相符。
关键词：
船舶行为; 自动识别系统（AIS）; 港口匹配; 进离港
中图分类号： U697.1
文献标志码： 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
基金项目： 国家自然科学基金（51309044）
作者简介：
王永明（1973—）， 男， 安徽寿县人，高级工程师，博士，研究方向为航运信息化，（E-mail）wangyongming@cttic.cn
0 引 言
船舶轨迹数据是一种典型的时空大数据，各种船舶监测系统（LRIT，VMS，VDR和AIS [1]等）所獲取的船舶轨迹数据记录了船舶及海上交通的时空变化过程，蕴含了丰富的语义信息。对船舶轨迹数据进行挖掘可发现船舶群体活动的时空特征及演化规律[2]、船舶主航迹带及其成因等。掌握船舶进离港的规律，对于船舶轨迹的分析[3]具有重要意义。
港口是船舶航行中的关键节点，也是整个船舶航行过程中语义信息最丰富的环节。在港船舶会产生包括接受引航、等待、卸货、装载、理货、报关等诸多行为。狭义的船舶进离港就是进港和出港航行，广义的则是包括船舶进入港区、接受引航、在锚区停留等待、在泊位作业、离开泊位出航、机动航行等的全部过程。对舶舶进离港行为的精细判断，对于优化港区引航调度、提升港口作业效率具有重大的意义[4]。
快速、准确地挖掘出船舶进离港的行为是对船舶进离港行为捕获算法的要求。本文将算法分为两个阶段：船舶停泊检测阶段和船舶进离港检测阶段。在船舶停泊检测阶段对船舶的航行与停泊特征进行区分。在船舶进离港检测阶段通过对速度、航向、活动范围等因素的综合考虑，捕获船舶进离港事件。本文采用纬度分桶法、网格法和Kd树法解决船舶进离港行为捕获算法中的核心问题：快速找到距离当前船舶最近的港口。通过对港口位置的先验知识的利用，结合相关的数据结构，不断提高算法效率。最终发现，用网格法每秒可处理约16万条数据（目前系统接收的实时AIS数据每秒约3 000条），满足实时处理的需求。
1 基于AIS数据的船舶进离港
目前，很少看到有关船舶进离港行为捕获算法的文献。在一些根据船舶进离港数据进行研究的文献[5-6]中，船舶进离港行为捕获算法非常粗糙，且没有清晰地展现计算过程。这一方面是因为目前船舶进离港行为判断算法只在一些航运网站（如国内的宝船网、船讯网，国外的Marine Traffic）上使用，另一方面是因为船舶进离港行为判断算法有自身的一些难点需要解决。
首先，AIS的航次信息中含有ETA及目的地这两个字段，即预计到达时间和目的港。最简单的船舶进离港行为可直接根据其静态信息（船名、船舶呼号、MMSI、IMO编号等）得到。然而，静态信息是在设备安装时由专业技术人员根据船舶国籍证书输入的，而有些工程师在安装时没有严格按照相关规则设置静态信息，各类船舶的操作员均未按规定操作AIS设备，从而造成AIS静态信息错误，无法直接使用。比如，对一张含有635 055条数据的静态表进行分析发现，船舶MMSI不正常的有27 186条（占4%），呼号不可用的有287 167条（占45%），目的港不可用的有459 998条（占72%），ETA不可用的有507 481条（占80%）。因此，直接根据静态信息判断船舶进离港是不可取的。
其次，港口区域较难定义。有的港口比较小，适合用基于港区的位置和大小设置的圆表示。有的港口，如上海港，范围非常大，包含几百个泊位和锚区，很难用一个简单的几何图形来描述，则可用自定义的不规则区域来描述。
再次，每新获取一条AIS数据，算法都会对所有的港口进行遍历，现阶段算法还能勉强满足系统需要，而一旦有更多的港口数据，用该算法遍历港口所需要的时间就会增加，难以满足在线处理的实时性要求。
最后，有些船的AIS信息发送不正常。比如，检测到某船t1时刻在港口A，t2时刻在港口B，但由于该船主动关闭了AIS，所以其出港口A未被检测到。这
会对后续利用进离港事件进行分析的其他应用产生影响。本文采取的做法是将此前出港口A事件补全，并给出异常等级参考。
1.1 基于AIS的船舶进离港定义
港口区域一般可被定义成圆形或矩形，相应圆的半径或矩形的长、宽可以根据港口的大小设置。由于AIS信息中的经纬度有一定的误差，如果船舶在划出的港口区域附近连续不断地发出AIS信息，仅按船舶的位置来匹配港口的位置、計算进离港事件，那么当船舶处于区域边界时算法会判断出一系列的进离港事件，从而可能导致利用进离港事件进行分析的其他应用判断其为异常点，或者至少会受到干扰。因此，只有结合船舶的速度、转向率、航行状态等，才能更准确地判断船舶进离港事件。
很多沿着江河航行的船舶可能实际进入了某港区水域，但没有发生靠离泊位的行为。如每天经过新加坡港的船舶数量庞大，但很多船舶只是过境通航，并没有进出新加坡港。
基于以上考虑，本文对船舶进离港的定义为：船舶以低于2 kn 的速度进入港口范围内，且以高于2 kn的速度离开港口范围，进入与离开的时间间隔不小于30 min，船舶在港期间活动范围不大于1 000 m;在此期间，船舶分别发生一次进港和离港事件。港口范围一般用港口中心经纬度加半径表示，港口半径根据其大小进行差异化设置。形状不规则的港口可用矩形或引入JTS开源模块来表示。（JTS是加拿大的 Vivid Solutions公司做的一套开放源码的 Java API，它提供了一套空间数据操作的核心算法。）
1.2
船舶进离港行为时空分析和意义
通过研究船舶进离港行为，可以了解船舶航行规律和港口运作规律[7-8]。基于船舶进离港事件，可以对船舶和港口进行一系列有意义的分析，如统计港口吞吐量、统计全球或所关注港口的船舶进出情况、估算港口的运作效率等，并为决策者提供一定的参考信息。这对货主选择效率高的航运公司和航运公司选择效率高的港口码头具有重要参考价值。
目前船舶进离港信息仅掌握在港口经营人手中，是分散且不对外公开的。AIS船位信息是可以通过广播公开获得的，利用公开信息辨别进离港事件，在经济情报获得、安全情报获得、适应于大数据时代的数据素材生成方面具有重大意义。
在经济情报获得方面，通过船舶进离港行为将船舶整个航程进行切分，结合船舶档案、船型、吃水、靠泊时间等，能够对贸易量做比较精准的推测，进而掌握大宗货物的流向，分析宏观经济。同时，通过分析船舶进离港行为，挖掘船舶航行规律，可以评估航运公司、港口运营效率。
在安全情报获得方面，船舶进离港行为分析可以推广到进离区域分析。对于一些关键区域、作业平台区域、敏感对峙区域等进行进离区域分析，能够有效地追踪和甄别潜在的海上犯罪和敌对力量，包括海上走私、海上赌博、海上贩毒、围攻海上作业平台以及海盗等。
在生成适应于大数据时代的数据素材方面，可以增加语义、切割航线段。水上交通与陆上交通不同，其语义信息并不丰富，目前在大数据时代也没有很好的办法来套用如机器学习、深度学习之类的方法。船舶进离港事件将航线段进一步切分成带有语义标记的航行事件，使得船舶航行不再是一系列轨迹点记录，而是一系列带有语义信息的事件，这一系列事件可以作为高阶处理方法的素材。
2 船舶进离港行为捕获算法
在船舶静态AIS信息不可用的情况下，为快速得到船舶进离港事件，可对船舶动态AIS信息进行充分挖掘。综合考虑船舶的速度、位置、运动特征等，在线检测出全球船舶进离港事件。
船舶在到港时会低速进入港区，低速到达锚地，等待有可用的泊位（并持续一段较长时间）。其间，船舶的活动范围有限。本文对低速阈值、活动范围阈值给出了经验值，并依据此经验值检测船舶进离港事件。
为快速得到船舶所在的港口，先对全球港口在地理位置上进行预处理，构造相关的数据结构，使得查询船舶所处港口的速度得到大幅提升，从而满足在线检测的需求。
2.1 数据预处理
AIS信息在传输过程中会出现一定的错误，因此在
输入AIS数据前，需要对其进行预处理，删除明显错误的AIS数据，如：经度的正常范围为-180°～180°，纬度的正常范围为-90°～90°，不在此范围内的AIS数据都会被删除。[9]
2.2 船舶进离港行为捕获算法设计
对某单船的速度进行研究，其速度随时间的变
化大致如图1所示。T1时刻船舶进港，T1～T2时间
图1 单船速度变化示意图
图2 船舶进离港行为捕获
算法流程
内船舶低速在港区内移动，T2时刻船舶离港。根据船舶速度和活动范围可判断出船舶航行状态的变化，再结合船舶和港口的位置即可对船舶进离港行为作出判断。
在线船舶进离港行为捕获算法分为两个阶段：（1）根据船舶速度、活动范围、轨迹点数等判断其是否发生停泊事件;（2）结合全球港口信息，检测船舶停泊事件是否为船舶进离港事件。算法流程见图2。
根据上述分析设计出船舶停泊事件检测的流程，见图3。
算法维护每条船的低速轨迹序列，根据每条实时的AIS数据：若船舶速度低于给定的阈值，则将该船加入到相应的序列;若船舶速度高于阈值，则认为该船是从停泊状态转到航行状态，是一个可能的停泊结束事件。若确实存在该船的低速轨迹点序列，则此轨迹点序列的首尾轨迹点被认为是停泊事件的起讫点。为能够判断准确，接着加入平均速度、活动范围等信息进行进一步确认。首先判断该船的低速轨迹序列的点数是否大于设定的阈值，以免低速轨迹序列点数太少，给停泊事件检测造成误差。若点数符合要求，则求出轨迹序列平均速度，若平均速度大于等于阈值，则认为停泊状态可信度不高。最后，求出轨迹点序列的最大、最小经纬度，即将该船的活动范围看成一个矩形，将矩形对角线的一半作为该船的活动半径。若此活动半径在设定的阈值范围内，则可判断这是一个停泊事件。
图3 船舶停泊事件检测流程
将轨迹点序列起讫点的AIS信息字段中的定位时间分别设为停泊事件的起止时间，并将平均速度、活动半径等参数记录到该船停泊事件中。在上述计算平均速度和活动半径的过程中，为确保准确性，省略了轨迹点序列前后的部分轨迹点，仅将中间数据质量更高的轨迹点序列用于计算，以进一步提高船舶停泊事件的可信度。
表1 P0与P1的比较逻辑
当得到船舶停泊事件后，结合全球港口信息可得到船舶进离港事件。船舶停泊检测流程输出的结果为船舶停泊对象STOP，属性包括活动半径、中心经纬度、停泊起始时刻、停泊结束时刻等。计算出此中心与最近的港口P1的距离，且判断此距离是否小于设定的阈值（此阈值反映港口区域的大小）。系统维护一张全局在港船舶列表，列表的键为船舶MMSI，
值为对应的停泊港口P0。同时，每个港口各自维护一张在港船舶列表，列表的键为船舶MMSI，值为停泊对象STOP。比较P0与P1的关系，可得到船舶的进离港事件。比较逻辑如表1所示，其中p0和p1为具体的港口。
当P1和P0均为NULL时，说明船A正处于动力航行状态。
当P1为NULL，P0不为NULL时，说明船A之前在港口p0内，当前不在任何港口内，表明船A已经离开港口p0。
當P1不为NULL，P0为NULL时，说明船A之前未到任何港口，当前在港口p1内，表明船A已经进入港口p1。
当P1和P0均不为NULL时，若P1=P0则说明船舶停泊在p1内，若P1≠P0则说明船A此刻进入p1，之前某一时刻离开p0。离开p0事件并不是此时发生的，而是之前某一时刻发生的，但由于该船的AIS信息异常，如该船主动关闭AIS发射器，所以该船的离港事件未能被及时检测到。若需要区分此类事件，可对其做相应的异常标记。
船舶进离港事件检测流程见图4。船舶在港口内可能会在锚地与泊位间移动，每次移动均会产生停泊事件，即系统可能会检测到多次停泊事件。对于这种情况，只需更新当前港口内对应于该船的STOP对象的停泊结束时间。当检测到进港事件时，向全局在港船舶列表中增加相对应的船舶与所停泊港口的键值对，同时向发生船舶停泊事件的港口所维护的在港船舶列表中添加船舶与STOP对象的键值对;当检测到离港事件时，则需要删掉相应的键值对。
船舶进离港行为捕获算法伪代码如下：
输入：船舶STOP对象数据流
输出：船舶进离港事件流
Init HashMap<Ship，PORT>m;//所有在港船舶
Init HashMap<Ship，STOP>s;//每个港口维护的在港船舶
For stop in STOP_stream：
Ship ship = new Ship（stop）;
Port P1 = CurInPort（ship）; //当前距离最近港口
If （Dist（P1， ship） > DistThreshold） continue;
Port P0 = m.get（ship）; //全局表中所对应港口
if（P1==NULL && P0==NULL） nothing to do;
Else if （P1==NULL && P0！=NULL）
generateEvent（ship， P0， departure）; //离港
m.remove（ship）; //维护所有在港船舶
P0.s.remove（ship）; //维护P0的在港船舶
Else if （P1！=NULL && P0==NULL）
generateEvent（ship， P1， In）//进港
m.put（ship， P1）;
P1.s.add（ship， stop）;
Else if （P1！=NULL && P0！=NULL）
if （P1==P0） upDateEndTime（P0， stop）;
Else //先离港，再进港
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 船舶进离港事件检测流程
从上述伪代码可看出，通过系统所维护的全局在港船舶列表，可以快速找到P0，要得到P1则需要通过实时计算当前距船舶最近的港口，因此计算的快慢决定了算法的效率。提高算法效率的核心在于如何快速找到与当前船舶距离最近的港口。
3 基于船舶位置的港口匹配方法
基于當前船舶位置，设计纬度分桶法、网格法和Kd树法等3种算法对港口进行快速检索。这3种算法均利用港口的先验地理信息，将全球港口存储到特定的数据结构中，以加快查询与当前船舶最近的港口的速度。
图5 纬度分桶法桶编号示意图
3.1 算法介绍
纬度分桶法：根据纬度将全球港口划分到180个桶中。算法根据AIS中的纬度字段快速定位船舶所在的纬度桶，遍历相邻的3个纬度桶。纬度分桶法桶编号示意图见图5。
网格法[10]：在纬度分桶的基础上，对经度也划分桶，形成网格，见图6。将全球港口划分到1°×1°的网格中。算法根据AIS中的经度、纬度字段快速定位船舶所在网格，遍历相邻9个网格中的所有港口，找到距离当前船舶最近的港口。一般1°×1°的网格边长约为60 n mile（约110 km），远远超过港区大小。因此，其他网格中的港口与该船的距离必然大于设定距离阈值，不合要求，即其他网格中的港口与该船的距离不用计算。
图6 网格法网格编号示意图
Kd树[11-12]法：Kd树（多维二叉搜索树）是由Bentley于1975年提出的。通常用Kd树做数据索引和查询。Kd树通过把一个空间划分成多个不相交的子空间来组织k维空间中的点集，其中小于等于划分值的点划分到左子树，大于划分值的点划分到右子树。Kd树本质上是一种二元搜索树，它用超平面把空间划分成若干子区间来对数据进行搜索，从而可以高效地找到某一点的最近邻。将全球港口按照经纬度划分存储到一棵二叉树中的步骤：首先，将所有港口按经度排序，取排在中间的港口作为第1个节点插入Kd树;然后，将余下的港口按纬度排序，取排在中间的港口作为第2个节点插入Kd树;重复上述步骤，最终所建的二叉树是一棵高度平衡的二叉树。找到Kd树中某船的最近邻，即距离该船最近的港口。
3.2 算法分析
前述3种算法都利用港口的地理信息预先构建了一张“表”，在实时查询与某船距离最近的港口时，利用这张“表”加快查询的速度。因此，港口在“表”中分布得越均匀，查询的速度越快。目前系统中港口总数为7 805个。
用纬度分桶法划分的桶中的港口数分布见图7。由图7可知：大部分港口集中在小部分纬度桶中;从第120号到第150号的桶中的港口总数为4 904个，占系统中港口总数的62.8%。这说明港口在纬度桶中的分布极不均匀。
图7 用纬度分桶法划分的桶中港口数分布
用网格法划分的网格中的港口数分布见图8。由图8可知，3.4%的网格中的港口总数占系统中港口总数的90%。与纬度分桶法一样，网格中的港口数分布极不均匀。
图8 用网格法划分的网格中的港口数分布
图9 Kd树法划分效果
Kd树法的划分效果见图9。竖直线为竖直划分（根据X坐标划分），水平线为水平划分（根据Y坐标划分）。由图9可知，Kd树法划分出的空间并不均匀，地图下方的空白较多，空间较大，而地图中部空间小且子空间排列紧密。
现实世界中的港口分布并不均匀，因此在用纬度分桶法和网格法划出的桶和网格中的港口分布也不均匀。在极端情况下，所有的港口都聚集在一个桶或一个网格中，计算效率退化为与暴力解法的计算效率相等。
下面具体分析算法的时空复杂度。设港口数为M，待计算AIS信息条数为N。用纬度分桶法设置的桶的数量为D，而用网格法设置的网格数为D0·D1。
对于纬度分桶法和网格法，建“表”的时间分别花在定位港口所对应的桶和网格上。因此，时间复杂度均为O（M），空间复杂度则除了要存储每个港口还要存储桶或网格，故分别为O（D+M）和
O（D0·D1+M）。对于Kd树法，建“表”的插入时间为log2M，因此总的建表时间为O（Mlog2M），空间复杂度则为O（M）。
在查找时间方面，假定AIS数据均匀分布，每个桶或网格被查找到的概率相等。对于纬度分桶法，M个港口均匀分布在D个桶中，查找时间复杂度为O（（1+M/D）·N）。对于网格法，M个港口均匀分布在D0·D1个网格中，查找时间复杂度为O（（1+M/（D0·D1））·N）。对于Kd树法[13]，平均复杂度为O（（Mlog2M）·N），在最差的情况下要遍历到每个港口，因此，在最差的情况下时间复杂度为O（M·N）。
3.3 运行效率测试与分析
为了测试3种算法在真实数据中的表现，选取全球2015年10—12月的AIS数据。在硬件平台为Xeon（R） CPU E3-1200（@3.10 GHz），内存8 GB，软件为Windows 7 x64和JRE 1.7.0的试验环境下
对3种算法进行效率测试。分别使用1万条、5万
条、10万条、50万条、100万条、500万条、1 000万条
图10 系统采用3种算法处理
AIS数据所耗费的时间
AIS数据作为测试集，分别记录系统采用3种算法处理完所有数据所耗费的时间（均取3次试验的平均值）。试验结果见图10。
从图10可以看出，3种算法的时间效率均与AIS数据数量呈线性关系。从图10中还可以看出：网格法的效率最高;Kd树法由于每次进行最近邻查询都要进行多次距离计算，所以其算法效率较低;纬度分桶法和网格法都天然地减少了待查询的港口数量，因此效率都较Kd树法高。
4 船舶进离港行为捕获算法正确性验证
为验证系统所捕获到的进离港事件的正确性，随机选取客船、货船和渔船各10艘进行对比分析。图11所示为其中1艘MMSI为235000864的客船的历史轨迹（数据来源于宝船网）。从数据库中查询到系统捕获到的进离港事件，见图12。比较图11
图11 某客船的历史轨迹
图12 捕获到的某客船的进离港事件
与12可知该客船先后经过港口LOCHMADDY，UIG，TARBERT，系统捕获到了相应的进离港事件。所选取的其他客船、货船和渔船的进离港事件也均被正确捕获，这里不再赘述。
随机抽取的船舶轨迹与系统捕获到的船舶进离港事件能很好地吻合，表明船舶进离港捕获算法能正确捕获船舶的进离港事件。
5 结束语
在线船舶进离港捕获算法存在港口范围难定义、AIS信息中的经纬度误差造成的船舶频繁进出港区边界等问题。本文为解决这些问题做了有效尝试，首次在全球港口数据库上对全球AIS数据进行试验。试验结果表明，网格法在船舶进离港行为捕获算法中取得了最高的时间效率，具有实际应用的价值。由于现实世界的港口分布并不均匀，未来可以考虑分区域来划分网格，以达到更高的时间效率。
如果能够捕获全球船舶的进离港事件，用统一的船舶进离港事件格式表示，就能为后续用更高阶的方法来发现知识规律提供极大的便利。
参考文献：
[1]赵学俊， 董晓永， 赵丽宁. AIS与船舶航行安全[J]. 世界海运， 2003， 26（2）： 24-26.
[2]何时浩. 基于AIS信息的船舶航迹动态行为分析技术研究[J]. 科技视界， 2017（1）： 232，238.
[3]朱姣， 刘敬贤， 陈笑， 等. 基于轨迹的内河船舶行为模式挖掘[J]. 交通信息与安全， 2017， 35（3）： 107-116.
[4]刘满娜. 基于AIS的港口监控与分析系统的设计与实现[D]. 北京： 北京邮电大学， 2011.
[5]向哲， 施朝健， 胡勤友， 等. 利用AIS数据计算港口间竞争度的方法[J]. 上海海事大学学报， 2016， 37（1）： 60-64.DOI：10.13340/j.jsmu.2016.01.011.
[6]刘茹茹， 洪锋， 刘传洋. 基于AIS信息的船舶抵离港频数的统计[J]. 电脑知识与技术， 2014， 10（13）： 3160-3161.
[7]洪曙东. AIS在港口调度管理应用的研究[J]. 中国港口， 2010（7）： 51-52.
[8]张建雄. 基于AIS的港口船舶动态统计系统[J]. 中国水运， 2015（2）： 56-57.
[9]潘家财， 姜青山， 邵哲平. 船舶会遇的时空数据挖掘算法及应用[J]. 中国航海， 2010， 33（4）： 57-60.
[10]韩家炜， 坎伯. 数据挖掘： 概念与技术[M]. 北京： 机械工业出版社， 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]唐寧九， 游洪跃， 朱宏， 等. 数据结构与算法分析[M]. 成都： 四川大学出版社， 2006.
[13]SEDGEWICK R. Algorithms[M]. Chennai Area， India： Pearson Education India， 1988.
