VTS雷達(dá)站選址-雷達(dá)配置優(yōu)化模型

艾云飛， 呂 靖， 張麗麗， 曹德勝

(大連海事大學(xué) 交通運(yùn)輸管理學(xué)院， 遼寧 大連 116026)

VTS雷達(dá)站選址-雷達(dá)配置優(yōu)化模型

艾云飛， 呂 靖， 張麗麗， 曹德勝

(大連海事大學(xué) 交通運(yùn)輸管理學(xué)院， 遼寧 大連 116026)

為使VTS系統(tǒng)的功能正常發(fā)揮，對(duì)其雷達(dá)站選址以及雷達(dá)配備方案進(jìn)行研究。首先運(yùn)用多層次模糊綜合評(píng)價(jià)方法對(duì)雷達(dá)站候選點(diǎn)進(jìn)行初選；然后考慮雷達(dá)對(duì)水域監(jiān)測(cè)的可靠性，建立雷達(dá)站選址配置雙目標(biāo)優(yōu)化模型，第1目標(biāo)為選址配置成本最小，第2目標(biāo)為水域單元被監(jiān)測(cè)的可靠性最大；最后分別賦予2個(gè)目標(biāo)優(yōu)先級(jí)，將模型轉(zhuǎn)化為單目標(biāo)模型，并針對(duì)模型設(shè)計(jì)遺傳算法求解。算例結(jié)果表明，最終方案能夠?qū)崿F(xiàn)水域的全面覆蓋和重點(diǎn)水域的多重覆蓋，目標(biāo)函數(shù)優(yōu)先級(jí)的變化會(huì)影響最終決策方案。將程序運(yùn)行10次，計(jì)算結(jié)果具有穩(wěn)定性。

水路運(yùn)輸； VTS雷達(dá)站； 多層次模糊綜合評(píng)價(jià)； 選址-配置； 可靠性； 遺傳算法

雷達(dá)站是船舶交通管理系統(tǒng)(Vessel Traffic Services, VTS)最核心的組成部分之一，其位置的選擇以及雷達(dá)配置對(duì)系統(tǒng)功能的發(fā)揮有決定性影響。研究VTS雷達(dá)站選址及雷達(dá)配置問(wèn)題的目的是合理確定雷達(dá)站的建設(shè)位置、雷達(dá)型號(hào)，以最少的投入滿(mǎn)足對(duì)區(qū)域的覆蓋要求。

目前，對(duì)基站選址問(wèn)題的研究大多集中于覆蓋思想。TOREGA等[1]最早提出集合覆蓋問(wèn)題，其目標(biāo)是在滿(mǎn)足覆蓋所有需求點(diǎn)的前提下，使需要建立設(shè)施的地點(diǎn)的個(gè)數(shù)或建設(shè)費(fèi)用最少。集合覆蓋會(huì)產(chǎn)生資源閑置，為使有限的資源發(fā)揮最大效用，CHURCH等[2]提出最大覆蓋問(wèn)題，即在服務(wù)站的數(shù)目和服務(wù)半徑已知的前提下，如何設(shè)立P個(gè)服務(wù)站使得滿(mǎn)足最大的需求。HOGAN等[3]對(duì)最大覆蓋模型進(jìn)行了擴(kuò)展，進(jìn)一步提出了備用覆蓋模型，即有一些點(diǎn)要被多個(gè)服務(wù)設(shè)施同時(shí)覆蓋2次或以上。LEE等[4]研究了Wi-fi設(shè)備選址問(wèn)題。ERDEMIR等[5]研究了航空醫(yī)療設(shè)備和地面救護(hù)車(chē)的選址問(wèn)題。BELL等[6]基于覆蓋思想研究了航空警報(bào)器的選址問(wèn)題。楊成龍[7]研究了3G基站選址的覆蓋問(wèn)題，對(duì)一般3G系統(tǒng)的基站選址問(wèn)題分別建立了集覆蓋模型和最大覆蓋模型。朱思峰等[8]基于覆蓋思想建立了基站選址優(yōu)化模型，并運(yùn)用多目標(biāo)量子免疫算法進(jìn)行求解。

