“多對多”模式下GEO 衛(wèi)星在軌加注任務(wù)規(guī)劃

韓 鵬，李興龍，李傳江，智 慧

（1.哈爾濱工業(yè)大學(xué) 航天學(xué)院，黑龍江 哈爾濱 150001；2.上海宇航系統(tǒng)工程研究所，上海 201109）

0 引言

近年來，隨著人類太空探索活動的不斷增加，在軌服務(wù)技術(shù)得到了大量關(guān)注。利用在軌服務(wù)技術(shù)可以極大地延伸各類在軌航天器的運行壽命，大大提高了經(jīng)濟效益。在軌加注作為在軌服務(wù)技術(shù)中的一種，同樣受到了廣泛的關(guān)注，并取得了長足的發(fā)展。許多國家相繼完成了在軌加注任務(wù)的在軌實驗驗證，如我國的“天源一號”、美國的“任務(wù)延壽飛行器”等?，F(xiàn)有的在軌加注模式多為“一對一”加注，其仍具有較高的成本。未來，隨著航天技術(shù)的發(fā)展和對在軌服務(wù)運營成本的進一步控制，在軌加注的模式將由“一對一”逐步發(fā)展成為“一對多”“多對多”的加注模式，這就對在軌加注的任務(wù)規(guī)劃和軌道機動優(yōu)化帶來了進一步的挑戰(zhàn)。

運行在地球同步軌道的衛(wèi)星通常具有高價值、高成本的特點，承擔(dān)著預(yù)警、通信、氣象檢測等重要任務(wù)。因此，為同步軌道衛(wèi)星設(shè)置在軌加注系統(tǒng)，以延長其服務(wù)壽命是非常必要且具有經(jīng)濟效益的。

許多學(xué)者針對不同模式下的在軌加注任務(wù)規(guī)劃問題展開了研究。歐陽琦等率先研究了“多對多”場景下地球同步軌道（Geostationary Earth Orbit，GEO）衛(wèi)星的在軌加注任務(wù)規(guī)劃問題，采用遺傳算法（Genetic Algorithm，GA）對問題進行求解；ZHANG 等在考慮J2 攝動和時間窗口約束的前提下，研究了同一軌道上服務(wù)星為目標星實施在軌加注的任務(wù)規(guī)劃問題；ZHOU研究了“太空站-服務(wù)星-目標星”模式下的GEO 衛(wèi)星在軌加注任務(wù)規(guī)劃問題，并通過兩組典型算例驗證了算法的有效性；在文獻［8］的基礎(chǔ)上，文獻［9］進一步研究了具有多個太空站的GEO 衛(wèi)星在軌加注任務(wù)規(guī)劃問題，仿真結(jié)果表明，所提出的算法能適用于規(guī)模更大的問題；CHEN 等研究了將P2P（Peer-to-Peer）與“多對多”模式相結(jié)合的混合策略下的在軌加注任務(wù)規(guī)劃問題；文獻［11］研究了服務(wù)星和目標星相互協(xié)作，同時展開軌道機動模式下的在軌加注問題，仿真實驗表明，協(xié)作模式相比常規(guī)的“多對多”模式更加節(jié)省燃料。

綜合以上文獻，不同學(xué)者針對在軌加注場景提出了多種加注模式，包括“太空站-服務(wù)星-目標星”模式、P2P 模式、“服務(wù)星-目標星相互協(xié)作”模式等?；诂F(xiàn)有的航天技術(shù)，實現(xiàn)復(fù)雜的在軌加注模式難度較大，且成本較高，因此，“一對多”“多對多”的在軌加注模式仍是最具可行性的在軌服務(wù)模式，研究“多對多”模式下的在軌加注任務(wù)規(guī)劃問題仍具有重要意義。本文將借鑒VRP（Vehicle Route Planning）問題中的建模方式，將“多對多”在軌服務(wù)場景表示為一張完全有向圖，基于完全有向圖建立在軌加注任務(wù)規(guī)劃模型，并在此基礎(chǔ)上，給出軌道轉(zhuǎn)移燃料消耗計算模型。

