用于資源動態(tài)預(yù)留的航天測控資源配置優(yōu)化算法*

梁 軍,陳學(xué)軍,劉建平,原東陽,羅清青

(西安衛(wèi)星測控中心,西安 710043)

0 引 言

航天測控設(shè)備是航天測控網(wǎng)的主要組成部分,在日常運(yùn)行中承擔(dān)著對航天器進(jìn)行跟蹤測量、遙測、遙控和通信等測控任務(wù)[1]。隨著在軌航天器數(shù)量的不斷增加,對航天測控資源的需求迅速增多,航天器測控需求的類型也變得越來越多樣化,給測控系統(tǒng)帶來越來越大的壓力,在一定條件下能為在軌航天器提供支持服務(wù)的容量也是有限的[2-3]。

在航天器數(shù)量和航天器任務(wù)需求增加的條件下,測控需求與航天測控資源可提供的服務(wù)能力之間的矛盾不斷增加[4]。由于航天測控設(shè)備建造和維護(hù)成本較高,如何經(jīng)濟(jì)、科學(xué)和合理地配置航天測控資源,對測控設(shè)備進(jìn)行最優(yōu)調(diào)度進(jìn)而提高地面設(shè)備的使用率[5],充分發(fā)揮航天測控資源效益和最大限度地滿足各類航天器任務(wù)的需要,是一個迫切需要研究解決的重大問題[6-7]。航天測控資源的配置優(yōu)化問題主要是研究如何針對現(xiàn)有的航天器測控需求合理地配置一定數(shù)量的航天測控資源,通過尋找最優(yōu)的配置方案使用戶預(yù)期的目標(biāo)函數(shù)達(dá)到最優(yōu)化[8-9],進(jìn)而提升航天測控設(shè)備的整體運(yùn)行效能,保障更多的航天測控需求,以解決當(dāng)前航天測控資源緊張的問題。

近年來,圍繞不同問題領(lǐng)域中的資源高效配置和優(yōu)化問題,國內(nèi)外學(xué)者對其建模和求解方法進(jìn)行了一些研究[10-12],但是并沒有考慮資源動態(tài)預(yù)留情況下的資源配置優(yōu)化。為此,本文著重在考慮資源動態(tài)預(yù)留的情況下進(jìn)行航天測控資源配置優(yōu)化問題的建模和求解。本文立足于航天器用戶方的測控需求滿足率最大化的目標(biāo)和航天測控設(shè)備管理方的測控設(shè)備利用率最大化的目標(biāo),建立了能在國內(nèi)東部、西部、南部和北部四大測控區(qū)域中更加均衡地預(yù)留出更多、更重要的設(shè)備的航天測控資源配置優(yōu)化模型,進(jìn)而提出基于可回溯的并行最佳優(yōu)先搜索的航天測控資源配置優(yōu)化算法,實現(xiàn)了在以日計劃形式進(jìn)行的航天測控資源周期調(diào)度中資源動態(tài)預(yù)留的預(yù)期效果,為在航天測控資源調(diào)度過程中優(yōu)化提升航天測控設(shè)備的服務(wù)能力奠定了理論基礎(chǔ)。

1 問題描述

航天測控資源配置優(yōu)化問題屬于組合優(yōu)化問題,但又比經(jīng)典的組合優(yōu)化問題求解困難,主要是因為該問題的約束條件繁雜且數(shù)量眾多,目標(biāo)函數(shù)的組成成分多樣且在優(yōu)化過程中呈現(xiàn)出不確定性。航天測控資源配置優(yōu)化問題主要解決的是如何給地面站配置設(shè)備,使得配置方案的綜合效能最好,包括地面站點(diǎn)位的選址和航天測控設(shè)備配置數(shù)量的優(yōu)化等。

在實際中,地面站點(diǎn)位的選址要受到地形、當(dāng)?shù)貧夂?、政治條件以及航天器用戶方的需求等諸多因素的影響,在具體實踐中一般要對地面站點(diǎn)位的選址進(jìn)行單獨(dú)的研究論證。因此,本文中航天測控資源配置優(yōu)化問題主要研究的是在滿足航天器用戶方提出的全部任務(wù)需求的前提下,如何在現(xiàn)有的航天測控設(shè)備集合中選擇數(shù)量盡可能少的設(shè)備來為所有任務(wù)需求配置可用的服務(wù)時間窗口,通過尋找最優(yōu)的配置方案來使既定的目標(biāo)函數(shù)達(dá)到最優(yōu)化。例如,假定航天測控設(shè)備集合中有J套設(shè)備(即SD={D1,…,Dj,…,DJ}),在滿足所有任務(wù)需求的情況下,設(shè)備集合SD中參與任務(wù)的設(shè)備所組成的子集合(即SE={D1,…,De,…,DE},E≤J)以及相應(yīng)的服務(wù)時間窗口集合(即SW={W1,…,We,…,WE},We為第e套參與任務(wù)的設(shè)備De上執(zhí)行的服務(wù)時間窗口集合),則為航天測控資源的一種配置方案,配置優(yōu)化的目標(biāo)就是在航天測控設(shè)備集合中尋找能使目標(biāo)函數(shù)達(dá)到最優(yōu)的一種配置方案。因此,航天測控資源配置優(yōu)化問題中涉及到的輸入、輸出和優(yōu)化目標(biāo)等相關(guān)要素描述如下:

