目前，每年约70亿吨的货物(约占全球贸易总量的90%)通过海洋运输，船舶租金和燃料等成本每天累积成千上万美元^[1]，航线安全和高效的重要性不言而喻。从文献^{[2, 3, 4, 5]}可以看出，航程规划一直是近20年来海洋运输的研究热点。

根据环境信息和船舶状况，航程规划可分为静态规划和动态规划两类^[6]。静态规划主要是基于已知的海域港口、地形和水深等信息，以避让静态碍航物与实现最短航线设计为目标。典型算法包括基于网格数据的邻域二分查找方法^[7]、惩罚算法^[8]、迷宫算法^[9]，基于矢量数据和空间几何解析^[10]的航路二叉树^[11]及递归改进搜索算法^[12]、遗传算法^[13]，基于已知经验航线网络的A^*算法^[14]、Dijkstra算法^[15]等。环境不变性是静态规划的前提假设，故前述研究仅限于起航前的计划航线搜索及优化。动态规划则需要考虑水文气象、突发事件等环境综合因素进行最优航线设计。但综合分析动态规划相关的随机动态网络规划方法^[16]、船舶失速数值方法^[17]以及基于滚动时域的启发式遗传搜索算法^[18]等典型方法可知，环境因素及其动态变化产生的碍航特征并未得到系统分析，且实际航行中对计划航线进行动态修正和决策的场景研究也较少见。

安全性、可达性和经济性是航程计划制定时需要综合考虑的要素。本文通过将经验航线与海域实时动态环境信息叠加，构建包含时序禁航信息的动态通达网络模型，在此基础上考虑航速、油耗等船舶航行能力约束，按照“优度递减”的策略设计一种海域环境变化情景下的最优航程动态规划方法，为航船舶的续航、改航和停靠等后续航程计划的制定提供决策支持。 1 动态通达网络模型 1.1 动态通达网络定义

动态通达网络是在由港口集、经验航线集构建的静态网络基础上，叠加海域中灾害性天气和管制等海域限制因素对局部航线的通行影响，拓扑重构得到的弧段具有动态通达特征的一种网络模型。动态通达网络G(V,E)的要素定义如下：

1) 网络结点集V。V中的网络结点v_i是港口集H[港口编号]、航线集L自身的交点集K[航线编号₁,航线编号₂]、航线集L与碍航区O的交点集B[碍航区编号]等三类点集的并集，其属性项定义为v_i[结点编号,类型编码,港口编号,航线编号₁,航线编号₂,碍航区编号,影响碍航区序列]。其中，根据结点来源，类型编码分别用“H”、“K”和“B”区分，影响碍航区序列则以“,”为分隔符存储多个包含结点的碍航区编号，其他属性项内容则分别与3类点集的对应属性项内容一致。

2) 网络弧段集E。E中的网络弧段e_i是航线集L[航线编号]中航线被结点集合K、B分割后生成的航线段，其属性项定义为e_i[弧段编号,结点编号₁,结点编号₂,航线编号,弧段长度,禁航时段序列]。其中，结点编号₁和结点编号₂分别存储弧段端点对应的结点编号；航线编号则与弧段所在航线的对应属性一致；禁航时段序列采用分隔符“;”将多个碍航区的分段影响时间信息连接成一维序列化字符串存储，而单个禁航时段的具体格式为“(序号,碍航区编号,禁航开始时间,禁航结束时间)”。

由定义可知，动态通达网络模型实现了空间拓扑及环境影响等多源信息的网络集成，除了具备静态网络中的结点-弧段拓扑关系外，网络结点来源具有多样性，网络弧段通达具有动态性。这使得本文研究的航程决策分析区别于传统静态航线网络分析。 1.2 碍航区多边形提取

碍航区指对船舶安全通行产生影响而需要避离的障碍区域，其动态变化是导致航线通达性改变的主要因素。根据碍航区是否具有空间移动性，将其分为静止碍航区和移动碍航区。

1) 静止碍航区。根据出现时间的持续性，静止碍航区分为临时性和永久性两类。前者如军事禁航区、季节性渔场、能见度管制等，后者如岛礁、浅滩、沉船等。提取这些区域边界的特征点地理坐标，生成静止碍航区多边形集合 O_s={o_i^s,1≤i≤m}。m为静止碍航区个数，o_i^s的生存周期为[t_t^k,t^k_e]。

2) 移动碍航区。台风等极端天气在空间上沿可预测方向以一定的作用半径移动，进而形成移动碍航区O_D={o^D_k,1≤k≤n}(n为碍航区中心个数)。移动碍航区的描述参数包括初始时刻中心坐标(φ_k,λ_k)、影响半径r_k、移向C_k、移速v_k，其在时段[t^s_k,t_k^e] 的空间影响范围可以通过移动轨迹缓冲带计算得到的多边形来表示。

