基于改进A*算法的内河水网航线规划及应用

潘明阳 刘乙赛 李琦 李超 陈志体

摘要：为避免船舶搁浅、撞桥等事故的发生，研究针对复杂内河水网的航线规划算法及其应用模式。根据航道通航条件，设计内河水网的有向拓扑网络，并从添加航道约束条件、优化代价函数和估价函数三个方面对A *算法进行改进，实现针对不同船舶参数的最优航线规划。结合船舶助航APP研究航线规划算法的应用方法，并以东莞水系为场景进行算法测试。结果表明，改进的A *算法能够很好地应用于内河水网的航线规划，而且可在手机移动终端高效运行。研究的航线规划算法和应用模式对保障复杂水网的船舶航行安全具有重要的意义。

关键词： 内河水网; 改进A *算法; 航线规划; 船舶助航APP

中图分类号： U697.31;TP399    文献标志码： A

Abstract： To avoid accidents such as ship grounding and ship bridge collision， a route planning algorithm and its application mode for complex inland waterway network are researched. According to waterway navigation conditions， a directed topological network for inland waterway network is designed， and the A * algorithm is improved from three aspects of adding channel constraint conditions， optimizing the cost function and the valuation function to realize the optimal route planning for different ship parameters.The route planning algorithm is applied in a ship navigation-aid APP， and is tested with Dongguan waterway network as the scene. The results show that the improved A * algorithm can be well applied to the route planning of the inland waterway network， and it can run efficiently in the mobile phone terminal. The route planning algorithm and its application mode are of great significance to ensure the ship navigation safety of complex waterway network.

Key words： inland waterway network; improved A * algorithm; route planning; ship navigation-aid APP

珠江水系是一個由西江、北江、东江和珠江三角洲诸河汇聚而成的复合水系，全长2 214 km，是我国境内第三长河流。珠江水系支流众多，水道纵横交错，尤其是珠江三角洲诸河形成了稠密的水网，大小河流上百条。珠江水系的航道复杂多变，给通航船舶的航行安全带来了很大的麻烦，水系内常常发生由驾驶员不熟悉航道特点所导致的搁浅和撞桥等事故。据不完全统计，2016—2017年珠江水系内发生大大小小的撞桥事故近十起，造成了重大的经济损失和社会影响[1]。广东内河航道和海事等管理部门为改善通航环境采取了诸多措施，尤其是近年来利用信息化手段，研发了数字航道、智慧海事监管平台等系统，通过电子巡航等动态监管手段来保障航道的通航安全。然而到目前为止大多数研究是从监管的角度出发的，少有从船舶的角度出发专门研究如何合理规划航线以更好地规避航行风险的。虽然不少在内河航行的船舶已经安装了电子海图系统，但这些设备存在着数据陈旧、无法获取实时航道信息等问题，而且不具备根据最新数据进行航线规划的功能。

以往关于航线规划或设计的研究大多聚焦于海上航行，利用海图水深、航道和障碍物等数据寻找出单条可通航航线，例如：李源惠等[2]提出了一种基于动态网格模型的航线自动生成方法，该方法利用电子海图信息进行航线设计;张莉等[3]提出了一种基于电子海图的航线多尺度生成方法，实现海图航线的多尺度自动生成;范云生等[4]提出了一种基于电子海图栅格化的全局路径规划方法，用于无人水面艇的全局路径规划。与这类非连通式场景不同，内河水系不仅形成了网络结构，而且其不同航路的通航条件差异很大，因此内河水系路径规划面临着更多的水上航行约束。路径规划是人工智能领域的一个重要研究领域，用于解决可拓扑为点线网络的规划问题，在移动机器人、无人机、地图导航等领域应用广泛。路径规划算法主要有人工势场法、栅格法、遗传算法、神经网络算法和A *算法等[5]，其中A *算法以其高效的全局优化路径搜索能力，在机器人路径规划[6-7]、驾车路径规划[8-9]、层次卫星网络[10]等基于离散拓扑网络的路径规划中发挥了重要作用。然而，目前在水上导航领域关于内河水网航线自动规划的研究比较少见。

