基于改进蚁群算法的船舶冰区航行路径规划

童帮裕, 胡坚堃

(上海海事大学 物流科学与工程研究院， 上海 201306)

随着北极冰缘线面积逐年下降，部分海域已处于可航状态，远洋船队在高纬冰区海域航行已成为可能，尤其是北极航道的开辟和“冰上丝绸之路”战略的推动，利用冰区航道开展商业活动越来越频繁。[1]但由于冰情复杂，船舶在冰区航行易受到海冰侵袭，导致碰擦、搁浅、受困等情况的发生，船舶和船上人员的安全受到很大威胁。[2]以往，船舶冰区航行路径的选择大多凭经验进行选择，随着近年来冰区航行频率增加，为确保航行安全，维护船队利益最大化，对冰区航线进行科学的规划显得尤为重要。

目前，对船舶路径规划尤其是特殊航区路径规划方面的研究相对较少。CHANG等[3]基于航行环境建立栅格海图，利用迷宫算法使规划的路径能够有效地规避障碍物。RAFAL[4]在船舶航线规划模型中加入避障容差和转弯次数，并设计具有线性时间和空间复杂度特征的算法。甘茂成[5]构建起点与终点到障碍物之间公共切线组成的切线图网络模型，并采用Dijkstra算法规划最短航线。李源惠等[6]设计出一种能够快速判断网格可航性的动态网格航线自生成法，规划的航线能够有效地规避障碍物。这些研究虽然能够规划出较好的路径，但主要集中在对障碍物规避和最短路径的寻找上，没能考虑到特殊航区路径规划中的更多要求。

多种算法的结合实现算法性能提升是算法研究的主要方向。LIU等[7]利用人工势场法中的势场力重新构造启发信息，提出势场蚁群算法，算法虽然收敛速度良好，但缺乏全局搜索能力，易出现停滞。庄晓东等[8]把人工势场的路径规划结构作为先验知识初始化蚁群算法的参数，有效提高没有先验知识的优化效率，但该算法结构复杂，运算耗费时间长。刘雄等[9]为提高规划路径的平滑度，运用人工势场法对蚁群算法的全局路径节点进行平滑处理，但其重复规划能力较差，结构不稳定。受蚁群算法和人工势场法的启示，本文设计一种新的蚁群算法。仿真结果表明该算法能够有效满足船舶冰区航行路径规划的需求。

1 问题描述

冰区航行是指船舶在穿过冰区或受到海冰威胁的高纬航线上航行。北极航道的西北航线和东北航线、北大西洋航线以及南极航线都是著名的冰区航线。[10]不同于一般海区，海冰对船舶航行的影响较大，船舶在冰区航行需要频繁改变航向，操纵、航行定位和确保安全航行等都相当困难。[11]目前，虽然高纬已出现可供船舶航行的航道，但依然分布有大量的浮冰和薄冰带，严重影响航行安全。

船舶航行路径规划是指在特定条件下找到一条从初始点到目标点的最优路径。船舶在冰区航行的路径规划除要寻找一条安全的避险路径外，同时还要处理多个优化目标，冰区路径规划实际上就是一个针对航路点、障碍物的非线性规划寻优问题。

2 模型建立

2.1 航行环境建立

船舶在一个有限区域内的航行可视为船舶在二维平面上的运动。针对需要规划航线的船舶，以S-57电子海图为标准，在其航行的冰区内建立栅格模型。为保证船舶与冰山等障碍物的安全距离，避免航线与海冰障碍区的重叠，对海冰栅格内的障碍物进行膨化处理，即栅格内只要存在障碍物即为海冰障碍物栅格。