1.3 动态通达网络建立

动态通达网络的实时构建是快速、有效整合航程规划所需信息的基础算法，是将碍航区与静态航线网络叠加，确定航线禁止航行时间段的过程，具体如图 1所示。

图 1 动态通达网络的建立流程Fig. 1 Building Processes of Dynamic Access Network

图选项

动态通达网络建立包括4个技术环节：(1)静态网络构建。将港口间所有航线进行相交运算得到交点集 K和航线段集合L₁，与港口集H一起构建静态网络。(2)碍航区分割航线。将静态碍航区和动态碍航区的多边形与航线段集合L₁进行叠加，对如下两种情况分别进行处理：① 多边形包含航线段：将对应碍航区的[碍航区编号]直接添加到航线段端点的属性项[影响碍航区序列]中；② 多边形与航线段相交：生成交点集B和打断相交航线，航线段集合L₁变为L₂，将对应碍航区的[碍航区编号]直接赋予交点的[碍航区编号]并同时将其添加到多边形包含的航线段端点属性项[影响碍航区序列]中。(3)航线网络拓扑重构。将三类点集H、K和B合并生成网络结点集V，将航线段集合L₂作为网络弧段集E，搜寻网络弧段e_i起始、终止结点的[结点编号]分别存入属性项[结点编号₁]和[结点编号₂]中，实现网络拓扑的构建。(4)弧段禁航时序提取。根据弧段[结点编号₁]和[结点编号₂]在V中检索对应结点，提取结点的[影响碍航区序列]。当同一碍航区编号在起始和终止结点的[影响碍航区序列]中都出现时，表明该航线段受到碍航区影响。当影响碍航区为静态时，在该弧段的[禁航时段序列]中添加一个根据碍航区编号和其生存周期[t^s_k,t_k^e]生成的禁航时段。当影响碍航区为动态时，则需要考虑其预报的移动特性计算影响弧段的禁航时段。

如图 2所示，以碍航区轨迹线上的点 (φ_k,λ_k)为中心，r_k为影响半径做缓冲区C，分别计算C与弧段进入相切的时间t_s(图 2(a))和离开相切的时间t_e(图 2(c))，向该弧段[禁航时段序列]中添加时间段为[t_s,t_e]的禁航时段。

图 2 移动碍航区影响弧段的禁航时段Fig. 2 Time Segment of Sailing Prohibited by the Influence of Mobile Obstacle

图选项

局部海域变化情景下的航程规划的实质是按照一定的约束准则在动态通达网络G(V,E)中开展路径寻优，并设计4类优度逐级递减的航程规划方案判别的算法过程。

1) 规划参数的初始化。除了需要按§1中 方法构建动态通达网络 G(V,E)外，还需要以下 规划参数：① 计划航线L_p即G(V,E)中连接出发港h_s和目的港h_t的路径；② 决策时点，为获取气象信息进行决策分析的时点t₀，对应时点船的空间位置P₀；③ 舰船性能参数，主要指船舶的续航能力：假设船舶油储备量为Q，以经济航速V航行的单位油耗为F(V)，则续航能力A=Q/F(V)。

2) 三种约束准则建立。为实现航程安全性、可达性和经济性，航线规划需遵循三个准则。(1) 航线通达准则：保证船舶到达新规划航线中每个航段的起始端点时，航段都是通畅的；(2)续航约束准则：新规划航线总长度不得超过舰船的续航能力；(3)航线择优准则：新规划航线应是所有可选航线中最短的。

3) 优度递减决策过程。沿计划航线继续前行(续航)、选择新的最短绕行航线(改航)、选择最佳邻港进行停靠搜索(停靠)或原地等待救援是4类优度递减的船舶应对极端天气的决策策略。最优航程规划的决策过程遵循“择优不成则退而求其次”的原则进行。

具体技术流程如图 3所示。

图 3 最优航程规划的技术流程图Fig. 3 Technology Flowchart for Optimal Voyage Planning

图选项

如图 3所示，最优航程规划流程中总共包括航程通达性的判断算法、航线改变局部绕行算法、最短绕行航线搜索算法和最佳停靠邻港搜索算法等4个算法。 2.2.1 航程通达性的判断算法