本文从为船舶服务的角度出发，根据船舶自身的条件（船舶高度、吃水等），结合航道通航条件（航道等级、水深和桥梁净空高度等），应用A *算法为船舶智能地规划出一条最优航线，并通过基于电子航道图的船舶助航APP为船舶提供助航服务，以尽可能地避免船舶搁浅、撞桥等事故。

1 应用场景

本文研究的应用场景为珠江三角洲诸河中的东莞辖区，见图1。东莞辖区位于珠江入海口，辖区内水网稠密，包括东江、东莞水道、太平水道、倒运海水道、中堂水道、麻涌水道、洪屋涡水道、大汾北水道、南丫水道、潢涌水道、寒溪河和大汾南水道等大小河流100多条，航道错综复杂，并呈网状结构。此外，东莞辖区内航道还具有如下一些特点：（1）大多为天然航道，航道等级多，河床高程和可通航净宽差异大;（2）航道直通入海，受上游季节性的丰枯水期影响以及下游海水的潮汐影响，水位变化复杂;（3）桥梁密集（例如东莞水道万江桥至石龙南桥段约18 km的航道中有9座桥梁），而且大多数桥梁由于建造年代较早（最早的是1907年完工的），其通航净空较小。

东莞辖区的航道内遍布港口、大桥和交叉口，不仅加大了船舶搁浅、撞桥等安全风险，而且容易导致船舶航线规划不合理，造成货运延误，产生经济损失。因此，如何有效地利用电子航道图、航道维护尺度和桥梁监管等数据，更好地为通航船舶服务，从而提高辖区的通航安全和效率，成为东莞航道建设与管理的当务之急。

2 航线规划算法

2.1 内河水网数据结构设计

为利用A *算法进行航线规划，对东莞辖区的水网地理数据进行了重新设计和组织。如图2（图1中虚线框的局部放大）所示，将航道拆分为一个个航段（图中的L1、L2、L3和L4），每个航段的端点（如图中的沙田游艇俱乐部、杨公洲中、南大大桥、上屯和必潭州等）除了可能是航道交叉节点外，还可能是对应着码头（如图中的乌沙洲头、南大大桥、南角围和阳南洲等）等可成为航线起止点的关键节点。此外每个航道还包含构成航段几何形状的普通转向点（如图中的W1、W2、W3、W4、W5、W6），以及在其间的桥梁（如图中的东江大桥、南大大桥）。

整个水网的数据结构见图3。图3中，节点数据表用于存放节点信息，包括节点编号、节点名称、节点类型（航道交叉点或码头）和节点位置（即经纬度坐标）等。如果节点类型为码头关键节点，可关联其相应数据表获取详细信息。航段数据表存放由两个节点组成的航段信息，包括航段编号、航段名称、起点编号、终点编号、航段等级、维护水深、维护航宽、航段长度、交通管制状态等。通过该表建立起整个水网的拓扑结构。转向点数据表按顺序存放每个航段从起点到终点的转向点信息，包括转向点编号和名称、所属航段编号、转向点的经纬度坐标等，用于绘制完整的规划航线。桥梁数据表存储桥梁基本信息，包括编号、名称、所在航段编号、净空高度、桥孔宽度、桥梁的经纬度坐标等，并通过航段编号与航段进行关联。

2.2 改进A *算法

A *算法是一种在静态网络中求解最短路径最有效的方法，它不仅利用代价函数计算从出发节点开始的代价，而且利用估价函数计算当前节点到目标的期望代价，在综合评估代价函数和估价函数后再进行全局最优的宽度优先搜索。A *算法是一种启发式算法，其估价函数能够将搜索导向目标节点，从而大大提升算法效率。然而，在蜿蜒曲折、复杂多变的内河水网中为船舶进行航线规划，并不只是简单的寻找最短路径，而是找出能保障船舶安全通航的最優航线。因此，在利用A *算法进行航线规划时，需要根据内河通航条件以及船舶的参数等具体约束对A *算法进行改进。

2.2.1 添加通航约束条件

