考虑风浪流影响的船舶路径规划及算法

谢新连，王余宽,2，何 傲，潘 伟，许小卫

(1. 大连海事大学 综合运输研究所，辽宁 大连 116026； 2. 武汉理工大学 航运学院，湖北 武汉 430063)

0 引 言

人工智能技术日益进步，船舶业也向着智能化方向发展，2016年中国船级社颁布的《智能船舶规范》中将航线规划技术列为船舶智能化的一项重要途径。为船舶规划航线，尤其当面临海上搜救、海上缉私等对时间要求紧迫的任务时，为巡逻船或执法船等规划出航行耗时短的路径是必要的。另外，海洋气象环境会造成船舶失速，此时考虑海洋气象环境的影响智能规划航行路径，则更能提高船舶航行效率，提升船舶智能化水平。

目前，国内外已有大量的船舶路径规划研究，主要集中于不考虑海洋气象环境的研究上。蒋美芝等[1]考虑海上碍航区和船舶经济效益设计船舶航线，基于栅格环境建模和蚁群算法求解路径；SONG Rui等[2]针对A*算法求解无人水面艇避障路径不光滑的问题，对A*算法进行改进并求解获取了平滑程度较高的路径；谢新连等[3]将航行经验转化为船舶航行规则，利用强化学习和A*算法为受限水域内船舶规划全局避碰航线；S.M.LEE等[4]考虑船舶排放法规的约束，以航速优化为目标求解不同航段的航法；XIE Lei等[5]设计了一种全局多方向的A*算法，对海上风电场内工作的船舶规划航线；LIU Yuanchang等[6]应用改进随机树算法，以距离最短为目标为船舶设计了平滑性较大的航线；Y. SINGH等[7]考虑了动态碍航物和水流对船舶航行的影响，设计了一种改进A*算法求解船舶避障路径；H.KIM等[8]针对无人水面艇在风浪流环境中避障航行设计航线，其获取的路径转向点较多不适用于转向慢或回转半径大的船舶。

多数研究未考虑海洋气象环境或仅考虑海流对船舶航行的影响，综合考虑风、波浪及水流影响对船舶路径进行规划的研究尚少。但实际上，船舶受到风、波浪和水流的干扰后，会出现明显的失速现象，因此，为船舶规划能够避障航行且耗时最短的航线时，考虑风、波浪及水流的影响是必要的。

笔者从3个方面设计船舶路径优化方案：①分析海洋环境对船舶航行带来的干扰，设计了考虑风、波浪、水流及安全水深影响的路径规划方案；②为提高算法收敛精度和效率，设计了交叉变异算子自适应的改进遗传算法；③为优化算法运行耗时，对改进的遗传算法设计主从并行化模型实现模式。通过方案设计和算法优化求解，以提高船舶路径智能规划的有效性。

1 风浪流影响

1.1 风浪流干扰力

船舶航行时，风、波浪和水流作用于船体产生阻力，使得船速和航向发生改变。通常，将船舶所受海洋环境阻力分为风力、波浪力和水流作用力，由于实际海况中风和波浪存在的不确定性[9]，船舶受力公式一般通过模拟试验获得，即在风洞和水池条件下模拟风浪流环境，计算船舶航行过程受到风浪流的干扰力。

用τwind和τcurrent分别表示船舶所受风和水流的干扰力矢量，二者计算方法为式(1)[10]～式(2)[11]：

(1)

(2)

式中：ρa和ρw分别为空气和海水密度;AFw和ALw分别为水面以上风的正投影和侧投影面积;CXw和CYw分别为X方向和Y方向的风力负荷系数;γrw为风向与船艏的夹角;Vrw为风对船舶的相对速度;AFc和ALc分别为水面以下水流的正投影和侧投影面积;CXc和CYc分别为水流作用力沿X方向和Y方向的负荷系数;γrc为水流向与船艏的夹角;Vrc为水流对船舶的相对速度。

实际应用中计算船舶所受X方向和Y方向的风力合力和水流合力，结合式(1)和式(2)计算得式(3)：

(3)

