基于LGN-VNS的多衛(wèi)星區(qū)域目標(biāo)覆蓋算法

伍 藝，余曉剛，夏 維

(1.合肥工業(yè)大學(xué) 管理學(xué)院，安徽 合肥 230009；2.北京市遙感信息研究所，北京 100192；3.過程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230009；4.智能互聯(lián)系統(tǒng)安徽省實(shí)驗(yàn)室，安徽 合肥 230009)

0 引言

使用衛(wèi)星進(jìn)行大面積區(qū)域目標(biāo)觀測是現(xiàn)代衛(wèi)星的常見應(yīng)用形式之一，隨著城市規(guī)劃和建設(shè)、大規(guī)模海洋搜索、區(qū)域搜救和農(nóng)林變化監(jiān)測等應(yīng)用場景的增加被逐漸廣泛應(yīng)用于各種領(lǐng)域[1-4]。一般來說，大多數(shù)應(yīng)用場景中的覆蓋需求有時(shí)間限制，對區(qū)域目標(biāo)的覆蓋往往很難由一顆衛(wèi)星單獨(dú)完成。在這種情況下，必須對多顆衛(wèi)星進(jìn)行協(xié)同規(guī)劃以提供區(qū)域覆蓋方案[5]。

多衛(wèi)星區(qū)域目標(biāo)覆蓋(Multi-satellite Regional Target Coverage，MSRTC)問題是一個(gè)與計(jì)算幾何高度耦合的NP-Hard衛(wèi)星資源調(diào)度問題[6]。解決MSRTC問題需要根據(jù)目標(biāo)區(qū)域信息和衛(wèi)星的參數(shù)來規(guī)劃衛(wèi)星在運(yùn)行到達(dá)目標(biāo)區(qū)域上空時(shí)的覆蓋姿態(tài)、單次覆蓋的起始時(shí)間以及結(jié)束時(shí)間。每顆衛(wèi)星的單次覆蓋范圍是一個(gè)覆蓋部分目標(biāo)的條帶狀區(qū)域，多星協(xié)同覆蓋的結(jié)果由單次覆蓋結(jié)果組合而成。MSRTC作為一個(gè)與計(jì)算幾何高度耦合的問題，需要進(jìn)行離散化處理。在對單個(gè)衛(wèi)星的覆蓋問題的研究中，Walton[7]將目標(biāo)區(qū)域劃分為幾個(gè)緊密排列的平行條帶。但由于不同衛(wèi)星的運(yùn)行軌道不平行，該方法僅適用于單顆衛(wèi)星覆蓋問題，不適合多顆衛(wèi)星覆蓋。在對多衛(wèi)星區(qū)域覆蓋問題的處理中，網(wǎng)格離散化方法是目前區(qū)域處理的常用手段[8]，Zhu等[9]甚至提出了基于網(wǎng)格的條帶構(gòu)造方法。然而，網(wǎng)格離散法在實(shí)際使用中很難直接確定最佳網(wǎng)格粒度，在大多數(shù)應(yīng)用中是憑借經(jīng)驗(yàn)確定網(wǎng)格粒度的[10-11]。值得注意的是，Hu等[12]提出了一種父子網(wǎng)格結(jié)構(gòu)，在父子網(wǎng)格結(jié)構(gòu)中，大粒度的父網(wǎng)格可以經(jīng)過劃分得到粒度較小的子網(wǎng)格?；谶@些研究，本文拓展了父子網(wǎng)格結(jié)構(gòu)，提出了一種局部劃分的網(wǎng)格嵌套(Local Grid Nesting，LGN)策略，有效降低冗余計(jì)算。

對于解決MSRTC問題中覆蓋方案的優(yōu)化方法，已有不少學(xué)者進(jìn)行了相關(guān)研究。賀仁杰[13]建立了2種調(diào)度模型，并設(shè)計(jì)了禁忌搜索和列生成2種算法。Wu等[14]將問題劃歸為生成任務(wù)集和任務(wù)規(guī)劃2個(gè)階段，提出了融合蟻群算法和局部搜索算法的方法。孫凱等[15]采取了學(xué)習(xí)型遺傳算法來解決該問題。盡管已有很多元啟發(fā)式方法被用于解決MSRTC問題，但該問題的NP-Hard特性及復(fù)雜性決定了對適用算法的研究仍有很大的發(fā)展空間。

