基于多维度数据挖掘的船舶最优航线路线生成研究

黄曼绮，魏雨东

(电子科技大学成都学院 计算机学院，四川 成都 611731)

0 引 言

在经济全球化发展大趋势下，国家之间贸易交流日益频繁，而大宗货物运输通常使用海运方式[1]。面对较为复杂多样的海洋航行环境以及海上运输线路存在交叉的问题，为船舶规划最优航行线路是海上运输行业重点研究方向[2]。当前也有很多学者研究船舶最优航线生成方法，王立鹏等[3]提出的船舶航线规划算法，该算法通过建立船舶航行时回转与降速模型得到船舶航线数据，再通过分析海图航线规划和陆地物标之间的关系，最后利用四叉树和不规则边界检测方式生成船舶航线。韩志豪等[4]提出深度强化学习的航线生成方法，该方法将电子海图上的航线作为初始数据，利用深度学习神经网络对电子海图上的航线进行采样处理后，输出船舶航行最优航线。但是上述2 种方法生成的航线均存在无法规避较小障碍物、生成线路不是最佳线路问题，为此本文研究基于多维度数据挖掘的船舶最优航线生成方法。

1 船舶最优航线生成方法

1.1 基于多维度数据挖掘的初始航线生成

挖掘官方电子海图（eiectronic navigational charts，ENCs）的海域港口、陆地物标（岛屿、礁石）等多维度坐标数据，并将每个港口、陆地物标看作一个节点，使用改进随机路径图（improved probabilistic roadmap，IPRM）方法生成船舶航行初始航线，其详细过程如下：

从官方电子海图中挖掘到海域港口、陆地物标节点数据后，在船舶航行起点与目的地空间内选择N个节点，连接这些节点后，将起点和目的地之间的连线和该连线附近的障碍物边缘区域作为关键区域，对该区域进行节点扩充处理后，得到船舶初始无向路径网络图G(V,E)，其中V表示无向路径网络图内涵盖的节点集，E表示船舶起点和目的地之间所有可能的路线集。当船舶初始全局航线内存在动态障碍物（有其他船舶穿过）时，需考虑动态障碍物躲避问题。此时需对官方电子海图每8 h 更新一次，重新生成船舶航线无向路径网络图即可。

1.2 最优航线路线生成多维指标设置

在一条航线上，可能存在2 艘或者多艘船舶同目的地相同的情况。当线路生成不合理时，船舶出发或者到达目的地时潮汐较大或过小均影响船舶出入港，因此需从潮汐、船舶安全航行距离多个维度设置最优航线路线生成多维指标。

1）船舶航行安全距离指标

2 艘或者多艘船舶向同一目的地航行时，相邻2 艘船舶中，后一艘船舶的航速不得高于前一艘船舶。假设用i和j表示从同一位置出发的2 艘船舶，其初始距离可看作0，若该2 艘保持相应安全距离，则前方船舶j需始终比后方船舶i多航行 6Li的距离。假设船舶同向航行时间为t，其表达公式为：

式中：Di，Dj分别表示船舶i和j从起点到目的地所用时间。

2 艘船舶航行速度满足如下条件：

式中：Vi，Vj分别表示船舶i和j的航速；t′表示前方船舶j比i先航行的时长。

由式（1）和式（2）综合可得到2 艘船舶安全航行时间间隔，其表达式为：

式中：Xi j表示船舶的前方船舶i是否为j的判断阈值，若是则取值为1，反之则为0。

2）航线目的地潮汐时间指标

受潮汐运动影响，船舶无法实现全时间通航。为保障船舶到达港口附近时能高效进港，需要假设该港口入港航段为单向通航。假设船舶平均吃水为D，在潮汐状态下，每小时时间点涨潮高度为已知数值，则按照潮汐测量通用公式，在1 小时内涨潮函数线性表达式为：

式中：Z表示潮汐量；zd表示初始低潮汐量；k表示1 个小时内涨潮差值；t˙表示涨潮持续时间。通过该公式结果，并结合当时农历日期即可得到船舶进目的地港口的可通航时间T。

由于船舶大多数均满载货物，其入港时吃水较深，入港时则需乘潮，其到达目的地进入港口潮汐时刻约束条件如下：

