基于層次聚類自動巡航的港區船舶碰撞危險識別方法研究*

陳德軍 劉 冬 郭南彬 牟軍敏

(內河航運技術湖北省重點實驗室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—)：男，博士，教授，主要研究領域為海事安全管理