根据船舶的吃水、船舶高度等信息，添加航道的通航约束条件，使不满足通航条件的航道不参与航线规划。增加的航道约束主要包括以下几点：

（1）水深约束：如果航段维护水深小于船舶吃水与富余水深之和，则判断该航段不满足安全通航条件。

（2）净高约束：如果航段中包含桥梁，而且只要有桥梁的净高小于船舶高度与富余高度之和，或者桥孔宽度小于船舶宽度与富余宽度之和，则判断该航段不满足安全通航条件。

（3）交通规则约束：如果航段有水上交通规则管制，而且航道的可通航方向与规划航线方向相背，则判断该航段不满足安全通航条件。

增加通航约束条件不仅满足船舶在航道安全通行的最低要求，而且能过滤不符合通航条件的航段，减少水网搜索节点个数，提高搜索效率。

2.2.2 改进A *算法的代价函数

对于在内河中行驶的船舶，最短的航线不一定是最适合的，过桥或通过相对低等级的航段都意味着风险的提升。因此，根据航道特征对经典A *算法中只计算距离的代价函数进行改进，使得节点的代价变为航段等级、途经桥梁数量和距离的加权结果，改进后的代价函数如下：g（n）=ni=1（ω1Li+ω2Bi+ω3Ci）

（1）式中：n是待扩展节点;g（n）是从出发节点到节点n的代价;下标i代表从出发节点到节点n之间的节点序号;Li代表第i个节点与前一节点间航段的等级信息，按惯例其数值越低，航段等级越高，航道维护尺度越好，越有利于船舶安全通行;Bi代表第i个节点与前一节点间所包含的桥梁数量，数量越少意味着撞桥风险越小;Ci代表第i个节点与前一节点间的实际距离;ω1、ω2和ω3分别代表航段等级、桥梁数量和距离的权重值，满足ω1+ω2+ω3=1，它们的具体数值通过不断的实验来确定。该代价函数的3项指标是同方向的作用关系，即：距离越短越好、桥梁数量越少越好、航段等级越低越好，而且它们的数值量级相差不大，避免出现权重不敏感问题。

2.2.3 改进A *算法的估价函数

2.3 基于改进A *算法的航线规划

基于上述内河水网数据结构将东莞水系的航道组织为一个搜索区域，下面以沙田游艇俱乐部与必潭洲之间的航道（见图4）为例，说明基于改进A *算法的航线规划算法。

（1）确定航线规划的起点和终点。图4a中，设A和B分别为在地图上选出的起点和终点。为在已设定的搜索区域进行路径规划，需要将A和B映射到水网中的节点，分别对应图中的“沙田游艇俱乐部”和“必潭洲”，代表在搜索区域的出发节点和目标节点。该映射过程通过距离优先法来确定。

（2）基于A *算法，创建空的Open表和Closed表。Open表记录所有在寻找最优航线时会被考虑的节点，Closed表记录已经扩展过不会再被考虑的节点。在Open表中添加起点“沙田游艇俱乐部”。

（3）从Open表弹出第一个节点，判断是否为目标节点，若是则规划结束，否则将该节点放入Closed表并进行节点扩展，即从水网中获取所有与它相邻的节点（如图4中的“乌沙洲头”“杨公洲中”等）。

（4）对新扩展出的节点进行可否通航判断。首先检索出与新节点连接的航段，根据航道属性与船舶属性添加约束条件，判断其通航属性是否有该方向上的交通管制标记，若是则将新节点放入Closed表，否则放入Open表;其次，将航段的航道尺度属性（维护水深）与船舶吃水进行比较，判断船舶是否能够安全通过该航段，若是则将新节点放入Open表，否则放入Closed表;最后，检索出该航段上所有桥梁的实时信息包括基于水位变化的净空高度和净宽，比较船舶高度与桥梁净空高度、船舶宽度与桥梁净宽，如果满足通航要求则将新节点放入Open表，否则放入Closed表。如图4b中：“沙田游艇俱乐部”与“乌沙洲头”之间的航段，由于等级太低，水深小于船舶2 m吃水，不满足通航要求，因此将节点“乌沙洲头”放入Closed表;节点“杨公洲中”满足通航条件，因此将其放入Open表。