(1)輸入要素:給定調(diào)度周期;給定低軌航天器需求型任務(wù)集SR;給定航天測控設(shè)備集SD,以及每個需求型任務(wù)Rg的可支持設(shè)備列表Lg;給定每個需求型任務(wù)Rg的航天器對其可支持設(shè)備列表Lg中所有設(shè)備的星地可見預(yù)報,并形成需求型任務(wù)Rg的備選可用弧段集。

(2)輸出要素:參與任務(wù)的航天測控設(shè)備集合以及數(shù)量;為每個需求型任務(wù)Rg進(jìn)行保障的設(shè)備和服務(wù)時間窗口的配置方案。

(3)優(yōu)化目標(biāo):對于航天器用戶方而言,最大程度地提高任務(wù)需求的滿足率;對于航天測控設(shè)備管理方而言,最大程度地提高設(shè)備利用率,進(jìn)而給一些關(guān)鍵任務(wù)在國內(nèi)東部、西部、南部和北部四大測控區(qū)域中更加均衡地預(yù)留出更多、更重要的設(shè)備。

2 航天測控資源配置優(yōu)化模型建立

2.1 原子型任務(wù)的形式化描述

地面站原子型任務(wù)(以下簡稱原子型任務(wù))是指地面站根據(jù)航天器用戶方提出的低軌任務(wù)需求對航天器進(jìn)行單次保障服務(wù),這樣就將航天器用戶方提出的低軌任務(wù)需求轉(zhuǎn)化為若干個相互之間存在著關(guān)聯(lián)約束的原子型任務(wù)。因此,原子型任務(wù)集是指多個原子型任務(wù)組成的集合,表示為SA={A1,…,Ai,…,AI},Ai∈SA為第i個原子型任務(wù),I為原子型任務(wù)的數(shù)量。其中,單個原子型任務(wù)A可采用公式(1)所示的8元組進(jìn)行規(guī)范化描述,式中每個元素的含義如表1所示。

表1 原子型任務(wù)中8元組含義及描述

2.2 優(yōu)化模型建立

航天測控資源配置優(yōu)化問題是多類且大量約束并存的、資源高度沖突的組合最優(yōu)化問題。航天測控資源配置優(yōu)化模型是對航天測控資源配置優(yōu)化問題的數(shù)學(xué)描述,也是設(shè)計求解方法的基礎(chǔ)。本節(jié)將分析航天測控資源配置優(yōu)化過程中的決策變量、約束條件和目標(biāo)函數(shù)等建模要素,從而構(gòu)建出航天測控資源配置優(yōu)化模型。

2.2.1 決策變量

航天測控設(shè)備對航天器星地可見預(yù)報的一個備選可用弧段定義為

式中:NC為可用時間窗口編號;D為航天測控設(shè)備代號;SP為航天器代號;TS為開始時刻;TE為結(jié)束時刻。

對于原子型任務(wù)集SA中的第i個原子型任務(wù)Ai而言,其備選可用弧段集為Bi,備選可用弧段的總數(shù)為Hi。其中,第i個原子型任務(wù)在航天測控設(shè)備集SD中的第j個可支持設(shè)備Dj上執(zhí)行的第k個備選可用弧段Ck屬于子集Bij(Bij?Bi),該集合中備選可用弧段的個數(shù)為Hij(Hij≤Hi)。因此,決策變量定義為

2.2.2 約束條件

(1)原子型任務(wù)執(zhí)行的唯一性約束

原子型任務(wù)執(zhí)行的唯一性約束是指每個原子型任務(wù)最多只能執(zhí)行一次。這是由于能夠為每個原子型任務(wù)提供任務(wù)保障的航天測控設(shè)備有多個,每個原子型任務(wù)具體在哪個設(shè)備的哪個可用時間窗口上執(zhí)行是一個可以選擇的過程。只要為原子型任務(wù)選定一個可用時間窗口,該原子型任務(wù)即被成功調(diào)度,重復(fù)執(zhí)行同一個原子型任務(wù)會造成航天測控設(shè)備的資源浪費(fèi),可能導(dǎo)致無法保障其他原子型任務(wù)的完成。

用決策變量表示這種類型的約束就是每個原子型任務(wù)對應(yīng)的決策變量的取值最多為1,如式(4)所示:

(2)航天測控設(shè)備執(zhí)行任務(wù)的唯一性約束

①每個航天測控設(shè)備在執(zhí)行一個原子型任務(wù)的過程中不執(zhí)行其他的原子型任務(wù)。

②每個航天測控設(shè)備在執(zhí)行一個原子型任務(wù)時需要滿足設(shè)備狀態(tài)的轉(zhuǎn)換時間。

③每個航天測控設(shè)備在一個調(diào)度周期內(nèi)(本報告中為一天)有最大期望負(fù)荷率約束。

根據(jù)對地面站測控過程的描述可知,航天測控設(shè)備所處的捕獲時間段和跟蹤時間段稱為測控任務(wù)持續(xù)時間,必須在可用時間窗口內(nèi);而航天測控設(shè)備所處的準(zhǔn)備時間段和釋放時間段稱為設(shè)備轉(zhuǎn)換時間,可以在可用時間窗口內(nèi),也可以不在可用時間窗口內(nèi)。

