基于优先队列回溯算法的电子航道图航路规划设计

马志云 施俊羽

摘 要：电子航道图航路规划是指长江航道中的船舶利用自然水深航行，对于不吃水船舶要结合航道实际情况和船舶航行基础，对航路进行合理规划。本文利用优先队列回溯算法，设计电子航道图航路规划。从实验结果可以看出，此算法能够对航道进行快速、精准、合理的规划，运行速度快，航道规划需求得到满足，具有较强实用性。

关键词：优先队列回朔算法;电子航道图;航路规划

中图分类号：U612.2           文献标识码：A            文章编号：1006—7973（2021）03-0072-03

航运作为国民经济基础产业，在服务性行业和综合运输体系中具有重要地位，其占地少、能耗比较小、成本低、运能比较大，促进了航运的发展。在科学技术和信息技术不断发展的过程中，航运以数字航运、智能航运作为主要发展目标。在大型化、信息化船舶数量的现代航运技术不断发展和使用的过程中，电子航道要求权威、精准、丰富的支持。所以，为了促进航运发展，满足社会需求，要求实现电子航道图航路的规划设计[1]。

1航道规划中的问题

航路规划目的就是以船舶在长江中的吃水进行航路的合理规划，使船舶在长江中能够顺利航行，并且对长江航道最大通行量进行保证，提高经济效益。通过几何观点分析，问题主要包括：C指约束集，S指资源集，E指需求集，最终目标为需求集中全部元素处于集合S中，从而使映射满足约束集[2]。

结合实际情况，需求集是指船舶集E={1，2，3，....}，通过此编号能够实现传播具体信息的提取，比如传播长度、宽度、载重量、航速等。

资源集指的是长江断面集S={1，2，3，...}，元素指的是断面编号，从而得到断面基本信息，包括断面分叉、断面测点深度等信息。主要硬约束包括：

其一，航路水深。在航路水深规划过程中，要求大于船舶吃水，确定在规划航路中船舶能够安全的运行;

其二，航路宽度。使航路宽度设置为船舶宽度的2.0B-4.5B，在行驶过程中，船舶会受到水流、风向的影响，轨迹无法平行与航路，那么导航中的船舶左右摆动;

其三，航路底边和船舶富裕间距。为了避免由于岸吸导致船舶存在搁浅的问题，要求保此河底一定的距离[3]。

2航路规划算法

2.1优先队列

优先队列指的是以临近排序思想作为基础，实现数据集排序，对比小范围记录，将重复记录精准提取。通过所抽取的字段实现关键字创建，之后排序，并且寻找数据库中固定范围中队列匹配记录[4]。

2.2创建环境模型

在规划航路前，要先在内部世界模型中实现环境障碍物表示模型的创建，使规划航路时搜索量得到降低。现代国内外对环境建模方法进行研究，包括拓扑图法、可视图法、单元数法等，本文使用栅格法实现建模。此方法主要原理就是使船舶工作空间划分多个小栅格，每个小栅格接近周围栅格，创建栅格地图。内河水域通航环境对比海洋环境，影响因素比较复杂[5]。所以，利用优化队列回溯算法规划全局路径，通过电子航道图得出船舶工作过程中环境信息，通过栅格对船舶工作空间进行划分，创建栅格地图，使船舶运动轨迹与环境中信息在栅格地图中进行存储，包括不完全可行、完全不可行、完全可行的栅格。先使不完全可行栅格在完全不可行栅格中创建，障碍栅格为安全可行栅格，表示为涂黑的方块。船舶起始位置栅格值得就是起始栅格和船舶目标位置栅格，最后对栅格环境编号进行划分[6]。

模型创建后进行存储，利用行列划分矩阵存储的方法实现栅格存储，创建数组与栅格的关系，图1为栅格环境模型。对建模复杂性进行考虑，使船舶在栅格运行过程中定义八种，详见图2。电子航道图能够提供给船舶全局环境的信息来源，通过以上创建的环境模型，对电子航道图进行栅格化，使电子航道划分的栅格具有相同的大小，利用栅格地图标记值存储环境信息[7]。

