郭健 柴華 王磊

（航天工程大學 航天指揮學院，北京101416）

1 引言

隨著航天器產業(yè)的快速發(fā)展，空間目標變得越來越多，對空間目標管理與維護的需求也越來越迫切［1，2］?？臻g目標探測能力是實現(xiàn)空間目標管理與維護的重要保證，而車載光學測量設備是提高戰(zhàn)時空間目標探測能力的有效手段之一。車載光學測量設備具有可移動、小型化、可批量部署、生存能力強等突出優(yōu)點［3］，擁有較好的應用前景。但同時由于在信息化戰(zhàn)爭條件下，空間目標攜帶的偵察載荷能夠快速發(fā)現(xiàn)和定位威脅源，為遠程武器提供目標指示，從而對車載光學測量設備實施精確打擊。因此，研究一種最少暴露時間下的車載光學測量設備任務規(guī)劃方法就顯得尤為重要。

2 問題描述

某類車載光學測量設備（以下簡稱設備）的使用具有如下特點：設備隨載車部署于隱蔽的車庫中，需要執(zhí)行探測任務時設備隨載車沿公路運輸，由車庫前往預設測站；到達預設測站后，在空間目標過頂?shù)囊粋€較短時間區(qū)間內設備對其進行探測，該時間區(qū)間稱為設備對空間目標的探測窗口；對每一個空間目標，設備須對其探測一定次數(shù)才能保證完成探測任務，且設備在探測過程中還要滿足相應的約束。一次高效探測任務的完成，往往要涉及多套設備、多個車庫、多個測站和多個目標。因此，須預先制定快速測量／機動隱蔽狀態(tài)轉換時的探測方案，明確參加本次任務的多套設備分別在什么時刻到什么地點去探測哪一個空間目標。

在制定設備探測方案時，探測任務規(guī)劃的問題可描述為：現(xiàn)有X個隱蔽車庫｛A1，A2，…，Aβ，…，AX），車庫Aβ停放設備的數(shù)量為aβ（β ＝1，2，…，X），須在t1～t2時間區(qū)間內對NT個空間目標進行探測且每個目標要探測NS次，可供使用的測站有NL個，求最少暴露時間下的探測方案。

上述問題的內涵近似于軍事運籌學領域經典的武器目標分配（Weapon Target Assignment，WTA）問題。國內外對WTA 問題的研究主要劃分為模型研究和算法研究兩類。模型研究探討如何建立更為合理、貼近實際的模型［4］；而算法研究則是針對給定模型探索如何更快速有效地解決WTA 問題［5］。在WTA 模型研究方面，20 世紀90 年代以來，美軍國防分析研究所一直致力于WTA 模型研究，文獻［6］將基本WTA 問題擴展到多武器平臺對多目標的打擊；文獻［7］考慮了武器的費用以及不同武器組合對目標的打擊情況，提出改進的武器優(yōu)化與資源需求模型；文獻［8］建立了以干擾效能指數(shù)最大化為目標的干擾分配數(shù)學模型，用來解決不同作戰(zhàn)對手、力量配置、對抗手段情況下的分配決策問題；文獻［9］基于自適應決策中心的協(xié)同決策體系結構，提出了一種動態(tài)武器目標分配的協(xié)同決策模型；文獻［10］為解決艦艇編隊所面臨的多種類、多批次目標飽和攻擊火力分配問題，建立了編隊防空多平臺多防空武器的火力分配模型；文獻［11］在分析裝甲分隊火力打擊戰(zhàn)法的運用方式及其對分配結果影響的基礎上，建立了面向裝甲分隊戰(zhàn)法運用的兩階段WTA 模型。在對WTA 問題的求解上，文獻［12］對比分析了傳統(tǒng)匈牙利算法與智能優(yōu)化算法，創(chuàng)建了可適用于所有類型目標分配問題的可適應匈牙利算法；文獻［13］為了有效解決多導彈對多機動目標的攔截對抗實戰(zhàn)中的目標分配問題，提出一種基于精英策略的多種群自適應遺傳算法；文獻［14］研究了在復雜的戰(zhàn)場作戰(zhàn)環(huán)境中多個動態(tài)威脅下如何快速規(guī)劃出最優(yōu)航路，提出一種在優(yōu)化算法框架下稀疏A*算法與遺傳算法相結合的動態(tài)航路規(guī)劃算法；文獻［15］根據(jù)粒子聚集度來判斷早熟停滯，提出了一種改進的量子粒子群優(yōu)化算法；文獻［16］使用多目標模糊優(yōu)選理論建立最佳武器-目標分配模型，采用了蟻群算法將分配模型轉化為蟻群網絡進行求解。

