一种基于AIS数据的船舶航线自动规划方法

石 浩， 乔继潘， 季 盛

(上海船舶运输科学研究所 航运技术与安全国家重点实验室，上海 200135)

0 引 言

近年来，随着大数据、物联网等概念的提出和快速发展,船舶智能化和无人化发展逐渐成为造船业和航运业研究的热点，得到了世界各国的广泛关注[1]。航线自动规划技术作为智能船舶和无人驾驶船舶最关键的技术之一，在保证船舶安全航行和提高船舶营运效率等方面有着重要作用。船舶航线自动规划是指自动为船舶规划从始发地到目的地的航线，在航线和航行时间最短等特定条件下，结合安全性和能源消耗要求，找到一条最优航行路径，使船舶在航行过程中能安全可靠地避开所有障碍物[2]。

当前国内外已有很多学者对航线自动规划方法进行研究。例如：童帮裕等[3]基于电子海图建立冰区航道环境栅格模型，结合人工势场法对蚁群算法进行改进；潘明阳等[4]根据内河水网航道通航条件，基于有向航路网络拓扑法构建航行环境模型，通过改进的A*算法求解最优航线；金建海等[5]提出一种改进的无人艇航线规划方法，在粒子群优化算法的基础上引入人工势场法的思想，通过量子粒子群优化算法求解最优航线，提高全局搜索能力；谢新连等[6]针对海上施工水域，利用Maklink航线网络构建航路网络，利用Dijkstra算法求解初始航线，并基于蚁群算法对该航线进行优化；姚肖肖等[7]通过对船舶自动识别系统(Automatic Identification System，AIS)轨迹数据进行聚类提取关键转向点，结合电子海图相关数据构建无向航路网络，根据船舶航路的通航频率设置蚁群算法的初始信息素浓度，求解以总航程最短为优化目标的安全、经济的最优航线；吴泽亮[8]提出一种改进的蚁群算法，采用Adadelta算法改变蚁群算法的信息素更新规则，动态调整信息素挥发系数，提高蚁群算法的随机性，从而极大地改善蚁群算法的性能；陈晓等[9]基于海图上的Maklink图论，结合无向航路网络拓扑法构建航行环境模型，通过蚁群算法对采用Dijkstra算法生成的最短航行路径进行优化；范云生等[10]提出一种依据电子海图，结合栅格法建立航行环境模型，通过遗传算法求解最优航线的航线自动规划方法；SONG[11]针对水面无人艇的全局路径规划，采用栅格法建立航行环境模型，采用改进的蚁群算法求解最优航线；SZLAPCZYNSKI[12]根据路径规划理论设计最优航线。目前相关研究还存在以下问题：

1)现有的航线自动规划算法采用的数据大部分为电子海图上的信息数据，动态地更新这些数据需花费大量的经济成本和时间成本；

2)无论是基于电子海图还是基于AIS数据构建航路网络拓扑结构，考虑的航行限制因素都比较多，附加工作量比较大，部分研究试验环境单一，缺少实例验证，需在尽可能降低时间成本和减少附加工作量的情况下充分研究复杂航行环境，找到能符合实际情况的航线自动规划算法；

3)绝大多数航线规划算法都只能计算出局部最优航线，不具备全局搜索能力。

对此，以国内外已有研究为基础，针对其中存在的问题，对海上航行环境和航线规划方法进行分析，探索出一种无需依靠电子海图信息数据进行环境建模，性能优良，能在复杂航行环境下便捷、准确地完成全局最优航线自动规划的航线自动规划方法至关重要。本文主要在上述研究的基础上，结合海量AIS轨迹数据、栅格法和蚁群算法构建基于AIS数据中的可通航点的栅格环境模型，结合蚁群算法规划出一条经济、便捷的船舶航线，并通过实例验证说明该方法在全局最优航线自动规划方面的应用效果和可行性。

1 航线自动规划方法和主要流程

本文所述航线自动规划方法主要基于海量AIS数据确定航行区域内的可通航点，对航行区域地图进行栅格划分和矩阵化处理，根据AIS数据中的可通航点确定栅格网格的矩阵值，定义可通航栅格。结合全球经纬度距离公式，利用邻接矩阵对各可通航栅格网格进行距离计算。基于蚁群算法和计算得到的邻接矩阵寻找从起始点至终点的最优距离，并输出规划航线。由于初始航线是基于栅格网格得到的，输出的转向点较多，可在此基础上根据船员在规划航线时的习惯做法规划出符合船舶实际航行习惯的航线。