現(xiàn)有文獻中，任務(wù)規(guī)劃問題的求解算法多基于元啟發(fā)式智能優(yōu)化算法，并針對問題特性對算法進行適當(dāng)改進，如遺傳算法、粒子群算法、蟻群算法等。這類算法的特點是靈活性強，便于處理各類復(fù)雜的約束條件，但存在局部搜索能力較差、易陷入局部最優(yōu)的缺陷。針對以上缺陷，本文基于遺傳算法，設(shè)計了一種將大鄰域搜索（Large Neighbourhood Search，LNS）算法和遺傳算法相結(jié)合的混合啟發(fā)式算法（Large Neighbourhood Search-Genetic Algorithm，LNS-GA）。該算法利用大鄰域搜索算法中的“破壞”和“修復(fù)”思想，對遺傳算法每一代種群中的精英個體進行進一步的迭代搜索，從而增強算法的局部搜索能力。最后，通過仿真對比實驗驗證了本文所提出算法的有效性和優(yōu)越性。

1 任務(wù)規(guī)劃模型建立

1.1 “多對多”在軌加注任務(wù)場景描述

如圖1 所示，在“多對多”在軌加注任務(wù)場景中，若干個燃料消耗殆盡的目標衛(wèi)星運行于GEO 圓軌道，每個目標衛(wèi)星具有確定的燃料加注需求，但其軌道半長軸、軌道傾角、升交點赤經(jīng)、定點經(jīng)度等參數(shù)存在差異。若干個規(guī)格完全相同的服務(wù)航天器被同樣部署至GEO 圓軌道上，其攜帶固定容量的燃料，燃料可加注給目標衛(wèi)星，也可用于自身軌道機動。每個服務(wù)航天器干重相同，并且攜帶1 臺比沖固定的發(fā)動機用于變軌。服務(wù)航天器需依次轉(zhuǎn)移至目標衛(wèi)星附近，與目標衛(wèi)星完成對接，并為其加注燃料。在完成既定任務(wù)后，服務(wù)航天器離開目標衛(wèi)星進入停泊軌道待命。進行任務(wù)規(guī)劃的目的是為每個服務(wù)航天器預(yù)先確定最優(yōu)的服務(wù)目標和服務(wù)順序，在保證所有目標衛(wèi)星均可被加注燃料的前提下，最小化服務(wù)所有航天器的燃料消耗。

圖1 “多對多”在軌加注任務(wù)場景Fig.1 Many-to-many on-orbit refueling mission scenario

1.2 任務(wù)規(guī)劃模型

如圖2 所示，可將“多對多”在軌加注場景中的所有服務(wù)航天器和目標衛(wèi)星表示為一個完全有向圖=(，)。其中，為節(jié)點集合，包括目標節(jié)點集合、服務(wù)航天器初始節(jié)點集合和虛擬結(jié)束點；為連接所有節(jié)點的邊的集合。一組規(guī)模相同的服務(wù)航天器由集合表示，其規(guī)模與相同。

圖2 完全有向圖表示的“多對多”在軌加注場景Fig.2 Fully directed graph for the many-to-many on-orbit refueling scenario

服務(wù)航天器需從初始節(jié)點出發(fā)，依次機動至多個目標點附近為其進行在軌加注，最后到達虛擬結(jié)束點，結(jié)束任務(wù)。每個服務(wù)航天器在初始節(jié)點處的最大燃料均為，所攜帶的燃料可用于在軌加注和軌道轉(zhuǎn)移，每個服務(wù)航天器必須在燃料用盡前完成所有既定的在軌加注任務(wù)。每個目標衛(wèi)星只能且僅可被一個服務(wù)航天器服務(wù)一次。對于目標衛(wèi)星，其燃料需求為d。服務(wù)航天器從目標點轉(zhuǎn)移至的燃料消耗為c，c的計算將在1.3 節(jié)中敘述。定義決策變量x，該變量表示服務(wù)航天器是否服務(wù)完成目標點后繼續(xù)服務(wù)，若是，則x=1，否則x=0。通過對決策變量的優(yōu)化，實現(xiàn)在滿足路徑約束和服務(wù)航天器燃料約束的前提下，使得所有服務(wù)航天器的燃料消耗之和最小。

基于以上定義，則可得到“多對多”在軌加注的任務(wù)規(guī)劃模型。

1）決策變量：x，?∈，∈，∈。

2）目標函數(shù)：

3）約束條件：

上述公式中：式（1）為規(guī)劃模型的目標是最小化所有服務(wù)航天器的燃料消耗；式（2）確保了每個目標僅可被一個服務(wù)航天器進行一次在軌加注；式（3）確保服務(wù)航天器無法轉(zhuǎn)移至任意初始節(jié)點；式（4）和式（5）為從每個服務(wù)航天器初始節(jié)點僅可出發(fā)一個與其編號相同的服務(wù)航天器；式（6）保證了每個航天器維修路徑的連續(xù)性；式（7）為每個航天器最終必須轉(zhuǎn)移至虛擬結(jié)束點；式（8）為從任意節(jié)點到虛擬結(jié)束點的燃料消耗為0；式（9）保證每個航天器的總?cè)剂舷牟怀^其攜帶的最大燃料；式（10）為決策變量的取值約束。

