基于LINGO模型的VTS雷達(dá)站選址-配置

孫耀華， 戴 冉， 張超越， 劉高磊， 趙延鵬， 張 鋒

(大連海事大學(xué) 航海學(xué)院，遼寧 大連 116026)

船舶交通管理(Vessel Traffic Services，VTS)系統(tǒng)的主要功能是搜集和處理船舶交通信息，從而對(duì)水域內(nèi)的船舶實(shí)施監(jiān)控和組織管理。[1]作為VTS系統(tǒng)的重要組成部分，VTS雷達(dá)站的選址和雷達(dá)設(shè)備的配置在很大程度上影響著VTS系統(tǒng)功能的發(fā)揮。研究VTS雷達(dá)站選址和配置問題，需綜合考慮雷達(dá)站的建設(shè)成本、雷達(dá)的探測(cè)性能和最終的覆蓋效果等因素，最后在成本盡可能小的情況下達(dá)到覆蓋效果最優(yōu)的目標(biāo)。

目前對(duì)雷達(dá)站選址-配置問題的研究比較少。TOREGAS等[2]提出集合覆蓋思想，在滿足覆蓋要求的條件下使建站數(shù)量最少；CHURCH等[3]提出最大覆蓋的思想，在服務(wù)站數(shù)量已知的前提下，達(dá)到最大覆蓋的效果；史云劍[4]研究雷達(dá)站的盲區(qū)問題，并給出雷達(dá)最大作用距離和最小作用距離的計(jì)算方法，但沒有提出選址的具體模型；曹德勝等[5]運(yùn)用模糊綜合評(píng)價(jià)方法對(duì)備選雷達(dá)站進(jìn)行初選，建立雷達(dá)站選址雙目標(biāo)模型，設(shè)計(jì)遺傳算法求解；艾云飛等[6]建立雷達(dá)站選址-配置優(yōu)化模型，賦予目標(biāo)優(yōu)先級(jí)并設(shè)計(jì)遺傳算法求解。

綜上所述，當(dāng)前對(duì)VTS雷達(dá)站選址-配置問題的研究較少，方法較單一。由于雷達(dá)站選址-配置問題屬于多目標(biāo)優(yōu)化的最小生成樹(Minimal Spanning Tree, MST)問題，而交互式線性和通用優(yōu)化求解器(Linear Interactive and General Optimizer，LINGO)是解決MST問題的一種有效方法，因此本文借助LINGO建立VTS雷達(dá)站選址-配置雙目標(biāo)優(yōu)化模型來求解該問題。

1 LINGO介紹

LINGO是一種專門求解最優(yōu)化問題的軟件包，擁有一系列完全內(nèi)置的求解程序[7]，主要功能包括構(gòu)建線性、非線性和整數(shù)最優(yōu)化模型、讀取和寫入Excel及數(shù)據(jù)庫等。由于LINGO擁有方便構(gòu)建和維護(hù)交互式模型、方便進(jìn)行數(shù)據(jù)輸入和輸出選擇及求解器功能強(qiáng)大等優(yōu)勢(shì)，使得其應(yīng)用越來越廣泛。諸如錨位數(shù)計(jì)算問題、旅行商問題(Traveling Salesman Problem，TSP)、最短路問題和物流配送中心選址問題等多目標(biāo)規(guī)劃問題都能通過LINGO得到解決或優(yōu)化。[8-11]

2 VTS雷達(dá)站選址-配置問題描述

假設(shè)條件：

1) 隨機(jī)劃分若干個(gè)水域單元，各水域單元的重要程度已知。

2) 雷達(dá)有一定的作用距離，水域單元只有存在于該型號(hào)雷達(dá)的最大作用距離和最小作用距離之內(nèi)，才能表示被覆蓋。

3) 每個(gè)雷達(dá)站可建立點(diǎn)最多只能建立1個(gè)雷達(dá)站，且每個(gè)雷達(dá)站最多只能配置1種型號(hào)的雷達(dá)。

