基于遗传算法的渡轮横越航道动态路径规划研究

刘成勇 万 一 王 新 陈蜀喆

(武汉理工大学航运学院1) 武汉 430063) (湖北省内河航运技术重点实验室2) 武汉 430063)(长江引航中心3) 江阴 214400)

0 引 言

船舶横越是指船舶行驶方向与航道形成一定角度，从航道一侧穿越至另一侧的行为[1]．内河渡轮在横越航道时，极易与直行船舶发生碰撞，从而造成人员伤亡、水域污染、船舶受损甚至沉没等危险[2]．因此，如何确定渡轮与直行船舶的安全缓冲区、如何规划横越的安全轨迹，以及直行船舶数量与渡轮横越通过能力之间的关系，这些都是亟须解决的实际问题．

根据《内河避碰规则》要求，横江渡轮需穿越通航分道或分边航路时，应在无碍且沿规定航路行驶的船舶航行安全的情况下就近进行．对于渡轮航行过程中的碰撞风险，吕木荣等[3]通过水流、穿越角度及安全距离的影响，计算工程船穿越船舶流的时间与安全距离之间的关系．张赫等[4]通过船舶的不同穿越角度，选择有利的穿越时机达到合适的穿越间隙穿越水道，有效降低船舶的碰撞风险．高建杰[5]建立汽渡轮碰撞危险度阈值计算模型，实现渡轮碰撞危险的预警．路径规划算法研究可分为全局路径规划算法，例如，遗传算法[6]、A*算法[7]，和局部路径规划算法，例如蚁群算法[8]．对于传统路径规划算法改进也能得到较好的效果，例如将国际海上避碰规则引入到船舶路径规划中，能够使规划后的船舶路径更符合实际航行要求[9]；将无人船局部路径规划和控制循迹方法结合，可使规划后的无人船路径更短[10]；A*算法中引入激光雷达系统，可使得船舶路径跳出局部最小解．

渡轮横越航道时选择安全可靠的横越路径可以有效避免直行船舶带来的干扰问题．因此，了解不同航道饱和度情况下渡轮横越航道的通过率，对于提升航道资源规划和管理能力，以及优化航道交通资源配置具有重要意义．

1 横越渡轮与直行船舶安全间距

1.1 停船视距

为保证船舶通航安全，在船舶周围设置一个其他船舶不能进入的安全区域，这个安全区域称之为该船的船舶领域．船舶领域的计算可以采用停船视距法，船舶停船视距模型见图1．

图1 停船视距模型

s=s0+s1+s2

(1)

式中：s为最小停船距离；s0为两船间的安全距离，一般取1/4船长，即0.25l船；s1为驾驶员的反应距离；s2为船舶制动距离．船舶驾驶员的反应距离s1为驾驶员从发现危险到作出制动措施决定的这段反应时间内船舶航行的距离，计算公式为

s1=k0×s

(2)

式中：k0为反应距离和船舶间距之比，一般取42%．

对于船舶制动距离s2的计算主要考虑船舶制动过程中的作用力，在船舶制动过程中主要有两种作用力，即船舶制动力和水流力，见图2．内河船舶在实际制动过程中风力作用对船舶影响很小，可予以忽略．

图2 船舶制动受力分析

f1f2

f1=P/v

(3)

f2=kv2

(4)

船舶制动时受到的合力F和制动时的加速度a为

F=f1+f2=p/v+kv2

(5)

(6)

船舶制动距离s2计算为

(7)

式中：f1为船舶制动力；f2为水流力；P为船舶功率；v为静水速度；k为水流力系数，取2.84×104．

根据式(1)可得最小停船视距：

(8)

1.2 渡轮横越航道时的安全间距

图3为渡轮从码头O1～O2的横越航道示意图，O1为孩溪码头；O2为江心洲码头.渡轮横越航道时须与直行船舶保持适当安全间距，渡轮纵向与直行船舶的安全间距用渡轮停船视距SA表示，横向安全间距为直行船舶船舶领域．图4为直行船舶与渡轮纵向安全距离，实线框为直行船舶的船舶领域的边界，其他船舶均不可进入；虚线框为渡轮与直行船舶的碰撞危险缓冲区，渡轮横越时不可进入此区域．但是在实际航行过程中，船舶能够采取避碰行动，包括改变航向或者速度，因此实际的危险区域要小于理论危险区域．