變鄰域搜索(Variable Neighborhood Search，VNS)算法是一種局部搜索的啟發(fā)式算法?；谝粋€(gè)鄰域結(jié)構(gòu)的局部最優(yōu)解不一定是另一個(gè)鄰域結(jié)構(gòu)的局部最優(yōu)解的認(rèn)知，VNS的特點(diǎn)在于鄰域的設(shè)計(jì)和變換規(guī)則。VNS通過多個(gè)不同的鄰域動(dòng)作生成不同規(guī)模的鄰域，然后在多種鄰域內(nèi)交替搜索從而交替實(shí)現(xiàn)搜索到當(dāng)前解的局部范圍內(nèi)的最優(yōu)解和跳出局部最優(yōu)解。李志亮等[16]將離散差分進(jìn)化(Discrete Differential Evolution，DDE)與VNS算法相結(jié)合，提出了一種用于敏捷衛(wèi)星任務(wù)調(diào)度的算法。本文所提出的LGN策略能夠逐步細(xì)化對局部區(qū)域的離散，從而擴(kuò)展備選條帶集合，為VNS構(gòu)造新的搜索鄰域提供更大的變換空間。結(jié)合LGN策略，VNS的局部搜索特性能夠隨著搜索范圍的擴(kuò)展發(fā)揮出更大的效用。

本文提出了LGN策略，能夠?qū)πl(wèi)星覆蓋問題中的區(qū)域目標(biāo)進(jìn)行局部的離散，并結(jié)合VNS算法框架，設(shè)計(jì)了解決MSRTC問題的基于局部嵌套的變鄰域搜索(Variable Neighborhood Search Algorithm Based on Local Grid Nesting，LGN-VNS)算法，提供了解決MSRTC問題的有效算法。

1 問題描述與建模

1.1 MSRTC問題描述

在描述MSRTC問題之前，需要介紹一些相關(guān)概念。地面軌道為從衛(wèi)星運(yùn)行軌道到地球中心的直線與地球表面相交形成的曲線；覆蓋時(shí)間窗為衛(wèi)星飛越或接近目標(biāo)區(qū)域并能有效進(jìn)行目標(biāo)覆蓋的時(shí)間段，一個(gè)覆蓋時(shí)間窗的起止時(shí)間點(diǎn)分別被稱為最早覆蓋開始時(shí)間和最晚覆蓋結(jié)束時(shí)間；側(cè)擺角為衛(wèi)星在垂直于其軌道的平面上具有一定的側(cè)擺范圍，最大側(cè)擺角表示衛(wèi)星向一側(cè)擺動(dòng)到極限位置的角度；視場角為衛(wèi)星所攜帶的覆蓋傳感器的固定覆蓋角度，由傳感器配置決定，與衛(wèi)星的側(cè)擺角度無關(guān)；最大覆蓋區(qū)域?yàn)樵跈C(jī)會(huì)的最早覆蓋開始時(shí)間和最晚覆蓋結(jié)束時(shí)間內(nèi)，當(dāng)衛(wèi)星在2個(gè)方向上擺動(dòng)到最大側(cè)擺角時(shí)，衛(wèi)星可以覆蓋到的最大地面范圍；條帶為衛(wèi)星進(jìn)行一次掃描的覆蓋范圍，可表示為一個(gè)條帶，由可見區(qū)域平面上的一個(gè)矩形表示。由于衛(wèi)星可以在側(cè)擺的姿態(tài)下進(jìn)行覆蓋，因此條帶的位置可能被相應(yīng)的地面軌道穿過中心，也可能不與之相交，但始終與相應(yīng)的地面軌道平行。一個(gè)條帶的長度取決于覆蓋的開始和結(jié)束時(shí)間，寬度則由視場角、側(cè)擺角和衛(wèi)星高度共同決定。MSRTC問題的示意如圖1所示。

圖1 MSRTC問題示意Fig.1 MSRTC problem diagram

