車載光學測量設備任務調度問題建模與求解*

柴 華，宋旭民，趙 乾，胡 濤

(1. 航天工程大學 航天指揮學院， 北京 101416； 2. 北京市遙感信息研究所， 北京 100089；3. 中國衛星發射測控系統部， 北京 100094)

空間目標編目是管理空間資產、維護空間環境的重要手段[1-2]。隨著航天產業的快速發展與空間目標的不斷增多，提升空間目標探測能力已成為空間目標編目的迫切需求。與傳統大型地基測量設備相比，車載光學測量設備[3-4]具有成本低、小型化、可移動、可批量部署等優點，為提升空間目標探測能力提供了一種新的思路，具有誘人的應用前景。本文以此為背景，開展車載光學測量設備觀測任務調度問題研究，所構建的數學模型與分析方法對車載光學測量設備的運用實踐具有一定的參考價值。

1 問題提出

本文涉及的車載光學測量設備(以下簡稱設備)的使用具有如下特點：設備部署于特定的地面測站，在空間目標過頂的一個較短的時間區間內，設備可對其進行觀測，該時間區間稱為設備對空間目標的觀測窗口(觀測窗口的計算涉及設備工作機理與空間目標需滿足的運動特性、光學特性約束，這一問題并非本文關注的重點，此處不再贅述)。設備可隨載車沿公路機動，往返于車庫與測站、測站與測站之間。設備機動到達特定測站后、具備觀測狀態前需要進行的準備工作的耗時稱為展開時間topen，設備完成一次觀測后、具備機動狀態前需要進行的準備工作的耗時稱為收攏時間tclose，設備在同一測站的兩次觀測之間需要進行的準備工作(伺服轉動、搜索、捕獲等)的耗時稱為冷卻時間tcool。

對上述車載光學測量設備的使用涉及一個觀測任務調度問題，該問題可描述為：

現有M臺測量設備Ei(i=1,2,…,M)，設備Ei的初始位置為Pi；所有設備最早可由t0時刻出發，需在t1至t2時間內對N個空間目標Tj(j=1,2,…,N)進行觀測；有L個可供使用的測站Sk(k=1,2,…,L)，求最優的觀測方案。

上述問題的本質是一個武器目標分配(Weapon Target Assignment, WTA)問題。WTA問題關注的核心是如何把具有不同殺傷力和經濟價值的武器分配到不同的目標，構成整體效益最優的火力打擊方案[5]。

國內外對WTA問題的探索可劃分為模型研究與算法研究兩類[6-7]。模型研究討論如何將背景各異的工程實際問題抽象為可供求解的WTA數學模型[8]；算法研究則針對特定模型，考察如何給出效率更高的求解算法[5]。

WTA屬于尋優決策問題，其模型研究主要聚焦三方面要素：第一，模型假設與自變量描述，即如何準確刻畫問題的自變量；第二，約束條件確定，即如何排除無效解；第三，目標函數或評價指標選擇，即如何衡量較優解。針對分析過程中是否考慮時間窗口約束，可將WTA模型進一步區分為靜態模型與動態模型。美國早在20世紀50年代就開始了WTA建模研究。20世紀80年代，Hosein等[9]對WTA問題展開了系統研究，給出了靜態WTA與動態WTA的定義，針對靜態WTA問題提供了一般性的解決方案。Rosenberger等[10]探索了武器平臺對多目標打擊的WTA問題，增加了武器可用數量與效能兩個約束條件，將武器目標分配抽象為一個線性整數規劃模型。進入21世紀以來，國內學者對WTA建模問題開展了大量研究。韓松臣[11]提出了基于馬爾科夫決策過程最優化的動態WTA方法。王正元等[12]建立了坦克戰斗中的動態WTA模型并提出了求解方法。胡建[13]探索了大氣層外導彈防御中多攔截器的目標分配問題。張先劍[14]構建了基于雙方動態博弈的攻防對抗綜合數學模型，并利用納什均衡和帕累托最優算法進行了分階段求解。針對傳感器-武器-目標分配問題，王藝鵬等[15]等提出了一種分階段建模與求解策略。上述對WTA模型的研究主要呈現兩個特點：一是涉及大量相似而不相同的工程實際問題，使得建立的數學模型存在差異；二是對靜態分配問題的研究較為充分，而動態分配問題尚未得到較好的解決。

