基于層次聚類自動(dòng)巡航的港區(qū)船舶碰撞危險(xiǎn)識(shí)別方法研究*

陳德軍 劉 冬 郭南彬 牟軍敏

(內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室1) 武漢 430063) (武漢理工大信息工程學(xué)院2) 武漢 430070)

基于層次聚類自動(dòng)巡航的港區(qū)船舶碰撞危險(xiǎn)識(shí)別方法研究*

陳德軍1,2)劉 冬2)郭南彬2)牟軍敏1)

(內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室1)武漢 430063) (武漢理工大信息工程學(xué)院2)武漢 430070)

港區(qū)船舶碰撞危險(xiǎn)的自動(dòng)巡航分析和識(shí)別對(duì)于港區(qū)交通監(jiān)管具有重要意義.針對(duì)船舶風(fēng)險(xiǎn)監(jiān)管分析的時(shí)間提前量需求，引入DCQA和TCQA，綜合選用DCPA和TCQA作為提前操作的判別參數(shù)組，結(jié)合AGNES算法，提出1種基于層次聚類自動(dòng)巡航的碰撞危險(xiǎn)分析方法，該方法對(duì)轄區(qū)內(nèi)船舶實(shí)時(shí)動(dòng)態(tài)數(shù)據(jù)進(jìn)行聚類，最后識(shí)別出存在碰撞危險(xiǎn)的船舶流區(qū)域，以及該會(huì)遇區(qū)域中存在碰撞風(fēng)險(xiǎn)的重點(diǎn)船舶.

船舶航行監(jiān)管；自動(dòng)巡航方法；碰撞危險(xiǎn)；層次聚類分析;綜合選用Comprehensive

0 引 言

近年來，依托船舶交通管理系統(tǒng)(vessel traffic system, VTS)開發(fā)新功能，對(duì)于水上交通安全、區(qū)域船舶航行狀況監(jiān)管以及管轄區(qū)域的運(yùn)輸效率具有明顯的促進(jìn)作用.但是，根據(jù)國(guó)內(nèi)外對(duì)于VTS及其相關(guān)工作的研究發(fā)現(xiàn)，目前VTS的應(yīng)用仍然存在著一些效率欠佳的工作方式[1]，例如，工作值班人員依托電子海圖，去人工監(jiān)測(cè)并判斷港區(qū)船舶流中存在碰撞危險(xiǎn)的船舶，這類工作方法已不能完全應(yīng)對(duì)目前繁忙港區(qū)船舶碰撞的全面監(jiān)測(cè)，不能主動(dòng)發(fā)現(xiàn)船舶流中存在碰撞的危險(xiǎn)熱點(diǎn)，因此可能導(dǎo)致漏查和延遲[2-3].如何依托VTS已獲取的豐富數(shù)據(jù)源，利用有效的自動(dòng)巡航方法實(shí)現(xiàn)船舶碰撞風(fēng)險(xiǎn)識(shí)別和全局危險(xiǎn)熱點(diǎn)主動(dòng)發(fā)現(xiàn)，進(jìn)一步提升港區(qū)船舶遠(yuǎn)程監(jiān)管的智能化和可視化水平，是當(dāng)前需要深入研究的熱點(diǎn)問題.

文獻(xiàn)[4-5]對(duì)于VTS系統(tǒng)中船舶之間碰撞危險(xiǎn)預(yù)警存在“數(shù)量多質(zhì)量低”的問題，提出和引入形成進(jìn)入緊迫會(huì)遇局面的距離(distance of close-quarters situation of approach，DCQA)和形成緊迫會(huì)遇局面的時(shí)間(time of close-quarters situation of approach，TCQA)概念，避免直接利用最近會(huì)遇點(diǎn)的距離(distance of close point of approaching，DCPA)和最近會(huì)遇點(diǎn)的時(shí)間(time of close point of approaching，TCPA)閾值進(jìn)行判斷帶來的缺陷，提高危險(xiǎn)識(shí)別的準(zhǔn)確率，減少虛警和預(yù)警延遲等情況.但其只是以單船為研究中心，沒有實(shí)現(xiàn)船舶流的全局分析和區(qū)域危險(xiǎn)發(fā)現(xiàn).文獻(xiàn)[1]以結(jié)合勢(shì)力場(chǎng)的概念，采用基于密度的聚類算法(density based clustering，DENCLUE)構(gòu)建船舶安全場(chǎng)，宏觀展示周圍的危險(xiǎn)情況并利用其評(píng)價(jià)宏觀碰撞危險(xiǎn)度，但是其船舶的碰撞危險(xiǎn)只是基于船舶周圍安全場(chǎng)的展示，且計(jì)算較為復(fù)雜.