波浪可分为规则波和不规则波，后者存在较大不确定性和计算复杂性[12]，模型仅考虑规则波产生的干扰力。规则波干扰力计算方法中较为常用的是Daidola基于水池船模试验提出的计算方法如式(4):

(4)

式中：ρa为海水密度;ls为船长；κ2为波浪振幅;γw为波向角;λw为波长;Cw为波浪力负荷系数。

1.2 船舶失速

(5)

船舶受海洋气象环境影响导致航速变化如图1，结合速度矢量运算得到船舶受环境影响后的航速v′，用式(6)表示为：

图1 船舶受风浪流影响示意

(6)

2 路径规划方案设计

2.1 方案假设

船舶路径规划的目标是在保证船舶航行安全的前提下规划出一条满足航行要求(如航行距离最短、航行耗时最短等)的路径。结合船舶驾驶操作要求，路径规划应考虑船舶吃水深及碍航区边界是否规则等因素。另外考虑到海洋环境的复杂性以及船舶本身的特性，建立以下假设：①水域内风和波浪分别为恒风和规则波；②风浪强度在船舶耐受范围内；③视水域为二维平面环境，船舶运动忽略高度条件；④船舶在路径转向点更改航速不占用时间。

2.2 安全航行水域提取

通常，航行水域内碍航区边界并不规则，采用Graham凸包算法[13]将原始碍航环境处理为凸多边形，顶点的数量取决于地图的比例和大小。另外，为保证船舶不与航行空间内的任何障碍物相撞或过于接近，也不会受水深影响发生搁浅，将碍航区的边界向外延伸hkm，扩展后覆盖的水域为航行保护区，如图2，扩展区以外的水域为安全水域，凸包算法和外延操作过程如式(7):

图2 扩展保护区示意

(7)

式中:Wk为水域中第k个碍航区;hmin为考虑安全水深的影响需要外延至少hmin才可获取安全水域;Sk为第k个扩展保护区;dr为所有扩展保护区组成的顶点集合中的第r个顶点。

2.3 航行网络图构建

2.3.1 构建Maklink图

在建立航行水域碍航区凸多边形模型的基础上，应用Maklink图论进行航行环境建模，其步骤为：

步骤1障碍物顶点集合D内所有点两两相连，所有连线从短到长排序并组成候选链接线集合Φ。

步骤2选择Φ中的最短线段Φmin。

步骤3判断该线段与障碍区S是否相交，如果相交则转向步骤8，如果未相交则转向步骤4。

步骤4判断该线段与相应凸多边形顶点产生的两个外角是否都≤180°，若是则转向步骤5，若否则转向步骤6。

步骤5删除该顶点的其他链接线，转向步骤9。

步骤6检查该顶点的其他链接线是否都≤180°，若是则转向步骤7；若否则转向步骤9。

步骤7删除该顶点的其他候选链接线，转向步骤9。

步骤8从集合Φ中删除该线段。

步骤9判断是否遍历Φ内所有线段，若是则结束，集合Φ内剩余的线段集合则为生成的Maklink线；若否则转向步骤2。

经过以上步骤得到碍航区环境，图3给出2个示例，Maklink线集合M={Mj,j=1,2,…,J}。

图3 航行网络

2.3.2 路径转向点表达

(8)

(9)

式中：θj∈[0,1],j=1,2,…,J。

由式(9)可知，θj任取一个值则相应产生一个路径点。因此，即使Maklink线是有限的，但路径可选择的转向点是无限的，所以需要建立最优化数学模型以求解最优路径点。

2.4 初始路径规划

在存在J条Maklink线的航行网络图中，每条Maklink线上的点均为候选转向点，利用 Dijkstra 算法在Maklink图上生成由点序列集合P={pi,i=1,2,…,I}组成的一条初始船舶避碰路径，I表示初始路径点共在I条Maklink线上产生，每个点均为其所在Maklink线的中点，此时θj取值为0.5。集合P内点的个数I小于Maklink线的数量J，基于集合P再求解最优路径将提升求解效率，用式(10)表示Dijkstra 算法的求解操作：

P={pi,i=1,2,…,I}=Ψ(M,θj),θj=0.5,j=1,2,…,J

(10)