图3 渡轮横越航道示意图

图4 直行船舶与渡轮纵向安全距离

2 基于遗传算法的路径规划模型

2.1 初始化

1) 航道格栅化 本文通过格栅法建立渡轮通航环境模型，使可航区域与障碍区域都呈现在一张格栅图上，易于使算法实现对路径的搜索任务．

用0、1、2对航道与在航船舶进行动态格栅化处理．图5为地图格栅化示意图．

图5 地图格栅化示意图

假设直行船舶保持航向和初始速度不变，渡轮只改变航行方向，渡轮离泊为t0时刻，此时第k个直行船舶起始坐标为(Xk(t0),Yk(t0))，起始速度vk，渡轮轨迹每增加一个格栅，时间t和格栅地图更新一次，ti时刻直行船舶位置为Ok(Xk(ti),Yk(ti))，则Xk(ti)=Xk(t0)+vkti，Yk(ti)=yk(t0)．

2) 种群初始化 遗传算法求解最优路径过程中，既要保证路径的可行性，还要保证路径的连续性．

ti、ti+1时刻航道内船舶分布见图6，以ti+1时刻新格栅地图为基础，选取ti时刻渡轮位置周围8个方向作为新格栅，并判断此格栅是否为障碍格栅，是否已经在原路径中，若是则删除该格栅，若不是则将该格栅新增到路径中．判断两个距离接近的格栅是否连续如式(9).

图6 不同时刻航道船舶格栅地图

δ=max{abs(xi+1-xi),abs(yi+1-yi)}

(9)

式中：xi、yi、xi+1、yi+1分别为两个距离接近的格栅坐标；max为取最大值操作；abs为取绝对值操作．如果δ=1，则表明两个距离接近的格栅pi和pi+1为连续路径，否则表明为间断路径．

2.2 适应度函数

使用渡轮航行中的最短路径作为评价指标，适应度函数用路径长度的导数表示．即

(10)

式中：n为个体路径中所含的格栅数目；L为个体路径的长度大小．

2.3 遗传操作

1) 遗传算子 为顺利完成种群初始化过程和迭代进化过程，初始种群中的所有个体都需要经历选择、交叉和变异操作，规划出一条安全合理的航行路径．

2) 选择操作 将适应度值从小到大排序，按照优胜劣汰的原则保留适应度值高的个体进入到下一代．例如定义种群中前40%为强者，剩下60%为弱者，弱者中有0.3的比例存活，则这强者和弱者中存活的个体构成一个新的种群，进行下一步的交叉操作．

3) 交叉操作 交叉的方法有很多种，本文采用单点交叉．选择相邻两个个体，两个体间中路径相同的点，在相同点中随机选择一个将该点之后的路径进行交叉操作，得到两条新路径．

4) 变异操作 变异操作能够增加种群多样性，使算法更加具有普遍性．种群更新完毕后输出结果．

3 实验与结果分析

3.1 研究区域与数据选取

选取位于长江下游尹公洲航道的孩溪至江心洲汽渡作为研究目标，见图7．

图7 长江下游尹公洲孩溪至江心洲渡轮水域航道图

根据AIS数据统计全天直行船舶中88%的船舶为3 000 t级以下的船舶，见表1．

表1 3 000 t级以下船舶船长及其比例

渡轮横越航道时，当航道行驶过程没有碍航船舶时渡轮一般以最短路径航行，若有碍航船舶时，可从右侧加速绕碍航船舶船艏或从左侧绕碍航船舶船艉行驶．由图8的尹公洲渡轮AIS数据轨迹图也可以看出这一规律．

图8 渡轮AIS轨迹图

3.2 渡轮停船视距