MSRTC問題的解由多個(gè)條帶構(gòu)成的覆蓋方案構(gòu)成。給出方案的過程就是確定各個(gè)衛(wèi)星到達(dá)每個(gè)覆蓋時(shí)間窗的覆蓋側(cè)擺角度，以及覆蓋的開始和結(jié)束時(shí)間。在本文中，MSRTC問題的目標(biāo)是利用相對不足的衛(wèi)星資源來盡可能地充分覆蓋目標(biāo)區(qū)域。因此，本文以目標(biāo)區(qū)域的有效覆蓋率最大為優(yōu)化目標(biāo)。有效覆蓋率是所有條帶的并集位于目標(biāo)區(qū)域內(nèi)的面積與目標(biāo)區(qū)域面積的比值。下文將針對該目標(biāo)進(jìn)行算法設(shè)計(jì)。

1.2 問題假設(shè)與轉(zhuǎn)化

在實(shí)際應(yīng)用中，衛(wèi)星在執(zhí)行覆蓋任務(wù)時(shí)會(huì)受到存儲(chǔ)容量、能量供應(yīng)、姿態(tài)調(diào)整和數(shù)據(jù)傳輸?shù)榷喾N因素的限制，本文進(jìn)行一些假設(shè)來簡化問題：

假設(shè)1：雖然衛(wèi)星地面軌道是彎曲的，但它們可以在較短的覆蓋時(shí)間內(nèi)近似為切向直線。這些近似的直線稱為地面軌道投影直線。

假設(shè)2：將一個(gè)覆蓋時(shí)間窗看作一個(gè)機(jī)會(huì)。每個(gè)機(jī)會(huì)都有其對應(yīng)的地面軌道投影直線、最早覆蓋開始時(shí)間和最晚覆蓋結(jié)束時(shí)間。

任何條帶的覆蓋開始時(shí)間、結(jié)束時(shí)間和側(cè)擺角度須滿足以下限制條件：

① 覆蓋開始時(shí)間和結(jié)束時(shí)間必須位于最早覆蓋開始時(shí)間和最晚覆蓋結(jié)束時(shí)間之內(nèi)；

② 覆蓋開始時(shí)間和結(jié)束時(shí)間的間隔不能超過衛(wèi)星的最長連續(xù)覆蓋時(shí)間；

③ 覆蓋側(cè)擺角不能超過衛(wèi)星的最大側(cè)擺角。

于是，對于同一個(gè)機(jī)會(huì)，不同的開始時(shí)間、結(jié)束時(shí)間和側(cè)擺角度的組合可以形成多個(gè)不同覆蓋范圍的備選條帶。來自同一個(gè)機(jī)會(huì)的一組條帶簇稱為備選條帶集合。同一個(gè)備選條帶集合中的條帶之間存在互斥關(guān)系：一旦確定一個(gè)條帶，將占用相應(yīng)的機(jī)會(huì)，同一機(jī)會(huì)的其他備選條帶將無法被選擇。

基于以上假設(shè)和簡化，MSRTC問題可以轉(zhuǎn)化為：根據(jù)目標(biāo)區(qū)域信息及衛(wèi)星參數(shù)，為所提供的衛(wèi)星覆蓋機(jī)會(huì)構(gòu)造備選條帶集合，并從每個(gè)機(jī)會(huì)的備選條帶集合中各選擇一個(gè)條帶，最終形成覆蓋方案。

1.3 問題建模

MSRTC問題建模涉及的符號(hào)及含義如表1所示。

表1 相關(guān)符號(hào)定義Tab.1 Definition of related symbols

決策變量：

目標(biāo)函數(shù)：

?i∈{1,2,…,|F|},?j∈{1,2,…,|Ci|},

?k∈{1,2,…,|Sij|}。

(1)

約束條件：

btijk≥Bij，

?i∈{1,2,…,|F|},?j∈{1,2,…,|Ci|},

?k∈{1,2,…,|Sij|}，

(2)

etijk≤Eij，

?i∈{1,2,…,|F|},?j∈{1,2,…,|Ci|},

?k∈{1,2,…,|Sij|}，

(3)

0≤etijk-btijk≤Tij，

?i∈{1,2,…,|F|},?j∈{1,2,…,|Ci|},

?k∈{1,2,…,|Sij|}，