船舶以网格为最小运动单位，航向均是前往下一个网格的中心点，航速保持不变，航程计算以网格中心点为准。按照船舶航行的安全航行范围和转向所需空间，将区域划分为若干λx×λy的矩形网格。船舶在网格间移动次数为fn，表示船舶在第n次运动后占据的网格点，只要船舶所在的网格发生一次变化，则n+1，同理，n-1和n+1次的变动分别为fn-1和fn+1，且不重复，所以船舶航线F由航路点f1、f2、…、fN组成。定义f1为冰区航段的起始点q0，fk为冰区航段的终结点qf。当船舶在绕行海冰时，优先选择与海冰流动方向错开的区域，称在这类区域里的航路点为流冰规避航路点secn，整个矩形网格区域应覆盖航段两侧海冰区域。对网格进行编号，沿横轴方向由上向下依次编号，网格数量为15个×15个，网格编号依次为1、2、…、225，航行环境示意见图1。

图1 航行环境示意

2.2 目标函数

航行路径规划要在保证航行安全的同时考虑到航线距离、操作复杂程度和流冰规避。因此，综合考虑船舶航行条件和船舶性能等因素，从航线距离、航线平均偏离度、流冰规避航路点选择3个方面建立多目标规划模型。

2.2.1航线距离

(1)

式(1)中:D(L)为航线距离；设第n次的航行路径所穿越的网格中心点为fn(n=1,2,…,N);d(fn,fn+1) 为点fn到点fn+1的直线距离。

2.2.2平均偏离距离

由于冰区水道曲折，为降低船舶操作难度和保证路径平滑度，加入规划路径与起始点和目标点间的直线段平均偏离距离比的指标为

(2)

2.2.3流冰规避区域选择

海冰会随着海浪、海风而不断地在海域内漂移，海冰运动方向受风与流作用的影响：北半球海冰移动方向偏于风向右方30°～40°；南半球则是在左方。[11]船舶通过冰区需要考虑到流冰的影响，所以航线对流冰的规避也是需要考虑的重要因素[12],即

(3)

式(3)中:k为一个0～1的变量，当fn∈secn时，k=1，否则k=0。

3 基于改进蚁群算法的路径规划

蚁群算法是模拟蚂蚁通过信息素交流寻找最短路径的智能算法。虽然蚁群算法具有先天性的图上作业优势，但也存在初期路径选择盲目、易陷入局部最优等问题。人工势场法的算法结构简单，路径搜索初期和后期差异较小，易同其他算法结合。本文结合两种算法的特性，利用人工势场法求得的初始路径和节点间距离因素改进启发信息，设计一种改进的蚁群算法。

3.1 人工势场法求解初始路径

人工势场法的基本思想是通过目标点引力场和障碍物斥力场共同作用来搜索出一条无碰撞的最优路径。其定义如下：

假设船舶当前所在位置X=(x,y)，目标点位置Xg=(xg,yg)，则引力势场函数为

(4)

式(4)中：φ为大于零的引力场因子；X为船舶位置向量;Xg为目标点位置向量。

斥力势场函数为

(5)

式(5)中：φ为大于零的斥力场因子；R为船舶到冰山的距离；Rmax为冰山的最大影响范围。

船舶在引力和斥力的共同影响下，向目标点方向运动并最终到达目标点。

3.2 改进启发信息的路径选择准则

传统的蚁群算法中，在t时刻蚂蚁k由节点i选择下一个节点j是根据初始信息素τij(t)和启发信息ηij(t)的大小进行判断的，路径选择准则如下：

(6)

(7)

式(6)和式(7)中：α和β分别为信息素重要程度和启发函数重要程度的因子，反映出信息素浓度和启发信息对蚂蚁下一步转移所起的作用强度；djg为待选节点j到目标点g的直线距离；allowk={0,1,2,…,n-1}为蚂蚁K待选节点。

针对传统蚁群算法获取第一条路径时更容易选择距目标点近的节点的情况，用人工势场法获得的初始路径和节点距离因素改进启发信息，建立新的路径选择准则。同时，引入信息递减系数υ来降低启发信息的影响。新的启发函数为

(8)

式(8)中：dij为节点i到节点j的直线距离；Ljg为采用人工势场法求得的节点j到节点g的距离；Nc为当前迭代次数；Nmax为最大迭代次数；υ为启发信息递减系数，且υ>1。

3.3 带有路径评价的信息素更新机制

