基于层次聚类自动巡航的港区船舶碰撞危险识别方法研究*

陈德军 刘 冬 郭南彬 牟军敏

(内河航运技术湖北省重点实验室1) 武汉 430063) (武汉理工大信息工程学院2) 武汉 430070)

基于层次聚类自动巡航的港区船舶碰撞危险识别方法研究*

陈德军1,2)刘 冬2)郭南彬2)牟军敏1)

(内河航运技术湖北省重点实验室1)武汉 430063) (武汉理工大信息工程学院2)武汉 430070)

港区船舶碰撞危险的自动巡航分析和识别对于港区交通监管具有重要意义.针对船舶风险监管分析的时间提前量需求，引入DCQA和TCQA，综合选用DCPA和TCQA作为提前操作的判别参数组，结合AGNES算法，提出1种基于层次聚类自动巡航的碰撞危险分析方法，该方法对辖区内船舶实时动态数据进行聚类，最后识别出存在碰撞危险的船舶流区域，以及该会遇区域中存在碰撞风险的重点船舶.

船舶航行监管；自动巡航方法；碰撞危险；层次聚类分析;综合选用Comprehensive

0 引 言

近年来，依托船舶交通管理系统(vessel traffic system, VTS)开发新功能，对于水上交通安全、区域船舶航行状况监管以及管辖区域的运输效率具有明显的促进作用.但是，根据国内外对于VTS及其相关工作的研究发现，目前VTS的应用仍然存在着一些效率欠佳的工作方式[1]，例如，工作值班人员依托电子海图，去人工监测并判断港区船舶流中存在碰撞危险的船舶，这类工作方法已不能完全应对目前繁忙港区船舶碰撞的全面监测，不能主动发现船舶流中存在碰撞的危险热点，因此可能导致漏查和延迟[2-3].如何依托VTS已获取的丰富数据源，利用有效的自动巡航方法实现船舶碰撞风险识别和全局危险热点主动发现，进一步提升港区船舶远程监管的智能化和可视化水平，是当前需要深入研究的热点问题.

文献[4-5]对于VTS系统中船舶之间碰撞危险预警存在“数量多质量低”的问题，提出和引入形成进入紧迫会遇局面的距离(distance of close-quarters situation of approach，DCQA)和形成紧迫会遇局面的时间(time of close-quarters situation of approach，TCQA)概念，避免直接利用最近会遇点的距离(distance of close point of approaching，DCPA)和最近会遇点的时间(time of close point of approaching，TCPA)阈值进行判断带来的缺陷，提高危险识别的准确率，减少虚警和预警延迟等情况.但其只是以单船为研究中心，没有实现船舶流的全局分析和区域危险发现.文献[1]以结合势力场的概念，采用基于密度的聚类算法(density based clustering，DENCLUE)构建船舶安全场，宏观展示周围的危险情况并利用其评价宏观碰撞危险度，但是其船舶的碰撞危险只是基于船舶周围安全场的展示，且计算较为复杂.

本文针对当前研究存在的不足，以港区船舶流为研究对象，结合DCQA和TCQA，采用层次聚类分析方法，提出一种基于最小距离的凝聚型层次聚类算法(agglomerative nesting，AGNES)港区船舶碰撞危险的自动巡航方法.该方法能及时计算出港区船舶流中存在相互碰撞危险的船舶聚类结果集，帮助监管人员从宏观上掌握和了解目前港区内船舶之间的碰撞危险情况，在持续的巡航过程中发现港区各区域危险热点的变化趋势，从而有针对性地关注某一片水域进行特定对象的跟踪监测，并及时进行相关处理.引入的TCQA概念也使在船舶进入紧迫局面之前为监管预警行动留有时间余量，使得预警时间更为合理.上述方法将有效减轻工作人员的劳动强度，提升辖区内船舶交通监管的可视化及避碰监管水平.

1 最小距离的AGNES层次聚类算法

1.1 相关概念及算法描述

基于层次的AGNES聚类算法[6-7]的基本思想是自下而上的过程，聚类过程把初始数据对象视为原子类，根据聚类的选择规则判断每1个原子类之间是否满足相似度选择条件，如符合，则把2个原子类归为一类，以新类替换原有类再次进行该分类过程，不停迭代该聚合过程，直至满足聚类停止条件,退出或者全部聚为一类.因此，相似度距离的选择判定对于聚类结果的产生至关重要，不合理的选择规则将会导致不合理的结果.假设存在任意2簇Ci和Cj，则具体簇间距离计算可分为以下4种.