本文針對(duì)當(dāng)前研究存在的不足，以港區(qū)船舶流為研究對(duì)象，結(jié)合DCQA和TCQA，采用層次聚類分析方法，提出一種基于最小距離的凝聚型層次聚類算法(agglomerative nesting，AGNES)港區(qū)船舶碰撞危險(xiǎn)的自動(dòng)巡航方法.該方法能及時(shí)計(jì)算出港區(qū)船舶流中存在相互碰撞危險(xiǎn)的船舶聚類結(jié)果集，幫助監(jiān)管人員從宏觀上掌握和了解目前港區(qū)內(nèi)船舶之間的碰撞危險(xiǎn)情況，在持續(xù)的巡航過程中發(fā)現(xiàn)港區(qū)各區(qū)域危險(xiǎn)熱點(diǎn)的變化趨勢(shì)，從而有針對(duì)性地關(guān)注某一片水域進(jìn)行特定對(duì)象的跟蹤監(jiān)測(cè)，并及時(shí)進(jìn)行相關(guān)處理.引入的TCQA概念也使在船舶進(jìn)入緊迫局面之前為監(jiān)管預(yù)警行動(dòng)留有時(shí)間余量，使得預(yù)警時(shí)間更為合理.上述方法將有效減輕工作人員的勞動(dòng)強(qiáng)度，提升轄區(qū)內(nèi)船舶交通監(jiān)管的可視化及避碰監(jiān)管水平.

1 最小距離的AGNES層次聚類算法

1.1 相關(guān)概念及算法描述

基于層次的AGNES聚類算法[6-7]的基本思想是自下而上的過程，聚類過程把初始數(shù)據(jù)對(duì)象視為原子類，根據(jù)聚類的選擇規(guī)則判斷每1個(gè)原子類之間是否滿足相似度選擇條件，如符合，則把2個(gè)原子類歸為一類，以新類替換原有類再次進(jìn)行該分類過程，不停迭代該聚合過程，直至滿足聚類停止條件,退出或者全部聚為一類.因此，相似度距離的選擇判定對(duì)于聚類結(jié)果的產(chǎn)生至關(guān)重要，不合理的選擇規(guī)則將會(huì)導(dǎo)致不合理的結(jié)果.假設(shè)存在任意2簇Ci和Cj，則具體簇間距離計(jì)算可分為以下4種.

1) 最小距離 又稱最近鄰方法，取Ci中對(duì)象p和Cj中對(duì)象q之間的距離d的最小值dmin.

2) 最遠(yuǎn)距離 又稱最遠(yuǎn)鄰方法，取Ci中的任一對(duì)象p與Cj中的任一對(duì)象q之間的距離d的最大值dmax.

3) 平均值距離 又稱質(zhì)心距離，分別計(jì)算Ci和Cj的中心點(diǎn)mi和mj，最后得到平均值mi和mj之差即平均值距離.

4) 平均距離 求Ci中的任一對(duì)象p與Cj中的任一對(duì)象q的距離之和，并除以元素個(gè)數(shù)，即得到平均距離davg.

