黃 川, 呂 靖, 艾云飛

(1.大連海事大學(xué) 交通運(yùn)輸工程學(xué)院,遼寧 大連 116026; 2.中國交通通信信息中心,北京 100011)

0 引言

船舶交通管理系統(tǒng)(Vessel Traffic Service,VTS,后文簡稱VTS系統(tǒng))自建立以來,在降低水上交通事故數(shù)量、提高船舶通航效率發(fā)揮了重要作用,但是目前隨著船型大型化和船舶數(shù)量的不斷增加,需要進(jìn)行額外監(jiān)控的水域數(shù)量也在飛速增長,因此有必要增加VTS系統(tǒng)數(shù)量確保水上交通安全進(jìn)行,而雷達(dá)站作為整個系統(tǒng)的核心部分,其位置選擇對整個系統(tǒng)的效率發(fā)揮有至關(guān)重要的作用,因此有必要對VTS雷達(dá)站選址進(jìn)行科學(xué)研究。

目前國外研究主要專注于VTS相關(guān)的立法法規(guī)[1]、VTS系統(tǒng)運(yùn)行的可靠性分析[2]、VTS系統(tǒng)建設(shè)的經(jīng)濟(jì)效益分析[3]和VTS系統(tǒng)的發(fā)展需求研究[4]等方面,對于VTS雷達(dá)站選址的研究較少,考慮到VTS雷達(dá)站選址屬于設(shè)施選址問題,因此對水運(yùn)其他研究對象選址進(jìn)行研究,主要包括應(yīng)急物資儲備庫[5]、干港[6]等。國內(nèi)關(guān)于VTS雷達(dá)站選址的研究主要有:曹德勝等[7]從多個方面構(gòu)建VTS雷達(dá)站候選點(diǎn)評價體系,然后基于集合0-1覆蓋模型構(gòu)建單目標(biāo)選址模型。艾云飛等[8]在此基礎(chǔ)上將雷達(dá)站配型和VTS中心選址因素考慮在內(nèi),構(gòu)建雙目標(biāo)模型和雙層模型并設(shè)計(jì)遺傳算法求解。黃川和呂靖[9]提出了水域精細(xì)劃分方法和水域風(fēng)險(xiǎn)評價指標(biāo)體系,基于ArcGIS軟件相關(guān)功能構(gòu)建了VTS雷達(dá)站雙目標(biāo)選址模型。

可以看出目前大部分研究只是關(guān)于VTS系統(tǒng)雷達(dá)站選址本身構(gòu)建模型進(jìn)行求解,而并沒有將建站環(huán)境中的相關(guān)因素考慮在內(nèi),本文在此基礎(chǔ)上對實(shí)際環(huán)境中山脈、森林等實(shí)體遮擋及雷達(dá)無線電波在介質(zhì)中傳播存在衰減兩個因素進(jìn)行考慮,而目前國內(nèi)外關(guān)于環(huán)境中遮擋因素的研究主要有遮擋環(huán)境下BDS/GPS的定位性能分析[10]、抗環(huán)境遮擋的目標(biāo)跟蹤算法研究[11]等。關(guān)于雷達(dá)無線電波傳播衰減則主要集中于雷達(dá)衰減訂正[12]、雷達(dá)衰減補(bǔ)償[13]等。目前關(guān)于這類選址模型求解算法國內(nèi)外研究較多,主要分為精確解算法和啟發(fā)式算法,精確解算法主要包括分支定界法、列生成算法[14]以及兩者組合形成的分支定價法等,啟發(fā)式算法則包括遺傳算法、蟻群算法等。