自WTA問題誕生之日起，國內外學者一直致力于尋找更加有效的求解算法。20世紀80年代以前，對WTA問題的求解局限于傳統算法，主要包括隱枚舉法、分支定界法、割平面法、動態規劃法等[5-6]。這些算法在數學上為精確算法，思想較為簡單，但編程實現較為煩瑣，且其收斂速度隨著武器、目標數目的增多而變慢，難以處理維數較大的WTA問題。20世紀80年代以來，隨著計算機技術的發展，一些新穎的啟發式優化算法，如遺傳算法、蟻群算法、粒子群算法、模擬退火算法、電磁算法及其混合優化策略等，為解決復雜問題提供了新的思路和手段。閆玉鐸[16]在傳統遺傳算法基礎上引入了1V1種群競爭機制、差分變異機制以及粒子群算法更新規則，提出了基于改進遺傳算法的陸軍分隊級計算機生成兵力WTA問題求解方法。針對動態戰場環境下多通道武器轉火和來襲目標分階段打擊問題，邵詩佳[17]提出了一種改進的蟻群算法。夏維等[18]針對毀傷效能最大和用彈量最少兩個目標函數，建立了基于改進型多目標粒子群優化算法的WTA模型，驗證了算法的有效性。上述研究為WTA算法的不斷完善提供了參考價值，然而，已有研究大多引入了一定的簡化假設與理想條件，仍屬理論研究范疇，在工程實際中的應用效果有待進一步檢驗。隨著高新技術的發展與戰場對抗強度的增加，適用于大規模動態WTA問題的求解方法仍然是后續研究的重點。

本文提出的屬于廣義、動態WTA問題。與經典的WTA問題相比，觀測任務調度問題不僅將時間窗口納入考慮，而且增加了測站這一維度。也就是說，觀測方案涉及設備、測站、目標、窗口四者的映射關系，從而增加了問題的復雜性。針對這一復雜問題，已有的WTA模型無法使用：常用的表征武器-目標對應關系的自變量xij難以涵蓋測站及窗口信息，而觀測方案約束條件與評價指標也需要結合實際背景分析確定。為解決這一矛盾，提出了一套結構巧妙的數學模型，將觀測方案簡化為一個一維數組，并結合觀測設備的工作流程給出了約束條件和評價指標的定義及計算方法。在此基礎上，將觀測方案尋優問題視為一個多屬性決策問題[19-20]，通過蒙特卡洛抽樣與線性加權綜合尋找較優解，為觀測方案的制定提供了一條有效途徑。

2 問題建模

車載光學測量設備觀測任務調度問題的建模分三部分，即觀測方案的描述、方案約束的確定以及方案指標的提煉。在執行觀測任務的過程中，一個觀測要素指明了某臺設備部署于某個測站在某個窗口觀測某個目標，而觀測方案實質上為若干觀測要素的集合。為了確保一個觀測方案切實可行，需要結合設備特點梳理確定方案約束，不滿足方案約束的觀測方案為無效方案；當存在多套可行觀測方案時，為了進行排序評優，需要提煉觀測方案的評價指標，從成本、收益等角度反映觀測方案的優劣。

2.1 觀測方案

觀測方案描述策略如下：

1)利用已有的觀測窗口算法，計算t1至t2時間內，設備部署在Sk測站對Tj目標的觀測窗口集合Wj,k,q(q=1,2,…,qjk)，由表達式可知，該集合中窗口數目為qjk；

3)引入一個長度為qtotal的一維數組，數組中的第x個元素對應于第x個觀測窗口，其取值y為0到M之間的整數，表示將第x個觀測窗口分配給第y臺設備以執行觀測任務。

如圖1所示，將M臺設備的一個觀測方案抽象為一個一維數組來表示。舉例來講，形如[1,0,2,1,0,3]的數組表示設備的觀測窗口共有6個，觀測方案指定第1臺設備在第1和第4個窗口實施觀測、第2臺設備在第3個窗口實施觀測、第3臺設備在第6個窗口實施觀測，其余窗口不實施觀測。

圖1 觀測方案的描述Fig.1 Description of observation plan

2.2 方案約束

滿不滿足約束決定了一個觀測方案是否可行。在方案尋優過程中，不滿足約束的觀測方案應該首先被排除。結合問題背景，提出觀測方案應該滿足如下約束。

2.2.1 設備轉場約束

在一個觀測方案中，一臺設備可能需要往返于多個測站以執行多個觀測任務。設備轉場約束是指觀測任務的編排應該將設備的機動時間、展開時間、收攏時間、冷卻時間等因素納入考慮，確保每一設備能夠在給定的時間內完成所有必需的動作，如圖2所示。

