基于瞬时水深模型的最短时间航线自动生成算法

2010-12-25张立华苏奋振彭认灿暴景阳

测绘学报 2010年5期

张立华,苏奋振,彭认灿,暴景阳,张莉

1.海军大连舰艇学院海洋测绘科学与工程系,辽宁大连116018;2.中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京100101;3.大连海事大学航海学院,辽宁大连116026

张立华1,2,苏奋振2,彭认灿1,暴景阳1,张莉3

提出一种基于瞬时水深模型的最短时间航线自动生成算法。基于海图静态水深和海域潮位模型,构建瞬时水深模型,动态提取碍航区,并进行航线可行性分析;利用动态规划思想,进行最短时间路径搜索;采用矩形包络分析、相近节点搜索和冗余点删除等策略,进行航线优化。实验表明:本算法能动态分析航线可行性,搜索最短时间航线。与传统算法相比,所提算法可提取航行时间更短的航线,所提取的最短时间航线,与舰船航行的起始时间和舰船航速相关。

瞬时水深模型;最短时间航线;航线分析

1 引言

海图航线设计是舰船安全、经济航行的先导和基础[1-5]。民用船只的航线通常较为固定,但船舶运营公司要想在日益激烈的市场竞争中立于不败之地,就必须考虑既经济,又安全的高质量航线[3,6-8]。而在海上避难、搜救等应急行动中,则希望快速地拟定出航行时间最短的航线[9]。在军事上,面对复杂多变的航行环境,如果能自动、快速地找到最短时间航线,可赢得战机,为战争胜利创造条件[4,9-11]。

传统的最短时间航线算法主要有两类方法:一类是气象定线方法,其核心是分析水文气象条件,采用计算等时线和动态规划等技术手段,优选船舶航线[8,12-14],这种方法专门针对不需要考虑复杂水深条件的远洋航行,研究航行时间最短的问题;另一类方法是最短距离方法,用求取的最短距离航线,近似地作为最短时间航线[3-7]。上述两类方法都基于海图静态水深(又称图载水深),没有考虑水位变化的动态影响。而在实际中,我国的大多数沿岸海区,高低潮时水位之差约为2～4 m。这种水位的动态变化,对舰船航行,特别是邻近安全水深的区域,具有重要影响[15-16]。如果能有效利用水位动态变化、基于海上实际的瞬时水深,进行舰船航行分析,完全有可能使舰船在避难、搜救、军事行动等应急航行中开辟航行时间更短的新航线,为应急行动赢得宝贵的时间。

因此,探索基于瞬时水深模型的最短时间航线自动生成算法,具有现实意义。

2 最短时间航线自动生成算法

2.1 基于瞬时水深模型的碍航区表达

本文采用舰船航行实际所用的海图作为基础数据平台,并以海图静态水深作为基础水深。采用基于POM模式和“Blending”同化法的数值计算,建立中国海区及邻近海域潮汐模型[17],预报海区水位。在静态水深的基础上,融合预报的动态水位,构建瞬时水深模型。然后,基于瞬时水深模型,根据舰船安全航行对水深的要求,实时提取浅水时变碍航区,并与其他固定的碍航区一起,组成碍航区集[5]。不同时间的碍航区集,形成碍航区集序列,图1是某海区某天不同时刻的碍航区集表达。

图1 不同时刻的碍航区表达Fig.1 Obstacle areas at different time

2.2 基于瞬时水深模型的航段可行性分析

瞬时水深,随着时间而变化,使得碍航区集也可能随之发生相应变化。因此,基于瞬时水深模型的航线分析,应根据碍航区集,动态地分析航段与碍航区的相交情况,判断航线的可行性。动态判断航段可行性方法的基本步骤是:

1.从航线起点方向开始,将准备分析的各直线航段,分成多个子段(分段数取决于航段的长度、水位变化情况和分析精度要求),舰船航行在每个子段时,各子段的水位值变化可忽略不计。

2.根据舰船航速和航行起始时间,依次计算舰船航行到各子段中间时刻的碍航区集,以中间时刻的碍航区集作为整个航段的碍航区集,从而判断舰船在子段上的航行可行性。如果有任意一个子段的航行可行性为否,则整个航段的可行性为否;只有当所有子段的航行可行性为是时,整个航段的可行性才为是。具体方法可参见文献[15]。

2.3 最短时间路径搜索

最短路径搜索是本算法的核心,利用动态规划思想,其基本步骤如下(图2):

1.在图上建立起始点 P0与目的点 PN之间的连线P0PN,将 P0PN划分为N个区段,每个区段的距离D取为舰船正常航速V和时间计算步长Δt的乘积,在每段点上作平行于 P0PN的垂线,在垂线上,由 P0PN左右两侧每隔D标出一个节点,于是得到一组节点为节点个数)。