2.3算法描述

利用节点到目标节点的初始节点最小代价途径估计模型表示为：

公式中的g（n）指的是前个节点到目前节点需要的代价和，m（n）为前个节点在目前节点运动所花费的代价，h（n）为实际环境节点n到目标节点的曼哈顿距离，（xn，yn）指的是节点n坐标值，（xgoal，ygoal）指的是目标节点坐标值。

3实验效果和分析

先导入原始数据，用户要输入航道水深、航宽、弯曲半径，计算机以实际需求计算航道，使用户输入参数得到满足。使航标点在已经规划航道中添加，对规划河道利用优先队列回溯算法正确规划航道，满足航道宽度需求，并且能够缩小挖凿区域。

另外，针对不规则航道区域，对测试算法精准性进行分析，观察自动规划与实际规划的航道是否相同。在不规则河道中，通过本算法规划。两条航道通航，通过算法对使用哪一条进行选择。标注航道，将航标点进行显示。针对不规则河道，尤其是分叉河道，人为观察是无法对具体通航区域进行判断的。通過本文算法，左右航道都能够通航，但是要利用具体计算选择哪条航道最优，选择合适算法与结果精准性具有密切关系，图3为航道规划的环境模型。

4电子航海图规划的建议

我国内河电子航道图规划现状会影响到我国内河航运的发展，为了促进我国内河航运健康发展，针对电子航海图规划提出以下建议：

其一，统筹规划。目前，缺乏电子航海图航路规划的统一规划，在技术方面并没有政策支持，生产力量分散，缺乏完善管理。所以，要创建强有力协调领导小组，使管理与规划得到加强。与我国内河航运具体情况结合，实现满足航路规划发展、使用和发布的标准制定;

其二，创建资源整合平台。以我国目前电子航道图自成体系情况，创建电子航道图生产与服务平台，从而实现资源共享，统一发布信息。不仅能够避免资源浪费与重复开发，还能够强化管理，提高对外服务能力;

其三，加強合作。对电子航道图航路规划的标准进行研发与制定，与国际区域之间的合作得到加强，积极地参与到国际内河电子航道图协调小组相应会议中，并且及时掌握电子航道图的发展，有效促进我国航路规划的发展[8]。

5结束语

目前，我国内河航运在不断的发展，但是因为内河航运发展比较晚，相应的标准研发也比较晚。所以，就要针对我国内河航运的问题与国内内河航运具体情况，使用智能化航运和电子化航运，设计电子航道图航路规划，对相应的标准进行完善，促进我国内河航运快速健康的发展。

参考文献：

[1]王兰， 张龙信， 满君丰，等. 异构计算环境下基于优先队列划分的调度算法[J]. 小型微型计算机系统， 2020， 041（002）：303-309.

[2]杨传印， 黄玮， 薛少聪，等. 基于优先队列的时变网络最短路径算法[J]. 计算机应用研究， 2019， 36（05）：129-134.

[3]易黎. 一种基于给定目标节点的个性化PageRank算法设计[J]. 计算技术与自动化， 2020， 039（001）：101-105.

[4]陈志轩. 工业无线网络TSN实时优先队列调度算法研究[J]. 软件工程与应用， 2019， 8（6）：8.

[5]万平. 基于A-star算法的航路规划算法设计与仿真研究[J]. 中国水运.航道科技， 2018， 000（004）：P.58-65.

[6]胡阳， 张谧， 王玲，等. 人工智能用于船舶航线优化的有效方案[J]. 科技创新导报， 2019， v.16;No.503（35）：143+145.

[7] Lu Xuan Xuan， Zhao Rui， Zhao Zhiming， et al. Research and Application of Optimization of Electronic Channel Map Making Based on Maritime Charting [J]. China Water Transport （first half month），2018000（010）：32-35.

[8] Xu Ning， Zhao Zhiming， Lu Xuanxuan， et al. J]. on Construction of Electronic Navigation Map and Safety Management Platform for Inland Waterways Henan Science and Technology ，2019000（010）：24-26.