基于雙層Voronoi 圖的常規(guī)導(dǎo)彈多波次打擊模型

吳閏平，劉衛(wèi)東，楊 萍，陳 鵬，李晨旭

（火箭軍工程大學(xué)，西安 710025）

0 引言

隨著軍事科技的高速發(fā)展，導(dǎo)彈武器作為集地理學(xué)、物理學(xué)、計算機科學(xué)、化學(xué)、材料學(xué)和軍事戰(zhàn)略學(xué)為一體的高科技作戰(zhàn)武器，作戰(zhàn)距離遠(yuǎn)、隱蔽性強、威力大，已經(jīng)成為各國作戰(zhàn)的首選方式。在導(dǎo)彈武器作戰(zhàn)方式中，大彈量、多波次的常規(guī)導(dǎo)彈打擊策略成為當(dāng)下主要研究方向之一。這就涉及到了作戰(zhàn)區(qū)導(dǎo)彈部隊的任務(wù)分配與機動問題。常規(guī)導(dǎo)彈多波次打擊流程為：中心庫裝彈→待機陣地待機→發(fā)射陣地第1 波次發(fā)射→轉(zhuǎn)載陣地第1 次轉(zhuǎn)載→發(fā)射陣地第2 次發(fā)射→……→發(fā)射陣地第n 次發(fā)射，在機動過程中，如何合理安排各個發(fā)射裝置的機動路徑與相應(yīng)陣地，使的機動路徑總體較短，暴露時間最短，降低被敵偵查設(shè)備發(fā)現(xiàn)的概率，以增大生存概率具有重要意義。

在之前的常規(guī)導(dǎo)彈多波次打擊問題的研究中，汪民樂［7］研究了多波次對地攻擊的火力分配問題；王桐［9］運用馬爾科夫鏈解決了多波次打擊敵方目標(biāo)的效果評判問題；楊萍［5］運用軍事運籌學(xué)與不確定理論，對多波次導(dǎo)彈打擊的戰(zhàn)前運輸問題進行了建模分析，王鵬［11］根據(jù)軍事公路運輸?shù)奶攸c，建立了基于GIS 的路線選擇模型，給出了相應(yīng)的求解方法?？傮w來看，前人所做的研究主要集中在導(dǎo)彈發(fā)射裝置的機動路徑優(yōu)化方面，以及在給定機動路徑的基礎(chǔ)上進行機動調(diào)度，解決了多波次導(dǎo)彈作戰(zhàn)的路徑規(guī)劃與機動調(diào)度基本問題。但以上研究基本都是對于較小規(guī)模作戰(zhàn)路徑選擇調(diào)度的研究，而對于大彈量、多波次打擊中的發(fā)射裝置機動問題研究較少。且使用全局優(yōu)化搜索方法會使得算法復(fù)雜度增加，算法效率降低，因此，本文首先采用雙層Voronoi圖模型對發(fā)射陣地進行了動態(tài)聚類，由專門的轉(zhuǎn)載陣地對其發(fā)射陣地轉(zhuǎn)載服務(wù)，將多中心優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。其次建立雙層規(guī)劃模型，上層使的總體機動路徑最短，下層使的第1 波次發(fā)射完畢后，導(dǎo)彈發(fā)射裝置從發(fā)射陣地到轉(zhuǎn)載陣地再到發(fā)射陣地的機動距離最短，最后設(shè)計了適用于此問題的遺傳算法進行了求解。

1 基于雙層Voronoi 圖的發(fā)射陣地動態(tài)聚類

Voronoi 圖模型對于解決較大規(guī)模的路徑優(yōu)化問題具有較大優(yōu)勢，本文運用雙層Voronoi 圖模型對各個發(fā)射陣地進行聚類，并通過雙層規(guī)劃理論構(gòu)建多波次發(fā)射路徑全局優(yōu)化模型，并使的整體算法復(fù)雜度降低，得到最佳的機動路徑。

1.1 Voronoi 圖構(gòu)建方法

本文通過構(gòu)建Delaunay 三角網(wǎng)的方式建立Voronoi 圖模型，步驟為：

1）離散的發(fā)射陣地自動構(gòu)建Delaunay 三角網(wǎng)。對離散的發(fā)射陣地和形成的三角形進行編號，并記錄每個三角形是由哪3 個離散的發(fā)射陣地構(gòu)成的。

2）計算并記錄所有三角形的外接圓心。

3）遍歷三角形鏈表，尋找與當(dāng)前三角形的三邊共邊的相鄰3 個三角形。

4）如果找到，則把尋找到的三角形的外心與該三角形的外心連接，存入維諾邊鏈表中。如果沒有找到，則求出最外邊的中垂線射線存入Voronoi 邊鏈表中。

5）遍歷結(jié)束，所有Voronoi 邊被找到，根據(jù)邊畫出Voronoi 圖。

生成Voronoi 圖的基本方法是構(gòu)建Delaunay 三角網(wǎng)，基本步驟為：