（5）设定估价函数（见图4c）。根据改进的代价函数和估计代价函数计算Open表中每个节点的估价函数值f，f=g+h，其中：g为从起始节点到该节点的实际距离与航道等级、航道包含的桥梁数量的加权结果，加权方法见式（1）;h为从该节点到目标节点的估计距离，计算方法见式（3）。然后，对Open表中的节点按估价函数值由小到大的顺序进行排序。

（6）跳转到第3步进行循环，直到目标节点出现，找到最优航线，或者直到Open表为空，航线规划失败。航线规划结果如图4d所示。

2.4 算法效率对比分析

为验证上述航线规划算法的效率，設计经典A *算法和只添加航道约束条件的A *算法进行对比。对比测试时，对于同样的条件，随机选取20组起点和终点，分别利用3种算法进行航线规划，然后对比在利用3种算法进行航线规划的过程中搜索的节点总数、规划航线中包含的桥梁数量、规划航线中航道的等级，结果见表1。

由表1可知，对A *算法添加航道约束条件，可以使航线规划时搜索的节点总数大大减少，从而大幅度提高搜索效率。而且，如果进一步改进估价函数，优先考虑包含的桥梁数量少、平均等级高的航道，并优化启发信息，则可以在提高搜索效率的同时规划出更加合理和安全的航线。

3 智能航线规划应用

3.1 系统架构

基于上述航线规划算法，开发“东莞航道公共信息服务”船舶助航APP，进行应用和验证。如图5所示，系统包括服务器和APP客户端。服务器端运行东莞航道指挥监测系统，维护东莞航道基本数据，包括航道基础信息、电子航道图和航道水网数据，其中桥梁的实时净空和净宽数据随水位变化实时更新。为支撑航道公共信息服务，服务端还提供各类航道信息的Web Service数据接口。APP客户端基于Android开发，从服务器端的Web Service接口获取数据，并完成助航和信息服务功能。为支持离线应用，APP客户端可对电子航道图、航道水网和桥梁等基础信息进行前端缓存，当服务器端更新数据后进行下载提醒。

在规划航线时，船舶用户需要输入起点、终点、船宽、船高和吃水等参数。如果APP客户端联网，则基于服务器端最新的数据利用上述航线规划算法获取最优航线;如果APP客户端离线，则基于缓存数据进行航线规划，但由于无法获取实时桥梁净空和净宽数据，所得航线无法体现水位的影响。

3.2 APP应用效果

如图6a所示，APP具有航道图浏览、导航规划和其他信息服务功能。如图6b所示，在进行航线规划时，用户既可以从节点列表中选择起点和终点，也可以在航道图上点选，系统会自动将其映射到对应的节点。如图6c所示，规划出的航线将显示在电子航道图上，且规划航线上的桥梁标识有净空高度信息。组成航线的所有航段以表格形式展示，可显示各航段等级、水深和航宽等详细信息。一旦开始导航，系统将实时进行语音提醒，包括航向航速提醒、航道交叉口提醒、桥梁提醒等。

3.3 APP航线规划效率分析

为验证改进的A *算法在APP客户端的航线规划效率，采用3部不同配置的手机（见表2）进行测试。选取珠江水系东莞辖区的水网数据（表3）进行航线规划。

由图7可见，本文提出的航线规划算法可在主流配置的手机移动终端高效运行，即使手机的配置较低，对于东莞辖区内的任何航线规划都能在毫秒的时间量级上完成。

与传统的ECS（electronic chart system，电子海图系统）相比，船舶助航APP不仅成本低廉，而且推广和普及速度极快，可迅速地将最新航道信息提供给水域内的所有船舶并为之提供助航服务。目前船舶助航APP已经在东莞航道局辖区试运行，为该区域航行的船舶提供航道公共信息服务，取得了良好的社会反响。

4 结 论