圖2 單臺設備典型觀測任務流程Fig.2 Typical observation process of single equipment

設備轉場約束的計算步驟如下。

步驟1：針對給定的觀測方案，梳理所有涉及的設備及每一臺設備需要實施觀測的窗口集合。

步驟2：針對第i臺設備，對其需要實施觀測的窗口集合中的元素按照時間先后進行排序。

1)：設備由初始位置轉場至第1個窗口對應測站實施觀測需滿足的時間約束為

(1)

式中，tmove(·)為已知地面上設備的初始位置與終點位置計算機動耗費時間的算子，該過程需考慮設備機動速度以及地理信息等因素，此處不再贅述。

步驟2)設備由第α個窗口對應測站轉場至第α+1個窗口對應測站實施觀測需滿足的時間約束為

(2)

步驟4：重復步驟2、步驟3，檢驗觀測方案涉及的所有設備轉場時間是否足夠，一旦出現不等式不成立的情形，則終止計算，判定該觀測方案不滿足設備轉場約束。

2.2.2 測站進出約束

在一個觀測方案中，一個測站可能需要被多臺設備使用以執行多個觀測任務。測站進出約束是指觀測任務的編排應該將設備進出測站所耗費的展開時間、收攏時間等因素納入考慮，確保每一測站能夠有效保障其被賦予的所有觀測任務，如圖3所示。

測站進出約束的計算步驟如下。

步驟1：針對給定的觀測方案，梳理出所有涉及的測站及每一個測站需要實施觀測的窗口集合。

步驟2：針對方案中的第k個測站，對其需要實施觀測的窗口集合中的元素按照時間先后進行排序。

步驟3：設排序后第k個測站需要實施觀測的窗口集合可表示為Wiβ,jβ,k,qβ(β=1,2,…,βk)，則測站進出約束的計算方法如下。

圖3 單個測站典型觀測任務流程Fig.3 Typical observation process of single station

1)如果第k個測站需要實施觀測的窗口不超過1個，則該測站不存在測站進出約束。

2)如果第k個測站需要實施觀測的窗口不少于2個，則第β個窗口與第β+1個窗口需要滿足的測站進出約束為：

(3)

步驟4：重復步驟2、步驟3，檢驗觀測方案涉及的所有測站進出時間是否沖突，一旦出現不等式不成立的情形，則終止計算，判定該觀測方案不滿足測站進出約束。

至此，給出任一觀測方案必須滿足的兩個約束。需要指出的是，式(2)與式(3)中的第一式本質上是等價的。在實際操作中，為了減小計算量，兩者取其一即可。

2.3 方案指標

方案指標是判定觀測方案質量的依據。在選取方案指標的過程中，應該注意以下原則：①完備性，即選擇的指標應該盡可能充分地涵蓋反映觀測任務過程的關鍵參數。②獨立性，即選擇的指標之間應該盡可能地保持獨立，避免指標之間含義重疊。③定量性，即選擇的指標應該便于量化計算，避免挑選界限模糊、主觀性強的指標。

2.3.1 總機動距離

總機動距離刻畫了一個觀測方案中所有設備需要機動的距離的總和，為了降低觀測方案的成本，總機動距離應該盡可能小。

總機動距離的計算步驟如下。

步驟1：針對給定的觀測方案，在計算設備轉場約束的過程中已經梳理得到了第i臺設備需要實施觀測的窗口集合Wi,jα,kα,qα,(α=1,2,…,αi)，則第i臺設備的機動距離可表示為：

(4)

式中，dmove(·)為已知地面上設備的初始位置與終點位置計算機動距離的算子，該過程需考慮地理信息等因素，此處不再贅述。

步驟2：總機動距離可表示為：

(5)

需要指出，對于觀測方案中沒有分配觀測任務的設備，其機動距離取0。

2.3.2 總觀測時長

總觀測時長刻畫了一個觀測方案對所有空間目標觀測的時間窗口長度的總和，為了提高觀測方案的效益，總觀測時長應該盡可能大。

總觀測時長的計算步驟如下。

步驟1：針對給定的觀測方案，在計算設備轉場約束的過程中已經梳理得到了第i臺設備需要實施觀測的窗口集合并將其表示為Wi,jα,kα,qα(α=1,2,…,αi)，則第i臺設備的觀測時長可表示為：