1）將所有的發(fā)射陣地構(gòu)建超級三角形，并放入三角形鏈表。

2）將發(fā)射陣地依次插入，找到可以將此發(fā)射陣地包含的兩個已存在的三角網(wǎng)的外接圓，刪除公共邊，并將新插入的發(fā)射陣地與其余4 個發(fā)射陣地連接，形成新的Delaunay 三角形鏈表。

3）對新形成的三角網(wǎng)進行優(yōu)化設(shè)計，并置入Delaunay 三角形鏈表。

4）重復(fù)第2）步，使得所有發(fā)射陣地插入。關(guān)鍵步驟2）的實施流程如圖1 所示。

圖1 Delaunay 三角形實施流程

1.2 轉(zhuǎn)載陣地雙層Voronoi 圖模型

1.2.1 建立雙層Voronoi 圖

本節(jié)通過引入一個點和一條線的K 環(huán)Voronoi鄰居的概念來介紹雙層Voronoi 圖，如下頁圖2 分別表示兩個不同發(fā)射陣地的Voronoi 距離，一個點的Voronoi 鄰居以及一條線的Voronoi 鄰居。

建立雙層Voronoi 圖，上層Voronoi 圖粗略地定義了每個轉(zhuǎn)載陣地的初始覆蓋區(qū)域，較低層次的Voronoi 圖定義了發(fā)射陣地的Voronoi 鄰居，這有助于通過將局部搜索空間限制為K 環(huán)Voronoi 鄰居來優(yōu)化每個轉(zhuǎn)載陣地的發(fā)射裝置路線問題。

1.2.2 算法實施

通過BVDH［1］算法對此問題進行求解，算法基本步驟為：

1）求解初始解

得到此問題的初始解，如果發(fā)射陣地位于上層轉(zhuǎn)載陣地Voronoi 圖的Voronoi 區(qū)域，則該發(fā)射陣地最初被分配到該轉(zhuǎn)載陣地。分配給轉(zhuǎn)載陣地的發(fā)射陣地的路線通過單個轉(zhuǎn)載陣地的“集群優(yōu)先，路線優(yōu)先”VRP［2］算法生成。

圖2 Voronoi 圖

圖3 雙層Voronoi 圖模型

2）初始解改進

運用SA 算法改進初始解，改進階段分為兩部分，為在一個轉(zhuǎn)載陣地的范圍內(nèi)的路線和轉(zhuǎn)載陣地之間的路線。首先為了改善一個轉(zhuǎn)載陣地范圍內(nèi)的路線，該算法通過將局部搜索空間限制為K 環(huán)Voronoi 鄰居內(nèi)并使用3 個流行的鄰居結(jié)構(gòu)1-0 交換移動，1-1 交換移動和2-opt 移動［3］來將發(fā)射陣地從一個路線重新排列到另一個路線。其次為改善在轉(zhuǎn)載陣地交匯間的發(fā)射裝置路徑，本文采用1-0交換方式和1-1 交換方式對初始解進行改進，這兩種方式是在上層Voronoi 圖的Voronoi 邊緣的K 環(huán)Voronoi 鄰居中實現(xiàn)的。不選用2-opt 移動是因為它可能會在站點上生成許多路由而增加當(dāng)前解決方案的總路線長度。算法改進過程如圖4 所示。

圖4 SA 算法改進步驟

BVDH 算法流程如下頁表1 所示。

3 雙波次打擊雙層規(guī)劃模型建立

3.1 模型建立

本文以雙波次打擊為例，建立雙層規(guī)劃模型，上層為整體最短機動路徑，下層為從第1 波次發(fā)射陣地到達(dá)轉(zhuǎn)載陣地進行轉(zhuǎn)載并機動至第2 波次發(fā)射陣地進行第2 波次發(fā)射的最短路徑。即

表1 BVDH 算法流程

其中，l1與l2分別表示第1 波次與第2 波次總的機動距離表示a 類發(fā)射裝置k 從待機陣地d 到發(fā)射陣地f1的距離；表示a 類發(fā)射裝置k 從發(fā)射陣地f1到轉(zhuǎn)載陣地z 的距離；表示a 類發(fā)射裝置k從轉(zhuǎn)載陣地z 到發(fā)射陣地f2的距離；為1 時表示a 類發(fā)射裝置k 從待機陣地d 到發(fā)射陣地f1，為0 時表示a 類發(fā)射裝置k 未從待機陣地d 到發(fā)射陣地f1；為1 時表示a 類發(fā)射裝置k 從發(fā)射陣地f1到轉(zhuǎn)載陣地z，為0 時表示a 類發(fā)射裝置k 未從發(fā)射陣地f1到轉(zhuǎn)載陣地z；為1 時表示a 類發(fā)射裝置k 從轉(zhuǎn)載陣地z 到發(fā)射陣地f2，為0 時表示a 類發(fā)射裝置k 未從轉(zhuǎn)載陣地z 到發(fā)射陣地f2。

在第1 波次齊射過程中，每個發(fā)射點位的使用不得超過一次：