(4)

lijk‖lij，

?i∈{1,2,…,|F|},?j∈{1,2,…,|Ci|},

?k∈{1,2,…,|Sij|}，

(5)

|ωijk|≤|Wij|，

?i∈{1,2,…,|F|},?j∈{1,2,…,|Ci|},

?k∈{1,2,…,|Sij|}，

(6)

?i∈{1,2,…,|F|},?j∈{1,2,…,|Ci|},

?k∈{1,2,…,|Sij|}。

(7)

式(1)表示目標(biāo)函數(shù)為每個(gè)選定條帶覆蓋區(qū)域的最大并集；式(2)表示覆蓋條帶的開始時(shí)間不得早于最早覆蓋開始時(shí)間Bij；式(3)表示覆蓋條帶的結(jié)束時(shí)間不得晚于最晚覆蓋結(jié)束時(shí)間Eij；式(4)表示覆蓋條帶的開始時(shí)間到結(jié)束時(shí)間的間隔不能超過最長覆蓋時(shí)間Tij；式(5)表示條帶的左邊界應(yīng)平行于相應(yīng)的地面軌道lij；式(6)表示條帶的側(cè)擺角不能超過相應(yīng)衛(wèi)星的最大側(cè)擺角Wi；式(7)表示每個(gè)機(jī)會(huì)選擇條帶的數(shù)量不多于1個(gè)。

1.4 基于網(wǎng)格的條帶構(gòu)造

基于上文對MSRTC問題的建模分析表明，解決該問題首先需要進(jìn)行有效的條帶構(gòu)造。理論上，覆蓋的開始和結(jié)束時(shí)間、衛(wèi)星偏轉(zhuǎn)角度等都是取值連續(xù)的量，會(huì)因此產(chǎn)生由連續(xù)的條帶簇組成的無限大的備選條帶集合。為了實(shí)現(xiàn)方案的可操作性，區(qū)域目標(biāo)需要進(jìn)行離散，常用的離散方法是網(wǎng)格離散法?；诰W(wǎng)格的條帶構(gòu)造法示意如圖2所示，目標(biāo)區(qū)域被離散成網(wǎng)格，網(wǎng)格中的每個(gè)正方形單元稱為一個(gè)單元格。

圖2 基于網(wǎng)格的條帶構(gòu)造法示意Fig.2 Diagram of strip construction algorithm based on grid

本文在網(wǎng)格化離散的基礎(chǔ)上，根據(jù)Zhu等[9]提出的基于網(wǎng)格的條帶構(gòu)造法構(gòu)造有限數(shù)量的條帶集合。基于網(wǎng)格的條帶構(gòu)造法通過在網(wǎng)格中選擇3個(gè)錨定單元格t，g和u，分別確定每個(gè)可行條帶的左邊界、上邊界和下邊界，再從覆蓋條帶反向確定觀測起止時(shí)間和側(cè)擺角度。無論是同一條帶還是不同條帶，錨定單元格可以被重復(fù)使用。圖2展示了一條斜率為負(fù)的條帶(形如“”)和一條斜率為正的條帶(形如“/”)。以前者為例說明一個(gè)條帶的構(gòu)造方法，后者的構(gòu)造方法與之類似：

已知機(jī)會(huì)cij和相應(yīng)的地面軌道投影直線lij，首先通過在每個(gè)單元格的左下頂點(diǎn)外形成一條平行于lij的直線來篩選出不違反最大側(cè)擺角約束的單元格。如果不違反約束，將這條線記為l1，并作為條帶的左邊界。一旦確定了條帶的左邊界l1，就可以根據(jù)式(8)計(jì)算出相應(yīng)的條帶寬度w(t)：

(8)

式中，dt為直線l1到lij的距離；hi為衛(wèi)星Fi所在的高度。