集合P中p1为路径起始点，pI为目的点，P′={pi,i=2,…,I-1}为所有转向点集合，各转向点顺序连接组成的航段集合用L={Lg，g=1,2,…,G}表示。结合式(10)和式(9)得初始路径点序列的坐标，用式(11)表示:

(11)

式中：i=1,2,…,I。

2.5 路径优化模型

由式(9)和式(10)知(θ1,θ2,…,θI)可以用来映射一组路径解的位置信息，基于此，考虑风、波浪、水流对船舶航行的影响时，船舶在不同航段的航速发生改变，此时满足路径避障且航行耗时最优要求的模型目标函数可表示为式(12)：

(12)

式中：Λθ={θi,θi∈[0,1],i=1,2,…,I}。

1)f1(Lg)为无避碰规则路径耗时代价目标函数。风、波浪及水流作用下船舶速度不同于静水航速，船舶于各个航段上的耗时发生改变，设计船舶于航段Lg航行的耗时代价函数为式(13)：

(13)

2)f2(Lg)为船舶路径碰撞代价目标函数如式(14)：

(14)

式中：Sk为规划海域中的第k个碍航区；Lg∩Sk≠∅为路径Lg与Sk有交点，此时碰撞代价无穷大，结合目标函数式(12)相当于此航段耗时代价无穷大；若无交点则不会发生碰撞，此时碰撞代价取值为1，相当于此航段产生的碰撞代价对航段耗时不产生影响。

3 算法设计

船舶路径规划模型中，每组路径解对应一组实数解，求解过程即是在其对应的数值空间上寻找最优值的过程。遗传算法是一种通过模仿自然选择和自然遗传学机理而发展起来的随机化搜索算法，其实数编码方式也能够较好地满足在数值空间上不断寻优的目标。标准遗传算法存在一个缺陷，即迭代寻优过程中不能有效地将上一代的优良信息保留至下一代，为此设计了交叉变异概率自适应的遗传算法，并采取并行式机制实现遗传算法，以助于提升算法的求解效率。基于改进遗传算法优化路径的算法流程图如图4。

图4 基于并行自适应遗传算法的路径优化流程

3.1 基于初始解的遗传算法

路径规划模型求解过程中，标准遗传算法是随机生成初始字符串种群，其缺陷是产生大量不可行种群导致种群搜索效率较低。因此，将Dijkstra算法规划的结果作为遗传算法的初始种群，使所有种群均在可行解的基础上进化，以此提升求解效率。

3.1.1 遗传编码

图5 染色体结构

(15)

3.1.2 评估适应度

适应度函数是从目标函数中推导出来的，目标函数是进行适当映射的必要条件，在每一代新生种群上评估所有个体的适应度，适应度函数约为船舶从出发点到目的地航行耗时的倒数，如式(16)：

(16)

3.2 算子选择概率自适应

遗传算法在迭代寻优时，染色体之间按照一定概率发生交叉变异来生成新解，一般设置染色体发生交叉和变异的概率为固定值，其缺陷是忽视了染色体之间信息优劣差异，使优势信息和劣势信息以相同概率进入到下一代中。因此，设计了交叉和变异概率自适应调整办法，概率自适应规则为当该个体适应度值小于均值时，个体交叉概率α和变异概率β取较大值，否则按照一定方式求取概率值，这种概率选择方式提高了优势信息的进化概率，有助于提升求解质量和效率。概率自适应规则具体如式(17)和式(18)：

(17)

(18)

3.3 AGA算法并行化

算法并行化指利用计算机的不同核心单元同时计算程序的各部分，以此减少程序运行时间。由于遗传算法一次迭代过程中每个染色体的评估都是独立的，所以每一代染色体的评估都适合并行化[14]。并行式自适应遗传算法(parallel adaptive genetic algorithm，PAGA)将各个染色体的适应度评估分配到计算机的各个核心上进行计算，这种并行模式也被称为主从模型并行机制。

主从模型并行机制的理想加速比计算如式(19)：

(19)

式中：γ为并行部分的核心单元数量；ε为串行运算时适应度值计算一次在程序迭代一次过程中的耗时占比。