该方法的主要流程见图1，具体步骤如下：

图1 航线自动规划方法主要流程

1)对船舶AIS数据进行预处理；

2)将航行区域地图栅格化，构建航行环境模型；

3)采用蚁群算法求解航线规划数学模型；

4)输出初始航线，进一步优化得到最终航线。

2 航行环境模型构建

2.1 船舶AIS数据预处理

针对AIS数据中可能存在离群值、异常值和冗余值的情况，结合其分布复杂的特点，在挖掘应用AIS数据之前需对其进行清洗整理[13]。对于离散船舶轨迹点的处理，主要采用聚类算法，主要有划分聚类、密度聚类、层次聚类和网格聚类等4种。在选择聚类算法时，主要考虑以下几点：

1)所选算法能自动确定类簇的数量；

2)聚类结果中各聚类簇的形状类似于圆形；

3)聚类簇的尺寸不应太大，且相邻聚类簇不应太小。

基于以上要求，本文选用DBSCAN密度聚类算法。该算法是一种基于密度的空间聚类算法，其核心是利用密度的概念，按一定的约束条件对需聚类的空间中的数据进行分类，将在指定距离范围内达到设定密度阈值的数据划分为簇，达到地理空间分类的目的，去除空间数据中的噪声点。

对AIS数据进行预处理的流程见图2，主要步骤如下：

图2 AIS数据预处理流程

1)清洗AIS数据。保留AIS数据中的经纬度、航速、吃水和航向等字段数据正常点，经度正常数据范围为-180～180，纬度正常数据范围为-90～90，航速正常数据范围为0～50，吃水正常数据范围为0～50，航向正常数据范围为0～360。以上字段信号非正常点默认为采集数据错误，防止此类错误干扰后续可通航栅格网络的划分。

2)设置通航条件。以吃水大于5 m、航速大于5 kn为标准，保留符合条件的AIS数据。

3)采用DBSCAN密度聚类算法剔除AIS数据中公共通航区内的离散点，距离范围设置为2 n mile，包含的点数阈值设置为3，排除AIS数据离散点对航路规划的干扰，具体AIS数据离散点示意见图3，其中下方的点即为需排除的离散点。DBSCAN密度聚类算法将AIS数据较为密集的区集合为一个簇，并形成符合主要航道要求的空间聚类。

图3 AIS数据离散点示意

2.2 可通航栅格环境模型

船舶在指定航行区域内的航行路径可简化为船舶在二维平面内两点间的航行路线。采用栅格法将指定的航行区域地图栅格化为若干个栅格，设定指定的单位分割度数作为栅格的边长。根据航行区域地图中的单个栅格是否可航行，确定可通航栅格(标记为白色)和不可通航栅格(标记为黑色)。采用栅格法将复杂航行环境下的航线规划问题转化为在二维栅格中寻找2个栅格中心点之间符合特定条件的最优路径的问题。

本文基于筛选后的AIS数据，采用栅格划分法构建航行区域可通航栅格环境模型，组成可通航区域。该模型的简化模型见图4，其中1个单元格为1个栅格，船舶以栅格为最小运动单位，航向均为前往下一个栅格的中心点所指的方向，设定航速保持不变，航程计算以栅格中心点为准。

图4 航行区域可通航栅格环境模型简化模型

1)对全球范围内的航行区域进行航线规划，以0.025°为单位分割度数划分全球经纬度，剔除高纬度地区(南纬75°至南极点，北纬75°至北极点)，确定全球栅格范围。

2)根据上一步确定的单位分割度数划分全球栅格范围，得到6 000×14 400块栅格。沿横轴方向由上向下依次对栅格进行编号，分别为1，2，3，…，直至所有栅格编号完毕。根据筛选后的AIS数据判断各栅格内是否出现过AIS数据，若出现过AIS数据，则将其确定为可通航栅格。采用DBSCAN密度聚类算法将可通航栅格组成可通航区域，从而剔除可通航离散栅格(图4中左下角被不可通航栅格包围的可通航栅格为需剔除的离散栅格)。