目前有關(guān)VTS雷達(dá)站選址以及雷達(dá)選型配置問(wèn)題的研究還比較少。史云劍[9]分析了雷達(dá)站盲區(qū)對(duì)選址的影響以及減少雷達(dá)盲區(qū)的措施，給出了雷達(dá)最大作用距離和最小作用距離的計(jì)算方法，但沒(méi)有給出雷達(dá)站選址的具體模型和方法。曹德勝等[10]對(duì)VTS雷達(dá)站選址問(wèn)題進(jìn)行研究，給出了雷達(dá)站候選點(diǎn)評(píng)價(jià)指標(biāo)、綜合模糊評(píng)價(jià)方法以及雷達(dá)站選址優(yōu)化模型。

在以往研究的基礎(chǔ)上，考慮雷達(dá)服務(wù)的可靠性，研究VTS雷達(dá)站的選址及雷達(dá)選型配置問(wèn)題，建立總費(fèi)用最小、水域單元被監(jiān)測(cè)的可靠性最大的雙目標(biāo)優(yōu)化模型，并針對(duì)模型設(shè)計(jì)遺傳算法進(jìn)行求解。

1 VTS雷達(dá)站選址問(wèn)題描述

VTS中心位置及雷達(dá)站候選點(diǎn)位置已知，建設(shè)雷達(dá)站并配置雷達(dá)以覆蓋所服務(wù)水域(見(jiàn)圖1)。

圖1 VTS雷達(dá)站選址

假設(shè)條件：

1. 水域劃分為若干單元，每個(gè)單元的船舶交通量已知，水域單元的重要度已知。

2. 每個(gè)雷達(dá)站候選點(diǎn)最多建立1個(gè)雷達(dá)站，每個(gè)雷達(dá)站只配置1種型號(hào)的雷達(dá)，并且雷達(dá)有監(jiān)測(cè)能力限制；雷達(dá)站覆蓋水域單元內(nèi)的船舶交通量不能超出雷達(dá)的最大監(jiān)測(cè)能力。

3. 每個(gè)雷達(dá)都有最大作用距離和最小作用距離。超出最大作用距離，雷達(dá)將不能發(fā)揮作用；小于最小作用距離的區(qū)域稱(chēng)為雷達(dá)的盲區(qū)，需要被覆蓋的水域不能在盲區(qū)內(nèi)。

4. 雷達(dá)對(duì)目標(biāo)進(jìn)行監(jiān)測(cè)時(shí)有一定可靠性，當(dāng)水域單元被多個(gè)雷達(dá)站覆蓋時(shí)，可靠性采用并聯(lián)系統(tǒng)可靠性計(jì)算方法來(lái)計(jì)算。

5. 為保障重點(diǎn)水域的通航安全，重點(diǎn)水域單元要同時(shí)被多個(gè)VTS雷達(dá)站覆蓋?？偝杀局饕ɡ走_(dá)站建站成本、線(xiàn)路鋪設(shè)成本、雷達(dá)配置成本，問(wèn)題的2個(gè)目標(biāo)是總成本最小、水域單元被監(jiān)測(cè)的可靠性之和最大。

2 雷達(dá)站候選點(diǎn)初選

通過(guò)對(duì)VTS雷達(dá)站建設(shè)進(jìn)行實(shí)際調(diào)研，建立雷達(dá)站候選點(diǎn)綜合評(píng)價(jià)指標(biāo)體系(見(jiàn)圖2)。

圖2 雷達(dá)站候選點(diǎn)評(píng)價(jià)指標(biāo)體系

運(yùn)用多層次模糊綜合評(píng)價(jià)方法對(duì)所建立的指標(biāo)進(jìn)行評(píng)價(jià)。評(píng)價(jià)的目的是從眾多候選點(diǎn)中選出適合建設(shè)VTS雷達(dá)站的點(diǎn)，為后面的模型計(jì)算做準(zhǔn)備，增加選址方案的合理性。[10]