與經典WTA 問題相比，本文研究的探測任務規(guī)劃問題不僅考慮時間窗口，地點要素還包括車庫和測站兩個維度，構成了一個涉及時間、設備、地點、目標四個獨立要素相互映射的問題，其內核更為復雜、規(guī)模發(fā)散更快，已有的WTA 模型無法使用，需要結合問題實際提出更加適用的求解策略。為解決這一問題，提出了一種分層求解方法，將這一涉及五個維度的復雜問題轉化為測量方案篩選與調度方案計算兩個相對維度較少的問題來處理，為快速準確地獲得最優(yōu)解提供了一條有效途徑。

3 分層任務規(guī)劃方法

分層任務規(guī)劃的總思路是：先求解所有獨立要素的解空間，再根據(jù)約束和評價指標求得最優(yōu)解。要解決的問題是：快速測量／機動隱蔽狀態(tài)轉換時的探測任務規(guī)劃問題。針對上述求解思路和要解決的問題，同時考慮到時間窗口交叉等因素，可將求解策略分成三步，即探測窗口全集計算、測量方案篩選和調度方案計算。探測窗口全集計算將獲得給定探測時間區(qū)間內所有測站對所有空間目標的所有探測窗口。測量方案篩選將從探測窗口全集中挑選滿足約束條件且評價指標優(yōu)異的子集作為最優(yōu)測量方案。調度方案計算將對照最優(yōu)測量方案編排制定設備自車庫至測站的最優(yōu)調度方案。分層任務規(guī)劃方法的操作流程如圖1 所示。

圖1 分層任務規(guī)劃方法的操作流程

3.1 探測窗口全集計算

探測窗口的計算涉及設備工作機理和空間目標的運動特性、光學特性等約束。利用已有的探測窗口算法，遍歷NL個測站和NT個目標，計算得到t1至t2時間區(qū)間內探測窗口全集，可表示如下：

式（1）中，Wijk表示探測窗口全集中的任意一個探測窗口，下標i表示窗口對應的測站，下標j表示窗口對應的空間目標，表示設備在第i個測站對第j個空間目標共有個探測窗口，下標k表示其中的第k個探測窗口。

3.2 測量方案篩選

首先從探測窗口全集中進行測量方案初選，獲得初選測量方案集合；然后剔除不滿足約束條件的測量方案，獲得可行測量方案集合；最后對可行測量方案進行對比分析，獲得最優(yōu)測量方案。

3.2.1 初選測量方案

基于獲得的探測窗口全集，利用排列組合原理進行測量方案初選，方法如下。

（1）依據(jù)空間目標劃分探測窗口全集。根據(jù)需要探測的NT個空間目標，將探測窗口全集S劃分為NT個子集，每一個子集表示為：

式（2）中，Sj表示探測窗口全集S中對應于第j個空間目標的所有探測窗口的集合，其中包含的探測窗口的個數(shù)為：

對于NT個空間目標，設備共需探測NI＝NS×NT次。

（2）得到初選測量方案。針對第j個目標，從中任選NS個元素（由排列組合理論可知，共有種可能的選法）。遍歷NT個目標，選出NI＝NS×NT個探測窗口，從而得到一個初選的測量方案。對于NT個目標，初選測量方案的總數(shù)為：

3.2.2 可行測量方案