綜上所述,目前對于VTS雷達(dá)站選址主要集中于集合0-1覆蓋進(jìn)行研究,對于選址環(huán)境及其他因素考慮較少,因此本文考慮建站環(huán)境中的遮擋以及雷達(dá)無線電波傳遞衰減因素,同時對每個水域進(jìn)行備擇覆蓋以防出現(xiàn)當(dāng)雷達(dá)失效時水域無法被監(jiān)控的問題,基于集合覆蓋構(gòu)建VTS雷達(dá)站選址模型,使得項(xiàng)目總建站成本最小和水域面積總覆蓋率最大,并設(shè)計(jì)自適應(yīng)權(quán)重多目標(biāo)粒子群算法進(jìn)行求解。

1 問題描述與模型構(gòu)建

1.1 問題描述

考慮到雷達(dá)環(huán)形搜索的工作特性,因此本文主要基于集合覆蓋模型研究在存在障礙物遮擋和雷達(dá)傳遞衰減情景中如何進(jìn)行VTS雷達(dá)站最優(yōu)選址,同時在建址過程中對雷達(dá)站建站點(diǎn)高程、雷達(dá)站建站高度、水域高程、單個雷達(dá)失效和環(huán)境遮擋物等予以考慮,具體示意圖如圖1所示。

圖1 VTS雷達(dá)站示意圖

在圖1中,整個建站環(huán)境空間大小為x,y,z∈[0,10],圖中X和Y軸構(gòu)成平面模擬為地球基準(zhǔn)平面,Z軸為垂直高度,Z軸數(shù)值代表模擬高程數(shù)據(jù),在該環(huán)境中存在山體障礙物ABCD和4個需要被監(jiān)控的水域,在此環(huán)境中考慮單個雷達(dá)失效時進(jìn)行VTS雷達(dá)站選址。

1.2 逐漸覆蓋函數(shù)

本文引入逐漸覆蓋函數(shù)進(jìn)行雷達(dá)衰減測度,從而在無線電波隨距離衰減的情況下研究雷達(dá)站對于水域監(jiān)測概率的變化情況,水域被覆蓋率區(qū)間也從傳統(tǒng)的0-1二元區(qū)間變?yōu)閇0,1]區(qū)間,常用逐漸覆蓋函數(shù)如圖2所示。

(a) (b)

1.3 障礙物遮擋覆蓋率計(jì)算方法

本節(jié)進(jìn)一步在考慮障礙物遮擋情況下結(jié)合候選站點(diǎn)和水域間的距離和1.2節(jié)的逐漸覆蓋函數(shù)計(jì)算雷達(dá)站點(diǎn)對于監(jiān)測水域的覆蓋率。

(a)當(dāng)雷達(dá)站與水域間距離不在雷達(dá)作用范圍內(nèi)時,即雷達(dá)站對于該水域的覆蓋率為0;(b)如果兩者間距離在雷達(dá)作用范圍內(nèi)且有障礙物遮擋時,則依據(jù)距離和逐漸覆蓋函數(shù)計(jì)算得到覆蓋率,在此基礎(chǔ)上乘以一個[0,1]間任意數(shù)的穿透率;(c)如果兩者間距離在雷達(dá)作用范圍內(nèi)且無障礙物遮擋時則以兩者間距離和逐漸覆蓋函數(shù)進(jìn)行覆蓋率測算。

現(xiàn)對情況(b)下覆蓋率計(jì)算過程進(jìn)行詳細(xì)說明。在圖3中存在障礙物T-RSQ和P-MON,水域8,目前擬建立雷達(dá)站KK。本文在計(jì)算過程中是以雷達(dá)站和水域的連線與錐體構(gòu)成的所有平面計(jì)算交點(diǎn)來驗(yàn)證障礙物是否形成遮擋。數(shù)學(xué)計(jì)算過程如下。

圖3 遮擋示意圖

1.4 模型構(gòu)建

(1)模型假設(shè)

1)優(yōu)化決策過程中外部環(huán)境將保持不變。

2)障礙物的數(shù)量和穿透率以及逐漸覆蓋函數(shù)公式已知。

(2)參數(shù)定義

決策變量:

yj為0-1變量,若雷達(dá)站候選點(diǎn)j被選中,則yj=1,否則yj=0。

模型參數(shù):

Ai表示需要覆蓋的水域,i=1,…,I,ξi為每個水域需要被覆蓋的次數(shù),μi為每個水域的面積覆蓋率,Si為每個水域的水域面積,S為所有水域的總面積。

Bj表示雷達(dá)站候選點(diǎn),j=1,…,J。

Cij為覆蓋率矩陣,由逐漸覆蓋函數(shù)f(D)和障礙物穿透率Og計(jì)算得出,D為所需覆蓋水域與雷達(dá)站候選點(diǎn)的歐氏距離。

Fg為建站環(huán)境中存在的障礙物,g=1,…,G,Og為對應(yīng)障礙物的穿透率。

Mj為雷達(dá)站候選點(diǎn)j的固定建設(shè)成本。

Ek為配置k型雷達(dá)的成本,k=1,…,K。

(3)模型構(gòu)建

本文的雙目標(biāo)選址模型目標(biāo)函數(shù)為:

(1)

(2)

約束條件為:

ξi≥2

(3)

(4)

(5)

(6)

(7)

目標(biāo)函數(shù)(1)表示雷達(dá)站建站總成本最小,第1部分雷達(dá)站建站成本,第2部分為雷達(dá)配置成本;目標(biāo)函數(shù)(2)表示監(jiān)管水域面積覆蓋率最大。約束條件(3)表示為了減弱單個雷達(dá)失效帶來的影響每個水域最少需要被覆蓋兩次;約束條件(4)表示水域面積等式;約束條件(5)表示每個選中的雷達(dá)站候選點(diǎn)只能配備1種雷達(dá);約束條件(6)表示如果水域被覆蓋一次或多次,則至少應(yīng)該建一個或多個雷達(dá)站,否則不建;約束條件(7)表示0-1變量約束。

2 算法描述

2.1 算法流程

本文采用自適應(yīng)權(quán)重多目標(biāo)粒子群算法對模型進(jìn)行求解,權(quán)重變化公式如(8)所示,算法流程如圖4所示。在進(jìn)行粒子適應(yīng)度計(jì)算時,中間涉及到雷達(dá)站對水域的覆蓋率計(jì)算這一步驟,具體運(yùn)算邏輯已在圖中進(jìn)行說明。

圖4 算法流程圖

(8)

2.2 算法有效性驗(yàn)證

為了全面地評價算法有效性,本文引入ZDT系列函數(shù)進(jìn)行測試,采取其中ZDT1,ZDT2和ZDT6進(jìn)行算法性能測試,設(shè)置相關(guān)參數(shù),得到結(jié)果如圖5-圖7所示?？梢娫撍惴ㄔ赯DT測試函數(shù)集上取得了較為光滑和均勻的Pareto前沿,可以看出改進(jìn)后的多目標(biāo)粒子群算法能夠有效獲得目標(biāo)問題的Pareto前沿,且非支配解具備良好的分布性,因此可以得出改進(jìn)后的算法是可行有效的。

圖5 ZDT1結(jié)果

圖7 ZDT6結(jié)果

3 案例分析及討論

3.1 案例分析

本文以某省份的VTS雷達(dá)站選址項(xiàng)目為研究對象,將其簡化為本文所需算例。整個選址示意圖如圖8(a)所示,在整個建站環(huán)境中存在若干分段河流,如圖中紅色曲線所示,同時存在山體障礙物D-ABC、P-MON和T-SQ,以及森林障礙物IJKL-GHEF。將這若干分段河流中風(fēng)險(xiǎn)較高的重要水域進(jìn)行提取最終共選擇10個水域,如圖8(b)所示,這10個水域的具體坐標(biāo)、高程及水域面積如表1所示。

表1 水域相關(guān)信息

(a)

