“多對多”模式下GEO 衛星在軌加注任務規劃

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

（1.哈爾濱工業大學 航天學院，黑龍江 哈爾濱 150001；2.上海宇航系統工程研究所，上海 201109）

0 引言

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

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

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

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

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

1 任務規劃模型建立

1.1 “多對多”在軌加注任務場景描述

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

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

1.2 任務規劃模型

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

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

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

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

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

2）目標函數：

3）約束條件：

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

1.3 軌道轉移燃料消耗模型

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

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

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

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

式中：=max {，}。

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

進一步，服務航天器從目標轉移至目標的燃料消耗為

2 求解框架設計

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

2.1 遺傳算法設計

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

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

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

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

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

2.2 大鄰域搜索算法設計

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

2.2.1 可行解“破壞”進程

對當前可行解進行破壞的過程是按照一定規則移除現有服務序列中固定數量的目標衛星。本文中，通過依次移除與已被移除目標相關性最大的目標完成可行解的破壞。

對于目標和，兩者相關性定義為

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

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

值得注意的是，每當從現有序列中移除一個目標后，均需要更新剩余目標和移除目標的相關性。

2.2.2 可行解“修復”進程

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

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

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

對于所有待插入目標重復執行步驟1～步驟2；

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

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

2.3 LNS-GA 算法框架

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

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

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

3 仿真實驗

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

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

表1 服務航天器軌道參數Tab.1 Orbit parameters of the service spacecrafts

表2 算法參數設定Tab.2 Parameter setting of the algorithms

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

圖4～圖5 分別為LNS-GA 和遺傳算法的迭代曲線?？梢钥吹?，LNS-GA 在設定的最小迭代次數內便收斂至最優值，遺傳算法在530 代的迭代之后才收斂。最終，LNS-GA 得到的適應度值為1 034.22，而遺傳算法得到的適應度為1 311.65，因此可以看出，LNS-GA 在結果的最優性上明顯好于傳統的遺傳算法，表明其具備更強的搜索能力。

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

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

圖6 LNS-GA 得到的任務規劃路徑Fig.6 Mission planning path obtained by the LNS-GA

兩算法得到的規劃結果的詳細信息見表3?？梢钥吹剑琇NS-GA 的規劃結果中，在執行完成本次任務后，仍有兩服務航天器燃料質量大于100 kg，存在進一步執行加注任務的能力，而遺傳算法得到的規劃方案中，所有服務航天器均喪失了進一步執行任務的能力，這進一步體現了LNS-GA算法的優越性。

表3 兩種算法得到的詳細任務規劃結果對比Tab.3 Detailed mission planning results obtained by the two algorithms

4 結束語

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