图2 最短时间航线规划Fig.2 Route programming of the shortest time distance

2.连接起始点 P0与第一条垂线的各节点,为一个判断航段。根据正常航速和起航时间,判断航段的可行性,并计算每条连线的航行时间。对不可航行的航段(如图2中的短划线所示),设置节点标志为无效节点,其余为有效节点。然后将第2条垂线上的每一节点与第一条垂线的各有效节点连接起来,并判断航段可行性,计算相应航行时间。如果第1条垂线上的所有有效节点到第2条垂线某节点航线都为不可行,则第2条垂线的此节点为无效节点,否则为有效节点。最后从起始点 P0出发,确定分别到2条垂线各有效节点航行时间最少的航线。

3.重复上述过程直到(N-1)步,可得到由P0点到 PN-1段各节点的最短时间航线,然后将PN-1段上各节点和终点 PN点连接,并选取 P0点到 PN点的最短时间航线,即为航时最小的最优航线。

2.4 路径搜索简化策略

由于所提算法基于瞬时变化的水深模型,需要根据航行时间,不断重复实时更新碍航区集,进行航线可行性分析,因此计算量很大。为了提高算法的效率,本研究采用以下策略(图3):

1.节点矩形包络内的碍航物分析。根据所有参与计算分析的节点坐标,求取其如图3所示的矩形包络AB CD。遍历所有的碍航区域,判断各碍航区域的外接矩形包络与节点矩形包络AB CD的相交性,将其包络不与AB CD相交的碍航区排斥,从碍航区集合中删除。在后续的航线可行性分析及计算过程中,不再对这些被排斥的碍航区进行处理。

2.相近节点搜索处理。从完备性上讲,最短时间航线搜索时,应从某一点(如图3中的起始点P0),分析到下一垂线(P1所处的虚线)所有节点的航线可行性,并计算可航行航段的航行时间。但从图3可以看出,即使在较复杂的区域,最短时间路径的节点变化也有一定的规律。设 P1在其所处垂线中的节点序号为i,从 P1到 P2,它们在相邻各自垂线中的序号没有变化。从 P2到 P3,序号变化为-1。从 P3到 P4,序号变化为0。在以后的计算与分析中,如果当前节点在垂线的序号为 i,只对下一垂线中相近的几个节点进行分析。如图3,P1的节点序号为 i,只对序号 i-2, i-1,i,i+1,i+2共5个节点进行分析(分析节点数可根据碍航区复杂程度进行设置,如果出现碍航区突变成过大的特殊情形,5个节点绕不过去,可进一步扩充节点数),最后找到最短时间航线中的节点 P2。通过如此简化,能在垂线节点数较大的计算分析中,有效节省时间。

3.航段可行性时间处理。从当前垂线中序号为i节点到下一垂线中节点序号i-2,i-1, i,i+1,i+2时,航行时间也存在一定的区别。为了简化计算,用当前分析节点到下一垂线各相近节点的航行时间平均值,作为当前分析节点到下一垂线各航段的更新碍航物时间,也就是以此平均航行时间的中间时刻提取浅水碍航区,进行航段可行性分析。

图3 路径搜索简化策略Fig.3 Simplification of the path search

2.5 航线优化

由于上述航线是从规则的网格节点中搜索出来,这种航线是一系列经过网格点的路径,如图3中 P1、P2、P3、P4、P5。而实际航线中,可能直接从 P1直线航行到 P5,并不需要经过图3中 P2、P3、P4这些冗余节点,这样航行时间将会更短。具体的处理方法可从 P1开始,判断 P1P3是否为可行航段。如果是,则删除 P2,依次判断,直至判断出 P1P5是可行航段,将 P4删除。由于进行可行性判断时,中间的碍航区还在变化,应当采用2.2中所述的动态判断航段可行性的方法,进行具体的分析。

3 实验与分析

3.1 水位对航线可行性的影响

对于安全水深为9.0 m的舰船,如果采用传统的静态水深模型,如图4(a)所示,从起点 S,不管怎样,都将无法航行到终点D。如果充分利用动态水位,完全可以在某时刻从 S直线航行到D,如图4(b)所示。由于水位的影响,瞬时水深和碍航区在不断地变化,考虑到表达的简便性,图上只显示了某涨潮时刻的瞬时水深及碍航区。

3.2 不同模型对航行路线及时间的影响