針對NInit個初選測量方案，需要分別判斷每一個初選測量方案是否滿足約束，滿足約束即為可行方案。可將任意一個初選測量方案表示為Sm，獲得可行方案的方法如下。

（1）判斷最小探測間隔約束。按照初選測量方案Sm中探測窗口對應的不同測站，將其劃分為若干個子集，并將子集中的探測窗口按照發(fā)射時刻先后排序，整理后對應于第i個測站的測量方案子集Smi為：

式（5）中，Wip表示Smi中的第p個探測窗口，表示Smi中的探測窗口個數(shù)。

針對子集Smi，將i由1 遍歷至NL，再將p由1 遍歷至，判斷下式是否成立：

式（6）中，Ti（p+1）為探測窗口Wi（p+1）對應的探測時刻，ΔTmin為設備在同一測站的兩次探測之間必須滿足的最小時間間隔。

在循環(huán)遍歷過程中，一旦式（6）不成立，則初選測量方案Sm為不可行方案，需要將其剔除；若式（6）成立，則認為初選測量方案Sm滿足最小探測間隔約束。

（2）判斷測站數(shù)目約束。針對初選測量方案Sm，將i由1 遍歷至NL，考察子集Smi中元素個數(shù)是否為0，元素個數(shù)不為0 的子集數(shù)目即為Sm涉及的測站數(shù)目NR。

判斷下式是否成立：

在循環(huán)遍歷過程中，若式（7）不成立，則Sm為不可行方案，需要將其剔除；若式（7）成立，則認為初選測量方案Sm滿足測站數(shù)目約束。

（3）判斷初選測量方案是否可行。若初選測量方案Sm同時滿足最小探測間隔約束與測站數(shù)目約束，則其為可行方案；否則，其為不可行方案。

將NInit個初選測量方案中所有不可行方案剔除，即可獲得可行測量方案集合。

3.2.3 最優(yōu)測量方案

針對選出的可行測量方案，通過設定評價指標來對比測量方案的優(yōu)劣?？蓪⑷我庖粋€可行測量方案表示為Sn，獲得最優(yōu)測量方案的方法如下。

（1）計算探測任務時長。按照可行測量方案Sn中探測窗口對應的不同測站，將其劃分為若干個子集，并將子集中的探測窗口按照探測時刻先后排序，整理后對應于第i個測站的子集Sni為：

式（8）中，Wiq表示Sni中的第q個探測窗口，表示Sni中的探測窗口個數(shù)。

可行測量方案Sn對應的探測任務時長ΔT可由下式計算：

式（9）中，Tfirst為可行測量方案Sn的開始探測時刻，Tlast為可行測量方案Sn的結束探測時刻；Ti1為Sni對應的最早探測時刻，TiNZi為Sni對應的最晚探測時刻。

（2）以探測任務時長作為評價指標尋找最優(yōu)測量方案。本文研究最少暴露時間下的測量方案，因此可以選取探測任務時長ΔT作為評價指標，將ΔT最短的可行測量方案作為最優(yōu)測量方案Sbest。

3.3 調度方案計算

調度方案計算將對照最優(yōu)測量方案進行設備調度計算，明確車庫與測站的對應關系，從而編排制定設備自車庫至測站的最優(yōu)調度方案，進行調度方案計算的方法如下。

將最優(yōu)測量方案Sbest按照其中的探測窗口對應的不同測站劃分為若干個子集，并將子集中的探測窗口按照探測時刻先后排序，整理后的Sbest可表示為：

針對Nbest個測站Bγ（γ ＝1，2，…，Nbest），為每一個測站配備1 套設備，則最優(yōu)測量方案共需要配備Nbest套設備。假設從Aβ到Bγ機動一套設備的時間為Cη，設備調度的目的是從X個待機車庫中選擇Nbest套設備并運輸至Nbest個測站，使得總運輸時間最短。該問題是運籌學中經典的運輸問題，可使用表上作業(yè)法求解獲得最優(yōu)調度方案。

4 算例驗證

