船舶航线生成研究

李成海 刘杰 胡甚平 崔建辉

摘 要：基于减轻船舶驾驶航线绘制劳动强度，克服绘制过程中人为主观因素影响的考虑，引进了蚁群计算法自动生成船舶航线研究问题。利用电子海图、阐述更好信息、搜寻策略、划分网络、选取航线、不航航和算法流程的具体做法。案例验证证明：船舶航线生成运用蚁群计算法具有准确和时效性。该研究实现了运用专家的搜寻策略思维下的船舶航行航线绘制的自动化，为制定船舶航线的高效、安全提供了理论依据。

關键词：船舶航行；船舶航线生成；蚁群计算法；搜寻策略；计算法流程

中图分类号：U697.3

文献识别码：A

0 引 言

船舶航行过程中航线绘制是最关键环节，绘制航线需要充分考虑海区季节性风浪影响、海区地理环境和海盗威胁等因素的影响，以经济、安全和高效三大指标为研究对象，力争达到航线生成最优。航线绘制受到时间，思维环境众多因素影响，导致绘制的航线有缺失。

随着电子海图技术的开发和利用，实现了船舶航线的自动生成。目前关于船舶航行航线自动生成的研究有：吴泽亮[1] 运用Adadelta算法使蚁群算法具有更强的随机性，提高了蚁群算法的性能。生成了一条距离最短且避开了碍航物的航线，而且。党庆一[2] 运用蚁群算法搜寻产生初始种群，再利用遗传计算法对各航线优化，获取最优航线。张立华等[3]通过对海图精度的定量分析，建立碍航物数据资料库，在二叉树计算法基础上，运用改进R的航行窗口提高航线生成效率。吕锦涛等[4]在同样的搜索效果前提下，运用航路堆栈航线生成法和当前的航路点，实时制定最优航线。王涛等[5]运用风、流作用的漂移量和航道富裕宽度，建立航道宽度计算模型，从而生成了考虑航道宽度的航行距离最短航线。张金水等[6]通过蚁群计算法和遗传计算法相结合研究航行船舶航线生成办法，在考虑了海图信息离散化和蚁群搜索生成初始种群的基础上，利用遗传优化取得最优航线。

本研究为提高航线绘制的高效和安全目的，引入了蚁群计算法，方便船舶航行航线生成研究。

1 基于蚁群计算法的船舶航线生成研究

1.1  蚁群计算法

蚂蚁从蚁窝对食品源的寻觅路径各不相同，但最终会汇集于同一最短捷径，这蚁群觅食路径留下的外激素成为交互信息源，从而找到蚂蚁觅食最佳路线。蚂蚁计算法是基于蚂蚁的自然功能设计的最佳决策方法，设某一数量的蚂蚁，被设定的觅食规则获取的最好路线[7-8]。

船舶航行航线生成，是依据季节性风浪影响、海区地理环境和人——机协调条件，搜寻的一条最经济又安全的航行路线，这与蚁群计算法适用条件高度一致。利用船用电子海图的海区信息功能，查找蚁群计算法信息生成所需要的航道宽度、海区水深、所经航区上的危险沉船及禁航区、管制区等信息，为蚁群计算提供便利[9]。因此，船舶航线生成引入蚁群计算法，完全可行。

1.2  设计海区栅格

设计海区栅格时需要充分考虑船舶航线生成的精准度和高效性。栅格设计的越密集，则生成的船舶航行航线越精准，缺点是计算量巨大[10]。本研究从计算航行区水域宽度，确立划分船舶航行海区栅格的方法。

考虑到外界因素影响，船舶航行路线，可为一个以设计的计划航线为中心向左右外延一定宽度的带区，称为航行区水域宽度。航行区水域宽度由定位精度和外界条件所决定。在设定航行区水域宽度时，考虑到定位精度的影响，以3倍均方差取值作为航行区水域宽度比较合理，此时船舶航行于航行区水域宽度外的概率大于3‰。航行船舶用路标导航时，航行区水域宽度不小于0.05 n mile，但GPS导航时，航行区水域宽度小于0.03 n mile。基本宽度需要根据驾驶员的业务和当时海况等确定。

将船舶航行区宽度作为设计海图栅格为单位，可使生成的航行航线保证船舶航行安全。对于狭窄航道，大多采用陆标导航方法航行，选用的航行区宽度需要航道宽度大于多倍船宽即可，具体宽度值需要根据航道的弯曲度、风流等情况确定[11-12]。

1.3  网栅信息

蚁群计算法依据网栅的信息集，搜寻的最优信息作为计算数据，网栅信息主要有，坐标系、航行状态、信息源和发挥系数组成。

网栅信息结构组成：

structure information：

Longitude和latitude代表网栅的经度和纬度，当网栅设置完成，网栅的经纬度值则确定。航行状态state，可航行性为real，不然为fake。网栅的初始情形为real，在搜寻过程中，部分或全部路线受阻，航行状态state，可能由real演变成fake。

信息源ψ代表该处蚂蚁通行指数，它是蚂蚁搜寻策略的关键，各处初始值相等，当搜寻过程中扩散和惩罚发挥作用，蚂蚁经过多处数值大，经过处少则数值小[13-14]。