1) 最小距离 又称最近邻方法，取Ci中对象p和Cj中对象q之间的距离d的最小值dmin.

2) 最远距离 又称最远邻方法，取Ci中的任一对象p与Cj中的任一对象q之间的距离d的最大值dmax.

3) 平均值距离 又称质心距离，分别计算Ci和Cj的中心点mi和mj，最后得到平均值mi和mj之差即平均值距离.

4) 平均距离 求Ci中的任一对象p与Cj中的任一对象q的距离之和，并除以元素个数，即得到平均距离davg.

依据获得的船舶流数据，比较两两船舶的航行参数，通过层层筛选，将被判断为存在碰撞危险的船舶归为一类，并进行重点关注和分析.这种将初始较多的船舶对象聚为较少船舶结果集，最后判断出船舶之间是否存在碰撞危险的过程，显然符合层次的AGNES聚类算法的思想，因此，采用基于最小距离层次聚类算法来实现港区船舶碰撞危险的自动巡航功能.

2 船舶碰撞危险判断

船舶航行过程中依据其行动相互影响的危险紧急程度可以分为4个阶段：自由行动阶段、产生碰撞危险阶段、紧迫局面阶段及紧迫危险阶段.在这4个阶段中对船舶之间产生碰撞危险的主要考虑因素是船舶之间的相对运动关系，其会遇几何分析见图1.

图1 船舶会遇矢量分析

由图1可知，通过船舶O与船舶T的会遇态势可求得最近会遇距离DCPA=D×sin(Cr-B)和到达最近会遇点的时间TCPA=D×cos(Cr-B)/Vr.

在利用船舶的航行动态参数判断是否存在危险时，大量的国内外船舶避碰研究几乎都是基于DCPA和TCPA设定阈值的方式.当船舶会遇时的DCPA以及TCPA小于设定系统阈值时即可发出预警信息，这些方式都希望能够及时预警，保证会遇船舶在安全会遇距离(safe distance of closest point of approach，DCPAs)上通过[8].但是利用以DCPA及TCPA阈值的预警方式是存在缺陷的.DCPA和TCPA在船舶会遇时分别代表船舶的会遇距离和会遇时间上的紧迫程度，然而事实上运动着的船舶与目标形成紧迫局面不是船舶到达最近会遇点(closest point of approach，CPA)，而是与运动着的本船相距一定距离的某一点上，当有碰撞危险目标小于这一距离时，本船与目标船形成紧迫局面将不可避免，单凭让路船采取避让行动已经不能在DCPAs外安全驶过.因此，直接采用DCPA和TCPA对船舶的碰撞危险进行判断是不合理的，为了避免这种紧迫局面的发生，引入DCQA和TCQA概念，DCQA为会遇中船舶形成会遇紧迫局面的距离,TCQA为船舶在会遇过程中将要形成紧迫局面的时间.当会遇目标船舶的TCQA>0时，即可“及早”地行动，避免船舶进入紧迫局面，见图2.

图2 船舶之间会遇示意图

由图2可知，现以DCPAs和船舶“操纵余地”之和作为DCQA的值，则DCQA=DCPAs+Ad+(Vt×Tn).其中：“操纵余地”取让路船全速满舵转90°后2船所移动的距离；Ad为让路船旋回进距，一般取值范围在(2.8，4.0)倍的船长；Tn=2Ad/(Vo)为让路船舶在全速情况下满舵旋回90°所需时间；DCPAs应从监管角度出发根据不同航行环境确定不同的值.如当在狭水道航速不受限的情况下DCPAs应大于其中大船的船长，在航速受限时，DCPAs大于两船船宽之和[9]或依据文献[4]通过船舶领域来确定DCPAs等；Vo是让路船舶的航行速度；Vt是直航船的航行速度.结合图1对于船舶会遇时的相互运动态势的矢量分析得

式中：Vr≠0；DCPA

在多艘船舶会遇判断中，当各船舶的DCPA0则说明未形成紧迫局面，这时才是判断船舶碰撞危险和采取巡航预警的准确时间点，避免虚警或延迟预警.