在第1 波次齊射完畢后，通過在轉(zhuǎn)載區(qū)域轉(zhuǎn)載后到達(dá)第2 波次發(fā)射點位，發(fā)射陣地只能使用一次：

第1 波次與第2 波次發(fā)射點位不得重復(fù)：

同一時刻，轉(zhuǎn)載陣地容納的發(fā)射裝置數(shù)量上限為s

其中，s 表示轉(zhuǎn)載陣地可以同時作業(yè)的發(fā)射裝置的數(shù)量，對于給定的作戰(zhàn)對象，s 是已知的。參與作戰(zhàn)的發(fā)射裝置總數(shù)少于各個待機陣地的發(fā)射裝置的總數(shù)

其中，S 表示發(fā)射裝置的總數(shù)，對于給定的作戰(zhàn)對象，S 是已知的。構(gòu)建雙層規(guī)劃模型為：

3.2 算法設(shè)計

設(shè)計適應(yīng)于此問題的遺傳算法求解最佳的機動路徑并進行機動調(diào)度，算法流程為：

Step1：確定染色體配置方案。將兩個波次的打擊任務(wù)分別定義為第1 波次發(fā)射編碼段，第2 波次發(fā)射編碼段及轉(zhuǎn)載陣地編碼段如圖5 所示。

圖5 染色體編碼圖

Step2：確定目標(biāo)函數(shù)。對于不同的發(fā)射裝置，不同的道路情況，求解出所有發(fā)射裝置的最短機動路徑；以所有發(fā)射裝置的最短機動路徑為適應(yīng)度函數(shù)，并使得兩個波次發(fā)射點位于同一轉(zhuǎn)載陣地的服務(wù)區(qū)內(nèi)，通過求解最小適應(yīng)度值來搜索最優(yōu)的機動方案。染色體編碼如圖6 所示。

圖6 染色體編碼圖

Step3：算法適應(yīng)性改造

1）隨機初始化種群方案；

3）交叉。從種群中隨機選取兩個個體，首先根據(jù)交叉概率判斷是否交叉，然后進行交叉操作。當(dāng)需要對發(fā)射陣地進行交叉時，首先判斷需要交叉的發(fā)射點是否與本染色體的發(fā)射點基因重復(fù)，如果重復(fù)，則放棄交叉操作；

4）變異。從種群中隨機選擇一個個體進行變異，當(dāng)需要對發(fā)射陣地變異時，首先判斷發(fā)射點位是否重復(fù)，如果重復(fù)，則放棄變異；

5）算法實施。根據(jù)遺傳算法特點及本問題的特殊性，建立算法實施框架如圖7 所示。

圖7 算法流程圖

4 算例分析

對于有2 個待機陣地、5 個轉(zhuǎn)載陣地、60 個發(fā)射陣地及62 個道路節(jié)點的給定路網(wǎng)如圖所示的具體路網(wǎng)進行兩個波次打擊問題的路徑規(guī)劃，每個波次使用24 輛發(fā)射裝置。其中，各個節(jié)點分別表示待機陣地（D）、轉(zhuǎn)載陣地（Z）、發(fā)射陣地（F）和道路節(jié)點（J），藍(lán)色的道路表示單行道，紅色的道路表示雙行道。

圖8 作戰(zhàn)路網(wǎng)

第1 階段：得出初始解［12］。

創(chuàng)建轉(zhuǎn)載陣地、發(fā)射陣地的Voronoi 圖以及發(fā)射陣地分布線的K 環(huán)Voronoi 鄰居。得出每個轉(zhuǎn)載陣地對于發(fā)射陣地的初始配屬如下頁圖9 所示。

初始陣地配屬關(guān)系如下頁表2 所示。

初始機動方案如表3 所示。

機動總距離為5 017.231 km。

第2 階段：改進階段。

運用Voronoi 圖算法改進后的陣地配屬關(guān)系如表4。

圖9 陣地初始配屬圖

表2 初始陣地配屬

表3 初始機動配置

表5 改進機動配置

改進后的機動方案如表5 所示。

機動總距離為4 352.837 km。相比初始方案減少了15.26%。

5 結(jié)論

常規(guī)導(dǎo)彈多波次作戰(zhàn)過程中合理高效的波次轉(zhuǎn)換是取得戰(zhàn)爭主動權(quán)的有效方式，針對全局優(yōu)化過程中出現(xiàn)的算法復(fù)雜度高，優(yōu)化效率低的問題，建立常規(guī)導(dǎo)彈多波次打擊時發(fā)射陣地與轉(zhuǎn)載陣地的雙層Voronoi 圖模型，對各個發(fā)射陣地歸屬于某一特定的轉(zhuǎn)載陣地，將多中心優(yōu)化問題簡化為單中心優(yōu)化問題。在此基礎(chǔ)上構(gòu)建上層為全局最短路徑下層為第2 波次最短路徑的雙層規(guī)劃模型，設(shè)計適合于此模型的遺傳算法，有效降低了算法的復(fù)雜度，求解效率較高。