(6)

步驟2：總觀測時長可表示為：

(7)

需要指出，對于觀測方案中沒有分配觀測任務的設備，其觀測時長取0。

2.3.3 觀測目標數目

觀測目標數目刻畫了一個觀測方案能夠覆蓋的所有空間目標的數目，為了提高觀測方案的效益，觀測目標數目應該盡可能多。

觀測目標數目的計算較為簡單，針對給定的觀測方案，梳理出所有涉及的空間目標的數目Ninvol即可。

至此，給出考察任一觀測方案質量的三個指標。

3 問題求解

前文對車載光學測量設備觀測任務調度問題進行了建模，接下來給出問題的求解策略。

1)給定已知條件，首先利用特定的觀測窗口算法計算設備部署在所有測站對所有目標存在的觀測窗口全集；

2)結合已知條件與觀測窗口全集，利用Monte Carlo抽樣方法抽取初始觀測方案集合；

3)判定所有初始觀測方案是否滿足方案約束，剔除無效方案，獲得可行觀測方案集合；

4)計算所有可行觀測方案的方案指標，利用多屬性決策方法進行指標聚合，從而實現對觀測方案的排序；

5)依據排序結果選定最優觀測方案。

在上述求解策略中，多屬性決策方法是解決問題的關鍵。

多屬性決策方法是決策與評估領域的經典方法，用于支持分析人員在面對多個選項或方案時做出最優決定。多屬性決策方法處理的一類常見問題是有限方案排序問題，即綜合考慮多方面屬性對不同方案質量進行評估的問題。

有限方案排序問題由以下兩類要素構成：

1)方案集X={X1,X2,…,Xm}，即參與排序的可行方案的集合；

2)屬性集O={O1,O2,…,On}，即反映方案質量的屬性指標的集合。

方案集對應于所有可行的觀測方案，屬性集對應于方案指標。多屬性決策方法的操作流程如圖4所示。圖4中，方案集與屬性集為方法輸入，評估結果為方法輸出，由輸入到輸出需經決策矩陣構建、決策矩陣規范化、權重矢量確定與指標聚合排序四步，下文將依次給出其過程。

圖4 多屬性決策方法的操作流程Fig.4 Workflow of the multi-attributes-decision-making method

決策矩陣包含了參與決策的所有信息，若將方案Xi的屬性指標Oj記為xij，那么決策矩陣可表示為：

(8)

考慮到不同屬性指標的量綱與物理含義等存在差異，需要對其進行規范化處理，使不同指標之間具備可比性與可加性。常用的指標規范化方法包括矢量規范化方法、極性變差法、線性變換法、Z-Score法等。采用離散信息損失相對較少的線性變換法進行矩陣規范化處理，其思路可由式(9)描述。

(9)

(10)

權重體現了評價指標的重要性程度以及對評價對象分辨信息量的多少，如何確定權重是多屬性決策方法研究的重點。常見的權重確定方法包括主觀賦權法與客觀賦權法。主觀權重主要源于決策者和相關專家對于指標相對決策目標所起作用重要性的認知，體現了決策者的一種偏好，因此主觀權重可以由決策者或者專家采取打分的方式確定，或者采用能使專家思維更加規范化的層次分析法獲得。客觀權重主要通過提取決策矩陣所蘊含的離散信息獲得，一般包括方案集之間的分類信息和聚類信息。采用一種客觀賦權法來實現對權重wA的確定，即文獻[21]中的相關系數與標準差(Correlation Coefficient and Standard Deviation，CCSD)方法，該方法的基本思想是：①考慮任一指標與剔除其之后其他指標加權綜合結果的相關性，如果相關系數大，表明該指標對評估結果影響較小，因而賦予其較小的權重，否則賦予其較大的權重；②考慮任一指標取值的標準差，如果標準差小，表明指標分布范圍小，因而其對評估結果的影響較小，賦予其較小的權重，否則賦予其較大的權重。綜合考慮相關系數與標準差，確定每一指標的最優權重。

CCSD方法具有簡潔、有效、便于擴展等優點，其操作方法如下。

由式(10)出發，若將屬性集中的指標Oj移去，則觀測方案Xi的剩余總體效能將變為：

(11)

指標Oj與剩余總體效能EXij的相關系數可由式(12)給出。

(12)