條帶的左邊界l1和條帶寬度w(t)已經(jīng)確定，可以相應(yīng)地確定條帶右邊界l2的位置。在lij上分別找到Bij和Eij時(shí)刻的對應(yīng)位置投影點(diǎn)PijB和PijE，并分別過PijB和PijE點(diǎn)做與lij垂直的直線lijB和lijE。最后，從直線lijB，lijE，l1和l2圍成的封閉區(qū)域內(nèi)選擇一對滿足以下條件的單元格g和u，經(jīng)過單元格g的左上頂點(diǎn)繪制一條垂直于lij的線并記為l3，經(jīng)過單元格u的右下頂點(diǎn)繪制一條垂直于lij的線并記為l4，衛(wèi)星到達(dá)l3和l4的時(shí)間間隔不得超過Tij。l3和l4分別形成條帶的上邊界和下邊界，衛(wèi)星相繼到達(dá)線l3，l4與lij的交叉點(diǎn)位置的時(shí)間，就是所構(gòu)造條帶的開始時(shí)間和結(jié)束時(shí)間。

基于網(wǎng)格的條帶構(gòu)造法就是在劃分的網(wǎng)格中找出所有符合上述條件的單元格組合，同時(shí)按照上述方法確定條帶的邊界及覆蓋范圍。構(gòu)造出的條帶之間允許重疊，但每個(gè)新生成的條帶應(yīng)與現(xiàn)有條帶進(jìn)行比較，以消除條帶集中的冗余。當(dāng)一條帶的覆蓋區(qū)域是另一條帶的子集時(shí)，需要?jiǎng)h除被包含的條帶。最終的覆蓋方案是從不同機(jī)會(huì)的條帶集合中分別選擇一個(gè)條帶作為對應(yīng)機(jī)會(huì)的實(shí)際覆蓋范圍。此外，本研究采用Vatti[17]提出的多邊形布爾運(yùn)算法計(jì)算所選條帶的并集，確定解的覆蓋范圍。

2 局部網(wǎng)格嵌套策略

根據(jù)條帶構(gòu)造方法可知，網(wǎng)格離散化的粒度是影響條帶數(shù)量的直接因素。在MSRTC問題中，當(dāng)網(wǎng)格劃分的粒度較大時(shí)，在此基礎(chǔ)上構(gòu)造出的條帶比較稀疏，不利于方案的組合。但是，當(dāng)網(wǎng)格劃分的粒度較小時(shí)，會(huì)產(chǎn)生數(shù)量較大的網(wǎng)格，隨之產(chǎn)生的條帶不僅數(shù)量較大，在位置上的排列也非常密集，還會(huì)在條帶構(gòu)造環(huán)節(jié)產(chǎn)生較大的計(jì)算負(fù)擔(dān)和搜索負(fù)擔(dān)。因此，本文提出了通過局部處理區(qū)域網(wǎng)格離散，控制網(wǎng)格數(shù)量減少冗余計(jì)算的LGN策略。

在Hu等[12]提出的父子網(wǎng)格中，一個(gè)區(qū)域可以先被劃分成粒度較大的網(wǎng)格作為父網(wǎng)格，通過對父網(wǎng)格的嵌套形成新的子網(wǎng)格。如果一次嵌套操作將一個(gè)單元格的邊長縮短到原來大小的1/2，父單元格將被分成4個(gè)子單元格；如果長度縮短到1/3，一個(gè)父單元格將產(chǎn)生9個(gè)子單元格。由此得到的子單元格也可以按照同樣的規(guī)則分裂下去。

這種父子網(wǎng)格結(jié)構(gòu)具有2個(gè)重要特性：第1，父單元格完全包含子單元格。這確保了不同層級(jí)的網(wǎng)格以及根據(jù)不同層級(jí)的網(wǎng)格構(gòu)造出的條帶可以共存。第2，在父網(wǎng)格中構(gòu)造的備選條帶在子網(wǎng)格中仍然是可行的。這意味著在給定的區(qū)域中，子單元格構(gòu)建的條帶集合完全包含父單元格構(gòu)建的條帶集合。嵌套網(wǎng)格意味著原始條帶集合的擴(kuò)展。根據(jù)這樣的性質(zhì)，本文將父子網(wǎng)格的嵌套應(yīng)用到局部網(wǎng)格區(qū)域，提出了LGN策略。