发挥系数Ø代表蚂蚁策略值，表示为不固定的到达目的地所需距离[15]。

1.4  搜寻方法

蚁群计算法的关键是搜寻，好的搜寻计算法，可使计算过程精准、高效，否则计算过程差错频出和迟缓。一种便捷的方法就是借鉴专家的研究成果，提高航线生成效率。

本研究依据蚁群计算中的MAX-MIN系统，一般计算法和混合算法，选用下列搜寻方法。

（1）向前搜寻方法

根据航线生成蚁群搜寻最优是关键这一思路，蚂蚁在网栅内向前运动时，有如下规则：

①向前运动前方的栅格是可行性的；

②向前运动前方栅格相比目前位置到目的地距离小；

③当向前运动网栅满足上述两条件时，如有多个选项，可用加权法随机选取。

加权法随机选取：根据蚁群搜索过程，随机选取轮盘法、最优化法随机取值范围，设定权重，再选取使用方法。这样做的优点是扩大搜寻范围，创造被选条件，减少搜寻阻断可能，最优搜寻效率高。在设定权重时，轮盘法搜寻初始取值0.9，最优化法取值0.1，从而确保搜寻范围，搜寻第二期权重值交换，提高收敛效率；蚁群搜寻过程中，轮盘法的权重为0.9-0.8×j/M，j代表迭代频次，M代表迭代总次数。

轮盘法和最优化法各自计算向前运动前方栅格的付出代价值F（g）：

式中的α、β代表常数，可控制信息源ψ和发挥系数Ø的影响范围，m代表可选的前方栅格数。

最简捷高效的方法是选取值小的栅格作为运动前方栅格；轮盘法依据前方栅格格式的代价值，选取向前运动前方栅格。

当向前运动前方栅格选取后，当前栅格选进航行路线点表；向前运动前方栅格设置为目前位置。重复上述操作，直到蚁群搜寻到目标终点。

（2）向后搜寻方法

如果蚂蚁某处的向前运动栅格全部为不可向前栅格时，须作向后搜寻过程。蚂蚁搜寻路线，如图1所示。

1.5  更新信息

更新信息是指，当每只蚂蚁搜寻结束并最终到达目的地后；一蚁群生成最优的前行运动航路后。

更新信息内容有“扩散”和“激励”。

更新信息的公式为：

（1）

式（1）中，ρ（1>ρ>0）代表控制信息增量参数，（1-ρ）ψ（e）使用网栅栅格e的信息被“扩散”，这成为对全体栅格的操作；ρ[Δψ（e）]是给予向前运动栅格的“激励”，只被允许对航路表中的栅格操作。T代表常数，T的大小表示每次激励的程度。F（e）表示通过e栅格付出的代价。

经更新信息后，没有蚂蚁出没的栅格，因为“扩散”作用，信息强度逐渐减弱，对蚂蚁的吸引力减小，蚂蚁经常出没的栅格，因为“激励”作用，信息强度逐渐增强，对蚂蚁的吸引力增大。

1.6  优选航线

优选航线是所有蚁群或一代蚁群搜寻结束后，生成的最优蚁群和最优的航行路线。

优选航行路线的标准：船舶航经的路线使之付出最小的代价。船舶航经路线付出的代价包括应对航行风险WG和经济效益的损失We。

应对船舶航行风险WG包括碍航物、海盗袭击和航道限制等。

经济效益损失We包括因绕航造成航时的延长和耗油总量的增加。本研究将经济效益损失简化为航行路程的函数：WG=DG/C。C代表船舶航行距离，DG代表系数。

碍航物导致航行船舶付出的代价：

（2）

式（2）中，DB代表系数，m代表航线上的碍航物总数，Cf代表航线距离碍航物的最小距离，CebP代表船舶航行所需的安全距离，Vc代表碍航物的半径。

航道限制导致船舶付出的代价：

（3）

式（3）中，DC代表系数，m代表航行路線转向点数，Cgfkr代表航路点水深，Ce代表航行安全水深，Cvbpk代表船舶吃水。

1.7  计划航线的处理

基于网栅栅格划分的蚁群计算法设计的船舶航行路线，呈现齿形形状，需要取直处理，才能成为真正的设计航线。

取直处理原则：

（1）船舶航行经过海区的水深须满足船舶吃水的要求，且大于船舶航行的安全水深。

（2）船舶航行经过海区船位与碍航物的距离须大于危险半径，且大于船舶航行的安全距离。

（3）航线上尽量减少转向点，且要求航程最短。

根据取直处理原则，采用以下步骤进行计划航线处理：

（1）航线的目的地设置为标准点；

（2）沿着航线从起始航点到目的地标准点逐个检查，并各转向点连成直线，然后连线向两侧扩大航行范围形成航行区带，检查航行区带是否与碍航物危险半径或不满足要求的浅水区有交汇点，如果有交集，须如下处理：记下该交汇点，以此交汇点作为标准点，重复（2）步骤，直到符合要求。