將航天測控設(shè)備的準(zhǔn)備時間、捕獲時間、跟蹤時間和釋放時間統(tǒng)稱為非空閑時間,則航天測控設(shè)備執(zhí)行任務(wù)的唯一性約束中的①和②重新表述為:當(dāng)航天測控設(shè)備處于非空閑時間段時,不能為其他原子型任務(wù)提供保障服務(wù),只有航天測控設(shè)備再次處于空閑時間段時,才能為新的原子型任務(wù)提供保障服務(wù),如圖1所示。

圖1 航天測控設(shè)備執(zhí)行任務(wù)的唯一性約束示意圖

為了方便描述航天測控設(shè)備可執(zhí)行弧段沖突集的生成算法,首先需要定義航天測控設(shè)備可執(zhí)行弧段這一數(shù)據(jù)結(jié)構(gòu)。一個航天測控設(shè)備的可執(zhí)行弧段E是在該航天測控設(shè)備的一個可用弧段C的基礎(chǔ)上加上該航天測控設(shè)備的準(zhǔn)備時間和釋放時間而產(chǎn)生的,定義如下:

式中:TES為可執(zhí)行弧段的開始時刻;TEE為可執(zhí)行弧段的結(jié)束時刻;tES為該可執(zhí)行弧段所屬的航天測控設(shè)備的準(zhǔn)備時間;tER為該可執(zhí)行弧段所屬的航天測控設(shè)備的釋放時間。

從圖1可以看出,對于一個原子型任務(wù)而言,由第j個航天測控設(shè)備Dj上的第e個備選可用弧段Ce,便可生成該航天測控設(shè)備保障這個原子型任務(wù)的一個可執(zhí)行弧段Ee。其中,該可執(zhí)行弧段的開始時刻和結(jié)束時刻的計算公式如(6)所示:

由此可知,第j個航天測控設(shè)備Dj從第e個可執(zhí)行弧段Ee的開始時刻TES到結(jié)束時刻TEE,該航天測控設(shè)備只能執(zhí)行一個原子型任務(wù),TES到TEE之間的時間段就是第j個航天測控設(shè)備的非空閑時間。

因此,如果用決策變量X來表示航天測控設(shè)備執(zhí)行任務(wù)的唯一性約束①和②,則為在第j個航天測控設(shè)備Dj上的第e個可用弧段Ce的可執(zhí)行弧段沖突集Wje中,最多只有一個可用弧段能被用來調(diào)度。

式中:Ek是可執(zhí)行弧段沖突集Wje中在第j個設(shè)備Dj上執(zhí)行的第k個可執(zhí)行弧段;K是可執(zhí)行弧段沖突集Wje中可執(zhí)行弧段的個數(shù)。

在調(diào)度周期內(nèi)第j個航天測控設(shè)備Dj的任務(wù)執(zhí)行總時長為因此,航天測控設(shè)備執(zhí)行任務(wù)的唯一性約束③可描述為

式中:是第j個航天測控設(shè)備Dj在一個調(diào)度周期內(nèi)的最大任務(wù)負(fù)荷量(也就是該設(shè)備在調(diào)度周期內(nèi)的所有可見預(yù)報取并集的時長);是第j個航天測控設(shè)備的最大期望負(fù)荷率。

(3) 航天器執(zhí)行任務(wù)的唯一性約束

①每個航天器在執(zhí)行一個原子型任務(wù)的過程中不能執(zhí)行其他原子型任務(wù)。

②每個航天器在執(zhí)行升降軌類型相同的多個原子型任務(wù)的過程中,需要滿足該航天器低軌需求型任務(wù)中的最小、最大間隔時間要求,并且升降軌類型相同的多個原子型任務(wù)被調(diào)度的可用弧段所屬的圈次應(yīng)該不同或者連續(xù)。

③每個航天器在執(zhí)行相鄰的升軌和降軌原子型任務(wù)的過程中,需要滿足該航天器低軌需求型任務(wù)中的相鄰升降軌最大間隔時間要求。

如圖2所示,航天器執(zhí)行任務(wù)的唯一性約束可理解為:對于屬于同一個航天器且升降軌類型相同的兩個原子型任務(wù),當(dāng)前原子型任務(wù)執(zhí)行的持續(xù)時間和該原子型任務(wù)執(zhí)行完畢后持續(xù)到最小間隔時間以及最大間隔時間以后的時間段,該航天器均處于非空閑狀態(tài),不能再執(zhí)行與該原子型任務(wù)屬于同一個航天器且升降軌類型相同的其他原子型任務(wù);對于屬于同一個航天器但升降軌類型不同的兩個原子型任務(wù),當(dāng)前原子型任務(wù)執(zhí)行的持續(xù)時間以及該原子型任務(wù)執(zhí)行完畢后持續(xù)到最大間隔時間以后的時間段,航天器均處于非空閑狀態(tài),不能再執(zhí)行與該原子型任務(wù)屬于同一個航天器但升降軌類型不同的其他原子型任務(wù)。