3 模型建立

3.1參數(shù)說(shuō)明

3.2水域單元被有效監(jiān)測(cè)的可靠性

假設(shè)能夠覆蓋水域單元i的雷達(dá)站有n個(gè)，則水域i能被有效監(jiān)測(cè)的必要條件為至少有1個(gè)雷達(dá)站能夠?qū)ζ溥M(jìn)行有效監(jiān)測(cè)，此系統(tǒng)為并聯(lián)系統(tǒng)，系統(tǒng)框圖見(jiàn)圖3。

圖3 并聯(lián)系統(tǒng)框圖

水域單元i被有效監(jiān)測(cè)的可靠性為

(1)

3.3模型建立

基于以上變量解釋?zhuān)瑪?shù)學(xué)模型的目標(biāo)函數(shù)為

(2)

(3)

約束條件為

式(2)表示建設(shè)成本最小，第1部分為雷達(dá)站的雷達(dá)配置成本，第2部分為雷達(dá)站建設(shè)固定成本，第3部分為雷達(dá)站到VTS中心的線(xiàn)路鋪設(shè)成本；式(3)表示水域單元被監(jiān)測(cè)的可靠性之和最大；式(4)表示水域單元至少被覆蓋1次，即水域單元被全面覆蓋；式(5)表示重要度大于閾值的水域單元至少被覆蓋2次，即水域單元重點(diǎn)加強(qiáng)；式(6)表示雷達(dá)站所監(jiān)測(cè)的水域單元的船舶交通量之和小于其最大監(jiān)測(cè)能力；式(7)表示每個(gè)雷達(dá)站只配置1種型號(hào)雷達(dá)；式(8)表示0-1變量約束。

4 求解算法設(shè)計(jì)

多目標(biāo)優(yōu)化問(wèn)題與單目標(biāo)優(yōu)化問(wèn)題的本質(zhì)區(qū)別在于其解不唯一，而是存在一個(gè)由眾多Pareto最優(yōu)解組成的最優(yōu)解集合。依據(jù)各個(gè)目標(biāo)的優(yōu)先級(jí)，將多目標(biāo)問(wèn)題轉(zhuǎn)換為單目標(biāo)問(wèn)題，該問(wèn)題亦屬于NP-Hard問(wèn)題，針對(duì)模型設(shè)計(jì)遺傳算法進(jìn)行求解。

4.1染色體編碼

采用二進(jìn)制編碼方式，染色體見(jiàn)圖4。1,2,…,n為對(duì)應(yīng)的雷達(dá)站候選位置，1,2,…,m為每個(gè)雷達(dá)站的候選雷達(dá)型號(hào)，染色體總長(zhǎng)度為nm。

圖4 染色體示例

4.2初始化種群及適應(yīng)度函數(shù)

設(shè)種群數(shù)量為M，初始種群采用隨機(jī)生成方法，即隨機(jī)產(chǎn)生1條染色體，若可行則予以保留，否則產(chǎn)生1條新的染色體，直到染色體數(shù)量達(dá)到M。適應(yīng)度函數(shù)設(shè)計(jì)為f=P1(I-Z1)+P2Z2。f為染色體的適應(yīng)度值；I為常數(shù)；Z1為染色體的第1目標(biāo)函數(shù)；Z2為染色體的第2目標(biāo)函數(shù)；P1，P2為2個(gè)目標(biāo)函數(shù)的優(yōu)先級(jí)，優(yōu)先級(jí)順序取決于決策者的偏好。

4.3精英保留策略

在每代種群中，對(duì)個(gè)體的適應(yīng)度值進(jìn)行排序，把排在前面的染色體作為精英個(gè)體保存，進(jìn)行完選擇、交叉、變異操作后，精英個(gè)體替代種群中適應(yīng)度比較低的個(gè)體直接進(jìn)入下一代。

4.4懲罰函數(shù)

