优先队列回朔算法在电子航道图航路规划中的应用研究

摘 要 电子航道图中的航路规划，是船舶在长江航道中利用自然水深通畅航行的重要保证。对于不同吃水的船舶，结合船舶航行基本要素和长江航道实际情况，合理地规划出适合该船舶航行的航路具有重大的实际意义。本文采用优先队列回朔算法，兼顾全局路径和局部路径规划，实现了电子航道图航路规划功能。实验结果表明，该算法能够较快的规划出合理航道，其规划准确，运行速度快，很好的满足了航道规划的需要，具有较强的实用性。

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

1 引言

从2012年开始，长江航道局开始推广应用长江电子航道图，该电子航道图最大的特点是图上水深数据更新较快，基本反映的是实际水深，船舶可以根据自己的吃水需求进行航路选择，也就是说吃水深的船舶可以选择满足自己吃水的深水区域航行，而吃水浅的船舶可以选择吃水浅的区域航行，从而最大限度的利用自然水深，提高船舶航行经济效益。

2 航路规划问题描述

航路规划的主要任务是根据船舶吃水在长江中合理规划出航路，让船舶在长江中能够顺利航行，保证航行安全。同时，还要保证长江航路的最大通行量，提高经济效益。用集合的观点来看， 问题涉及到需求集E、资源集S、约束集C ， 最终的目标就是为E 的所有元素在集合S 中找到符合约束集C 的映射。

结合实际， 需求集就是指船舶集E ={1， 2，3，……}，其中的元素为船舶的编号，用这个编号可以提取船舶的具体信息，如船舶宽度、长度、航速、载重量等。

资源集是指长江断面集S ={1，2，3， ……}， 其中的元素为断面编号， 通过这个编号可以取出断面具体信息，包括断面各个测点的深度信息，上下断面测点深度相关信息，断面分叉情况。

硬约束包括以下几条：

（1）航路水深。规划出的航路中的水深必须大于船舶吃水，并有一定的富余量，以确保船舶能够在规划的航路中安全航行。

（2）航路宽度。保证航路宽度在船舶宽度2.0B～4.5B的范围内。船舶在长江上行驶受风向、水流影响，其航迹很难与航路平行，故船舶航行基本上是在导航中线左右摆动呈蛇行路线。典型双向航路宽度约为8 倍船宽， 单向航路宽度约为5倍船宽。

（3）船舶与航路底边间的富裕间距。为了防止船舶因为岸吸现象擦壁或搁浅，必须与河底保持一定距离。

3 航路规划算法

3.1 优先队列策略

优先队列策略借用邻近排序算法的思想， 对数据集进行排序， 根据排序的顺序， 对范围相对较小的邻近记录进行匹配比较，找出重复记录。具体策略是抽取一个或多个字段构成关键字进行排序， 然后寻找数据库中各条记录在一个长度固定的子集队列中的匹配记录。

3.2 冲突检测及回溯实现

航路规划中的冲突检测是对当前船舶航行的吃水量、航行宽度、船舶长度等信息能否在长江的各个测量断面中找到满足要求的测点，并保证上一个断面到下一个断面的弯曲度不能过大，若对应断面测点段和上下断面测点弯曲度组合已被占用， 则是有冲突， 否则可以作为备选方案。

3.3 航路规划算法步骤

航路的自动规划需要根据船舶的基本要素信息、长江的测图断面数据和水下地形情况、自动在长江电子航道图上规划出合理的航路。我们采用了优先队列回溯航路规划算法。算法步骤描述如下：

步骤1 找出各个断面的通航区域，将水深作为权值组成各个断面的优先队列T，（T[i]表示第i个断面的通航区域优先队列）。

步骤2初始化一个栈H，将前两个断面的优先队列中的队首元素入栈，即Push（H，DeQueue（T[0]）），Push（H，DeQueue（T[1]））；当前断面所处位置的下标curse=0；记录相邻三个断面所选中的通航区段的下表为i=0，j=0，k=0。

步骤3判断是否所有断面已经找到了适合通航的区段，如果已找到所有可通航区段则结束，栈H中存储的即为个同行区段。如果没有找到所有断面的通航区段，转到（4）继续执行。

步骤4判断当前搜索的断面所在下标是否小于-2。如果小于-2则在第一个断面中找寻下一个通航区段的下标，即i++，此时设置第二个断面通航下标j=0，第三个断面通航下标k=0，然后转向（5）。如果不小于-2则直接转向（5）继续执行。

步骤5根据栈H和断面通航区域优先队列T，找到当前处理的断面相邻的三个断面的通航区段下标处对应的点firstP，secondP，thirdP，判断这三个点的夹角是否满足航道的斜率要求。如果满足要求就将当前处理断面的通航区段下标入栈H记录下来，然后转向（3）继续循环。如果不满足要求就寻找当前断面的下一个通航区段，即k++。

步骤6判断当前断面的所有通航区段是否已经扫描完。扫描完的话，说明在此断面中没有找到合适的通航区域，所以需要回溯，即curse--，然后执行（7）。没有扫描完的话就转步骤3继续循环找航道。

步骤7判断curse是否已经回溯到了第一个断面之前，如果回溯到了第一个断面之前说明此航道没有通航区域，需要抬升水位重新规划航道。如果没有回溯到第一个断面之前，说明还可以继续找其他区段进行规划，此时转（3）继续执行。

4 实验效果及分析

4.1 规则河道规划效果及分析

先将原始数据导入，选择一段河道导入原始数据。然后，用户输入需要规划航路的水深、航宽以及弯曲半径，计算机自动按要求计算出一条满足要求的航道，航道初始形态是两条线，这表示两条线之间的区域是满足用户输入参数的区域。

对已经规划出的航道添加航标点，最终的航道图如图4.1所示。

对于规则河道来说，很明显由优先队列回溯算法规划出的航道是正确的，它选择的区域既满足航宽要求，而且需要挖槽的区域又是最小。

4.2 不规则河道规划效果分析

选择一条不规则的航道区域，测试算法的准确性，看自动规划出的航道和现实中的航道规划是不是大体相同。不规则航道选取如图4.2所示。

在不规则河道中根据本人的算法进行航道规划。可以看出有两条航道大体都可以通航，具体规划哪一条，要根据算法的评判进行选择。规划后的航道图如图4.3所示。

对航道进行标注，显示航标点，如图4.4所示。对于不规则河道，特别是分叉河道，人眼是很难判断具体的通航区域的。在上图4.4中，左右航道可能都是能够通航的，但是要选择哪一条航道才是最优的，就需要具体的计算，选择合适的算法将直接决定结果的准确性。

5 结语

为解决电子航道图航路规划问题，本文提出了一种优先队列回溯算法，详细描述了该算法的具体流程及核心步骤。另外使用所述算法，分别对规则河道和不规则河道进行试验，呈现实验效果，实践表明，该算法规划准确，运算快捷，较好的解决了电子航道图中的航路规划问题。

参考文献

[1]张国平.加快推进长江电子航道图建设[J].中国水运，2010（04）.

[2]GB50139-2014，内河通航标准[s].

[3]彭军，向毅.数据结构与算法[M].北京：人民邮电出版社，2013.

作者单位

1.武汉市第二十中学 湖北省武汉市430014

2.长江武汉航道局 湖北省武汉市 430014

3.长江武汉航道局航道工程处 湖北省武汉市 430014