在LGN策略中，對一個(gè)局部區(qū)域LRcij的嵌套僅僅意味著機(jī)會(huì)cij具備了在新網(wǎng)格構(gòu)造條帶的條件。盡管局部區(qū)域間存在重疊，也不會(huì)影響到其他任何機(jī)會(huì)的條帶集合，以及其他機(jī)會(huì)對應(yīng)條帶的位置和覆蓋范圍。例如，如果2個(gè)機(jī)會(huì)c1和c2的局部區(qū)域LRc1和LRc2存在部分重疊，在對LRc1進(jìn)行局部嵌套時(shí)也會(huì)將重疊部分進(jìn)行分割。但是機(jī)會(huì)c2的網(wǎng)格層級(jí)并不因此發(fā)生變動(dòng)，也不會(huì)生成新的條帶，除非對LRc2單獨(dú)執(zhí)行嵌套。

根據(jù)本文所提出的LGN策略，對目標(biāo)區(qū)域進(jìn)行離散時(shí)不需要在起始階段就將整個(gè)區(qū)域完全劃分成眾多的小單元格，從而帶來過大的計(jì)算壓力；而是以一個(gè)較粗粒度的網(wǎng)格作為初級(jí)網(wǎng)格，在初級(jí)網(wǎng)格上構(gòu)造出可行的初始解，再以此為基礎(chǔ)根據(jù)需要對局部區(qū)域進(jìn)行細(xì)化。這個(gè)選擇局部區(qū)域進(jìn)行嵌套細(xì)化的操作可以自然地融合到局部搜索的過程中，根據(jù)搜索需要進(jìn)行局部嵌套，找到較優(yōu)的覆蓋方案。

3 基于局部網(wǎng)格嵌套的變鄰域搜索算法

3.1 變鄰域搜索算法

Hansen等[18]針對旅行商問題首次提出了變鄰域搜索算法，該算法是一種改進(jìn)的局部搜索算法，在求解大規(guī)模的組合優(yōu)化和全局優(yōu)化問題中性能良好。變鄰域搜索算法的思想基于以下基本事實(shí)：不同鄰域結(jié)構(gòu)之間的局部最優(yōu)解之間沒有必然聯(lián)系，全局最優(yōu)解是所有可能鄰域的局部最優(yōu)解。

① 構(gòu)造初始解X0，令最優(yōu)解Xb=X0。

② 若滿足終止條件，轉(zhuǎn)⑤；否則，隨機(jī)地從Xb的某一鄰域中選取解X作為變鄰域深度搜索的當(dāng)前解。

③ 令m=1，開始進(jìn)行變鄰域深度搜索。在X的Nm鄰域中進(jìn)行局部搜索，得到局部最優(yōu)解X′。

④ 如果X′優(yōu)于Xb，則更新Xb=X′，令m=1；否則，令m=m+1。

⑤ 若m<2，轉(zhuǎn)②；否則，輸出最優(yōu)解Xb。

3.2 LGN-VNS算法

根據(jù)LGN策略和VNS算法的特點(diǎn)，將二者進(jìn)行結(jié)合，提出了LGN-VNS算法。在LGN-VNS算法中，設(shè)計(jì)了2個(gè)鄰域結(jié)構(gòu)N1和N2，同時(shí)這些鄰域也在抖動(dòng)過程中使用。

3.2.1 鄰域結(jié)構(gòu)N1

3.2.2 鄰域結(jié)構(gòu)N2

與鄰域結(jié)構(gòu)N1相比，鄰域結(jié)構(gòu)N2替換的條帶更多，對當(dāng)前覆蓋方案的擾動(dòng)更大，增強(qiáng)了解的多樣性。

3.2.3 LGN-VNS算法步驟

③ 若滿足終止條件，則輸出最優(yōu)解；否則，從Xb的某一鄰域Nm中選取1個(gè)解X作為變鄰域深度搜索的當(dāng)前解。

④ 令m=1，Nm為當(dāng)前的鄰域結(jié)構(gòu)，在Nm中對X執(zhí)行局部搜索，直到得到局部最優(yōu)解X′。

⑤ 如果X′優(yōu)于Xb，則更新Xb=X′，令m=1；否則，令m=m+1。

⑥ 若m<2，轉(zhuǎn)③；否則，輸出最優(yōu)解Xb。

4 實(shí)驗(yàn)測試與結(jié)果