3 基于AGNES的碰撞危险自动巡航方法

3.1 船舶聚类分析最小距离的内聚规则

在对于港区船舶数据进行巡航分析时，要准确判断并预警船舶之间的碰撞危险，避免虚警或报警延迟使船舶进入紧迫局面，必须留有足够的判断和监管指挥反应时间.

现以DCPA和TCQA作为危险分析时数据对象是否能够内聚的标准.当DCPA0时，则说明会遇未进入紧迫局面，此时是采取“及早”行动的阶段.当TCQA减小时，说明会遇正向着紧迫局面行动.因此，为使船舶调度预警在船舶会遇的DCQA点之前，避免船舶进入紧迫局面，应及时行动使船舶能够在DCPAs外安全驶过，当船舶之间的DCPA

3.2 船舶碰撞危险自动巡航具体算法

定义类Point代表聚类时的船舶数据对象，记录船舶数据的位置、航速、航向、是否合并过标识以及所属簇等.类PointsDistance代表船舶在聚类分析时的相似度距离，记录两船之间的DCPA和TCQA值以及两个相关的Point对象等，类PointsSet代表聚类时进行合并的簇.具体过程如下.

步骤1 在聚类开始时初始化定义1个存放相似度距离的数组D，计算整个数据集中任意2个Point之间的相似度即PointsDistance，并将得到的PointsDistance对象放入数组D.在计算得到PointsDistance对象时，先对船舶数据进行预处理，若两艘会遇船舶之间距离相距较大，则无需再进行两船的PointsDistance的计算，简化相似度距离数组的生成.

步骤2 取得数组D的第一个PointsDistance对象，并根据取得的PointsDistance对象中记录的DCPA和TCQA值判断是否满足系统设定的最小距离阈值，如若满足，则判断PointsDistance中记录的2个Point对象的合并标识是否已经合并过了，如果2个Point都未合并，则将2个Point合并，更新合并标识为已合并，并将其放入新建的PointsSet簇对象中，更新Point的所属簇为该PointsSet；如果其中只有1个标识已合并，则把标识未合并的Point合并到标识已合并的Point所属簇中去，并更新Point相应标识；如果2个Point都已合并，则2个Point的所属簇合并为1个簇，并更新所有Point的所属簇标识.

步骤3 接着按数组D的升序获取下1个值，继续执行步骤2的判断操作，直至数组D所有数据获取执行完毕.

步骤4 以上步骤都执行完毕时，所有簇PointsSet的集合就是得到的聚类结果.

步骤5 持续该聚类分析过程实现了基于层次聚类自动巡航港区船舶碰撞危险识别.

4 实例分析

4.1 实验数据来源及系统阈值设定

实验选取浙北水域宁波舟山岛附近某一时刻的船舶航行数据，共1 096艘船舶并进行相关数据处理和筛选.主要的部分数据信息见表1.

表1 部分实验数据

聚类阈值(DCPAs和TCQAmin)设定是至关重要的，阈值设置过大使得聚类的结果不能够真实地反映目前港区的危险状态且使虚警增加，设置过小对于值班人员可能来不及行动.从巡航监管的角度综合考虑港区内船舶密度和航行情况，依据文献[4]中对于DCPAs的分析及船舶领域概念，本文依据大连海事的程浩在文献[8]中将安全会遇距离根据船舶的相对方位分别设为：在0°～112.5°之间则DCPAs设为0.85 n mile，在112.5°～247.5°之间则DCPAs设为0.45 n mile，在247.5°～360°之间则DCPAs设为0.7 n mile，TCQAmin设为5 min.具体的聚类分析阈值可根据自动巡航监管目的和实际水域船舶航行情况确定，如在受限水域时，若船舶的速度不受约束，DCPAs应大于会遇的两船中的大船的船长；在船舶速度受约束时，DCPAs应大于两船船宽之和.在航行不受限制的水域，天气和能见度良好时单船的DCPAs为0.5 n mile，当夜间或大风浪天气则应增加为1 n mile，TCQAmin则可以根据实际情况选择一个大于0的合理阈值.

4.2 实验结果及分析