式中：Qi表示船舶通过港口入港报告线时刻；GCp用于判断时间段p是否为高潮时刻，若是则取值1，反之则取值为0；BHip用于判断时间段p是否小于高潮时刻，若是则取值1，反之则取值为0；Φ表示随机常数；表示潮汐开始时刻；表示潮汐结束时刻。

1.3 最优航线生成方法

以船舶航线无向路径网络图G(V,E)为基础，依据船舶最优航线生成多维指标，使用改进和声搜索算法生成船舶航行最优航线。和声搜索算法（harmony search,HS）是数据挖掘算法内的智能优化算法，通过反复调整记忆库内解变量，使函数随着迭代次数不断收敛实现目标优化求解算法，该算法可调参数较少，应用较为广泛。但其随机生成节点时，会出现复杂多峰情况，导致算法迭代收敛效果不佳。所以对其进行改进处理，利用改进和声搜索算法按照船舶最优航线生成多维指标，从多个维度挖掘并生成船舶最优航线，其详细过程如下：

G(V,E)X={x1,x2,···,xn}

假设内的任意备选解由表示，由多个船舶航线线路组成和声搜索记忆库，其表达式如下：

式中：HM表示和声搜索记忆库；Xi表示船舶的全局航线；U表示和声搜索记忆库内的航线数量；f(·)表示评价航线生成质量的适应度函数。令R表示任意船舶航行线路，则航线生成质量适应度函数表达式为：

式中：Pi和Pi+1均为航程内S的转向点；S表示航程公里数；n表示转向点总数。

在和声搜索算法内引入遗传算法，使用遗传算法在和声搜索记忆库内通过交叉航线、消除节点以及微调节点位置后，生成最优船舶航线，其过程如下：

从HM内随机选择2 条新航线，当这2 条航线符合遗传算法的交叉条件后，使用遗传算法对其进行交叉处理，生成2 条新的航线。若线路和交点为pc；和表示线路内起点到转向点之间线路节点；和表示转向点到目的地线路节点；，，，，，均表示节点标记。此时会交叉生成2 条新的航行路线，其表达式为：

将新生成的2 条航线与未交叉前的原航线进行对比分析，将高质量的2 条航线存储到记忆库内。将记忆库内所有航线均进行交叉操作后，对记忆库内航线进行节点消除和微调处理。假设r表示随机数，PA表示航线节点消除概率（通常取值为0.2），当r＜PA时，

通过式（10）和式（11）生成新航线后，将新生成的航线与记忆库内适应度最差的航线进行比较，选择适应度数值最高的航线作为最优航线。

2 实验分析

2.1 初始航线生成测试

以一艘船舶作为实验对象，使用本文方法生成其初始航线，结果如图1 所示。

图1 船舶初始航线生成结果Fig.1 Initial route generation results of ships

可知，当该船需要从起点航行到目的地时，使用本文方法可生成若干条航线，且每条航线均可到达目的地，同时涵盖所有中转节点和转向点。该结果证明，使用本文方法可有效获取较为全面的船舶初始航线，也从侧面说明本文方法具备较好的航线生成能力。

2.2 最优航线生成测试

以一般船舶为实验对象，使用本文方法生成其最优航线路线，结果如图2 所示。

图2 船舶最优航线路线生成结果Fig.2 Generation result of optimal ship route

分析可知，使用本文方法可有效在初始航线中生成最优航线，且该路线在所有路线中航程最短，在该最优航线内，仅存在一个转向点，航线上无中转节点，可较大程度降低船舶航行耗时。综上结果，本文方法可有效生成最优航线。

以10 艘船舶作为实验对象，使用本文方法生成这10 艘船舶最优航线。将每条最优航线的适应度值作为衡量指标，测试本文方法生成最优航线能力，结果如图3 所示。

图3 最优航线适应度值Fig.3 Optimal route line fitness value

分析可知，本文方法生成的船舶航线的适应度数值始终在0.985～0.995 波动，说明本文方法生成航线较为准确，也是最优航线，应用效果较好。

3 结 语

本文研究基于多维度数据挖掘的船舶最优航线生成方法，考虑船舶航行安全距离和港口潮汐时间多维度，并以其作为挖掘最优航线指标，最终生成最优航线。经过实验验证：本文方法可有效生成最优航线，且所生成的最优航线适应度数值较高，应用效果较好。