1前言
长期以来，航线设计基本依靠人工分析静态海图，手工查询或凭经验评估水文、气象情况，从而拟定计划航线，这种传统的航线设计方法存在工作效率低、设计质量依赖于作业人员业务水平和工作态度等局限。为此，近年来，利用计算机的自动解算功能，探索船舶航线的最优化问题引起了国内外众多学者的关注。
现有的最优化方法可以归纳为4类:
①基于栅格海图的迷宫改进算法，但这类算法只基于并不常用的栅格电子海图，而且只对较为理想的情形进行了研究;
②气象定线方法，这种方法分析了潮流、风浪等信息的影响，研究了航时最短的问题。但这种方法仅分析了碍航物较少、航行环境相对简单的远海区域;
③基于已知航路点库的航线网络方，航线网络方法需要以一个已知的航路点库为基础，而实际中并不一定任何海区都事先建有合理的航路点库，更重要的是并非只有这些航路点之间可以航行;
④自动生成方法，李源惠等基于动态网格模型实现了航线自动生成;张立华先基于方位相差最小和航段最大等准则，建立了自动绕行碍航区的机制，提出了电子海图平台下最优航线的自动生成算法，然后通过揭示航段与碍航区空间关系的规律，将自动生成方法进一步拓展到某些特殊情形。这种方法在航线质量和自动化作业程度上都有了很大的提高。但仍没对大计算量的复杂航行环境进行研究，也只考虑了海图距离最短这一指标。
航线最优化方法主要是针对较为理想的情形进行了分析，适用范围有限。因此，有必要进一步改进电子海图上最优航线自动生成算法。本文进行了航线自动生成方法的二叉树构建，从转向角度、转向次数、最小航段三个方面探讨了可操作性质量评价指标的构建，最后提出了最短距离航线算法与最短时间航线算法相结合的方法。
2航线自动生成方法的航路二叉树构建
对于绕行碍航区的最短路径搜索算法研究，陈传波等利用所要绕行的碍航区的顶点与测试线(当前点与目的点的连线)距离最小原则进行优选;张立华则提出了最小夹角等原则进行最短路径搜索。上述“贪婪”方法(在当前情况的判断下进行优选，而舍弃另外一条路径，并没有考虑对后续情况的影响)虽然在大多数情况下是最优的，特别适用于碍航区比较少的海区。但是，当碍航区很多时，上述方法的贪婪性就更加明显，可能导致所优选的结果偏离实际最优。这样，需要进行多路径优化。
多路径优化:在航线生成过程中，当遇到新碍航物时，分别记录两条相切的可能性路径。如图1中在点S遇到新碍航物O1，需要同时建立两条路径SP1和SP3，分别沿碍航物O1绕行。但遇到新碍航物O2，又需重新从原来的两条路径各建立两条路径，从P2分别到P7和P8，从P4分别到P7和P8，这样形成四条路径。不断循环，直到与D可视，当有n个航行碍航物时，需要建立最多2n条路径，最后从中选取最短者为最后结果。
利用航线自动生成方法的二叉树构建进行多路径优化，可以避免贪婪算法的失真。因为在进行多路径优化过程中，每当遇到新碍航物时，需建立两条路径。这样，当航线搜索完毕时，航线几何形状如同一颗复杂的二叉树，并把它定义为航路二叉树。如图2，S为起始点(也即航路二叉树的父结点)，M为目的点，A、B…等为航路二叉树的中间结点。
关键步骤:①采用分块存储方法(存储子二叉树)进行数据存储;②采取一定的原则进行航线提取;③对比航线
图3为航路二叉树方法与航路“贪婪”方法的对比实验。图上折线显示了采用不同方法自动生成的最短距离航线。的航程，优选出最短路径。
在图3中，(b)中的航线显然短于(a)中的航线。根据实验效果可知，在某些特殊情况下，航路二叉树方法相对于航路“贪婪”方法更具合理性。
3可操作性质量评价指标的构建
航线设计过程中，不仅要重点考虑安全性、经济性，而且也要顾及船舶的可操作性。本文主要从转向角度、转向次数、最小航段三个方面探讨可操作性质量评价指标的构建。
基于上文叙述的航路二叉树构建的结果，选取优选的航线若干条，一般给出三条。然后可根据转向角、转向次数、最小航段指标依次进行优选。最后，给出综合评判指标，推荐一条最优航线。综合评判指标:需要提供上述三个指标的权值，一般由用户确定。
当得到综合评判指标之后，计算各航线在这个指标下的可信度，对比可信度，选择可信度最高的一条航线作为推荐的最优航线。
综合评判指标函数:
f=ax+by+cz(x+y+z=1)
式中，a为某航线转向角指标超标的指数;b为某航线转向次数;c为某航线最小航段指标超标的指数;x为转向角指标;y为转向次数指标;z为最小航段指标;可信度:r=1f。
本文对综合评判方法与最短距离方法进行了一定的对比。图4(a)中航线转向次数较多，而且有一个转向角过大，给舰船转向带来不便。而图4(b)中航线转向次数少，不存在过大转向角的情形，有利于舰船的操纵，能够避免大角度转向等不利舰船操纵的情况所带来的负面影响，显得更为合理。
4最短距离航线算法与最短时间航线算法的结合
船舶最短时间航线计算方法研究是船舶气象定线技术中的一个十分重要的课题。得到船舶最短时间航线通常有等时线法和动态规划法。
(1)等时线法
等时线法又叫作图法。它是利用天气预报图、波浪预报图和船舶失速图等，在航路图或航线选择专用图(空白海图)上，用作图比较方法选择气象航线。这种作图方法采用了球心投影底图，在这种图上大圆航线为直线，即两点间的最短距离连线为直线。那么，就可以以终点为圆心作弧与最近等时线相切，切点就是与终点距离最近的点。再以该点为圆心作弧与它的最近等时线相切，又得到一个新切点，以此类推，得到所有切点。连接所有切点和起始点、终点即为最短时间航线。
(2)动态规划法
动态规划法应用于船舶气象导航，就是在得到整个航行时间内的波浪场和海流场的预报条件下，找出出发点到终点航行时间最少的航向和航线。这种方法是解一组含有确定函数的船舶运动微分方程式。该函数满足航行时间最少条件。这种方法的基本特点:将求解整个航线的航时最少的一个复杂问题化成多个分段求解的简单问题。
上述求取船舶最短时间航线方法，充分考虑了航行区域的气象条件，从而优化使得航时最短，但是仅分析了碍航物较少、航行环境相对简单的远海区域，没有考虑水位变化的影响。在近岸航行时，碍航物较多，而且水深变化大，从而需要对其改进。
本文提出采用最短距离航线算法与最短时间航线算法相结合的方法，充分考虑避开碍航区，使最短时间航线在近岸多碍航物的情况下达到实用的程度。
①假设船舶的最大航速为Vmax，气象预报间隔为m，以起始点为圆心、(m×Vmax)为半径作圆弧与布设的辐射线相交。那么就可以以起始点和各相交点的连线作为航线测试线，从而可以根据最短距离航线算法得到各个区域的最短距离航线。根据波浪预报、船舶失速图，得到沿各最短距离航线航行m时间后的航路点sn(n=1，2，3…)。用曲线连接这些航路点，得到等时线。
②在最短距离航线的各航段中，特别是航程比较远的航段，考虑气象条件的影响，根据合理的预报间隔布设等时线，进行最短时间航线求解。
单独考虑距离或者时间因素的最短航线，会损失另一方面的优化程度。但将两方面结合起来进行航线优选，不仅航程相对较短，而且顾及到了水文气象等因素的影响使得航时有所缩短，进而得到更合理和实用的航线。
5结束语
改进电子海图上最优航线自动生成算法具有重要意义。根据对比实验效果，航路二叉树构建方法，可以进一步提高航线自动生成结果的质量;可操作性质量评价指标的构建，在航线可操作性方面有所改进，更能满足用户在可操作性上的需求;最短距离航线算法与最短时间航线算法相结合的方法，充分考虑和结合了两算法的优点，可以得到更实用的航线。当然本文只是对改进算法的一种初探，如何设计更合理、高效的算法，将是下一步研究的重点