Rj刻畫了指標Oj與剔除Oj后的剩余總體效能EXij的相關程度。若Rj很大接近于1，表示Oj與EXij相關性很大，引入Oj對評估結果影響很小，因而賦予Oj較小的權重；反之，若Rj很小接近于-1，則表示Oj與EXij相關性很小，需要賦予Oj較大的權重。

另外，若對于不同方案，指標Oj取值的標準差很小，說明Oj對方案排序所起的作用小，因而賦予Oj較小的權重；反之，若指標Oj取值的標準差很大，則賦予Oj較大的權重。

綜合相關性與標準差兩方面特性，采取如式(13)所示的權重確定策略。

(13)

式(13)為3方程3未知數的非線性方程組，其求解可通過構造如式(14)所示的優化模型來實現。

(14)

4 仿真校驗

首先給定初始條件，取t0、t1、t2時刻分別為:

t0=(2018-05-24 T 00:00:00 UTCG)

t1=(2018-06-01 T 00:00:00 UTCG)

t2=(2018-06-08 T 00:00:00 UTCG)

取設備載車的最大機動速度為60 km/h，設備的展開時間topen=3 h、收攏時間tclose=1 h、冷卻時間tcool=0.5 h。

假設有6臺觀測設備，其基本信息見表1。假設需對4個空間目標實施觀測，其在t1時刻的經典軌道根數見表2。假設可供使用的測站有4個，其基本信息見表3。

表1 觀測設備初始條件

表2 空間目標在t1時刻的經典軌道根數

表3 測站初始條件

本算例利用了衛星工具包(Satellite Tool Kit, STK)軟件[22]的衛星過境計算工具Access來計算設備觀測窗口，針對每一測站，分別添加一個傳感器對象Sensor，將Sensor類型設為簡單圓錐形，錐角取60°，使用Access工具可以獲得測站對目標的觀測窗口。本例利用了地球圓球模型來計算設備的機動距離與機動時間，即假設對于球面上任意兩點，設備以勻速沿球面劣弧由起點機動至終點。需要強調的是，對于更加精密的觀測窗口算法與設備機動算法，本文提出的方法同樣適用。

圖5給出了利用Access工具計算得到的所有測站對所有目標的觀測窗口的集合，圖5中每一條彩色豎線均表示一個觀測窗口。表4給出了測站1對目標1的11個觀測窗口的具體細節，限于篇幅，不再給出其他窗口細節。

圖5 所有測站對所有目標的觀測窗口全集Fig.5 Universal set of observation windows of all stations for all targets

表4 測站1對目標1的觀測窗口集合

由圖5可知，在給定的初始條件下，共有140個觀測窗口。因此，本文算例涉及的觀測方案是長度為140的一維數組。

利用蒙特卡洛抽樣方法抽取容量為10 000的初始觀測方案集合，剔除無效方案后，得到3 080個可行方案。這些觀測方案對應的指標分別如圖6～8所示。

圖6 可行觀測方案的總機動距離Fig.6 Total move distance of feasible observation plans

圖7 可行觀測方案的總觀測時長Fig.7 Total time interval of feasible observation plans

圖8 可行觀測方案的觀測目標數目Fig.8 Target amount of feasible observation plans

圖9 可行觀測方案的總體效能Fig.9 Overall efficiency of feasible observation plans

由總體效能可知：3 080個可行觀測方案中，第1 638個方案為最優方案，其對應的觀測方案見表5。表5方案對應的3個指標分別為總機動距離19 897.26 km，總觀測時長1 436 s，觀測目標4個。

表5 最優觀測方案

5 結論

本文為解決車載光學測量設備的觀測任務調度問題提出了一套結構巧妙且擴展性強的數學模型與方法框架。將涉及設備、測站、目標、窗口四者映射關系的觀測方案簡化為一個一維數組來處理，從而使觀測方案的尋優轉化為一個多屬性決策問題；隨著對問題認識的不斷加深與建模粒度的不斷細化，方法中涉及的觀測方案約束、觀測方案指標、觀測窗口算法、機動算法等環節均可改進并靈活替換，從而實現方法性能的快速提升。

需要指出的是，對于WTA這一NP完全問題，采用先進、高效的算法是快速獲得滿意解的保證。為驗證所提數學模型與方法框架的有效性，采用了蒙特卡洛抽樣與線性加權綜合算法來求解問題，算法的計算效率與所得方案的質量仍然有一定的改進空間。在下一步研究中，將嘗試引入遺傳算法、蟻群算法等智能優化思想，探索提出更加適用的求解算法，給出更高質量的解決方案。