3)采用邻接矩阵算法确定相邻可通航栅格距离，将栅格编号转换为经纬度，根据地球上两点之间距离的计算公式计算两相邻可通航栅格之间的距离。

2.3 航线规划的数学模型

规划航线的目的是避开障碍物，并使航行路径最短。因此，结合实际操作需要建立相应的数学模型，需优化的目标函数为

(1)

式(9)中：L为航线距离；fn为第n个航行路径穿越的网格中心点，n=1,2，…，N；S(fn,fn+1)为点fn与点fn+1之间的直线距离；N为规划的由初始点到目标点的航线中航路转向点的个数。船舶航线F由航路点f1，f2，…，fn组成。该模型的目标是求得航线距离L的值最小的路径，将该路径作为该条件下的最优航行路径。

3 基于蚁群算法的航线规划建模和求解

3.1 蚁群算法的原理

蚁群算法是模拟蚂蚁在寻找食物过程中寻求最短路线的行为，并对其进行抽象简化，得到的一种用来搜索最优路径的群体智能算法(或称启发式算法)，常应用于最短路径寻优问题的求解中[14]。

假设蚂蚁总数为m，航路转向点总数为n。第k只蚂蚁在t时刻由航路转向点i转移到航路转向点j的概率为

(2)

式(2)中：α为信息启发式因子，表示信息素浓度的重要程度；β为期望启发式因子，表示航路转向点之间距离的重要程度；τij(t)为航路转向点i和航路转向点j在t时刻的信息素浓度；ηij(t)为启发函数，表示蚂蚁个体由航路转向点i到航路转向点j的期望，取值为1/dij，dij为当前航路转向点i与下一个航路转向点j之间的欧式距离；allowedk为蚂蚁k能选择的航路转向点。蚂蚁根据路径上的信息素和距离选择可能的各种航线。

当所有蚂蚁全部完成迭代之后，对路径上的信息素进行更新，更新公式为

τij(t+n)=(1-ρ)τij(t)+Δτij(t)

(3)

(4)

(5)

3.2 基于蚁群算法的最短航线规划实施步骤

基于蚁群算法的最短航线规划流程见图5，具体实施步骤如下：

图5 基于蚁群算法的最短航线规划流程

1)将给定的出发点A(经度φA，纬度αA)和到达点B(经度φB，纬度αB)转换成全球栅格中的对应栅格位置出发点A(XA,YA)和到达点B(XB,YB)；

2)初始化每个蚂蚁种群，设定参数；

3)采用轮盘赌法选择下一个相邻可通航栅格，该栅格和两栅格之间的距离是基于全球可通航栅格网格划分模型计算得到的；

4)每只蚂蚁根据信息素找到路径，直至到达点B；

5)记录每只蚂蚁的通航路线和总的航行距离；

6)更新蚂蚁留下的信息素；

7)判断是否达到最大种群数；

8)输出航线最短的解。

4 实例分析及结果

4.1 数据基本情况及处理

本文将2020年5月某批次船舶航行产生的AIS轨迹数据作为原始数据样本，该数据样本共包含628艘船舶和对应的23 168个AIS轨迹数据点。作为实例验证，设定起始点为山东烟台港，目标点为辽宁大连港。对原始AIS数据进行预处理：

1)清洗AIS数据，保留其中经纬度、航速、吃水和航向等字段数据正常且符合条件的点，经度正常数据范围为121.12°E～122.02°E，纬度正常数据范围为37.57°N～38.945°N，航速正常数据范围为0～50 kn，吃水正常数据范围为0～50 m，航向正常数据范围为0°～360°。

2)设置通航条件，以吃水大于5 m、航速大于5 kn为标准，保留符合通航条件的AIS数据。

3)采用DBSCAN密度聚类算法剔除AIS数据中公共通航区内的离散点，排除AIS数据离散点对航路规划的干扰。在参数设定方面，给定的距离范围设置为2 n mile，包含的点数不小于给定的阈值3。

经上述处理之后，得到162艘船舶对应的1 963个轨迹数据点，将这些数据作为此次航线规划方法实例验证的基础数据。

4.2 实例分析过程

