VTS雷達站選址-雷達配置優化模型

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

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

VTS雷達站選址-雷達配置優化模型

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

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

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

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

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

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

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

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

1 VTS雷達站選址問題描述

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

圖1 VTS雷達站選址

假設條件：

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

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

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

4. 雷達對目標進行監測時有一定可靠性，當水域單元被多個雷達站覆蓋時，可靠性采用并聯系統可靠性計算方法來計算。

5. 為保障重點水域的通航安全，重點水域單元要同時被多個VTS雷達站覆蓋。總成本主要包括雷達站建站成本、線路鋪設成本、雷達配置成本，問題的2個目標是總成本最小、水域單元被監測的可靠性之和最大。

2 雷達站候選點初選

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

圖2 雷達站候選點評價指標體系

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

3 模型建立

3.1參數說明

3.2水域單元被有效監測的可靠性

假設能夠覆蓋水域單元i的雷達站有n個，則水域i能被有效監測的必要條件為至少有1個雷達站能夠對其進行有效監測，此系統為并聯系統，系統框圖見圖3。

圖3 并聯系統框圖

水域單元i被有效監測的可靠性為

(1)

3.3模型建立

基于以上變量解釋，數學模型的目標函數為

(2)

(3)

約束條件為

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

4 求解算法設計

多目標優化問題與單目標優化問題的本質區別在于其解不唯一，而是存在一個由眾多Pareto最優解組成的最優解集合。依據各個目標的優先級，將多目標問題轉換為單目標問題，該問題亦屬于NP-Hard問題，針對模型設計遺傳算法進行求解。

4.1染色體編碼

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

圖4 染色體示例

4.2初始化種群及適應度函數

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

4.3精英保留策略

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

4.4懲罰函數

當出現不滿足約束條件的個體時，需要對其適應度進行懲罰，將該個體的適應度減去常數P，即f′=f-P，降低其進入下一代的概率。

4.5遺傳算子和終止條件

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

5 算例分析

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

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

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

表1 水域單元數據

表2 雷達站候選點數據

表3 雷達數據

圖5 遺傳算法迭代圖

圖6 雷達站選址結果(第1目標優先)

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

表4 水域單元覆蓋情況

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

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

圖7 雷達站選址結果(第2目標優先)

對比圖6和圖7可知，選址方案的不同正是由2個目標函數的優先級變化導致的。

6 結 語

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

[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].武漢：華中科技大學,2011.

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

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

[10] 曹德勝,呂靖,艾云飛,等. VTS雷達站選址問題優化模型[J]. 北京航空航天大學學報, 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

教育部哲學社會科學研究重大課題攻關項目(11JZD049)； 中央高校基本科研業務費專項資金(3132014311-4)

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

1000-4653(2014)04-0054-05

U698

A