圖2 航天器執(zhí)行任務(wù)的唯一性約束示意圖

為了方便描述航天器可執(zhí)行弧段沖突集的生成算法,首先需要定義航天器可執(zhí)行弧段這一數(shù)據(jù)結(jié)構(gòu),如式(9)所示。航天器的一個可執(zhí)行弧段Z是在可用弧段C的基礎(chǔ)上加上該航天器低軌任務(wù)需求中的相同升降軌類型中的最小間隔時間、最大間隔時間和不同升降軌類型中的相鄰升降軌最大間隔時間而產(chǎn)生的。

式中:TZS為可執(zhí)行弧段的開始時刻;TZEmin為可執(zhí)行弧段的最早結(jié)束時刻;TZEmax為可執(zhí)行弧段的最晚結(jié)束時刻;TZemax為可執(zhí)行弧段的相鄰升降軌最晚結(jié)束時刻;tZSmin為低軌任務(wù)需求中相同升降軌類型的最小間隔時間;tZSmax為低軌任務(wù)需求中相同升降軌類型的最大間隔時間;為低軌任務(wù)需求中相鄰升降軌的最大間隔時間。

從圖2可以看出,由航天器低軌需求型任務(wù)集SR中第g個需求型任務(wù)Rg上的第e個可用弧段Cge,可生成一個可執(zhí)行弧段Zge。其中,可執(zhí)行弧段的開始時刻和結(jié)束時刻的計算如公式(10)所示:

由此可知,在第g個需求型任務(wù)Rg上的第e個可執(zhí)行弧段Zge的開始時刻到最早結(jié)束時刻

之間的時間段以及最晚結(jié)束時刻以后的時間段內(nèi),該航天器都不能再執(zhí)行與該可執(zhí)行弧段具有相同升降軌屬性的其他原子型任務(wù)。因此,到之間的時間段以及以后的時間段均為該航天器執(zhí)行與第e個可執(zhí)行弧段Zge具有相同升降軌屬性的原子型任務(wù)的非空閑時間。在第g個需求型任務(wù)Rg上的第e個可執(zhí)行弧段Zge的相鄰升降軌最晚結(jié)束時刻以后的時間段內(nèi),該航天器都不能再執(zhí)行與該可執(zhí)行弧段具有不同升降軌屬性的其他原子型任務(wù)。因此,以后的時間段均為該航天器執(zhí)行與第e個可執(zhí)行弧段Zge具有不同升降軌屬性的原子型任務(wù)的非空閑時間。

因此,如果用決策變量X來表示航天器執(zhí)行任務(wù)的唯一性約束①和②,則為在第g個需求型任務(wù)Rg上的第e個可用弧段Cge的具有相同升降軌屬性的可執(zhí)行弧段沖突集Vge中,最多只有一個可用弧段能被用來調(diào)度。

式中:Ck是可執(zhí)行弧段沖突集Vge中第k個可用弧段;K是可執(zhí)行弧段沖突集Vge中可執(zhí)行弧段的個數(shù);Ig是航天器低軌需求型任務(wù)集SR中第g個需求型任務(wù)Rg的原子型任務(wù)的個數(shù)。

同理,如果用決策變量X來表示航天器執(zhí)行任務(wù)的唯一性約束③,則為在第g個需求型任務(wù)Rg上的第e個可用弧段Cge的具有不同升降軌屬性的可執(zhí)行弧段沖突集Uge中,最多只有一個可用弧段能被用來調(diào)度。

式中:Ck是可執(zhí)行弧段沖突集Uge中第k個可用弧段;K1是可執(zhí)行弧段沖突集Uge中可執(zhí)行弧段的個數(shù)。

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

以原子型任務(wù)的備選可用弧段作為航天測控資源配置優(yōu)化問題的決策變量后,該優(yōu)化問題的求解就轉(zhuǎn)化為在決策變量集合X中選擇一組滿足各項約束條件并能使目標(biāo)函數(shù)值最優(yōu)的決策變量。其中,對于航天器用戶方而言,航天測控資源配置優(yōu)化的目標(biāo)函數(shù)是最大程度地提高低軌任務(wù)需求的滿足率;對于航天測控設(shè)備管理方來說,航天測控資源配置優(yōu)化的目標(biāo)函數(shù)就是最大程度地提高設(shè)備利用率,進(jìn)而給一些關(guān)鍵任務(wù)在國內(nèi)四大測控區(qū)域中更加均衡地預(yù)留出更多、更重要的設(shè)備。

(1)航天器用戶方的目標(biāo)函數(shù)

由于航天測控設(shè)備的可見時間窗口資源有限,航天器用戶方希望提出的低軌任務(wù)需求能最大程度得到滿足,即最大化低軌任務(wù)需求滿足率。當(dāng)?shù)蛙壢蝿?wù)需求轉(zhuǎn)換為原子型任務(wù)之后,低軌任務(wù)需求滿足率就轉(zhuǎn)換為原子型任務(wù)滿足率。原子型任務(wù)滿足率是成功調(diào)度的原子型任務(wù)的總收益值與低軌任務(wù)需求所要求的原子型任務(wù)的總收益值之間的比率。在航天測控資源優(yōu)化配置過程中,不但要盡可能多地完成原子型任務(wù),還要盡可能完成優(yōu)先級高的原子型任務(wù)。其中,低軌航天器用戶方給定低軌任務(wù)需求后,原子型任務(wù)的總收益值就是一個常量,表示為其中是第i個原子型任務(wù)Ai的優(yōu)先級。因此,原子型任務(wù)滿足率表示為