航程通达性判断是确定船舶经过航线上任一弧段时，航行是否受到碍航区影响的过程，这是决定后续航程是否需要调整的重要依据。具体方法如下：(1)设拟航行航线的航线段序列为 E_k{e₁,e₂,…,e_k}，初始化e_i通达性指示变量flag_i=0；(2)设当前船位为P₀，航速为V，决策转向时间为t₀，计算当前船位P₀沿航线到航线段e_i起点的累计距离D_i，则船舶到达时间为t₁= t₀+ D_i/V；(3)设航线弧段e_i的长度为d_i，则船舶离开航线段终点的时间t₂= t₁ +d_i/V，确定航线段e_i的拟通行时段T_i[t₁,t₂]；(4)提取航线段e_i的[禁航时段序列]，分段解析获取禁航时间段序列F{F₁,F ₂,…,F _t}，循环判断T_i与F_i的时间区间是否相交，如果相交，则令flag_i=1；(5)对航线所有航线段进行步骤(2)~(4)的计算判断，并对所有flag_i值(1≤i)求并，若结果为1，航程不通达，反之,通达。

航线改变局部绕行算法是要在避开碍航区O的情况下，获取船舶位置P₀的多条邻近航线，并确定邻近航线上距离P₀最近的点构成转向点集合S。参照文献^[10]思想，设计算法如下：(1)以当前位置P₀为中心，选取一个较小的半径做缓冲区，获取邻近航线段集合L_k{l₁,l₂,…,l_k}；(2)在邻近航线段l_i上取P₀的最近点P₁，以连线P₀P₁作为可航渡的测试线；(3)如果连线 P₀P₁与O中碍航区均不相交，则船舶可以直接通过P₀P₁绕行到航线段l_i上；否则，在距P₀最近的碍航区o_m的边界上寻找一个点P_t，使P₀P₁与P₀P_t之间的方位差最大，由P_t替代P₀，递归进行步骤(3)，直到P₀P₁之间不存在碍航区；(4)记录所有邻近航线上距离P₀最近的点P_1i到S中，为最短绕行航线搜索算法提供基础数据。

最短绕行航线搜索算法主要是在§2.2.2局部绕行计算结果的基础上，求解船舶位置P₀到目的港h_t的最短可通达航线。具体方法如下。

1) 对任一航线转向点P_1i，在动态通达网络G(V,E)上采用图论中深度优先遍历算法(DFS)^[19]，搜索P_1i至目的港h_t的所有路径，按照§2.2.1算法对所有路径进行通达性判断，形成可连通的路径集合R_i。

2) 在集合R_i中检索长度最短的路径，将路径长度与§2.2.2中计算得到的对应P₀P_1i长度相加，得到P₀-P_1i-h_t的最短航线距离。

3) 对集合S{P₁₁,P₁₂,…,P_1k}中所有邻近航线转向点都按照步骤(1)~(2)计算，得到P₀- P_1i -h_t的最短航线距离，建立最短航线集合SL，从中找出最短者为船舶位置P₀到目的港h_t的最短可通达航线S_l。

4) 比较S_l航线长度d与船舶续航能力A。如果dl包含的绕行航段P₀P_1i和最短路径的航线段集合，执行绕行策略；如果d>A，表明续航能力不足，需在中途选择港口停靠补给。

最佳停靠邻港搜索算法在续航能力不足绕行失败的情况下执行，目的在于确定一个最佳停靠港口供船舶增加补给，以保证船舶有足够的续航能力沿绕行航线到达目的港。一般基于两个原则进行邻港的搜索：(1)宽度搜索优先原则：分别在§2.2.3的最短航程集合S_e中每一条路径上，搜寻距离船舶位置 P₀最近的网络结点(类型编码=“H”)；(2)深度搜索优先原则：在§2.2.3的最短可通达航线S_l上，搜寻距离船舶位置P₀最近的网络结点(类型编码=“H”)。 2.3 方法实现

采用ESRI的Personal GeoDatabase存储本文涉及的底图、静态网络、碍航区、动态通达网络等数据，并使用ArcMap建立工程OVPS.mxd进行数据组织。利用C#和ArcObjects开发组件DANM.dll实现本文研究的规划算法，并在ArcMap中打开OVPS.mxd和加载DANM.dll执行规划方法的实验。 3 实验与分析 3.1 场景模拟

1) 静态航线网络。本文以东南亚海域为例，根据大洋航路图、航路设计图等资料选取香港( h₁)、马尼拉(h₂)、胡志明(h₃)、哥打基纳巴卢(h₄)、文莱(h₅)、诗巫(h₆)、古晋(h₇)、新加坡(h₈)8个主要港口和连接港口的15条已知经验航线。其中，航线l(h₁,h₄)与l(h₂,h₃)、l(h₃,h₆)与l(h₄,h₈)、l(h₃,h₇)与l(h₄,h₈)_、l(h₃,h₇)与l(h₆,h₈)分别相交于k₁、k₂、k₃、k₄。构建的静态航线网络(见图 4(a))包括网络结点12个(H类8个和K类4个)、网络弧段23条，拓扑信息如表 1所示。