依據(jù)獲得的船舶流數(shù)據(jù)，比較兩兩船舶的航行參數(shù)，通過層層篩選，將被判斷為存在碰撞危險(xiǎn)的船舶歸為一類，并進(jìn)行重點(diǎn)關(guān)注和分析.這種將初始較多的船舶對(duì)象聚為較少船舶結(jié)果集，最后判斷出船舶之間是否存在碰撞危險(xiǎn)的過程，顯然符合層次的AGNES聚類算法的思想，因此，采用基于最小距離層次聚類算法來實(shí)現(xiàn)港區(qū)船舶碰撞危險(xiǎn)的自動(dòng)巡航功能.

2 船舶碰撞危險(xiǎn)判斷

船舶航行過程中依據(jù)其行動(dòng)相互影響的危險(xiǎn)緊急程度可以分為4個(gè)階段：自由行動(dòng)階段、產(chǎn)生碰撞危險(xiǎn)階段、緊迫局面階段及緊迫危險(xiǎn)階段.在這4個(gè)階段中對(duì)船舶之間產(chǎn)生碰撞危險(xiǎn)的主要考慮因素是船舶之間的相對(duì)運(yùn)動(dòng)關(guān)系，其會(huì)遇幾何分析見圖1.

圖1 船舶會(huì)遇矢量分析

由圖1可知，通過船舶O與船舶T的會(huì)遇態(tài)勢(shì)可求得最近會(huì)遇距離DCPA=D×sin(Cr-B)和到達(dá)最近會(huì)遇點(diǎn)的時(shí)間TCPA=D×cos(Cr-B)/Vr.

在利用船舶的航行動(dòng)態(tài)參數(shù)判斷是否存在危險(xiǎn)時(shí)，大量的國(guó)內(nèi)外船舶避碰研究幾乎都是基于DCPA和TCPA設(shè)定閾值的方式.當(dāng)船舶會(huì)遇時(shí)的DCPA以及TCPA小于設(shè)定系統(tǒng)閾值時(shí)即可發(fā)出預(yù)警信息，這些方式都希望能夠及時(shí)預(yù)警，保證會(huì)遇船舶在安全會(huì)遇距離(safe distance of closest point of approach，DCPAs)上通過[8].但是利用以DCPA及TCPA閾值的預(yù)警方式是存在缺陷的.DCPA和TCPA在船舶會(huì)遇時(shí)分別代表船舶的會(huì)遇距離和會(huì)遇時(shí)間上的緊迫程度，然而事實(shí)上運(yùn)動(dòng)著的船舶與目標(biāo)形成緊迫局面不是船舶到達(dá)最近會(huì)遇點(diǎn)(closest point of approach，CPA)，而是與運(yùn)動(dòng)著的本船相距一定距離的某一點(diǎn)上，當(dāng)有碰撞危險(xiǎn)目標(biāo)小于這一距離時(shí)，本船與目標(biāo)船形成緊迫局面將不可避免，單憑讓路船采取避讓行動(dòng)已經(jīng)不能在DCPAs外安全駛過.因此，直接采用DCPA和TCPA對(duì)船舶的碰撞危險(xiǎn)進(jìn)行判斷是不合理的，為了避免這種緊迫局面的發(fā)生，引入DCQA和TCQA概念，DCQA為會(huì)遇中船舶形成會(huì)遇緊迫局面的距離,TCQA為船舶在會(huì)遇過程中將要形成緊迫局面的時(shí)間.當(dāng)會(huì)遇目標(biāo)船舶的TCQA>0時(shí)，即可“及早”地行動(dòng)，避免船舶進(jìn)入緊迫局面，見圖2.

圖2 船舶之間會(huì)遇示意圖