式中:J是指航天測控設(shè)備集SD中設(shè)備的個數(shù)。另外,如果原子型任務(wù)滿足率為100%,這說明所有任務(wù)均能完成,這時就無需考慮不同任務(wù)的優(yōu)先級高低對任務(wù)滿足率的影響。

(2)航天測控設(shè)備管理方的目標(biāo)函數(shù)

對于航天測控設(shè)備管理方來說,在航天測控資源優(yōu)化配置的目標(biāo)函數(shù)中,首先需要最大化航天測控設(shè)備的負(fù)荷率,也就是相當(dāng)于最小化參與任務(wù)的設(shè)備數(shù)量;其次需要使設(shè)備集合中未參與任務(wù)的預(yù)留設(shè)備的重要程度越高越好,也就是相當(dāng)于最大化預(yù)留設(shè)備的重要性指標(biāo);最后盡可能使預(yù)留設(shè)備在國內(nèi)四大測控區(qū)域中能夠均衡分布,也就是相當(dāng)于最大化預(yù)留設(shè)備所屬區(qū)域的均衡性指標(biāo)。

在最小化參與任務(wù)的設(shè)備數(shù)量的過程中,參與任務(wù)的設(shè)備數(shù)量的生成算法偽代碼如下(SE是指參與測控任務(wù)的設(shè)備集合,NE是指集合SE中設(shè)備的數(shù)量):

在最大化預(yù)留設(shè)備的重要性指標(biāo)的過程中,定義航天測控設(shè)備集SD中的第j個設(shè)備Dj的重要性指標(biāo)為Pj。其中,航天測控設(shè)備管理方給定航天測控設(shè)備集SD后,所有設(shè)備的重要性指標(biāo)的總值就是一個常量,表示為因此,設(shè)備集合中參與任務(wù)的設(shè)備的重要性指標(biāo)的總值如式(14)所示,則未參與任務(wù)的預(yù)留設(shè)備的重要性指標(biāo)的總值表示為(P-PU)。所以,最大化預(yù)留設(shè)備的重要性指標(biāo)就等同于需要最小化參與任務(wù)的設(shè)備的重要性指標(biāo)。

式中:PU表示參與任務(wù)的設(shè)備集合SE中所有設(shè)備的重要性指標(biāo)的總值。

在最大化預(yù)留設(shè)備所屬區(qū)域的均衡性指標(biāo)的過程中,定義航天測控設(shè)備集中的第j個設(shè)備Dj所屬的區(qū)域為Qj,取值為國內(nèi)的四大測控區(qū)域,即1表示西部區(qū)域,2表示東部區(qū)域,3表示南部區(qū)域,4表示北部區(qū)域。航天測控設(shè)備管理方給定航天測控設(shè)備集后,該集合中未參與任務(wù)的預(yù)留設(shè)備在四大測控區(qū)域中的個數(shù)則表示為Nt,其中t=1,2,3,4,分別表示在西部區(qū)域、東部區(qū)域、南部區(qū)域和北部區(qū)域中預(yù)留設(shè)備的個數(shù)。因此,預(yù)留設(shè)備所屬區(qū)域的均衡性指標(biāo)可以用各大區(qū)域中預(yù)留設(shè)備個數(shù)的標(biāo)準(zhǔn)差來進(jìn)行衡量。標(biāo)準(zhǔn)差的取值越小,說明預(yù)留設(shè)備在四大測控區(qū)域中的分布越均衡。

綜上所述,航天測控資源優(yōu)化配置問題采用的是兩層優(yōu)化目標(biāo),但本文重點(diǎn)研究在原子型任務(wù)滿足率達(dá)到100% 的前提下,如何最大程度地提高設(shè)備利用率,也就是重點(diǎn)對第二層目標(biāo)進(jìn)行優(yōu)化,進(jìn)而給一些關(guān)鍵測控任務(wù)在四大測控區(qū)域中更加均衡地預(yù)留出更多、更重要的設(shè)備。因此,本文將航天測控資源配置優(yōu)化模型中的目標(biāo)函數(shù)定義為