由于目前沒有MSRTC問題的公認(rèn)數(shù)據(jù)集，本文使用隨機(jī)生成的10個(gè)算例進(jìn)行實(shí)驗(yàn)測試。本節(jié)不僅驗(yàn)證了本文所提出的LGN-VNS算法對不同規(guī)模的算例的可行性；還通過與普通的VNS算法進(jìn)行對比，驗(yàn)證了LGN策略的有效性，最后通過與遺傳算法進(jìn)行對比，驗(yàn)證了LGN-VNS算法的有效性和高效性。

算例參數(shù)如表2所示。算例的區(qū)域規(guī)模有50 km×50 km，100 km×100 km，150 km×150 km，200 km×200 km和250 km×250 km 五種，所有算例的一個(gè)初始單元格均表示10 km×10 km的區(qū)域面積。隨著目標(biāo)區(qū)域面積的增加，相應(yīng)的機(jī)會(huì)數(shù)量也從5個(gè)逐漸增加到50個(gè)。為避免偶然因素，本文對以下實(shí)驗(yàn)都進(jìn)行了10次獨(dú)立重復(fù)。實(shí)驗(yàn)結(jié)果以覆蓋方案對目標(biāo)區(qū)域的有效覆蓋率為評(píng)價(jià)依據(jù)。所選條帶的并集和覆蓋方案的覆蓋率由多邊形布爾運(yùn)算法計(jì)算所得。本實(shí)驗(yàn)的測試平臺(tái)為具有24 GB RAM和運(yùn)行3.60 GHz 64位Windows10操作系統(tǒng)的IntelCorei7-7700處理器的PC，編程語言為C#。

表2 算例參數(shù)Tab.2 Parameters of instances

4.1 LGN-VNS算法求解MSRTC問題

首先，使用LGN-VNS算法進(jìn)行覆蓋方案規(guī)劃測試。圖3展示了LGN-VNS算法10次重復(fù)實(shí)驗(yàn)得到的最優(yōu)覆蓋方案，以及與最優(yōu)覆蓋方案相對應(yīng)的初始覆蓋方案。如圖3(b)表示LGN-VNS算法在算例1上尋找出的最優(yōu)覆蓋方案，圖3(a)表示該最優(yōu)覆蓋方案對應(yīng)的初始覆蓋方案。從圖3中不難看出，對于不同規(guī)模的算例，隨機(jī)生成的初始覆蓋方案經(jīng)過LGN-VNS算法的尋優(yōu)都得到了明顯提升。

(a) R1初始覆蓋方案 (b) R1最優(yōu)覆蓋方案

(c) R2初始覆蓋方案 (d) R2最優(yōu)覆蓋方案

(e) R3初始覆蓋方案 (f) R3最優(yōu)覆蓋方案

(g) R4初始覆蓋方案 (h) R4最優(yōu)覆蓋方案

(i) R5初始覆蓋方案 (j) R5最優(yōu)覆蓋方案

(k) R6初始覆蓋方案 (l) R6最優(yōu)覆蓋方案

(m) R7初始覆蓋方案 (n) R7最優(yōu)覆蓋方案

(o) R8初始覆蓋方案 (p) R8最優(yōu)覆蓋方案

(q) R9初始覆蓋方案 (r) R9最優(yōu)覆蓋方案

(s) R10初始覆蓋方案 (t) R10最優(yōu)覆蓋方案圖3 LGN-VNS算法所得最優(yōu)覆蓋方案Fig.3 Optimal coverage schemes obtained by LGN-VNS algorithm

表3記錄了LGN-VNS算法所得的最優(yōu)方案覆蓋率、對應(yīng)的初始方案覆蓋率、提升覆蓋率以及相對提升率。其中，相對提升率為最優(yōu)方案與對應(yīng)初始方案之間覆蓋率的差值與初始方案覆蓋率的比值。由表3可以看出，相較于初始方案，LGN-VNS算法的提升效果十分明顯，平均提升覆蓋率為29.87%，在其中的3個(gè)算例中甚至出現(xiàn)了40%以上的提升。平均相對提升率高達(dá)64.83%，其中的2個(gè)方案相對于其初始方案得到了100%以上的相對提升。