为了进一步测试不同水深模型对最短时间航线的具体影响,选择有代表性的某实验区域,如图5所示。基于瞬时水深模型的水深和碍航区还在时刻变化,但考虑到表达的困难性,图5(b)仍只对静态水深进行显示。对于安全水深为10 m的舰船,如果采用传统静态水深模型,从起点 S到D的最短时间航线如图5(a)所示,航程为18 837.7 m。如果航速为 10 kn,所用时间为1 h 01 min。如果采用瞬时水深模型,航速不变,充分利用水位变化,从2009年6月1日15时00分由起点S到D的最短时间航线如图5(b)所示,航程为12 625.0 m,所用时间为41 min。采用瞬时水深模型后,绝对航行时间可缩短20 min,相对缩短30.3%。

图4 基于不同水深模型的航线可行性分析Fig.4 Navigability of a route based on different depth model

图5 基于不同水深模型的最短时间航线Fig.5 The shortest time route based on different depth model

3.3 瞬时水深模型中不同起始时间、航速对航行路线及时间的影响

图6为测试瞬时水深模型中不同起始时间对航行路线及时间的影响。对于安全水深为10 m,航速为10 kn的舰船,如果从2009年6月1日13时00分由起点S到D,最短时间航线如图6(a)所示,航程为16 325.6 m,航行时间为53 min。如果航行起始时间为2009年6月1日16时30分,从起点S到D的最短时间航线如图6(b)所示,航程为13 889.4 m,航行时间为45 min。从实验可以看出,在舰船航速不变的情况下,图6(a)、(b)中的航行起始时间相对于图5(b)发生了变化,导致相应的最短时间航线也发生了变化。所以说,基于瞬时水深模型的最短时间航线与舰船航行起始时间相关,但从航行用时来说,都还是优于基于静态水深模型的最短时间航线的。

为了测试瞬时水深模型中不同舰船航速对航行路线及时间的影响。对于安全水深为10 m,从2009年6月1日16时30分开始起航,如果航速为5 kn,从起点S到D的最短时间航线如图7(a)所示,航程为16 145.6 m。如果航速为20 kn,最短时间航线如图7(b)所示,实际航程为13 746.5 m。从实验结果分析来看,在图7(a)、(b)中,尽管航行起如时间与图6(b)一样,但随着航速的变化,其最短时间航线发生了变化,所以说基于瞬时水深模型的最短时间航线,还与舰船航速相关。

图6 不同航行起始时间的最短时间航线Fig.6 The shortest time route based on different departure time

图7 不同舰船航速的最短时间航线Fig.7 The shortest time route based on different ship speeds

4 结论

本文基于瞬时水深模型,进行了最短时间航线自动生成的探索。通过研究,得出如下结论:

1.水位的动态变化,特别是邻近安全水深的区域,对舰船最短航行时间具有重要影响。本文所提算法,能根据水位变化,自动更新碍航区,分析航线可行性,搜索最短时间航线。

2.相对于传统静态水深模型的航线算法来看,如果采用相同的舰船航速,文中所提算法可以搜索出航行时间更短的航线,为舰船应急航行节省时间。

3.在同一航行区域,从某起点航行到某终点,如果航行起始时间和航速不同,最短时间航线可能不同。也就是说,两点之间的最短时间航线与舰船航行的起始时间和舰船航速相关。

当然,所提算法仍只是一种探索性算法,将来还应进一步分析碍航物分布更复杂的情形。同时,本文也只是主要论证了水深动态变化对最短时间航线的影响,至于潮流、海浪、风等多动态要素对航行的复合影响,有待于下一步研究。

[1] CHRISTIANSEN M,FAGERHOL T K,RONEN D.Ship Routing and Scheduling :Status and Perspectives[J]. Transportation Science,2004,38(1):1-18.

[2] INCE A N,TOPUZ E.Modelling and Simulation for Safe and Efficient Navigation in Narrow Waterways[J].Journal of Navigation,2004,57(1):53-71.

[3] RAFAL S.A New Method of Ship Routing on Raster Grids,with Turn Penalties and Collision Avoidance[J]. Journal of Navigation,2006,59(1):371-384.

[4] WANG Ke.A Study for Designing Navigation Route Based on ECDIS[D].Dalian:Dalian Naval Academy,2004.(王科.基于电子海图的航线设计研究[D].大连:海军大连舰艇学院,2004.)

[5] ZHANG Lihua,ZHU Qing,ZHANG Anming,et al.An Intelligent Method for the Shortest Routing[J].Acta Geodaetica et Cartographica Sinica,2008,37(1):114-119.(张立华,朱庆,张安民,等.一种智能的最短航线构建算法[J].测绘学报,2008,37(1):114-119.)

[6] CHANG K Y,JAN G E,PARBERRY I.A Method for Searching Optimal Routes with Collision Avoidance on Raster Charts[J].Journal of Navigation,2003,56(3): 371-384.