通過式(16)可以看出,目標(biāo)函數(shù)是由3個乘積項(分別對應(yīng)于上述的3個分目標(biāo))的加和構(gòu)成,每個乘積項都對應(yīng)于相應(yīng)的參考值作了歸一化處理,保證每個乘積項的數(shù)量級大小相同。權(quán)重系數(shù)α1和α2表示這3個分目標(biāo)在目標(biāo)函數(shù)中的權(quán)重不同,但又通過式(16)巧妙的構(gòu)造形式保證了這3個分目標(biāo)在目標(biāo)函數(shù)中的權(quán)重之和為1,這也表明目標(biāo)函數(shù)的取值范圍為[0,1]。同時也可以看出,當(dāng)權(quán)重系數(shù)α1=1時,目標(biāo)函數(shù)就只考慮最小化參與任務(wù)的設(shè)備數(shù)量,也就相當(dāng)于只考慮最大化預(yù)留設(shè)備的數(shù)量;當(dāng)權(quán)重系數(shù)α1=0,α2=1時,目標(biāo)函數(shù)就只考慮最小化參與任務(wù)的設(shè)備的重要性指標(biāo),也就相當(dāng)于只考慮最大化預(yù)留設(shè)備的重要性指標(biāo);當(dāng)權(quán)重系數(shù)α1=0,α2=0時,目標(biāo)函數(shù)就只考慮最小化四大測控區(qū)域中預(yù)留設(shè)備個數(shù)的標(biāo)準(zhǔn)差,也就相當(dāng)于只考慮最大化預(yù)留設(shè)備所屬區(qū)域的均衡性指標(biāo)。另外,當(dāng)權(quán)重系數(shù)α1和α2取其他值時,目標(biāo)函數(shù)就需要同時考慮以上3個分目標(biāo),使得到的航天測控資源優(yōu)化配置方案能在國內(nèi)四大測控區(qū)域中更加均衡地預(yù)留出更多、更重要的設(shè)備。

3 航天測控資源配置優(yōu)化算法

3.1 航天測控資源配置優(yōu)化問題求解框架

設(shè)計了如圖3所示的航天測控資源配置優(yōu)化問題的求解框架,統(tǒng)一了航天測控資源配置優(yōu)化問題的求解算法的輸入,將整個求解過程劃分為輸入數(shù)據(jù)預(yù)處理階段和優(yōu)化算法求解階段這兩個階段,進(jìn)而實現(xiàn)了航天測控資源配置需求與求解算法的解耦。其中,在輸入數(shù)據(jù)預(yù)處理階段,化解原子型任務(wù)之間非關(guān)聯(lián)約束的關(guān)鍵步驟就是依據(jù)不同航天測控設(shè)備對不同航天器的支持能力的差異性,從所有星地可見預(yù)報中篩選出每個航天器完全可用的星地可見預(yù)報,從而形成每個原子型任務(wù)的備選可用弧段集;處理原子型任務(wù)之間關(guān)聯(lián)約束的關(guān)鍵步驟就是依據(jù)原子型任務(wù)的備選可用弧段之間相互制約或沖突關(guān)系,生成每個原子型任務(wù)的每個備選可用弧段的沖突弧段集,這就相當(dāng)于在求解階段中優(yōu)化算法給所有原子型任務(wù)調(diào)度一個相互之間不違反關(guān)聯(lián)約束的可用弧段時,提前進(jìn)行了沖突一致性檢驗的計算,大大減少了優(yōu)化算法的運(yùn)算時間。

圖3 航天測控資源配置優(yōu)化問題求解框架

3.2 可回溯的并行最佳優(yōu)先搜索算法

3.2.1 算法總體描述

可回溯的并行最佳優(yōu)先搜索的主要思想為:把原子型任務(wù)集合中的所有原子型任務(wù)都作為一個單獨(dú)的節(jié)點(diǎn),在每個節(jié)點(diǎn)的備選弧段集上使用多線程并行計算每個備選弧段的目標(biāo)函數(shù)值,將其中的最小值作為該節(jié)點(diǎn)的目標(biāo)函數(shù)值,與該最小目標(biāo)函數(shù)值相對應(yīng)的備選可用弧段作為該節(jié)點(diǎn)的當(dāng)前候選弧段;在航天測控資源配置優(yōu)化目標(biāo)的指引下,選擇能使總的優(yōu)化目標(biāo)函數(shù)值最小的節(jié)點(diǎn)作為當(dāng)前候選節(jié)點(diǎn),并利用當(dāng)前候選節(jié)點(diǎn)的當(dāng)前候選弧段的沖突集對剩下未選節(jié)點(diǎn)的備選弧段集進(jìn)行剪枝,去除與當(dāng)前候選弧段相沖突的所有備選弧段;周而復(fù)始直至所有節(jié)點(diǎn)都被選定了一個備選可用弧段,從而生成一棵記錄了優(yōu)化解構(gòu)造路徑的倒立多叉樹。

如圖4所示,在優(yōu)化解的逐步構(gòu)造過程中,依次選定了節(jié)點(diǎn)2、節(jié)點(diǎn)3和節(jié)點(diǎn)5作為每一步中的候選節(jié)點(diǎn);當(dāng)節(jié)點(diǎn)5作為當(dāng)前候選節(jié)點(diǎn)時,如果在剩余未選的節(jié)點(diǎn)中出現(xiàn)備選弧段集被該節(jié)點(diǎn)的當(dāng)前候選弧段剪枝為空的情況,就意味著在剩余未選的節(jié)點(diǎn)中出現(xiàn)了無備選可用弧段的原子型任務(wù),此時可選擇進(jìn)行回溯操作,更替當(dāng)前的候選節(jié)點(diǎn)或當(dāng)前候選節(jié)點(diǎn)的當(dāng)前候選弧段,使備選弧段集被剪枝為空的原子型任務(wù)恢復(fù)全部或部分備選可用弧段,從而保證原子型任務(wù)的滿足率盡可能大。