首先給定初始條件：探測時間區(qū)間見表1。假設有3 個可用測站，其基本信息見表2。需要對3 個空間目標實施探測，其在t1時刻的經典軌道根數(shù)見表3。

表1 探測時間區(qū)間

表2 測站位置

表3 空間目標在t1 時刻的經典軌道根數(shù)

由表1、表2、表3 給出的初始條件，可以使用STK 軟件計算獲得探測窗口全集，該全集中包含的探測窗口見表4。

表4 探測窗口全集

由表4 可知，在給定的初始條件下，共有45 個探測窗口。根據(jù)需要探測的3 個空間目標，將探測窗口全集劃分為3 個子集，則對應于第1 個空間目標的子集S1中探測窗口的個數(shù)NW1 為16 個，對應于第2 個空間目標的子集S2中探測窗口的個數(shù)NW2為15 個，對應于第3 個空間目標的子集S3中探測窗口的個數(shù)為14 個。假設設備需要對每一個空間目標探測2 次。針對第1 個目標，從S1中任選2 個元素，共有120 種可能的選法；針對第2 個目標，從S2中任選2個元素，共有種可能的選法；針對第3 個目標，從S3中任選2 個元素，共有種可能的選法；每一次遍歷3 個目標選出的6 個探測窗口構成一個初選測量方案。初選測量方案的總數(shù)為120×105×91＝1 146 600 個。

假設同一測站的兩次探測之間必須滿足的最小時間間隔ΔTmin為6 小時，允許動用的測站的最大數(shù)目為3 個。利用式（5）～（7）給出的算法，剔除不滿足約束的初選測量方案，可獲得可行測量方案509 661 個。

針對509 661 個可行測量方案，利用式（8）（9）給出的算法，可獲得最優(yōu)測量方案，見表5。

表5 最優(yōu)測量方案

該最優(yōu)測量方案對應的探測任務時長ΔT為15.34 小時，需要配備的設備數(shù)目Nbest為3 套。

假設有2 個車庫，每個車庫停放的設備數(shù)量見表6。將設備從不同車庫機動到不同測站的運輸時間見表7。

表6 設備調度問題產銷平衡表

表7 設備調度問題單位運價表

針對表6、表7 給定的已知條件，運用表上作業(yè)法進行求解，得到設備最優(yōu)調度方案見表8，該方案對應的總運輸時長為180。

表8 設備最優(yōu)調度方案

至此，由表5 給出的最優(yōu)測量方案和表8 給出的最優(yōu)調度方案，共同構成了最優(yōu)探測方案。

為了進一步驗證本文提出的分層求解方法的有效性，采用了Monte Carlo 抽樣方法與本文提出的分層求解方法進行對比。Monte Carlo 抽樣方法的求解策略是從計算好的探測窗口全集中，隨機抽取容量為10 000 的初始探測方案集合，剔除無效方案后，選取找到最好的一個方案作為最優(yōu)探測方案。由于Monte Carlo 抽樣方法存在較大的不確定性，這里運行了5 次并對結果進行統(tǒng)計分析。算例結果見表9。

表9 最優(yōu)探測方案

從結果中不難看出，本文所提出的分層求解方法的求解質量要優(yōu)于Monte Carlo 抽樣方法。

5 結束語

實現(xiàn)戰(zhàn)時空間目標管理與維護迫切需要提升空間目標探測能力。本文為解決車載光學測量設備的探測任務規(guī)劃問題，提出了一種可操作的分層求解方法。首先計算探測窗口全集得到所有獨立要素的全部解空間，然后將涉及窗口、設備、車庫、測站、目標五者分配的探測任務規(guī)劃問題分成兩層來處理。第一層測量方案篩選考慮窗口、設備、測站、目標四個維度下的最優(yōu)解，第二層調度方案計算關注設備在車庫和測站兩個狀態(tài)中的最優(yōu)解，兩層分別得到的最優(yōu)測量方案與調度方案共同構成了最優(yōu)探測方案。本文提出的方法擴展性較強，可根據(jù)實際中的同類問題做出相應的改進，從而用于解決其他問題。