由圖2可知，現(xiàn)以DCPAs和船舶“操縱余地”之和作為DCQA的值，則DCQA=DCPAs+Ad+(Vt×Tn).其中：“操縱余地”取讓路船全速滿舵轉(zhuǎn)90°后2船所移動(dòng)的距離；Ad為讓路船旋回進(jìn)距，一般取值范圍在(2.8，4.0)倍的船長(zhǎng)；Tn=2Ad/(Vo)為讓路船舶在全速情況下滿舵旋回90°所需時(shí)間；DCPAs應(yīng)從監(jiān)管角度出發(fā)根據(jù)不同航行環(huán)境確定不同的值.如當(dāng)在狹水道航速不受限的情況下DCPAs應(yīng)大于其中大船的船長(zhǎng)，在航速受限時(shí)，DCPAs大于兩船船寬之和[9]或依據(jù)文獻(xiàn)[4]通過船舶領(lǐng)域來確定DCPAs等；Vo是讓路船舶的航行速度；Vt是直航船的航行速度.結(jié)合圖1對(duì)于船舶會(huì)遇時(shí)的相互運(yùn)動(dòng)態(tài)勢(shì)的矢量分析得

式中：Vr≠0；DCPA

在多艘船舶會(huì)遇判斷中，當(dāng)各船舶的DCPA0則說明未形成緊迫局面，這時(shí)才是判斷船舶碰撞危險(xiǎn)和采取巡航預(yù)警的準(zhǔn)確時(shí)間點(diǎn)，避免虛警或延遲預(yù)警.

3 基于AGNES的碰撞危險(xiǎn)自動(dòng)巡航方法

3.1 船舶聚類分析最小距離的內(nèi)聚規(guī)則

在對(duì)于港區(qū)船舶數(shù)據(jù)進(jìn)行巡航分析時(shí)，要準(zhǔn)確判斷并預(yù)警船舶之間的碰撞危險(xiǎn)，避免虛警或報(bào)警延遲使船舶進(jìn)入緊迫局面，必須留有足夠的判斷和監(jiān)管指揮反應(yīng)時(shí)間.

現(xiàn)以DCPA和TCQA作為危險(xiǎn)分析時(shí)數(shù)據(jù)對(duì)象是否能夠內(nèi)聚的標(biāo)準(zhǔn).當(dāng)DCPA0時(shí)，則說明會(huì)遇未進(jìn)入緊迫局面，此時(shí)是采取“及早”行動(dòng)的階段.當(dāng)TCQA減小時(shí)，說明會(huì)遇正向著緊迫局面行動(dòng).因此，為使船舶調(diào)度預(yù)警在船舶會(huì)遇的DCQA點(diǎn)之前，避免船舶進(jìn)入緊迫局面，應(yīng)及時(shí)行動(dòng)使船舶能夠在DCPAs外安全駛過，當(dāng)船舶之間的DCPA

3.2 船舶碰撞危險(xiǎn)自動(dòng)巡航具體算法

定義類Point代表聚類時(shí)的船舶數(shù)據(jù)對(duì)象，記錄船舶數(shù)據(jù)的位置、航速、航向、是否合并過標(biāo)識(shí)以及所屬簇等.類PointsDistance代表船舶在聚類分析時(shí)的相似度距離，記錄兩船之間的DCPA和TCQA值以及兩個(gè)相關(guān)的Point對(duì)象等，類PointsSet代表聚類時(shí)進(jìn)行合并的簇.具體過程如下.

步驟1 在聚類開始時(shí)初始化定義1個(gè)存放相似度距離的數(shù)組D，計(jì)算整個(gè)數(shù)據(jù)集中任意2個(gè)Point之間的相似度即PointsDistance，并將得到的PointsDistance對(duì)象放入數(shù)組D.在計(jì)算得到PointsDistance對(duì)象時(shí)，先對(duì)船舶數(shù)據(jù)進(jìn)行預(yù)處理，若兩艘會(huì)遇船舶之間距離相距較大，則無需再進(jìn)行兩船的PointsDistance的計(jì)算，簡(jiǎn)化相似度距離數(shù)組的生成.