1.3 軌道轉(zhuǎn)移燃料消耗模型

服務(wù)航天器欲在完成目標的加注后通過軌道轉(zhuǎn)移至目標附近，為進行燃料加注。服務(wù)航天器與目標所處軌道分別為{，，}、{，，}，其中，為軌道半長軸，為軌道傾角，為升交點赤經(jīng)。服務(wù)航天器采用霍曼變軌方法消除與目標衛(wèi)星的半長軸之差，并且，在合適的時機實施霍曼變軌，還可消除兩航天器的相位之差?；袈冘壭枰乃俣仍隽繛?/p>

式中：為地球引力常量，通常取=3.986×10km·s。

兩航天器之間還存在軌道面的差異，其軌道面夾角由軌道傾角和升交點赤經(jīng)共同決定，可由如下公式計算得到：

因此，服務(wù)航天器消除軌道面差異所需的速度增量為

式中：=max {，}。

綜上，可得服務(wù)航天器與目標衛(wèi)星交匯的所需的總速度增量為

進一步，服務(wù)航天器從目標轉(zhuǎn)移至目標的燃料消耗為

2 求解框架設(shè)計

“多對多”在軌加注任務(wù)規(guī)劃問題為一類典型的整數(shù)規(guī)劃問題，當(dāng)問題規(guī)模較大時，其通常呈現(xiàn)NP-Hard （Non-deterministic Polynomial Hard）特性。求解這類問題較為常用的算法為元啟發(fā)式算法，如遺傳算法、蟻群算法、粒子群算法等。遺傳算法由于其較強的全局搜索能力，近年來被廣泛應(yīng)用于各類優(yōu)化問題中，本文擬采用遺傳算法作為主框架來求解任務(wù)規(guī)劃問題。同時，考慮到遺傳算法缺乏局部搜索機制，因此，將大鄰域搜索算法與遺傳算法相結(jié)合，取長補短，設(shè)計了一種LNS-GA 算法，以增強算法的局部尋優(yōu)能力。以下將詳細介紹算法的具體流程。

2.1 遺傳算法設(shè)計

遺傳算法的設(shè)計通常包括3 部分：編碼解碼規(guī)則的設(shè)計、遺傳算子（選擇、交叉、變異算子）的設(shè)計、適應(yīng)度函數(shù)的設(shè)計。

本文采用序列編碼方式對決策變量x進行編碼，設(shè)共有個服務(wù)航天器和個目標衛(wèi)星，則染色體長度固定為=+-1。染色體由取值為1～的互不相同的基因構(gòu)成，其中，取值為1～的基因代表目標衛(wèi)星的服務(wù)順序，取值(+1)～的基因為分割位，將整個染色體分割為個部分，每個部分代表一個服務(wù)航天器的在軌加注順序。例如，對于5 個目標衛(wèi)星和2 個服務(wù)航天器的情況，一個可能的染色體5-3-1-6-2-4，該染色體含義為服務(wù)航天器1 依次對目標5、目標3、目標1 進行在軌加注；服務(wù)航天器2 依次對目標2、目標4 進行在軌加注。

遺傳算子包括選擇、交叉、變異算子。對于選擇算子，本文采用精英保留策略和輪盤堵轉(zhuǎn)法完成，即對于種群中適應(yīng)度函數(shù)最大的染色體，直接保留至下一代參與子代個體的生成，對于剩余染色體通過輪盤賭的方法進行篩選。交叉算子采用部分映射交叉法，即對于參與交叉過程的2 個染色體，隨機選擇2 個基因點位，將基因點位間的染色體進行互換，之后，消除每個染色體中的重復(fù)基因即可完成交叉過程，每個染色體以固定概率確定其是否參與交叉過程。變異過程針對單個染色體，對于進行變異的染色體，隨機選取2 個基因點位，將其基因進行互換即可，每個子代參與變異的概率為。

適應(yīng)度函數(shù)用于衡量每個染色體的可行解對應(yīng)指標函數(shù)的大小和對約束條件的適應(yīng)程度，因此，通常由指標函數(shù)項和違反約束條件的罰函數(shù)項組成?；诒疚乃龅男蛄芯幋a方式，其得到的可行解總是滿足式（2）～式（7）和式（10），需要利用適應(yīng)度函數(shù)對式（9）進行評估，因此，適應(yīng)度函數(shù)可設(shè)為