图 4 船舶航程规划的场景数据及规划结果Fig. 4 Scene Data and Results of Ship Voyage Planning

图选项

2) 碍航区域数据。以2013年菲律宾西部海域苏禄海海面生成的台风“清松”为例，参数为：1月3日20时，台风中心位置(9.1°N,119.5°E)；预计1月7日20时，台风中心位置(6.2°N,108.1°E)，根据航迹计算公式推算得到台风未来96 h的移动方向 C为 75 °SW、平均移速v为18.8 km/h，7级风圈半径约为120 km(见图 4(b))。

3) 动态通达网络。按§1所述方法将台风运动轨迹带与静态航线网络叠加，得到包含20个网络结点(H类8个、K类4个、B类8个)、31条网络弧段(4条受碍航区影响)的动态通达网络(见图 4(b))，拓扑信息如表 2所示。

表 2 动态通达网络的弧段拓扑信息Tab. 2 Arc Topological Information of Dynamic Access Network

表选项

4) 舰船计划航线。某船从新加坡( h₈)至香港(h₁)，计划航线由弧段e₃₀、e₂₀、e₁₉、e₆、e₅、e₄、e₁₄ 顺次连接而成。航速35 km/h，单位油耗2.491 7 t/h，续航能力A为2 500 km(见图 4(a))。

5) 决策时点与需求。以船舶接收到台风预报信息的时间1月3日08:00为决策时点，对应的决策船舶位置为P₀(见图 4(b))，现需要基于前述数据信息对船舶未来航程进行规划。 3.2 规划结果

1) 计划航线通达判断。计划航线上弧段 e₅(b4 b3)受台风影响，禁航时段为(201301041020,201301042206)，从P₀至b4、b3 的航线长度分别为1 010.524 8 km、1 248.641 6 km；船舶从P耗₀航至b4、b3时分别为28 h 43 min、35 h 29 min，在e₅拟通行时段为(201301041242,201301041929)。对比禁航和通行时段，可知时间重叠。据§2.2.1算法知该计划航线受台风影响不可通行。

2) 最短绕行航线搜索。按照§2.2.2算法，在P₀点以半径150 km搜索得到邻近航 线L_k{e₁₈,e₃₀}并确定对应转向点集合S{ P₀,P₁}。按照§2.2.3算法，对P₀至目标港口h₁的100条连通航线进行通达性判断，获取59条通达航线中最短的航线A：P₀-k₃-h₃-h₁(见图 4(c))；对P₁点至目标港口h₁的122条连通航线进行通达性判断，选取88条通达航线中最短的航线B：P₁-k₄-k₃-h₃-h₁(见图 4(d))。将两条最短航线加入最短绕行航线集S_e，比较长度得到最佳绕行航线为P₀-k₃-h₃-h₁(表 3)，绕行长度为2 443.57 km。

3) 最佳停靠邻港搜索。船舶满载续航能力2 500 km，在h₈P₀段已航行414.4 km，而上一步计算的最佳绕行航线长2 443.57 km，大于剩余续航能力2 085.6 km，因此应考虑选择合适邻港停靠增加补给。由§2.2.4算法，按照深度优先原则在最佳绕行航线P₀-k₃-h₃-h₁上搜索距离P₀最近的港口为h₃，得到P₀-k₃-h₃长度为1 275.16 km，满足船舶的续航能力。因此，该船应执行停靠h₃增加补给后续航到达h/₁的方案。 4 结 语

海域水文和气象信息很难做出长期准确的预报，基于可预报的海域环境动态变化信息，获取后续的最优航程计划是远洋航行和海洋指挥救援的重要技术需求。本文构建的动态通达网络模型很好地描述了军事禁航区、季节性渔场、能见度管制等临时性的和岛礁、浅滩、沉船等永久性的静止碍航区以及台风等极端天气形成的移动碍航区对航线网络的动态阻隔影响特征。在此基础上，按照“优度递减”策略设计的包含计划航线通达分析(续航决策)、最短绕行航线搜索(改航决策)、最佳停靠邻港搜索(停靠决策)等步骤的最优航程规划方法，顾及了航线通达、续航可行和航线最短等约束，很好地模拟了实际航行中因为规避环境动态变化影响对计划航线进行动态修正的决策场景。本文方法能够实现航程安全性、可达性和经济性的最佳结合，实验算法也验证了规划技术路线的可操作性。后续研究中，将综合考虑碍航区动态变化、大风浪中船舶失速、船舶停靠等候避让决策等多种要素的综合影响，使航程规划方法更加科学、合理。