步驟2 取得數(shù)組D的第一個(gè)PointsDistance對(duì)象，并根據(jù)取得的PointsDistance對(duì)象中記錄的DCPA和TCQA值判斷是否滿足系統(tǒng)設(shè)定的最小距離閾值，如若滿足，則判斷PointsDistance中記錄的2個(gè)Point對(duì)象的合并標(biāo)識(shí)是否已經(jīng)合并過了，如果2個(gè)Point都未合并，則將2個(gè)Point合并，更新合并標(biāo)識(shí)為已合并，并將其放入新建的PointsSet簇對(duì)象中，更新Point的所屬簇為該P(yáng)ointsSet；如果其中只有1個(gè)標(biāo)識(shí)已合并，則把標(biāo)識(shí)未合并的Point合并到標(biāo)識(shí)已合并的Point所屬簇中去，并更新Point相應(yīng)標(biāo)識(shí)；如果2個(gè)Point都已合并，則2個(gè)Point的所屬簇合并為1個(gè)簇，并更新所有Point的所屬簇標(biāo)識(shí).

步驟3 接著按數(shù)組D的升序獲取下1個(gè)值，繼續(xù)執(zhí)行步驟2的判斷操作，直至數(shù)組D所有數(shù)據(jù)獲取執(zhí)行完畢.

步驟4 以上步驟都執(zhí)行完畢時(shí)，所有簇PointsSet的集合就是得到的聚類結(jié)果.

步驟5 持續(xù)該聚類分析過程實(shí)現(xiàn)了基于層次聚類自動(dòng)巡航港區(qū)船舶碰撞危險(xiǎn)識(shí)別.

4 實(shí)例分析

4.1 實(shí)驗(yàn)數(shù)據(jù)來源及系統(tǒng)閾值設(shè)定

實(shí)驗(yàn)選取浙北水域?qū)幉ㄖ凵綅u附近某一時(shí)刻的船舶航行數(shù)據(jù)，共1 096艘船舶并進(jìn)行相關(guān)數(shù)據(jù)處理和篩選.主要的部分?jǐn)?shù)據(jù)信息見表1.

表1 部分實(shí)驗(yàn)數(shù)據(jù)

聚類閾值(DCPAs和TCQAmin)設(shè)定是至關(guān)重要的，閾值設(shè)置過大使得聚類的結(jié)果不能夠真實(shí)地反映目前港區(qū)的危險(xiǎn)狀態(tài)且使虛警增加，設(shè)置過小對(duì)于值班人員可能來不及行動(dòng).從巡航監(jiān)管的角度綜合考慮港區(qū)內(nèi)船舶密度和航行情況，依據(jù)文獻(xiàn)[4]中對(duì)于DCPAs的分析及船舶領(lǐng)域概念，本文依據(jù)大連海事的程浩在文獻(xiàn)[8]中將安全會(huì)遇距離根據(jù)船舶的相對(duì)方位分別設(shè)為：在0°～112.5°之間則DCPAs設(shè)為0.85 n mile，在112.5°～247.5°之間則DCPAs設(shè)為0.45 n mile，在247.5°～360°之間則DCPAs設(shè)為0.7 n mile，TCQAmin設(shè)為5 min.具體的聚類分析閾值可根據(jù)自動(dòng)巡航監(jiān)管目的和實(shí)際水域船舶航行情況確定，如在受限水域時(shí)，若船舶的速度不受約束，DCPAs應(yīng)大于會(huì)遇的兩船中的大船的船長(zhǎng)；在船舶速度受約束時(shí)，DCPAs應(yīng)大于兩船船寬之和.在航行不受限制的水域，天氣和能見度良好時(shí)單船的DCPAs為0.5 n mile，當(dāng)夜間或大風(fēng)浪天氣則應(yīng)增加為1 n mile，TCQAmin則可以根據(jù)實(shí)際情況選擇一個(gè)大于0的合理閾值.

4.2 實(shí)驗(yàn)結(jié)果及分析

圖3將聚類巡航結(jié)果采用不同的顏色進(jìn)行標(biāo)示，反映出互相之間存在碰撞危險(xiǎn)的船舶集合，及時(shí)給出預(yù)警，為巡航監(jiān)管值班人員對(duì)于船舶的會(huì)遇局面能夠有一個(gè)清晰的了解，為避碰監(jiān)管決策提供幫助.