當(dāng)出現(xiàn)不滿(mǎn)足約束條件的個(gè)體時(shí)，需要對(duì)其適應(yīng)度進(jìn)行懲罰，將該個(gè)體的適應(yīng)度減去常數(shù)P，即f′=f-P，降低其進(jìn)入下一代的概率。

4.5遺傳算子和終止條件

采用輪盤(pán)賭的方法進(jìn)行選擇，采用單點(diǎn)交叉、單點(diǎn)變異；遺傳算法到達(dá)最大迭代次數(shù)后停止。

5 算例分析

以某內(nèi)河港口VTS雷達(dá)站選址問(wèn)題為例，將水域劃分為20個(gè)單元，多層模糊評(píng)價(jià)選出雷達(dá)站候選點(diǎn)10個(gè)，雷達(dá)有2種型號(hào)，相關(guān)數(shù)據(jù)見(jiàn)表1～表3，每1 km線(xiàn)路鋪設(shè)成本為1，水域單元重要度的閾值為5，VTS中心的坐標(biāo)為(4,-1)。

P1gt;P2，適應(yīng)度函數(shù)f=10(100-Z1)+Z2，MATLAB編程，種群大小為50，染色體長(zhǎng)度為20，交叉概率為0.9，變異概率為0.1，每一代保留4個(gè)精英個(gè)體，迭代100次。將程序運(yùn)行10次，平均運(yùn)行時(shí)間11 s，計(jì)算結(jié)果比較穩(wěn)定，迭代見(jiàn)圖5。

從圖5中可以看出，隨著迭代次數(shù)增加，適應(yīng)度值和2個(gè)子目標(biāo)函數(shù)值呈現(xiàn)出不同的變化趨勢(shì)，適應(yīng)度值的變化正是兩目標(biāo)函數(shù)共同作用的結(jié)果。最終雷達(dá)站候選點(diǎn)3，4，9，10被選，配置雷達(dá)型號(hào)分別為型號(hào)1、型號(hào)2、型號(hào)1、型號(hào)1，建站成本為96.7，水域單元被覆蓋的可靠度之和為19.4，選址結(jié)果見(jiàn)圖6。

表1 水域單元數(shù)據(jù)

表2 雷達(dá)站候選點(diǎn)數(shù)據(jù)

表3 雷達(dá)數(shù)據(jù)

圖5 遺傳算法迭代圖

圖6 雷達(dá)站選址結(jié)果(第1目標(biāo)優(yōu)先)

最終方案實(shí)現(xiàn)了對(duì)水域單元的完全覆蓋；水域單元3，4，9，14，18，19的重要度大于閾值，選址方案實(shí)現(xiàn)了對(duì)這些單元的多重覆蓋，具體情況見(jiàn)表4。

表4 水域單元覆蓋情況

模型計(jì)算結(jié)果會(huì)導(dǎo)致最終雷達(dá)站的數(shù)量多于實(shí)際數(shù)量，這是因?yàn)榇嬖趥溆酶采w約束和雷達(dá)站最大監(jiān)測(cè)能力的約束。雖然成本會(huì)增加，但是提高了VTS對(duì)水域監(jiān)測(cè)的可靠性。

為進(jìn)一步說(shuō)明目標(biāo)函數(shù)的優(yōu)先級(jí)選取對(duì)選址方案的影響，將子目標(biāo)函數(shù)的優(yōu)先級(jí)變?yōu)镻2gt;P1，其他參數(shù)不變，結(jié)果雷達(dá)站候選點(diǎn)2，3，4，10被選，都配置型號(hào)1雷達(dá)，建站成本為99.3，水域單元可靠度之和為19.8，選址結(jié)果見(jiàn)圖7。

圖7 雷達(dá)站選址結(jié)果(第2目標(biāo)優(yōu)先)

對(duì)比圖6和圖7可知，選址方案的不同正是由2個(gè)目標(biāo)函數(shù)的優(yōu)先級(jí)變化導(dǎo)致的。

6 結(jié) 語(yǔ)