圖4 可回溯的并行最佳優(yōu)先搜索示意圖

3.2.2 回溯策略

為了使任務(wù)滿足率達(dá)到100%,在航天測控資源配置優(yōu)化解的構(gòu)造過程中,可能會進(jìn)行回溯操作。根據(jù)回溯操作的計算復(fù)雜程度,本文由簡單到復(fù)雜設(shè)計了兩種回溯策略。

(1)不更替當(dāng)前候選節(jié)點(diǎn)的回溯策略

這種回溯策略的原則是不增加算法運(yùn)算的開銷,不去重新計算所有未選節(jié)點(diǎn)的目標(biāo)函數(shù)值來更替當(dāng)前候選節(jié)點(diǎn)。采用這種回溯策略時,只需要在當(dāng)前候選節(jié)點(diǎn)的備選弧段集合中按照備選可用弧段的目標(biāo)函數(shù)值從小到大依次更替當(dāng)前候選弧段,直到剩余未選的節(jié)點(diǎn)中沒有出現(xiàn)備選弧段集被該當(dāng)前候選弧段剪枝為空的情況為止;如果當(dāng)前候選節(jié)點(diǎn)的所有備選弧段均被更替完畢,在剩余未選的節(jié)點(diǎn)中仍然出現(xiàn)備選弧段集被剪枝為空的情況,則本策略認(rèn)為參與航天測控資源配置優(yōu)化的資源不足,確實不能支持任務(wù)滿足率達(dá)到100%,其中一種處理方式為結(jié)束本次回溯操作,另外一種處理方式也可以是轉(zhuǎn)為第二種回溯策略繼續(xù)進(jìn)行回溯。

(2)更替當(dāng)前候選節(jié)點(diǎn)的回溯策略

這種回溯策略的原則是不考慮算法運(yùn)算的開銷,需要重新計算所有未選節(jié)點(diǎn)的目標(biāo)函數(shù)值來更替當(dāng)前候選節(jié)點(diǎn)。采用這種回溯策略時,需要將當(dāng)前候選節(jié)點(diǎn)的當(dāng)前候選弧段剔除后,再將當(dāng)前候選節(jié)點(diǎn)置為未選節(jié)點(diǎn),與其他未選節(jié)點(diǎn)一同計算目標(biāo)函數(shù)值來重新選出當(dāng)前候選節(jié)點(diǎn),直到剩余未選的節(jié)點(diǎn)中沒有出現(xiàn)備選弧段集被當(dāng)前候選節(jié)點(diǎn)的當(dāng)前候選弧段剪枝為空的情況為止;如果所有的當(dāng)前候選節(jié)點(diǎn)均被更替完畢,在剩余未選的節(jié)點(diǎn)中仍然出現(xiàn)備選弧段集被剪枝為空的情況,則本策略同樣認(rèn)為參與航天測控資源配置優(yōu)化的資源不足,確實不能支持任務(wù)滿足率達(dá)到100%,應(yīng)該結(jié)束本次回溯操作。

3.2.3 可回溯的并行最佳優(yōu)先搜索算法

可回溯的并行最佳優(yōu)先搜索算法流程如圖5所示。

圖5 可回溯的并行最佳優(yōu)先搜索算法流程圖

算法具體步驟如下:

Step1如果原子型任務(wù)集為空則失敗退出,否則轉(zhuǎn)Step 2。

Step 2把原子型任務(wù)集合中所有任務(wù)作為一個個單獨(dú)的節(jié)點(diǎn)s放入未擴(kuò)展節(jié)點(diǎn)表OPEN中,在每個原子型任務(wù)的備選弧段集上,計算每個備選弧段的目標(biāo)函數(shù),將其中的最小值作為當(dāng)前節(jié)點(diǎn)的目標(biāo)函數(shù)g(s),整個過程可通過并行計算得到;并按照g(s)對所有節(jié)點(diǎn)從小到大排序,初始化總的優(yōu)化目標(biāo)函數(shù)f=obj=0。

Step 3在具有相等的最小g(i)值的節(jié)點(diǎn)所構(gòu)成的集合中,選擇備選弧段數(shù)量最少的節(jié)點(diǎn)i進(jìn)行擴(kuò)展,并將其從OPEN表移至已擴(kuò)展節(jié)點(diǎn)表CLOSED中,總優(yōu)化目標(biāo)函數(shù)更新為f=f+g(i)。

Step 4根據(jù)節(jié)點(diǎn)i已選弧段的沖突弧段集,在OPEN表中對剩下節(jié)點(diǎn)的備選弧段集進(jìn)行剪枝,去除與已選弧段相沖突的備選弧段,以進(jìn)一步減小搜索空間。

Step 5如果在剩余節(jié)點(diǎn)中出現(xiàn)備選弧段集被剪枝為空的情況,則轉(zhuǎn)Step 7進(jìn)行回溯,否則轉(zhuǎn)Step 6。

Step6繼續(xù)擴(kuò)展節(jié)點(diǎn)i,多線程并行計算剩下的節(jié)點(diǎn)j的目標(biāo)函數(shù)g(j),利用g(j)對OPEN表中剩下的節(jié)點(diǎn)重新排序,并轉(zhuǎn)Step 10。