式中：為懲罰系數(shù)；(x)為懲罰項，

2.2 大鄰域搜索算法設(shè)計

大鄰域搜索算法（Large Neighborhood Search，LNS）由SHAW 在1999 年首次提出，是一種局部搜索算法，被廣泛應(yīng)用于各類路徑規(guī)劃和取貨-送貨等問題中，均取得了良好的效果。其基本思想是通過對可行解的“破壞”與重新“修復(fù)”而得到新的可行解，完成搜索尋優(yōu)過程。設(shè)計LNS 算法的關(guān)鍵是可行解“破壞”與“修復(fù)”規(guī)則的設(shè)計。

2.2.1 可行解“破壞”進程

對當(dāng)前可行解進行破壞的過程是按照一定規(guī)則移除現(xiàn)有服務(wù)序列中固定數(shù)量的目標衛(wèi)星。本文中，通過依次移除與已被移除目標相關(guān)性最大的目標完成可行解的破壞。

對于目標和，兩者相關(guān)性定義為

式中：V為目標和是否被同一服務(wù)航天器加注燃料，

C′為服務(wù)航天器從到的“代價”。由于實際的燃料消耗與服務(wù)航天器進行軌道轉(zhuǎn)移前的質(zhì)量相關(guān)，難以快速計算，因此，采用歸一化后的軌道轉(zhuǎn)移速度增量表征兩目標間的轉(zhuǎn)移代價：

值得注意的是，每當(dāng)從現(xiàn)有序列中移除一個目標后，均需要更新剩余目標和移除目標的相關(guān)性。

2.2.2 可行解“修復(fù)”進程

可行解的“修復(fù)”進程是只將由“破壞”進程移除的目標按照一定的規(guī)則重新插入到已有序列中，形成對原有問題的可行解。本文的插入方法將基于最遠插入啟發(fā)式規(guī)則，優(yōu)先在現(xiàn)有序列插入最小Δ增量最大的待插入目標衛(wèi)星。待插入目標的最小Δ增量是指，將目標插入現(xiàn)有序列任意位置中，插入前后服務(wù)序列總Δ增量最小的位置為最小Δ增量插入位置，對應(yīng)的Δ增量為對應(yīng)待插入目標的最小Δ增量。具體步驟如下：

對于任意待插入目標，先找出滿足時間約束的所有插入點，再分別計算上述插入點的Δ增量；

找出上述插入點中Δ增量最小的最佳插入點，并記錄Δ增量；

對于所有待插入目標重復(fù)執(zhí)行步驟1～步驟2；

找到最小Δ增量最大的待插入目標，將該目標插入至最佳插入點，并更新待插入目標集；

重復(fù)步驟1～步驟4，直到所有目標完成插入，形成新的可行解。

2.3 LNS-GA 算法框架

LNS-GA 算法的整體框架如圖3 所示。該框架中，將遺傳算法作為外層算法，以充分利用其全局搜索能力。

圖3 LNS-GA 算法流程圖Fig.3 Flow chart of the LNS-GA algorithm

由于LNS 算法流程復(fù)雜，運行耗時較長，無法對遺傳算法得到的所有個體進行局部尋優(yōu)，因此，在外層遺傳算法完成一次迭代后，僅選取部分精英個體傳遞至內(nèi)層的LNS 算法中，進行進一步的局部搜索優(yōu)化。LNS 算法針對每個精英個體進行有限代數(shù)的迭代尋優(yōu)，若在最大迭代次數(shù)內(nèi)找到更優(yōu)解，則提前結(jié)束算法，更新精英染色體；若在達到最大迭代次數(shù)后仍未找到更優(yōu)解，也同樣退出算法。更新后的精英個體也同樣作為父代繼續(xù)參與外層遺傳算法的迭代，直到外層遺傳算法達到其停止條件，算法停止。

3 仿真實驗

為驗證所提出的求解算法的有效性，本文設(shè)定了3 個服務(wù)航天器為30 個GEO 衛(wèi)星進行在軌加注的場景。服務(wù)航天器參數(shù)見表1。30 個目標的軌道參數(shù)為隨機設(shè)定，其軌道半長軸設(shè)定在42 000～42 500 km 之間，軌道傾角設(shè)定為0～5之間，升交點赤經(jīng)設(shè)定為0～360之間。每個服務(wù)航天器本身的質(zhì)量為1 000 kg，攜帶燃料質(zhì)量為1 500 kg，變軌發(fā)動機比沖=3 200 m/s。每個目標衛(wèi)星的燃料需求均設(shè)定為100 kg。分別采用LNS-GA 和標準遺傳算法對問題進行求解，并將結(jié)果進行對比，兩算法的參數(shù)設(shè)定見表2。算法的停止條件有兩個，一個是迭代次數(shù)達到最小迭代次數(shù)，另一個是連續(xù)50 代的最優(yōu)適應(yīng)度值不發(fā)生變化。兩算法得到的結(jié)果如圖4～圖7 所示。