如1.3節(jié)所述,當(dāng)雷達(dá)傳遞遇到被障礙物遮擋住情況時可以認(rèn)為覆蓋率為0或者將正常得到的覆蓋率乘以障礙物穿透率獲得在有障礙物遮擋情況下的覆蓋率。本案例采用障礙物穿透率方法進(jìn)行障礙物遮擋效果測算,從事實(shí)角度出發(fā)一般山體的穿透率明顯低于森林障礙物,故本文假定各障礙物穿透率如表2所示,各個障礙物坐標(biāo)及高程也一并給出。本文的雷達(dá)站候選點(diǎn)范圍為三維空間中任意整數(shù)點(diǎn)。假定地勢的高程變化截面圖如圖9(a)所示(垂直于Y軸得到),因?yàn)楦叱讨禐槌掷m(xù)變化狀態(tài),為計(jì)算方便和更貼近實(shí)際,將各點(diǎn)高程值變化為圖9(b)所示,故各雷達(dá)站候選點(diǎn)的實(shí)際高程值均可由此得到;另外假定雷達(dá)站的建站高度的高度為1,當(dāng)某點(diǎn)被選中建站時,該點(diǎn)的高程值計(jì)算為該點(diǎn)地理高程和建站高度之和,否則為該點(diǎn)地理高程;故在考慮這些因素后整個項(xiàng)目中雷達(dá)站選址建站的選點(diǎn)范圍為XYZ∈{(0,0)-(20,20),Z=各點(diǎn)高程值}的任意整數(shù)點(diǎn)。雷達(dá)參數(shù)設(shè)定如表3所示,選擇圖2(b)類逐漸覆蓋函數(shù)進(jìn)行雷達(dá)無線電波衰減測算,公式如式(9)所示。為防止因?yàn)閱蝹€雷達(dá)站失效水域無法被監(jiān)測的情況出現(xiàn),所有水域需要被覆蓋2次及以上以實(shí)現(xiàn)雷達(dá)站對水域的備擇覆蓋。

表2 障礙物相關(guān)信息

表3 雷達(dá)種類

(a)

(9)

在此實(shí)例中進(jìn)行粒子初始化,考慮到需要監(jiān)管的水域總數(shù)為10,故雷達(dá)站總數(shù)需小于10,因此雷達(dá)站建站數(shù)量在[5,9]內(nèi)波動,雷達(dá)站建站成本假定為500;本文在處理雙目標(biāo)函數(shù)過程中為方便進(jìn)行支配關(guān)系比較將適應(yīng)度函數(shù)變?yōu)閇H,10-X];覆蓋率計(jì)算按照1.3節(jié)覆蓋率計(jì)算方法和2.1節(jié)進(jìn)行程序設(shè)計(jì);粒子群大小設(shè)置為100,迭代代數(shù)為100,粒子維度為441,變異概率為隨機(jī)數(shù)變異,外部存檔數(shù)量上限為50,對于不滿足覆蓋次數(shù)和面積覆蓋需求的粒子施以[X+P,10-Z+P],P=10^8,從而讓其一直處于被支配地位,降低進(jìn)入非支配解集的概率。

經(jīng)過計(jì)算Pareto前沿如圖10所示。在最終求得的外部解集當(dāng)中設(shè)置粒子出現(xiàn)概率參考值,得到出現(xiàn)概率高于參考值粒子群并根據(jù)輪盤賭規(guī)則選取相對最優(yōu)解,已在圖10中用方框標(biāo)出,根據(jù)最優(yōu)解得出最終選址方案的總成本為6700,選中的8個雷達(dá)站候選點(diǎn)對于全局10個水域的總面積覆蓋率為84.86%,最終確定建址的雷達(dá)站候選點(diǎn)分布如圖11所示,用圓形代表。各建址雷達(dá)站候選點(diǎn)坐標(biāo)及所配置雷達(dá)種類如表4所示。

表4 雷達(dá)站坐標(biāo)及雷達(dá)配置

圖10 案例Pareto前沿

