基于匈牙利算法的多導彈陣地攔截指派規劃

周洪喜，張 進，彭晨遠,黎克波

(1 國防科技大學空天科學學院，長沙 410073；2 空天任務智能規劃與仿真湖南省重點實驗室，長沙 410073；3 63757部隊，黑龍江佳木斯 154002)

0 引言

陸基導彈防御系統能夠攔截敵方多種來襲目標，降低敵方軍事威脅和戰略威懾，有效保護己方重要價值目標。在實際運用中，采取多陣地協同防御攔截策略，可以提升攔截效果，在更短的時間內完成攔截任務，提升作戰效能。安炳合等基于改進煙花算法對多導彈目標分配問題進行了求解[1]；柴華、劉鑫等將導彈可達域概念應用于攔截問題分析中，并用降維分析方法計算了導彈攔截窗口[2-3]；徐品高、任仙海等分別從防御策略和整數規劃角度對排序問題進行了分析[4-5]。文中基于多導彈陣地協同攔截多目標問題，提出了一種基于匈牙利算法考慮多攔截窗口與發射時間間隔約束的攔截任務快速規劃方法。

1 攔截窗口建模分析

1.1 攔截彈空間可達域建模

對于給定的攔截彈陣地，在建立攔截彈空間可達域模型時，僅考慮攔截彈的助推段控制，忽略中段與末段控制，以標稱軌跡來建立空間可達域。在計算攔截彈的助推段飛行軌跡時，可供調節的參數有兩個，一是攔截彈的發射方位角，決定攔截彈的縱向射面；二是攔截彈的助推段控制策略，即最終程序角，調節攔截彈助推段的飛行軌跡，給定發射方位角與最終程序角可唯一地確定攔截彈彈道，所有彈道的集合構成攔截彈的空間可達域。

考慮攔截彈的攔截效能，分析時僅考慮攔截彈上升段，即彈道最高點之前的部分，圖1給出了發射方位角0°～360°，程序角分別為0°，25°，80°時的彈道軌跡。

圖1 不同程序角彈道覆蓋范圍

圖1中最下層和最上層彈道分別為程序角0°和80°的彈道軌跡，程序角越大彈道越陡峭，由于攔截彈性能限制，程序角無法達到90°，所以攔截彈陣地正上方區域無法覆蓋。攔截彈可達域就是由最下層和最上層彈道及中間彈道最高點所圍成區域，如圖2所示。

圖2 攔截彈空間可達域

1.2 攔截窗口分析計算

在進行攔截窗口分析時，來襲目標軌跡與攔截彈可達域存在兩種相交模式，如圖2所示。當目標軌跡從可達域邊緣穿越時攔截窗口是連續的；當目標軌跡從可達域中心穿越時，由于中心區域無法覆蓋，攔截窗口分為兩段。由于地球自轉影響，攔截彈可達域模型呈現出復雜的空間幾何構型，難以用解析的方式進行描述，給攔截窗口計算帶來了困難。在實際求解過程中，通常采用降維分析的方法，即分別以等效高程和空間方位角截取可達域，將可達域離散為網格點，當來襲目標彈道落在離散網格點之間時攔截彈具備攔截能力，此時對應的時刻即為攔截窗口。

2 攔截任務指派問題模型和求解方法

2.1 平衡指派問題數學模型

對于n個攔截彈陣地攔截n個來襲目標的任務指派問題，稱為平衡指派問題，規定每個陣地只攔截一個目標，且每個目標只由一個陣地進行攔截。已知aij表示第j個陣地攔截第i個目標的攔截窗口時間，[aij]稱為時間系數矩陣。xij為決策變量，當xij=1時表示第j個陣地攔截第i個目標，否則xij=0。規劃目標為任務完成總時間最少，即任務完成的總效率最高，于是平衡指派問題的數學模型可以表述為：

(1)

式中f為任務完成的時間和。

平衡指派問題可采用匈牙利算法進行快速求解。

2.2 任務完成時間最短的指派問題數學模型