圖7 遺傳算法得到的任務(wù)規(guī)劃路徑Fig.7 Mission planning route obtained by the GA

表1 服務(wù)航天器軌道參數(shù)Tab.1 Orbit parameters of the service spacecrafts

表2 算法參數(shù)設(shè)定Tab.2 Parameter setting of the algorithms

圖4 LNS-GA 迭代曲線Fig.4 Iterative curve of the LNS-GA

圖4～圖5 分別為LNS-GA 和遺傳算法的迭代曲線。可以看到，LNS-GA 在設(shè)定的最小迭代次數(shù)內(nèi)便收斂至最優(yōu)值，遺傳算法在530 代的迭代之后才收斂。最終，LNS-GA 得到的適應(yīng)度值為1 034.22，而遺傳算法得到的適應(yīng)度為1 311.65，因此可以看出，LNS-GA 在結(jié)果的最優(yōu)性上明顯好于傳統(tǒng)的遺傳算法，表明其具備更強的搜索能力。

圖5 遺傳算法迭代曲線Fig.5 Iterative curve of the GA

圖6～圖7 分別為兩種算法得到的規(guī)劃結(jié)果中每個服務(wù)航天器的服務(wù)路徑，圖中表示的目標衛(wèi)星和服務(wù)航天器均為其初始運行軌道的角動量在天赤道面的投影。衛(wèi)星軌道角動量的投影分布一定程度上反映了不同衛(wèi)星的軌道在軌道半長軸、軌道傾角、升交點赤經(jīng)等參數(shù)上的差異。因此，坐標平面內(nèi)兩目標衛(wèi)星之間的距離越大，表明服務(wù)航天器在兩目標之間的轉(zhuǎn)移的速度增量越大，而服務(wù)航天器燃料的消耗量也與其所需的速度增量成正比。服務(wù)航天器的最優(yōu)服務(wù)順序?qū)?yīng)著在天赤道面上服務(wù)航天器依次為目標衛(wèi)星完成在軌加注的最短路徑。可以看出，由LNS-GA 得到的每個服務(wù)航天器的任務(wù)規(guī)劃路徑較為連續(xù)，沒有互相交叉，路徑總長度較短，燃料消耗較少；而GA 得到的規(guī)劃結(jié)果中，單個服務(wù)航天器的規(guī)劃路徑存在交叉的情況，總體路徑長度要長于LNS-GA 的規(guī)劃結(jié)果，因此燃料消耗會更大。

圖6 LNS-GA 得到的任務(wù)規(guī)劃路徑Fig.6 Mission planning path obtained by the LNS-GA

兩算法得到的規(guī)劃結(jié)果的詳細信息見表3。可以看到，LNS-GA 的規(guī)劃結(jié)果中，在執(zhí)行完成本次任務(wù)后，仍有兩服務(wù)航天器燃料質(zhì)量大于100 kg，存在進一步執(zhí)行加注任務(wù)的能力，而遺傳算法得到的規(guī)劃方案中，所有服務(wù)航天器均喪失了進一步執(zhí)行任務(wù)的能力，這進一步體現(xiàn)了LNS-GA算法的優(yōu)越性。

表3 兩種算法得到的詳細任務(wù)規(guī)劃結(jié)果對比Tab.3 Detailed mission planning results obtained by the two algorithms

4 結(jié)束語

本文針對“多對多”模式下的在軌加注任務(wù)規(guī)劃問題進行了研究，基于完全有向圖給出了任務(wù)規(guī)劃數(shù)學(xué)模型，同時給出了GEO 衛(wèi)星間軌道轉(zhuǎn)移燃料消耗的數(shù)學(xué)模型。為求解上述問題，在現(xiàn)有遺傳算法的基礎(chǔ)上設(shè)計了一種LNS-GA 混合算法，該算法相比遺傳算法改進了局部搜索能力。最后通過仿真對比實驗驗證了所設(shè)計算法的有效性和優(yōu)越性。后續(xù)的研究中，應(yīng)著重考慮時間約束下的在軌加注任務(wù)規(guī)劃問題的建模與求解。