4) 不同雷達(dá)的檢測(cè)穩(wěn)定性不同，容易受天氣、海況和地形等外界因素的干擾，使得其覆蓋穩(wěn)定性有一定的差異。需被多重覆蓋的重點(diǎn)水域是指由于建筑物、島嶼等物體的遮擋而產(chǎn)生盲區(qū)，從而需多臺(tái)雷達(dá)進(jìn)行覆蓋的水域。

5) 總成本包括雷達(dá)成本、雷達(dá)站建設(shè)成本和線路鋪設(shè)成本。

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

3.1 引入?yún)?shù)

E為水域單元編號(hào),e=1,2,…,E;F為雷達(dá)站可建立點(diǎn)編號(hào),f=1,2,…,F；H為VTS中心;Lf為f雷達(dá)站配置雷達(dá)的最大探測(cè)距離;lf為f雷達(dá)站的最小探測(cè)距離;Def為水域單元e與雷達(dá)站f之間的距離,當(dāng)lf≤Def≤Lf時(shí)，水域單元e被雷達(dá)站f覆蓋;Dfh為雷達(dá)站可建立點(diǎn)到VTS中心的距離;NF={f|lf≤Def≤Lf}為能覆蓋水域e的雷達(dá)站集合;NE={e|lf≤Def≤Lf}為能被雷達(dá)站覆蓋的水域單元集合;i為0-1變量，若水域單元e被覆蓋2次以上，則ie=1,反之ie=0；j為0-1變量，若雷達(dá)站可建立點(diǎn)f被選中，則jf=1,反之jf=0；Yf為0-1變量，若選中f雷達(dá)站，且配備雷達(dá)，則Yf=1，反之Yf=0；qe為水域單元e的重要性，其大小反映水域單元是否被遮擋，需多重覆蓋來消除盲區(qū)；Q為閾值，若qe≥Q,則水域單元e需至少覆蓋2次；xe為水域單元e的船舶流量；Xf為雷達(dá)可建立點(diǎn)f配置雷達(dá)的最大監(jiān)測(cè)能力；λf為雷達(dá)監(jiān)測(cè)的穩(wěn)定性；μe為水域單元e被監(jiān)測(cè)的穩(wěn)定性；Af為單個(gè)雷達(dá)站的建設(shè)成本；B為雷達(dá)站到VTS中心每公里線路的鋪設(shè)成本；C為雷達(dá)的成本；δ為成本最小目標(biāo)函數(shù)的優(yōu)先度；1-δ為穩(wěn)定性最高目標(biāo)函數(shù)的優(yōu)先度。

在當(dāng)前大學(xué)教育強(qiáng)調(diào)全面發(fā)展和創(chuàng)新性思維階段，以及高校建設(shè)“雙一流”背景下，注重高校本科生畢業(yè)論文的選題，注重高校本科生專業(yè)綜合素質(zhì)能力的提升，既有助于提高大學(xué)生的職業(yè)生存能力和社會(huì)競(jìng)爭(zhēng)力，也有利于促進(jìn)高校審視學(xué)科發(fā)展和專業(yè)培養(yǎng)人才的模式，從而為國家和社會(huì)輸送專業(yè)能力強(qiáng)、素質(zhì)過硬、具有探索和創(chuàng)新精神的復(fù)合型人才。高校本科畢業(yè)論文的指導(dǎo)工作任重道遠(yuǎn)，仍然需要一線教學(xué)和教務(wù)人員不斷探索和實(shí)踐完善?！?/p>

3.2 建立模型

根據(jù)以上引入的變量建立目標(biāo)函數(shù)，有

(1)

(2)

(3)

Z=δmin ?+(1-δ)maxη

(4)

式(1)表示總成本最小，包括雷達(dá)成本、雷達(dá)站的建設(shè)成本和被選雷達(dá)站到VTS中心的線路鋪設(shè)成本；式(2)表示水域單元被有效監(jiān)測(cè)的穩(wěn)定性；式(3)表示水域單元被有效監(jiān)測(cè)的穩(wěn)定性之和最大；式(4)表示賦予2個(gè)目標(biāo)優(yōu)先級(jí)。