4 算例仿真

4.1 仿真结果

为验证路径规划方案的有效性，在运行内存为8GB且CPU为Intel core i5-8265u的计算机上仿真。仿真环境以图3(a)为例，包含5个障碍区，设置水域内风级为5级，水流速为2 m/s，风、波浪和水流方向为北偏东45°，静水船速为10 m/s，环境负荷参数参照文献[8]、文献[10]设置如表1。

表1 算例仿真环境负荷参数

采用并行式自适应遗传算法为船舶规划路径，如图6可以看出，未对水域内碍航区进行处理时，规划的路径穿越可能存在的浅水区等不安全水域，船舶按照此路径航行可能发生搁浅、触礁以及与碍航区边界发生碰撞的情况。经过对水域内碍航区适当处理后获得安全航行水域，此时规划的路径完全避开了可能发生搁浅等危险的水域。

图6 安全航行水域规划路径

图7中给出考虑与未考虑风浪流干扰情况下规划的路径。考虑风浪流后路径航行里程有所增加，但航行耗时从378.35 s下降到354.80 s，说明优化后的路径一定程度上规避了环境带来的干扰。另外，针对考虑风浪流与未考虑风浪流两种情况下，采用可视图法、蚁群算法(ant clony optimization，ACO)、标准遗传算法(genetic algorithm，GA)和自适应遗传算法(adaptive genetic algorithm，AGA)分别求解，路径如图8，航程耗时见表2。

图7 风浪流干扰下规划路径对比

图8 考虑风浪流后不同算法规划路径

考虑风浪流后，利用可视图法规划出的路径航程与未考虑风浪流求解结果均为2 425.2 m，结合路径结果对比后发现与未考虑风浪流时为同一条路径，分析其原因在于可视图法不同于其它3种智能优化算法，可视图法的可行路径解集由安全水域的边界点之间相互连接组成，可供选择的路径有限，而海洋环境的影响有时不足以使船舶路径在有限的可行解中发生改变。

由表2知，相较于未考虑风浪流，考虑风浪流后蚁群算法、标准遗传算法和自适应遗传算法求解结果在航程上有所增加，但航行耗时分别减少了5.25%、6.19%和6.22%，这说明考虑风浪流的影响后规划出的路径可以帮助船舶缩短航行耗时。另外，自适应遗传算法规划路径航行耗时为354.80 s，在4种算法中求解结果最优，说明了文中对标准遗传算法进行的交叉变异算子自适应优化是有效的。

表2 不同方法求解结果

4.2 算法耗时分析

在考虑风浪流与未考虑风浪流两种情况下，保证相同求解质量时，分析不同算法的计算效率，并增加了图3(b)的环境进行实验，该环境下实验结果如图9。另外，PAGA算法采用八核心并行机制实现，不同方法分别求解20次的运行耗时平均值如表3。

图9 多障碍区环境路径规划结果

表3 不同求解算法运行耗时

当考虑风浪流影响进行船舶路径规划时，相较于串行机制，主从并行机制实现遗传算法的程序运行耗时更短，且多障碍区环境相较于简单环境更接近并行化机制的理想加速比，这说明主从并行自适应遗传算法能够显著降低算法运行耗时，有效提升了算法效率。

5 结 语

船舶智能化已成为船舶业发展的趋势，智能船舶的应用优势逐步显现，而航线规划技术是智能船舶的一项重要功能。针对船舶航线规划研究中较少考虑海洋气象环境影响的情况，建立了以航行安全为前提、以航行耗时最短为目标的船舶路径规划方法。

综合考虑海上复杂环境因素的影响，考虑航行水域水深限制，计算风、波浪及水流造成的船舶失速，基于Maklink 图论和改进的自适应算法求解船舶航行路径，以帮助船舶更安全、快速地到达目的地。与标准遗传算法和蚁群算法和可视图法对比，在相同迭代次数下求解航行路径，改进的自适应遗传算法所求路径船舶航行耗时更短。另外，在保证一定求解质量的情况下，将自适应遗传算法采用主从并行机制实现能够显著缩短程序运行耗时，有效地提升了船舶路径规划效率。