本文针对内河水系特点，从为船舶服务的角度出发，研究了内河航线规划算法并进行了应用。研究结果表明：充分考虑航海特色对内河水网数据进行精心设计，诸如对成熟的路径规划算法——A *算法稍加改进，可以解决内河水网的航线规划问题，从而为船舶提供更智能的助航服务，避免搁浅、撞桥等事故，更好地保障船舶航行安全;改进算法能够在配置较低的手机终端上高效运行，通过APP的形式进行应用，并以最快的速度、最方便的渠道进行普及和推广。

目前，针对海上智能船舶、无人驾驶船舶已经开展了一系列的研究[11]，内河船舶的智能化和无人驾驶亦将成为后续的研究热点，航线自动规划也将是其中最为关键的技术之一。围绕智能航线规划，后续可以做的研究有：进行航线规划算法的优化以适应更大范围水域（如整个珠江水系）的应用;结合人工智能的其他技术不断完善算法的实用性和智能性，如研究潮汐和水位预测模型，结合船舶航速更准确地计算船舶航行至桥梁附近时的净空高度和宽度，从而更好地满足船舶借助潮汐进行通航的需求，或者基于AIS数据评估和预测航道拥堵情况并作为估价函数的考虑因子，以更好地满足实时性的需求。

参考文献：

[1] 余丹亚.偶发的船撞桥事件背后的必然性分析[J].珠江水运， 2018（5）： 101-103. DOI： 10.14125/j.cnki.zjsy.2018.05.051.

[2] 李源惠， 潘明阳， 吴娴.基于动态网格模型的航线自动生成算法[J].交通运输工程学报， 2007， 7（3）： 34-39.

[3] 张莉， 金一丞， 汪柱， 等.电子海图的航线多尺度生成方法[J].测绘科学， 2011， 36（5）： 197-199. DOI： 10.16251/j.cnki.1009-2307.2011.05.022.

[4] 范云生， 赵永生， 石林龙， 等.基于电子海图栅格化的无人水面艇全局路径规划[J].中国航海， 2017， 40（1）： 47-52， 113.

[5] 张广林， 胡小梅， 柴剑飞， 等.路径规划算法及其应用综述[J].现代机械， 2011（5）： 85-90. DOI： 10.13667/j.cnki.52-1046/th.2011.05.014.

[6] GURUJIA K， AGARWAL H， PARSEDIYA D K. Time-efficient A * algorithm for robot path planning[J]. Procedia Technology， 2016， 23： 144-149.DOI： 10.1016/j.protcy.2016.03.010.

[7] FERNANDES E， COSTA P， LIMA J. Towards an orientation enhanced Astar algorithm for robotic navigation[C]//2015 IEEE International Conference on Industrial Technology （ICIT）， Seville， Spain， 2015： 3320-3325. DOI： 10.1109/ICIT.2015.7125590.

[8] PAN Hu， GUO Chen， WANG Zhaodong. Research for path planning based on improved Astar algorithm[C]// 2017 4th International Conference on Information， Cybernetics and Computational Social Systems （ICCSS）， Dalian， China， 2017： 225-230. DOI： 10.1109/ICCSS.2017.8091416.

[9] CHENG Liping， LIU Chuanxi，YAN Bo. Improved hierarchical A-star algorithm for optimal parking path planning of the large parking lot[C]//Proceeding of the IEEE International Conference on Information and Automation， Hulunbeier， China， 2014： 695-698. DOI： 10.1109/ICInfA.2014.6932742.

[10] JI Xuezhi， LIU Lixiang， ZHAO Pei， et al. A-star algorithm based on-demand routing protocol for hierarchical LEO/MEO satellite networks[C]//2015 IEEE International Congference on Big Data， Santa Clara， USA， 2015： 1545-1549. DOI： 10.1109/BigData.2015.7363918.

[11] 高宗江， 張英俊， 孙培廷， 等.无人驾驶船舶研究综述[J].大连海事大学学报， 2017， 43（2）： 1-7. DOI： 10.16411/j.cnki.issn1006-7736.2017.02.001.

（编辑 贾裙平）