在蚁群算法中，蚂蚁在完成一次迭代后，会对路径(i,j)上的信息量调整，调整如下：

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

(9)

(10)

式(9)～式(10)中:τij(t+n)为t+n时刻路径(i,j)上的信息量；ρ为信息素挥发系数；1-ρ为信息素残留因子；τij(t)为本次循环中路径(i,j)上的信息素增量。

(11)

选用ant-cycle system模型，Q为一个常数即信息素强度；ω为路径评价函数，根据路径评价结果对信息素进行更新。评价函数为

ω=ω1L+ω2T+ω3K

(12)

式(12)中:L为路径长度；T为平均偏离距离；K为航行上流冰规避航路点选择次数。ω1、ω2、ω3分别为路径长度、平均偏离距离、流冰规避航路点选择的权重。

3.4 算法步骤

改进的蚁群算法见图2。

1) 建立航行环境的栅格模型，设置起始点、目标点、障碍区域和流冰规避航路点。

2) 设置蚂蚁数量m、最大迭代次数Nmax、信息素重要程度a、启发函数重要程度β、信息素浓度Q、启发信息递减系数υ、信息素挥发系数ρ、路径长度权重ω1、平均偏离距离权重ω2、流冰规避航路点选择权重ω3等相关参数。

3) 用人工势场法求得初始路径和节点距离信息Ljg，并根据改进的蚂蚁路径选择准则选择下一步路径点。

4) 若蚂蚁到达目标，则结束本轮循环，按照信息素更新机制更新信息素。

5) 判断是否达到最大迭代次数，若是，则终止并输出最优路径，否则转到步骤3)。

图2 算法流程

4 仿真计算

冰区航行需要对航行海域内的冰情充分掌握。夏季，海冰不断的裂解和漂移形成可通航水域。船舶的通行情况主要受冰量影响，即海冰密集度。通常海冰覆盖在60%以下即为可通航。[13]选取冰量为30%和50%的海域，采用本文的改进蚁群算法试验航行路径规划的效果，并与传统蚁群算法进行对比。

选取的某冰区海域面积为9 km×9 km，考虑到航行安全和船舶转弯占用面积等因素，将其划分为300 m×300 m的网格，建立起30个×30个的环境栅格。采用MATLAB进行计算。设参数：m=45、Nmax=150、Q=15、α=1、β=15、ρ=0.95、υ=4、ω1=8、ω2=6、ω3=3，并设置海冰障碍物左侧为流冰规避区域。分别在海冰覆盖率为30%和50%的海域模型中进行20次试验选取最优路线。

1) 海冰覆盖率为30%时，得到的最优路径见图3，两种算法的相关性能指标比较见表1。

a) 常规蚁群算法路径

b) 改进的蚁群算法路径

表1 海冰覆盖率为30%情况下两种算法性能指标比较

试验证明:在海冰覆盖率为30%时，两种算法都能较快收敛并得到最优路径，虽然改进蚁群算法的路径长度较长，但转弯点较少、平均偏离距离较短，更多地经过流冰规避区域，船舶航行操作相对简单、安全。

2) 海冰覆盖率为50%时，得到的最优路径见图4，两种算法的相关性能指标比较见表2。

a) 海冰常规蚁群算法路径

b) 改进的蚁群算法路径

表2 海冰覆盖率为50%情况下两种算法性能指标比较

试验证明：在冰量较大的复杂环境中，传统蚁群算法规划的路径并不理想。本文改进蚁群算法的寻优能力强，在转弯点个数、平均偏离距离和流冰规避上都有明显的优势。由此可见，改进蚁群算法能够更好地满足冰区航线需要。

5 结束语

本文针对冰区船舶航行路径规划的特点，充分考虑到船舶路径规划的经济性、操作性、安全性。应用本文方法获得的路径要优于传统蚁群算法的路径，且简单可行。本文研究也存有不足之处，具体表现在：环境模型中没能考虑到冰山的动态可变性，没能考虑到狭窄环境中与其他船舶的避让，以及缺乏对船舶航速等方面的考虑，这些也是未来对船舶冰区航行所需要研究的方向。