Step7根據(jù)當(dāng)前采用的回溯策略,判斷參與航天測控資源配置優(yōu)化的資源是否確實不足,如果確實不足則轉(zhuǎn)Step 8,否則轉(zhuǎn)Step 9。

Step8當(dāng)前采用的回溯策略認(rèn)為參與航天測控資源配置優(yōu)化的資源確實不能支持任務(wù)滿足率達(dá)到100%,立即結(jié)束本次回溯操作,并將無備選可用弧段的節(jié)點(diǎn)從OPEN表移至未完成節(jié)點(diǎn)表INCOMPLETE中,并轉(zhuǎn)Step 6。

Step9回溯節(jié)點(diǎn)i,采用3.2.2節(jié)中描述的回溯策略進(jìn)行回溯操作,并更新總的優(yōu)化目標(biāo)函數(shù)值f,并轉(zhuǎn)Step 4。

Step 10如果未擴(kuò)展節(jié)點(diǎn)表OPEN為空,當(dāng)前的已擴(kuò)展節(jié)點(diǎn)表CLOSED就是航天測控資源配置優(yōu)化方案,并根據(jù)輸入的地面測控設(shè)備集SD和當(dāng)前參與測控任務(wù)的設(shè)備集SE生成地面測控設(shè)備預(yù)留方案,算法結(jié)束,否則轉(zhuǎn)Step 3。

4 仿真算例

4.1 仿真算例配置

航天器低軌任務(wù)需求如表2所示,航天測控設(shè)備如表3所示。

表2 地面測控資源配置需求描述

表3 航天測控設(shè)備描述

4.2 航天測控資源配置優(yōu)化方案

4.2.1 航天測控資源調(diào)度方案

在一個主頻為3.40 GHz、內(nèi)存為8.00 GB的臺式計算機(jī)上對本文提出的用于資源動態(tài)預(yù)留的航天測控資源配置優(yōu)化算法進(jìn)行仿真測試。在4.1節(jié)的仿真算例中,對優(yōu)化目標(biāo)計算公式(16)中的權(quán)重系數(shù)α1和α2均以0.01為步長在0～1范圍內(nèi)進(jìn)行網(wǎng)格化搜索,經(jīng)過多次試驗發(fā)現(xiàn),當(dāng)權(quán)重系數(shù)α1取值在0.9附近和α2取值在0.4附近時,本文提出的算法運(yùn)行得到的地面測控設(shè)備預(yù)留方案的優(yōu)化效果較好,此時,得到的航天測控資源調(diào)度方案稱為本文方案,具體數(shù)據(jù)可掃描本文OSID碼查看。

同樣對4.1節(jié)中配置的仿真算例進(jìn)行優(yōu)化計算,文獻(xiàn)[12]提出的地基測控網(wǎng)資源分配算法運(yùn)行得到的航天測控資源調(diào)度方案稱為文獻(xiàn)[12]方案,具體數(shù)據(jù)可掃描本文OSID碼查看。

根據(jù)本文方案和文獻(xiàn)[12]方案數(shù)據(jù)可知,兩種算法運(yùn)行得到的航天測控資源調(diào)度方案中設(shè)備執(zhí)行任務(wù)的甘特圖如圖6所示。

圖6 兩種算法得到的航天測控資源調(diào)度方案中設(shè)備執(zhí)行任務(wù)的甘特圖

4.2.2 地面測控設(shè)備預(yù)留方案

本文提出的算法運(yùn)行得到的地面測控設(shè)備預(yù)留方案如表4所示。

表4 本文算法運(yùn)行得到的地面測控設(shè)備預(yù)留方案

文獻(xiàn)[12]提出的算法運(yùn)行得到的地面測控設(shè)備預(yù)留方案如表5所示。

表5 文獻(xiàn)[12]算法運(yùn)行得到的地面測控設(shè)備預(yù)留方案

從表4和表5的對比可以看出,相比文獻(xiàn)[12]提出的測控資源分配算法,本文提出的用于資源動態(tài)預(yù)留的航天測控資源配置優(yōu)化算法能夠預(yù)留出更多完全不參與測控任務(wù)的、且更重要的設(shè)備。此外,從圖6的兩種算法得到的航天測控資源調(diào)度方案中設(shè)備執(zhí)行任務(wù)的甘特圖也可以看出,本文所提算法能為參與測控任務(wù)的設(shè)備制定更加緊湊的工作計劃,使得設(shè)備的資源利用率得到足夠提升,進(jìn)而在四大測控區(qū)域中能夠更加均衡地預(yù)留出更多、更重要的設(shè)備。

5 結(jié) 論

本文從地面測控設(shè)備管理方的角度出發(fā),建立了能在國內(nèi)東部、西部、南部和北部四大測控區(qū)域中更加均衡地預(yù)留出更多、更重要的設(shè)備的航天測控資源配置優(yōu)化模型,并提出了可回溯的并行最佳優(yōu)先搜索算法對航天測控資源配置優(yōu)化問題進(jìn)行仿真求解。仿真結(jié)果表明,本文提出的航天測控資源配置優(yōu)化算法能有效實現(xiàn)資源動態(tài)預(yù)留的預(yù)期效果。