對于平衡指派問題，其規劃目標總效率最高，但在處理一些特殊問題時，例如應急支援保障或導彈防御攔截過程中，不僅關心任務完成的總效率，而且要求任務能夠盡快完成，即完成最后一項任務所用時間最短，其數學模型可以表述為：

(2)

式中F為每次求得的參考解中的最大值。

任務完成時間最短的指派問題是一類非線性多目標規劃問題，不能夠直接運用匈牙利算法進行求解，白國仲證明了該問題可以通過對匈牙利算法改進后進行求解[6]，具體求解方法是：每次得到參考解中的最大值F后，對原時間系數矩陣按式(3)進行調整：

(3)

式中:g(aij)為原時間系數矩陣中元素aij經式(3)調整之后的值;M為任務計算時間周期。由此得到一組新的時間系數矩陣，重新利用匈牙利算法進行求解，重復上述操作，直到求得的結果不再變化時即得到了完成任務時間最短的解。

2.3 單陣地攔截多目標的任務指派問題求解

對于m個陣地攔截n個目標的任務指派問題，要求1個陣地最多可攔截p個目標，采用“1個陣地化成p個陣地法”和“加邊補0法”，對原時間系數矩陣進行拓展[7]，生成一個pm階方陣，如式(4)所示，其中列元素為原時間系數矩陣中的列元素重復p次，行元素中前n行與原系數矩陣中行元素相同，余下的pm-n行元素采用虛擬形式由0補齊，再按照任務完成時間最短的問題進行求解。

(4)

2.4 考慮攔截窗口時間間隔和多攔截窗口問題求解

由于同一陣地可以攔截多個目標，且攔截各目標時可能具有多個攔截窗口，每個攔截窗口具有不同的時長，在實際攔截中同一陣地連續攔截兩個目標之間的時間間隔需要滿足一定的發射準備時間要求，這時在進行任務規劃時就需要綜合考慮多個攔截窗口以及每個攔截窗口的時長情況[8]。首先利用前面的方法求解出一組最優解，然后對最優解中同一陣地攔截多個目標的時間間隔進行分析，看是否滿足發射準備時間間隔要求，如果滿足，則保留；如果不滿足，則需要考慮后一攔截目標的窗口寬度和額外窗口情況后重新進行規劃，其數學模型如式(5)所示：

(5)

式中T0為發射準備時間。

3 算例分析

考慮到地球自轉對攔截彈空間可達域的影響，按照經緯度不同選取5個陣地進行可達域計算，陣地設置如表1所示。

表1 導彈陣地設置

選取5個來襲目標進行分析，任務分析開始時刻目標在地心地固坐標系下的空間狀態如表2所示，分析時間為世界時2020年8月1日4時～8月2日4時共24小時。

表2 來襲目標初始時刻空間狀態

給出每個陣地攔截對每個目標的攔截窗口及窗口寬度如表3所示。

表3 攔截窗口 單位：s

選取每個陣地攔截每個目標的第一個攔截窗口生成的時間系數矩陣可表示為：

3.1 平衡指派問題求解

按照平衡指派問題，應用匈牙利算法對上述時間系數矩陣進行求解，得到的決策變量矩陣為：

由決策變量矩陣得到的按照平衡指派問題求解得到的攔截任務分配方案如表4所示。

表4 平衡指派攔截任務分配方案

攔截用時時間和為24 515 s；用時最大時間為陣地2攔截目標1的時間11 295 s。

3.2 完成任務時間最短問題求解

完成任務時間最短，即完成最后一個任務用時最少，可以應用改進的匈牙利算法進行求解，同時分析同一陣地可以攔截多目標情況，運用“1個陣地化成p個陣地法”和“虛擬任務法”對系數矩陣進行拓展后再進行求解。

3.2.1 每個陣地最多攔截1個目標

應用改進匈牙利算法進行迭代求解，得到的決策變量矩陣為：

由決策變量矩陣得到按照完成任務時間最短求解得到的攔截任務分配方案如表5所示。

表5 每個陣地最多攔截1個目標的任務分配方案