圖11 選址結(jié)果

3.2 敏感性分析

觀察案例分析最后所得結(jié)果可以看出Pareto前沿的選址方案中雷達(dá)站數(shù)量區(qū)間為[7,8],而案例分析在粒子初始化所設(shè)置的雷達(dá)站數(shù)量區(qū)間為[5,9],在最終帕累托前沿并沒有出現(xiàn)其他數(shù)量的非支配解,通過對算法及參數(shù)設(shè)置進(jìn)行分析,本文認(rèn)為沒有數(shù)量5和6的非支配解可能是由于覆蓋半徑和逐漸覆蓋函數(shù)導(dǎo)致,沒有數(shù)量9的非支配解則因?yàn)槌跏冀舛鄻有圆粔?而對于不同種類覆蓋函數(shù)因?yàn)樽钚『妥畲蟾采w半徑設(shè)置數(shù)值一樣,因此不同的覆蓋函數(shù)只會獲得不同的目標(biāo)函數(shù)數(shù)值,而不太可能造成解的缺失,且經(jīng)過對案例多次的Pareto前沿計(jì)算,所有前沿均沒有出現(xiàn)數(shù)量5和6的非支配解,因此認(rèn)為是由于覆蓋半徑和約束導(dǎo)致在數(shù)量5和6出現(xiàn)無解的情況,因此本節(jié)從覆蓋半徑進(jìn)行敏感性分析,算法環(huán)境和前面案例一樣,最大覆蓋半徑分別設(shè)置為7和9,最終結(jié)果如表5所示,帕累托前沿圖如圖12和圖13所示。

圖12 最大覆蓋半徑為7的Pareto前沿

圖13 最大覆蓋半徑為9的Pareto前沿

從分析結(jié)果可以看出,當(dāng)最大覆蓋半徑為7的時候,最終獲得非支配解較少,總建站成本為7700,對全局10個水域?qū)崿F(xiàn)了86.97%的覆蓋,需要建9座雷達(dá)站,而非支配解較少的原因可能是因?yàn)樗惴]有搜尋到建8座及以下的可行解,也可能是算法尋優(yōu)能力還不夠,但是說明隨著覆蓋半徑的縮小,需要修建更多座數(shù)量雷達(dá)站來滿足約束條件;而當(dāng)最大覆蓋半徑變?yōu)?時,可以看出最終的帕累托前沿面上對于建設(shè)6,7,8,9座雷達(dá)站均存在非支配解,最終選擇的相對最優(yōu)解的建站總成本為6600,實(shí)現(xiàn)了90.44%的面積覆蓋率,需要建設(shè)8座雷達(dá)站,相比于半徑為7的情況下以更小的總建站成本實(shí)現(xiàn)了更大的面積覆蓋率,因此在實(shí)際建站過程中,部署性能更為優(yōu)異的雷達(dá)可能會比多修建雷達(dá)站實(shí)現(xiàn)的監(jiān)管效果更好,需根據(jù)具體情況進(jìn)行決策。

4 結(jié)論

文章考慮到VTS雷達(dá)站在VTS系統(tǒng)中的關(guān)鍵作用,針對其選址問題進(jìn)行研究,考慮到建站環(huán)境中的障礙物遮擋和雷達(dá)無線電波在介質(zhì)中傳播存在衰減因素,并考慮到單個雷達(dá)站失效引起水域無法被覆蓋問題基于集合覆蓋進(jìn)行選址建模并設(shè)計(jì)粒子群算法進(jìn)行多目標(biāo)求解,同時對雷達(dá)最大覆蓋半徑展開敏感性分析,結(jié)果證明本文模型可以對VTS雷達(dá)站選址進(jìn)行有效優(yōu)化。但是選址是一個綜合性工程,所需要顧及因素較多,因此接下來可以從其他方面進(jìn)行研究,同時本文算法也有較大研究空間以期改進(jìn)。