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

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

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

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

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

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

水路運輸； VTS雷達站； 多層次模糊綜合評價； 選址-配置； 可靠性； 遺傳算法

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

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

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

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

1 VTS雷達站選址問題描述

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

圖1 VTS雷達站選址

假設(shè)條件：

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

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

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

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

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

2 雷達站候選點初選

通過對VTS雷達站建設(shè)進行實際調(diào)研，建立雷達站候選點綜合評價指標(biāo)體系(見圖2)。

圖2 雷達站候選點評價指標(biāo)體系

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

3 模型建立

3.1參數(shù)說明

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

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

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

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

(1)

3.3模型建立

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

(2)

(3)

約束條件為

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

4 求解算法設(shè)計

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

4.1染色體編碼

采用二進制編碼方式，染色體見圖4。1,2,…,n為對應(yīng)的雷達站候選位置，1,2,…,m為每個雷達站的候選雷達型號，染色體總長度為nm。

圖4 染色體示例

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

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

4.3精英保留策略

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

4.4懲罰函數(shù)

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

4.5遺傳算子和終止條件

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

5 算例分析

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

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

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

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

表2 雷達站候選點數(shù)據(jù)

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

圖5 遺傳算法迭代圖

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

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

表4 水域單元覆蓋情況

模型計算結(jié)果會導(dǎo)致最終雷達站的數(shù)量多于實際數(shù)量，這是因為存在備用覆蓋約束和雷達站最大監(jiān)測能力的約束。雖然成本會增加，但是提高了VTS對水域監(jiān)測的可靠性。

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

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

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

6 結(jié) 語

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

[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基站選址中覆蓋問題的研究[D].武漢：華中科技大學(xué),2011.

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

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

[10] 曹德勝,呂靖,艾云飛,等. VTS雷達站選址問題優(yōu)化模型[J]. 北京航空航天大學(xué)學(xué)報, 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é)社會科學(xué)研究重大課題攻關(guān)項目(11JZD049)； 中央高?；究蒲袠I(yè)務(wù)費專項資金(3132014311-4)

艾云飛(1987—)，男，河北唐山人，博士生，研究方向為交通運輸規(guī)劃與管理、應(yīng)急管理。E-mail：fair126aiyf@126.com

1000-4653(2014)04-0054-05

U698

A