模型的目標(biāo)函數(shù)需滿足約束條件

(5)

(6)

(7)

ie,jf,Yf∈{0,1}

(8)

式(5)表示每個(gè)水域單元至少被覆蓋1次，即全面覆蓋；式(6)表示由于建筑物、島嶼等原因存在雷達(dá)覆蓋盲區(qū)的水域單元至少被覆蓋2次，即重點(diǎn)水域的多重覆蓋；式(7)表示水域單元的船舶流量不超過雷達(dá)站的最大監(jiān)測(cè)能力；式(8)表示變量服從0-1約束。

4 LINGO實(shí)現(xiàn)的算例及分析

4.1 算例參數(shù)信息

假定將某港口水域劃分為20個(gè)單元，各單元位置坐標(biāo)已知。VTS雷達(dá)站可建立點(diǎn)有8個(gè)，位置坐標(biāo)已知。VTS中心坐標(biāo)已知。最多設(shè)立4個(gè)雷達(dá)站，每公里線路鋪設(shè)成本為1，水域單元的重要度閾值為5。[12]水域單元參數(shù)見表1，VTS雷達(dá)站可建立點(diǎn)參數(shù)見表2，雷達(dá)參數(shù)見表3。

表1 水域單元參數(shù)

表2 雷達(dá)站可建立點(diǎn)參數(shù)

4.2 算例分析

運(yùn)用LINGO求解模型，賦予雙目標(biāo)優(yōu)先級(jí)。

1) 取δ=0.5，即雙目標(biāo)優(yōu)先級(jí)相同。運(yùn)行結(jié)果顯示，1號(hào)、3號(hào)、5號(hào)和8號(hào)雷達(dá)站可建立點(diǎn)被選中，結(jié)果達(dá)到水域單元完全覆蓋和因建筑物、島嶼等遮蔽而存在盲區(qū)的重點(diǎn)水域多重覆蓋的目標(biāo)。VTS雷達(dá)站建設(shè)成本為100.2，水域單元被監(jiān)測(cè)的穩(wěn)定性之和為42.5。VTS雷達(dá)站選址-配置結(jié)果見圖2。各水域單元覆蓋情況見表4。VTS中心坐標(biāo)為(5,0)。

表3 雷達(dá)參數(shù)

編號(hào)重要度覆蓋次數(shù)編號(hào)重要度覆蓋次數(shù)13211432421262322133243214325621542683167275217418421852962194210442032

2) 取δ=0.8，即成本目標(biāo)優(yōu)先于穩(wěn)定性目標(biāo)。運(yùn)行結(jié)果顯示，1號(hào)、4號(hào)、7號(hào)和8號(hào)雷達(dá)站可建立點(diǎn)被選中，結(jié)果達(dá)到水域單元完全覆蓋和因建筑物、島嶼等遮蔽而存在盲區(qū)的重點(diǎn)水域多重覆蓋的目標(biāo)。VTS雷達(dá)站建設(shè)成本為98.4，重點(diǎn)水域多重覆蓋的穩(wěn)定性為36.9。VTS雷達(dá)站選址-配置結(jié)果見圖3。各水域單元覆蓋情況見表5。

3) 取δ=0.2，即穩(wěn)定性目標(biāo)優(yōu)先于成本目標(biāo)。運(yùn)行結(jié)果顯示，3號(hào)、4號(hào)、5號(hào)和6號(hào)雷達(dá)站可建立點(diǎn)被選中，結(jié)果達(dá)到水域單元完全覆蓋和因建筑物、島嶼等遮蔽而存在盲區(qū)的重點(diǎn)水域多重覆蓋的目標(biāo)。VTS雷達(dá)站建設(shè)成本為107.6，水域單元被監(jiān)測(cè)的穩(wěn)定性之和為51.3。VTS雷達(dá)站選址-配置結(jié)果見圖4。各單元水域覆蓋情況見表6。