表3 LGN-VNS算法所得最優(yōu)方案及其提升率Tab.3 Optimal solution obtained by LGN-VNS algorithm and their lifting rate 單位：%

4.2 LGN-VNS與VNS算法比較分析

LGN-VNS與VNS算法所得解的平均覆蓋率及差值如表4所示。由表4可以看出，LGN-VNS所得方案的平均覆蓋率遠(yuǎn)高于VNS算法?？傮w平均覆蓋率之差為14.27%，在其中的4個(gè)算例中達(dá)到了20%以上的差距。

表4 VNS，LGN-VNS平均覆蓋率及差值Tab.4 Average solution results of VNS algorithm，LGN-VNS algorithm and the difference 單位：%

LGN-VNS與VNS的平均提升覆蓋率對比如表5所示。由表5可以看出，LGN-VNS的平均提升率均值達(dá)29.73%，同樣遠(yuǎn)高于VNS算法的16.38%，提升覆蓋率的平均差值為13.34%。對于算例3，兩算法的平均提升率之差甚至達(dá)到了33.72%。充分證明了LGN-VNS的搜索能力優(yōu)于VNS，驗(yàn)證了LGN策略的有效性。

表5 VNS，LGN-VNS提升覆蓋率均值及差值Tab.5 Average lift rate of VNS algorithm， LGN-VNS algorithm and the difference 單位：%

4.3 LGN-VNS與遺傳算法的比較分析

為了驗(yàn)證LGN-VNS算法的有效性，將其與遺傳算法(GA)進(jìn)行了求解效果和求解時(shí)間上的比較。在GA中采用同樣方式獲得初始解。GA的種群規(guī)模設(shè)置為10，最大迭代次數(shù)設(shè)置為100，當(dāng)連續(xù)20代的種群最優(yōu)解不發(fā)生改變時(shí)，迭代自動(dòng)結(jié)束。

LGN-VNS算法與GA的平均覆蓋率及求解時(shí)間對比如表6所示。由表6可以看出，LGN-VNS算法在所有算例中得到的覆蓋方案，不僅結(jié)果都明顯好于GA，而且所用時(shí)間也明顯短于GA。LGN-VNS算法的求解均值整體高于GA14.40%，但整體求解時(shí)間僅為GA的36.44%。這表明LGN-VNS算法能夠較快地得到質(zhì)量較高的解，充分體現(xiàn)了LGN-VNS算法的有效性和高效性。

表6 LGN-VNS，GA平均覆蓋率及求解時(shí)間Tab.6 Average coverage rate and solution time of LGN-VNS algorithm and GA algorithm

5 結(jié)束語

本文分析了MSRTC問題中區(qū)域目標(biāo)的離散精度對覆蓋方案的最優(yōu)性和獲得方案的復(fù)雜程度的影響，在網(wǎng)格離散法和基于網(wǎng)格的條帶生成法的基礎(chǔ)上，改進(jìn)了父子網(wǎng)格嵌套機(jī)制，提出了一種局部網(wǎng)格嵌套的LGN策略；并結(jié)合VNS搜索算法，提出了LGN-VNS算法。

對10個(gè)規(guī)模不同的隨機(jī)算例進(jìn)行的測試實(shí)驗(yàn)表明，LGN-VNS算法對MSRTC問題的搜索性能提升非常明顯，對隨機(jī)生成的測試算例表現(xiàn)出平均提升覆蓋率為29.73%的提升效果，遠(yuǎn)遠(yuǎn)高于普通VNS算法的16.38%。另外，在對10個(gè)隨機(jī)算例的實(shí)驗(yàn)中，LGN-VNS算法的求解結(jié)果全部高于普通VNS算法，平均高出14.27%。不僅如此，LGN-VNS算法在求解效果和求解效率方面都好于GA，表現(xiàn)出了明顯的優(yōu)越性。

經(jīng)實(shí)驗(yàn)驗(yàn)證，本文提出的LGN-VNS算法在求解MSRTC問題方面具有明顯的優(yōu)勢，能夠在較短的時(shí)間內(nèi)得到相對不充足的衛(wèi)星覆蓋資源下高覆蓋率的區(qū)域目標(biāo)覆蓋方案。