圖3 聚類結(jié)果展示

在全局危險(xiǎn)情況描述中，由于聚類分析的結(jié)果集中，每個(gè)集合所聚集的船舶數(shù)量及其互相之間的碰撞危險(xiǎn)影響程度不同，所形成的復(fù)雜局面必然不同.根據(jù)在巡航時(shí)得到船舶之間TCQA的值在一定程度上代表會(huì)遇局面的緊迫程度，采用熱圖展示的方式，在發(fā)布的海圖服務(wù)圖層之上進(jìn)行疊加顯示.用不同色調(diào)的顏色表示不同水域內(nèi)形成會(huì)遇局勢(shì)的緊急情況.圖4中海圖上陰影較深的地方說明碰撞危險(xiǎn)緊迫程度較高，應(yīng)及時(shí)跟蹤監(jiān)測(cè).陰影較淺的區(qū)域說明受影響船舶相對(duì)較少，緊迫程度較低.在持續(xù)的自動(dòng)巡航分析和識(shí)別過程中可以清晰地掌握轄區(qū)的區(qū)域碰撞危險(xiǎn)情況，為港區(qū)交通監(jiān)管提供可視化輔助分析.

圖4 港區(qū)全局危險(xiǎn)展示

5 結(jié) 束 語

對(duì)港區(qū)船舶流進(jìn)行船舶避碰巡航監(jiān)管，防止碰撞事故的發(fā)生，是幾年來的研究熱點(diǎn)和難題.采用基于最小距離的改進(jìn)型AGNES算法，結(jié)合DCPA，TCQA及其他船舶航行要素，對(duì)于監(jiān)測(cè)到的在航船舶流航行信息進(jìn)行聚類分析，得到存在可能碰撞的船舶結(jié)果集.在持續(xù)的聚類巡航分析下，得到整個(gè)監(jiān)管區(qū)內(nèi)船舶碰撞危險(xiǎn)區(qū)域的變化趨勢(shì)，使監(jiān)管人員對(duì)所監(jiān)管區(qū)域的碰撞危險(xiǎn)有了全局的掌握和了解，也能夠反映船舶之間存在連續(xù)的碰撞影響，有利于交通管理人員的跟蹤分析，為港區(qū)船舶的巡航監(jiān)管提供了有效的手段.

[1]蔡誠(chéng)君.基于場(chǎng)論的水域船舶碰撞危險(xiǎn)度研究[D].大連：大連海事大學(xué),2015.

[2]程家友.談電子巡航在長(zhǎng)江海事的應(yīng)用[J].中國(guó)海事,2013(2):42-44.

[3]曾宇璋,黃仕祥,汪潔，等.基于電子巡航實(shí)現(xiàn)港區(qū)船舶調(diào)度管理的可行性分析[J].中國(guó)水運(yùn),2014,14(12):53-54.

[4]邱志雄.海上船舶碰撞擱淺危險(xiǎn)監(jiān)管方法的研究[D].大連：大連海事大學(xué),2009.

[5]孫苗.應(yīng)用AIS信息實(shí)現(xiàn)瓊州海峽VTS船舶交通智能管理的研究[D].廈門：集美大學(xué),2014.

[6]李欣欣.基于MPI的層次聚類算法的研究及實(shí)現(xiàn)[D].哈爾濱：哈爾濱理工大學(xué),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]程浩.海上交通安全中船舶避碰決策技術(shù)研究[D].大連：大連海事大學(xué),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

*國(guó)家自然科學(xué)基金項(xiàng)目(51579201)、內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室開放基金項(xiàng)目(NHHY2014006)、中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(2016-zy-044)資助

U676.1

10.3963/j.issn.2095-3844.2017.01.003

陳德軍(1964—)：男，博士，教授，主要研究領(lǐng)域?yàn)楹Ｊ掳踩芾?/p>