[7] LI Yuanhui,PAN Mingyang,WU Xian.Automatic Creating Algorithm of Route Based on Dynamic Grid Model[J]. Journal of Traffic and Transportation Engineering,2007,7 (3):34-39.(李源惠,潘明阳,吴娴.基于动态网格模型的航线自动生成算法[J].交通运输工程学报,2007,7(3): 34-39.)

[8] VLACHOS D S.Optimal Ship Routing Based on Wind and Wave Forecasts[J].Appl Num Anal Comp Math,2004, 1(2):547-551.

[9] THEUNISSEN E,GROOT C A de,SABELIS H,et al. Nautical and Aeronautical Electronic Charting/Navigation Systems—Developments,Similarities and Differences[C]∥Proceedings of the 23rd Digital Avionics Systems Conference.Salt Lake City:IEEE,2004:24-28.

[10] MONTES A A.Network Shortest Path Application for Optimum Track Ship Routing[D].Monterey:Naval Postgraduate School,2005.

[11] BEKKER J F,SCHMID J P.Planning the Safe Transit of a Ship through a Mapped Minefield[J].JORSSA,2006, 22(1):1-18.

[12] PADHY C P,SEN D,BHASKARAN P K.Application of Wave Model for Weather Routing of Ships in the North Indian Ocean[J].Natural Hazards,2008,44(3):373.

[13] LI Yuanlin,CHEN Hongbin.Design of Optimum Ship Route Using Weather Routing Techniques[J].Journal of South China University of Technology:Natural Science, 1997,25(12):65-69.(李远林,陈宏彬.船舶最佳气象航线的设计[J].华南理工大学学报:自然科学版,1997, 25(12):65-69.)

[14] WANG Fengwu,JIA Chuanying.The Study on the Optimal Ship Routing[J].Journal of Dalian Maritime University,1998,24(2):61-64.(王凤武,贾传荧.船舶优选航线的研究[J].大连海事大学学报,1998,24(2):61-64.)

[15] ZHANGLihua,LIU Yanchun,ZHU Qing,et al.Analysis of Feasibility of Routing Based on Changing Water Levels[J].Geomatics and Information Science of Wuhan University,2008,33(9):892-895(张立华,刘雁春,朱庆,等.基于动态水位的航线可行性分析方法[J].武汉大学学报:信息科学版,2008,33(9):892-895.)

[16] SU Fenzhen,ZHOU Chenhu,YANG Xiaomei,et al. Theory,Technology and Application of MarineGeographic Information System[M].Beijing:Ocean Press, 2005.(苏奋振,周成虎,杨晓梅,等.海洋地理信息系统——原理、技术与应用[M].北京:海洋出版社,2005.)

[17] XU Jun,BAO Jingyang,LIU Yanchun,et al.A Regional Tide Model around China Developed by POM and Blending Assimilation Method[J].Hydrographic Surveying and Charting,2008,28(6):15-17.(许军,暴景阳,刘雁春,等.基于POM模式与Blending同化法建立中国近海潮汐模型[J].海洋测绘,2008,28(6):15-17.)

A Method for the Shortest Time Routing Based on an Instantaneous Depth Model

ZHANGLihua1,2,SU Fenzhen2,PENG Rencan1,BAO Jingyang1,ZHANGLi3
1.Department of Hydrography and cartography,Dalian Naval Academy,Dalian 116018,China;2.State Key Laboratory of Resources and Environmental Information System,Institute of Geographic Sciences and Natural Resources Research,CAS,Beijing 100101,China;3.Navigation Department of Dalian Maritime University,Dalian 116026,China

A method for the shortest time routing based on an instantaneous depth model is proposed.Firstly,an instantaneous model is constructed based on static depths in a chart and a tidal model in a sea area,then obstacles are acquired and the navigability of a route is analyzed.Secondly,the shortest time path is searched using a dynamic programming method.Finally,the path is optimized by the strategies including excluding obstacles outside the rectangle border of all nodes,searching close nodes in next stage and deleting redundant nodes for a more direct navigation.Experimental results demonstrate:①the proposed method can analyze the navigability of the routes dynamically and acquire the shortest time route;②the route acquired by the proposed method has the shortest time than that by the traditional methods;③the shortest route depends on the start time of navigation and the ship speed.

instantaneous depth model;the shortest time route;route analysis

ZHANG Lihua(1973—),male,PhD,associate professor,majors in marine GIS.

1001-1595(2010)05-0516-06

P208

国家863计划(2009AA12Z202);国家自然科学基金(40801189,40801158);中国博士后科学基金(20080430547)

(责任编辑:丛树平)

2009-06-23

2009-11-01

张立华(1973—),男,博士,副教授,研究方向为海洋GIS。

E-mail:zlhua@163.com