攔截用時時間和為24 587 s；用時最大時間為陣地2攔截目標4的時間為8 551 s，相較于平衡指派的任務分配方案，任務能夠提前2 744 s完成。

3.2.2 每個陣地最多攔截2個目標

每個陣地最多攔截2個目標，按照“1個陣地化成2個陣地法”和“虛擬任務法”對時間系數矩陣進行拓展，再應用改進的匈牙利算法進行求解，得到的拓展時間系數矩陣和決策變量矩陣分別為：

由決策變量矩陣得到每個陣地最多攔截2個目標時的攔截任務分配方案如表6所示。

表6 每個陣地最多攔截2個目標的攔截任務分配方案

陣地1先攔截目標5，再攔截目標1；陣地3攔截目標3；陣地4先攔截目標2再攔截目標4；陣地2和陣地5不進行攔截。攔截用時時間和為18 428 s；用時最大時間為陣地1攔截目標1的時間為5 397 s。與每個陣地只攔截1個目標的任務分配方案進行比較，攔截每個目標的時間和任務完成時間都明顯縮短。

3.2.3 每個陣地最多攔截3個目標

每個陣地最多可攔截3個目標，按照“1個陣地化成3個陣地法”和“虛擬任務法”對時間系數矩陣進行拓展，再應用改進匈牙利算法進行迭代求解，得到每個陣地最多攔截3個目標的攔截任務分配方案如表7所示。

表7 每個陣地最多攔截3個目標的攔截任務分配方案

陣地1先攔截目標3，再攔截目標5和目標1；陣地4先攔截目標2再攔截目標4；陣地2、3和5不進行攔截。攔截用時時間和18 327 s；用時最大時間為陣地1攔截目標1的時間5 397 s。任務完成時間沒有改變，但僅用2個陣地就可以完成攔截任務，可以盡量少的暴露陣地設施。

3.3 考慮任務準備時間和攔截彈飛行時間

實戰應用中攔截彈攔截目標需要考慮攔截彈發射準備時間、攔截彈飛行時間以及地面雷達設備跟蹤引導時間，通過分析，對于攔截目標彈道高度在700 km以下時，攔截彈飛行的時間均小于300 s，假設攔截彈發射準備時間為600 s，地面雷達設備需要在攔截彈發射前和命中目標后持續跟蹤偵察目標300 s，攔截彈飛行過程中需要全程跟蹤，所以一個陣地連續攔截兩個目標的窗口時間間隔至少為900 s，如果再考慮其他因素則要求的時間間隔將遠大于900 s。

表8給出了時間間隔為900 s、1 500 s、1 800 s、3 000 s、3 600 s時，每個陣地最多攔截2目標的任務分配方案。

表8 不同時間間隔的任務分配方案比較

對比表6中不考慮時間間隔時的攔截任務分配方案，當時間間隔為900 s時，陣地1、3將攔截目標1、3進行了交換；當時間間隔為1 500 s時，目標1分配給了陣地5，且陣地4攔截目標4的窗口時間向后推遲了3 s；當時間間隔為1 800 s時，目標4分配給了陣地5；當時間間隔為3 000 s時，陣地5攔截目標1的窗口變為第二攔截窗口；當時間間隔為3 600 s時，每個陣地都只能完成一次攔截任務，問題轉化為1個陣地攔截1個目標的情形，最終任務分配方案與每個陣地最多攔截1個目標的任務分配方案相同。當時間間隔不同時，攔截任務分配方案將發生較大變化，可以看出任務準備時間對攔截任務分配具有較大影響。

4 結論

通過改進的匈牙利算法對多陣地協同攔截多目標問題進行了規劃求解。仿真結果表明：該方法能夠快速得到多陣地協同攔截多目標情況下任務完成時間最短的任務分配方案，且分配算法隱含了完成所有任務時間和最小的條件，保證完成每個目標攔截任務的時間盡可能短。通過設置導彈陣地攜帶不同數量攔截彈以及不同任務準備時間間隔進行對比分析，結果表明：采用每個陣地多次發射策略，并縮短連續發射準備時間間隔，有利于快速完成攔截任務。