船舶停船视距的计算主要通过根据船舶的船型数据和船舶航速，从而确定渡轮与直行船舶相互之间和的安全距离和危险缓冲区大小．尹公洲航道孩溪至江心洲渡轮船长61 m、宽13 m、吃水6.9 m，主机功率300 kW，船舶总吨位500．根据AIS数据统计渡轮在正常航行过程中平均航速为7.5 kn(3.8 m/s)，最高航速为10.4 kn(5.35 m/s)．基于式(8)，渡轮停船视距计算见表2．

3.3 地图格栅化

1) 船舶领域格栅化处理 根据AIS数据分析，在内河中直行船舶船舶领域和船长的比值在2.5～3.5倍，船舶领域宽度和船长的比值在1.5～1.9．在统筹兼顾计算量和计算精度的基础上，本次研究单位格栅为50 m×50 m．由于各区域大小只能为格栅大小的整数倍，船舶领域取平均值，长轴取为3倍船长，船舶领域短轴取1.6倍船长，渡轮与直行船舶中的危险缓冲区取1倍渡轮船长．其中渡轮占一个单位格栅，直行船舶格栅可取船长为40，60，80，100 m四种船型，以60 m船长船舶为例，船舶领域长轴为180 m，短轴为96 m，因此船舶领域格栅为4×2，渡轮危险缓冲区为4×1，见图9．其中深灰色区域为直行船舶船舶领域格栅，浅灰色区域为渡轮与直行船舶间的危险缓冲区．

图9 船长为60 m的直行船舶领域格栅图

2) 航道格栅化处理 横越渡轮平均航速为7.5 kn．假设航道中的直行船舶都沿直线匀速行驶，在渡轮航行开始到结束的时间内船舶，下行直行船舶平均可航行1.8 km，上行船舶船速小于下行船舶．航道地图长度取3.6 km、宽度0.9 km，其中航道宽度为0.6 km，满足模拟渡轮横越航道的要求．渡轮横越时，航道范围内存在15条船舶，根据AIS数据可得到船舶的动态信息和静态信息包括航向、船长、船宽、速度和位置等．根据航道环境和位置信息绘制渡轮横越航道时的船舶分布图，见图10．图中浅色区域为小型船舶上行推荐航道，深色区域为双向通航的深水航道．根据表3统计的信息对t0时刻的航道地图格栅初始化，见图11．

图10 渡轮横越航道时船舶分布图

表3 航道内船舶AIS数据信息统计表(部分)

图11 t0时刻航道格栅图

3.4 路径规划对比分析

为验证遗传算法应用于渡轮横越航道路径规划的正确性和有效性, 在pycharm环境下对算法进行仿真实验．交叉概率为0.6，变异概率为0.2，最大子代数为1 000．图12为动态避障路径规划的仿真结果, 直行船舶是运动状态，其中方块深色部分表示船舶领域，浅灰色部分表示渡轮与直行船舶的移动安全区．通过遗传算法对渡轮横越路径进行计算，得到横越路径后与渡轮实际横越路径进行比较．渡轮实际横越轨迹和遗传算法路径轨迹图，见图13．

图12 动态格栅路径规划结果

图13 渡轮横越航道规划路径与实际路径对比图

(11)

一般平均相对误差在0%～15%内属于合理范围，计算得MRN=7.6%，在合理范围内．因此遗传算法用于渡轮横越航道的路径规划是正确和有效的．

4 结 束 语

内河渡轮横越航道时不能干扰航道内正常航行船舶，在航路选择上既要考虑航行安全又要注重效率．本文以以长江下游典型渡区航段为例，通过停船视距理论计算横越渡轮与直行船舶的安全间距及安全缓冲区，以船舶AIS交通流数据为基础，分析航道通航环境和渡轮横越规则，对船舶运动轨迹与航道图进行动态格栅化处理，并基于遗传算法对渡轮横越航道的路径集合进行选择、交叉、变异操作．仿真实验对比分析中，遗传算法模型的交叉概率取0.6，变异概率取0.2，最大子代数为1 000，结合尹公洲孩溪至江心洲渡轮，对渡轮横越航道进行路径规划，并与船舶AIS轨迹进行对比分析，平均相对误差为7.6%，误差在合理范围内，实验结果表明能够为渡轮横越航道时的航迹控制起到辅助支持作用，可优化内河渡轮航线．