研究VTS雷達(dá)站選址及雷達(dá)配置問(wèn)題，考慮雷達(dá)對(duì)水域監(jiān)測(cè)的可靠性；基于備用覆蓋模型，建立了雷達(dá)站選址配置雙目標(biāo)優(yōu)化模型，并針對(duì)模型設(shè)計(jì)了遺傳算法。算例分析中的最終選址配置方案能夠?qū)崿F(xiàn)既定目標(biāo)；最終雷達(dá)站數(shù)量多于實(shí)際數(shù)量，這是因?yàn)榇嬖趥溆酶采w約束和雷達(dá)站最大監(jiān)測(cè)能力約束；目標(biāo)函數(shù)的優(yōu)先級(jí)會(huì)影響最終選址配置方案。接下來(lái)將研究更加精確的算法對(duì)模型進(jìn)行求解。

[1] TOREGA C， SWAIN R, REVELLE C. The Location of Emergency Service Facilities[J]. Operations Research, 1971, 19:1363-1373.

[2] CHUREH R L, MEADOW S B. Location Modeling Using Maximum Service Distance Criteria[J]. Geographical Analysis, 1979, 11:358-373.

[3] HOGAN K, REVELLE C. Concepts and Applications of Backup Coverage[J]. Management Science, 1986, 32:1434-1444.

[4] LEE G, MURRAY A T. Maximal Covering with Network Survivability Requirements in Wireless Mesh Networks[J]. Computers, Environment and Urban Systems, 2010, 34:49-57.

[5] ERDEMIR E T, BATTA R, SPIELMAN S,etal. Joint Ground and Air Emergency Medical Services Coverage Models: A Greedy Heuristic Solution Approach[J]. European Journal of Operational Research,2010, 207:736-749.

[6] BELL J E, GRIFFIS S E, CUNNINGHAM W A,etal. Location Optimization of Strategic Alert Sites for Homeland Defense[J]. Omega, 2011,39:151-158.

[7] 楊成龍. 3G基站選址中覆蓋問(wèn)題的研究[D].武漢：華中科技大學(xué),2011.

[8] 朱思峰,陳國(guó)強(qiáng),張新剛,等. 多目標(biāo)優(yōu)化量子免疫算法求解基站選址問(wèn)題[J]. 華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版,2012,40(1):49-53.

[9] 史云劍. 談VTS建設(shè)中雷達(dá)站的選址[J]. 航海技術(shù),2005(6):37-38.

[10] 曹德勝,呂靖,艾云飛,等. VTS雷達(dá)站選址問(wèn)題優(yōu)化模型[J]. 北京航空航天大學(xué)學(xué)報(bào), 2014, 40(6):727-731.

OptimizationModelofVTSRadarStationAllocationandRadarSystemConfiguration

AIYunfei,LYUJing,ZHANGLili,CAODesheng

(Transportation Management College, Dalian Maritime University, Dalian 116026, China)

Radar station allocation and radar system configuration,which have significant influence on the performance of a VTS system, are studied. To begin with, the multi-level fuzzy comprehensive evaluation method is used to choose the candidate points of radar stations. Then a bi-objective optimization model is built under the condition of ensuring radar monitoring reliability. The objectives are to minimize total construction cost, and to maximize monitoring reliability. The problem is converted into single objective problems by giving different priority to each objective and solved with a genetic algorithm. The method has been checked through analyzing an example system. The result shows that the design guarantees complete coverage of required water area with multi radar monitoring at the key water areas. The variation of the priority setting of the objective functions will change the output system scheme. The program has been run 10 times to check its consistency.

waterway transportation; VTS radar station; multi-level fuzzy comprehensive evaluation; allocation-configuration; reliability; genetic algorithm

2014-06-27

教育部哲學(xué)社會(huì)科學(xué)研究重大課題攻關(guān)項(xiàng)目(11JZD049)； 中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金(3132014311-4)

艾云飛(1987—)，男，河北唐山人，博士生，研究方向?yàn)榻煌ㄟ\(yùn)輸規(guī)劃與管理、應(yīng)急管理。E-mail：fair126aiyf@126.com

1000-4653(2014)04-0054-05

U698

A