編號(hào)重要度覆蓋次數(shù)編號(hào)重要度覆蓋次數(shù)13111442421262322133343214335621543682167275217428421853963194310442032

通過3次運(yùn)算發(fā)現(xiàn)，運(yùn)行結(jié)果隨著δ值的變化而變化，說明目標(biāo)優(yōu)先級(jí)會(huì)對(duì)選址-配置結(jié)果產(chǎn)生影響。為得到更可靠的結(jié)論，分別取δ=0,0.1,0.2,…,1.0，得到不同的選址-配置方案，運(yùn)行結(jié)果見表7。

由運(yùn)行結(jié)果可知，最終的方案均實(shí)現(xiàn)了水域單元的全面覆蓋和因建筑物、島嶼等遮蔽而存在盲區(qū)的重點(diǎn)水域多重覆蓋的目標(biāo)。δ值不同，運(yùn)行結(jié)果不同，說明雙目標(biāo)的優(yōu)先級(jí)會(huì)影響最終的選址-配置方案，且隨著δ值的不斷增大(即成本目標(biāo)的優(yōu)先度越來越高，穩(wěn)定性目標(biāo)的優(yōu)先度越來越低)，總成本和穩(wěn)定性的變化基本上呈遞減的趨勢(shì)，符合模型假設(shè)和實(shí)際情況。將程序運(yùn)行20次，結(jié)果穩(wěn)定，說明模型具有可行性。

表6 δ=0.2時(shí)水域單元覆蓋情況

表7 選址-配置結(jié)果

5 結(jié)束語

1)創(chuàng)新性地將LINGO引入到VTS雷達(dá)站選址-配置問題的求解中。運(yùn)用LINGO建立雙目標(biāo)優(yōu)化模型并求解出可靠運(yùn)行結(jié)果。結(jié)果穩(wěn)定，易于實(shí)現(xiàn)，模型具有可行性。

2)綜合考慮水域遮蔽物、雷達(dá)盲區(qū)、雷達(dá)作用距離、建設(shè)成本和水域船舶流量對(duì)雷達(dá)選址-配置的影響，所得結(jié)果對(duì)實(shí)際工作中雷達(dá)的選址-配置有指導(dǎo)意義。在具體實(shí)施過程中，根據(jù)實(shí)際情況選擇不同的優(yōu)先級(jí)，實(shí)施不同的方案。

[1] 易中立. 基于宜昌VTS雷達(dá)站的船用雷達(dá)交管化研究[D].大連：大連海事大學(xué),2010.

[2] TOREGAS C, SWAIN R, REVELLE C, et al. The Location of Emergency Service Facilities[J]. Operations Research, 1971, 19(6):1363-1373.

[3] CHURCH R L, MEADOWS M E. Location Modeling Utilizing Maximum Service Distance Criteria[J]. Geographical Analysis, 2010, 11(4):358-373.

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

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

[6] 艾云飛,呂靖,張麗麗,等. VTS雷達(dá)站選址-雷達(dá)配置優(yōu)化模型[J]. 中國航海,2014,37(4):54-58.

[7] 楊松姍,張金中.利用LINGO模型進(jìn)行錨位數(shù)計(jì)算的探討[J]. 港工技術(shù), 2016,53(4):29-30.

[8] 吳希. LINGO軟件在貨物運(yùn)輸問題中的應(yīng)用[J]. 中國商論,2016(25):71.

[9] 陳允峰. 利用lingo軟件解決最短路問題的兩種方法[J].信息技術(shù)與信息化,2015(10):141-142.

[10] 吳有平,劉杰,何杰. 多目標(biāo)規(guī)劃的LINGO求解法[J]. 湖南工業(yè)大學(xué)學(xué)報(bào),2012,26(3):9-12.

[11] 徐麗蕊. 基于LINGO的城市物流配送路徑優(yōu)化[J].電子設(shè)計(jì)工程,2013,21(22):52-54.

[12] 曹德勝. 我國VTS績(jī)效評(píng)價(jià)與雷達(dá)站選址研究[D].大連:大連海事大學(xué),2014.