（3）设计航线的起始点和目的地终点与步骤（2）记录的交汇点处理后形成的新点的连线，就成为一条取直的计划航线。取直过程如图2所示。

2 船舶航行计划航线自动生成的蚁群计算法程序

船舶航行计划航线自动生成的蚁群计算法程序，见表3。

网栅栅格初始信息源ψ，都设置为0.5，发挥系数Ø依据网栅栅格到目的地终点距离Cj大小来确定，Øj=10/Dj j开始的可航行状态，根据电子汇图提供的水深和等深线信息资料，运用高端模型（digital、evaluation、model，DEM）对图上各点水深量进行计算，看其水深值是否符合要求，选取real还是fake。

在船舶航行计划航线自动生成进程中，在优化搜寻的前提条件下，形成多条可航行路线，从已产生的NXM条可航行路线中选取最经济最短的航行路线。

船舶航行计划航线自动生成的计算法范例，如图3所示。

根据蚁群计算法思路和程序，运用vc++6.0编程程序，使蚁群计算法船舶航行计划航线自动生成成为事实。图4为黄海北部，随意选取的船舶航线路线起始点和目的地，利用蚁群计算法自动生成的船舶航行路线范例。

海区搜寻范围为10×7 n mile，船舶航行区带设定为0.2 n mile，每群蚂蚁数设定为10，迭代总次数设定为100，图4中圆圈为设定的碍航物危险范围，利用P4 2.8G计算机运作，航线生成时间小于1 s。图4中齿形线为蚁群计算法自动生产的最初优化船舶航行路线，粗线为去之后的船舶航行计划航线。图4中最初优化航线齿形曲折，是蚁群中蚂蚁数较少导致的，增大蚁群中蚂蚁数，同时增加迭代次数，将产生最优效果。取直后的船舶航行路线和人工绘制的航行路线基本相同。

3 结束语

通过图4的范例，进一步表明蚁群计算法对于自动生成船舶航行线路具有可行性。这不仅能减轻船舶驾驶员繁重的工作，同时提高了生成船舶航行线路的效率，同时不超过1 s。这条航行线路综合考虑了影响船舶航行安全的各种因素，克服了人工绘制航行路线用时长，且常因考虑不周全导致不是最优化航行路线的难题，最大的优点是广采专家思路，在搜寻过程中体现，使生成的船舶航行路线更具专家思路，从而该航行线路最优。

参考文献

[1] 吴泽亮.基于蚁群算法的航线自动生成方法[J].舰船科学技术，2019，41（14）：43-45.

[2] 党庆一.数据驱动的舰船航线生成算法[J].舰船科学技术，2019，41（02）：7-9.

[3] 张立华，戴泽源，贾帅东.融合多幅海图的航线自动生成改进方法[J].哈尔滨工程大学学报，2019，40（06）：1090-1097.

[4] 吕锦涛，刘志强，王娜.基于航路堆栈的航线自动生成方法[J].计算机应用，2018，38（S1）：16-19.

[5] 王涛，张立华，彭认灿，曹鸿博，姜林君.顾及航道宽度的最短距离航线自动生成方法[J].海洋测绘，2016，36（03）：29-31+36.

[6] 张金水，何立居，李启华，李晓阳，吴国华.蚁群算法和遗传算法结合的航线生成[J].中国航海，2015，38（02）：9-12+17.

[7] 李启华，李晓阳，吴国华.蚁群搜索与遗传优化结合的航线自动生成[J].广州航海学院学报，2014，22（04）：11-14.

[8] 张浩，张梅彩，陈建华.最短时间航线自动生成的改进方法[J].海洋測绘，2014，34（04）：47-49+54.

[9] 张树凯，刘正江，蔡垚，史国友，梁伟珍.无人船艇航线自动生成研究现状及展望[J].中国航海，2019，42（03）：6-11.

[10] 李冉. 基于AIS数据的内河船舶习惯航线生成研究[D].大连海事大学，2019.

[11] 张海妮.基于蚁群优化算法的无人船艇航线自动生成及路径规划[J].舰船电子工程，2019，39（03）：46-49+97.

[12] 刘高磊，张锋，吕建，赵延鹏，黄富程.一种利用AIS数据挖掘的航线生成方法[J].中国水运（下半月），2018，18（12）：61-63.

[13] 马升麾. 基于AIS数据的航线生成[D].大连海事大学，2017.

[14] 王涛，张立华，彭认灿，曹鸿博，姜林君.考虑转向限制的电子海图最短距离航线自动生成方法[J].哈尔滨工程大学学报，2016，37（07）：923-929.

[15] 张浩，张梅彩，陈建华.最短时间航线自动生成的改进方法[J].海洋测绘，2014，34（04）：47-49+54.

基金项目： 1.国家重点研发计划项目（3.1）2021YFC2801000，北极航道通信导航保障技术研究与系统开发。

2.国家重点研发计划项目（4.2）2019YFB1600602，在航船舶安全风险辨识与防控平台。

作者简介：

李成海，正高级船长，副教授，主要研究方向：海上航行安，（E-mail）LICHENGHAI@163.com