图3将聚类巡航结果采用不同的颜色进行标示，反映出互相之间存在碰撞危险的船舶集合，及时给出预警，为巡航监管值班人员对于船舶的会遇局面能够有一个清晰的了解，为避碰监管决策提供帮助.

图3 聚类结果展示

在全局危险情况描述中，由于聚类分析的结果集中，每个集合所聚集的船舶数量及其互相之间的碰撞危险影响程度不同，所形成的复杂局面必然不同.根据在巡航时得到船舶之间TCQA的值在一定程度上代表会遇局面的紧迫程度，采用热图展示的方式，在发布的海图服务图层之上进行叠加显示.用不同色调的颜色表示不同水域内形成会遇局势的紧急情况.图4中海图上阴影较深的地方说明碰撞危险紧迫程度较高，应及时跟踪监测.阴影较浅的区域说明受影响船舶相对较少，紧迫程度较低.在持续的自动巡航分析和识别过程中可以清晰地掌握辖区的区域碰撞危险情况，为港区交通监管提供可视化辅助分析.

图4 港区全局危险展示

5 结 束 语

对港区船舶流进行船舶避碰巡航监管，防止碰撞事故的发生，是几年来的研究热点和难题.采用基于最小距离的改进型AGNES算法，结合DCPA，TCQA及其他船舶航行要素，对于监测到的在航船舶流航行信息进行聚类分析，得到存在可能碰撞的船舶结果集.在持续的聚类巡航分析下，得到整个监管区内船舶碰撞危险区域的变化趋势，使监管人员对所监管区域的碰撞危险有了全局的掌握和了解，也能够反映船舶之间存在连续的碰撞影响，有利于交通管理人员的跟踪分析，为港区船舶的巡航监管提供了有效的手段.

[1]蔡诚君.基于场论的水域船舶碰撞危险度研究[D].大连：大连海事大学,2015.

[2]程家友.谈电子巡航在长江海事的应用[J].中国海事,2013(2):42-44.

[3]曾宇璋,黄仕祥,汪洁，等.基于电子巡航实现港区船舶调度管理的可行性分析[J].中国水运,2014,14(12):53-54.

[4]邱志雄.海上船舶碰撞搁浅危险监管方法的研究[D].大连：大连海事大学,2009.

[5]孙苗.应用AIS信息实现琼州海峡VTS船舶交通智能管理的研究[D].厦门：集美大学,2014.

[6]李欣欣.基于MPI的层次聚类算法的研究及实现[D].哈尔滨：哈尔滨理工大学,2012.

[7]PATEL S, SIHMAR S, JATAIN A. A study of hierarchical clustering algorithms[C]. 2015 2nd International Conference on Computing for Sustainable Global Development (INDIACom), Bharati Vidyapeeth, New Delhi,2015:537-541.

[8]程浩.海上交通安全中船舶避碰决策技术研究[D].大连：大连海事大学,2009

[9]TAM C, BUCKNALL R, GREIG A. Review of collision avoidance and path planning methods for ships in close range encounters[J]. Journal of Navigation,2009,62:455-476.

Research on Ship Collision Risk Identification in Port Area Based on AGNES Automatic Patrol

CHEN Dejun1,2)LIU Dong2)GUO Nanbin2)MOU Junmin1)

(HubeiInlandShippingTechnologyKeyLaboratory,Wuhan430063,China)1)(SchoolofInformationEngineering,WuhanUniversityofTechnology,Wuhan430070,China)2)

The automatic patrol analysis and identification of ships in port area play an important role in traffic supervision and management. For the existing problems in traffic supervision, by introducing DCQA and TCQA and selecting DCPA and TCQA as the parameter set of operation ship in advance, a collision risk automatic patrol method is proposed to cluster the real-time dynamic data in precinct combined with AGNES algorithm. This method can identify the zones and ships with collision risk and provide visualization aided supervision.

traffic supervision; automatic patrol method; collision risk; cluster analysis; hierarchical clustering

2016-10-12

*国家自然科学基金项目(51579201)、内河航运技术湖北省重点实验室开放基金项目(NHHY2014006)、中央高校基本科研业务费专项资金项目(2016-zy-044)资助

U676.1

10.3963/j.issn.2095-3844.2017.01.003

陈德军(1964—)：男，博士，教授，主要研究领域为海事安全管理