首先基于筛选处理的AIS数据构建可通航栅格环境模型，并将其转化为邻接矩阵。

1)以0.025°为单位分割度数划分经度在120.895°E～122.270°E，纬度在37.570°N～38.945°N的既定经纬度范围，确定船舶航行区域的栅格范围。设定起始点的经纬度范围，经度范围为121.27°E～121.57°E，纬度范围为37.67°N～37.85°N；设定目标点的经纬度范围，经度范围为121.72°E～122.02°E，纬度范围为38.765°N～38.945°N。

2)根据上一步骤确定的单位分割度数划分指定航行区域的栅格范围，得到将航行区域分割成55×55个单元栅格的栅格环境模型。沿横轴方向由上向下对栅格依次编号，分别为1，2，3，…，直至所有栅格编号完毕。根据筛选处理之后的AIS数据判断各栅格内是否出现过AIS数据，若出现过AIS数据，则将其确定为可通航栅格，否则将其确定为不可通航栅格，由此得到此次实例验证的可通航栅格环境模型(见图6)。

3)采用邻接矩阵算法确定两相邻可通航栅格之间的距离，将具体栅格编号转换为经纬度，根据地球上两点之间距离的计算公式计算两相邻可通航栅格之间的距离。

随后，通过MATLAB软件实现基于蚁群算法的最短航线求解。设置出发点A(经度为121.495°E，纬度为37.800°N)和到达点B(经度为121.770°E，纬度为38.815°N)，并将其转换成指定航行区域栅格中的对应栅格位置出发点，设置最大迭代次数Nmax=500次，蚂蚁个数m=100个。运行蚁群算法程序，完成最短航线规划任务。同时，为验证本文所提方法的航线规划效果，将采用该方法规划得出的最短航线与基于AIS数据和A*算法得出的最短航线相对比。

4.3 实例分析结果

基于船舶航行AIS轨迹数据和栅格法构建航行区域可通航栅格环境模型，采用蚁群算法得到的最短航线规划结果见图7；基于AIS数据和A*算法得到的最短航线规划结果见图8。为观察蚁群算法在搜索最短航线时的收敛过程，给出采用蚁群算法计算求解最短航线的整个收敛过程(见图9)。

通过对试验结果进行对比可知：采用蚁群算法得到的最短航线长度为270.5 km，航路转向点个数为25个；采用A*算法得到的最短航线长度为279.4 km，航路转向点个数为29个。2种方法相比，本文所提方法在航线长度上可节省约3%，且初步规划出的航路转向点个数更少。2种方法均符合船舶实际航行要求，与传统的在纸质海图上绘制航线和在电子海图上输入航路转向点生成航线相比，在便捷性和安全性等方面的表现更优。因此，采用本文所提方法规划出的航线在经济性、安全性和便捷高效性等方面具有一定的优势；此外，与其他航线自动规划方法相比，在节省时间和经济成本的同时，提高了全局搜索能力。

5 结 语

本文通过构建基于AIS数据的栅格环境模型，结合蚁群算法进行了船舶航线自动规划。通过在中国沿海港口进行实例验证，说明了该方法在全局最优航线自动规划方面具有经济、便捷、安全的应用效果。

与其他航线规划方法相比，本文所提方法的主要优势和创新之处在于：能在不使用大量电子海图的情况下对收集的AIS数据进行筛选，从而构建出符合实际应用要求的航线，节省时间成本和经济成本；能利用实时更新的AIS数据充分研究船舶在复杂航行环境下的航行情况，从而保证船舶安全航行；采用蚁群算法获得能避免陷入局部最优的最短航线。

另外，本文所提方法仍有一些不足之处有待完善，例如：在实际生产过程中，海洋环境复杂多变，若可航范围较大，在采用该方法对海洋环境进行栅格化编码时，栅格过大会导致精度较差,易出现偏差，栅格过小会需要较多的计算资源，所需时间过长，效率较低，需结合实际情况做出评估，确定合适的划分标准；可结合改进之后的蚁群算法提升原有算法的效率和准确性。由于初始航线是基于栅格网格得到的，输出的航线转向点较多，与实际规划的航线有一定的偏差，因此可根据船员规划航线的习惯，进一步采用航线平滑处理等方法对航线进行优化，规划出符合实际航行习惯的航线。