文/何苗　王強(qiáng)　荀毅　魏曉航

?

軍事工程搶修任務(wù)規(guī)劃問題研究

文/何苗王強(qiáng)荀毅魏曉航

摘 要：本文針對(duì)戰(zhàn)時(shí)軍事工程搶修問題，研究在搶修資源有限的情況下，如何科學(xué)合理地安排搶修活動(dòng)，最大限度恢復(fù)軍事工程防護(hù)能力。通過引入搶修時(shí)間窗，同時(shí)考慮軍事工程搶修的時(shí)間約束和邏輯約束，建立了使軍事工程防護(hù)能力恢復(fù)最大的搶修任務(wù)規(guī)劃優(yōu)化模型，設(shè)計(jì)了一種離散型粒子群算法對(duì)模型求解。最后，以戰(zhàn)場(chǎng)軍事工程搶修任務(wù)為背景，用算例驗(yàn)證了模型的實(shí)用性和算法的有效性。

關(guān)鍵詞：軍事工程搶修；任務(wù)規(guī)劃；時(shí)間窗；離散粒子群算法

現(xiàn)代信息化戰(zhàn)爭(zhēng)中，廣泛應(yīng)用高新技術(shù)，特別是精確制導(dǎo)武器和激光、隱形技術(shù)的發(fā)展和普及，使得軍事偵察手段日益先進(jìn)，武器系統(tǒng)命中率越來越高，破壞性越來越大。軍事工程設(shè)施作為保障部隊(duì)執(zhí)行作戰(zhàn)指揮、通信聯(lián)絡(luò)、后勤補(bǔ)給等任務(wù)的基本平臺(tái)，是敵方攻擊的首要目標(biāo)。因此，如何快速搶修戰(zhàn)損的軍事工程，盡快恢復(fù)其保障能力，是贏得未來戰(zhàn)爭(zhēng)主動(dòng)權(quán)的關(guān)鍵。在戰(zhàn)爭(zhēng)中，軍事工程搶修最重要的特點(diǎn)就是時(shí)效性，要求使用一切可以利用的搶修資源，在盡可能短的時(shí)間內(nèi)，對(duì)軍事工程的毀傷部分進(jìn)行修繕加固，使之恢復(fù)防護(hù)能力，抵御敵軍武器系統(tǒng)攻擊。軍事工程搶修任務(wù)具有不同的技術(shù)特點(diǎn)，同時(shí)，各搶修分隊(duì)力量構(gòu)成存在著差異，搶修資源有限，不同搶修分隊(duì)完成同一搶修任務(wù)的時(shí)間不同。因此，搶修資源優(yōu)化配置對(duì)盡可能完成更多的軍事工程搶修任務(wù)，最大限度恢復(fù)軍事工作在作戰(zhàn)體系中的保障能力具有顯著影響，軍事工程搶修任務(wù)規(guī)劃問題也就成了一個(gè)需要研究解決的問題。

目前，對(duì)軍事工程戰(zhàn)損評(píng)估、搶修組織實(shí)施和搶修裝備技術(shù)等方面均已有深入研究［1～3］。但是在軍事工程搶修資源配置和搶修任務(wù)規(guī)劃問題方面的研究甚少。關(guān)于搶修任務(wù)規(guī)劃調(diào)度問題的研究，主要針對(duì)戰(zhàn)場(chǎng)裝備搶修及應(yīng)急資源調(diào)度問題，建立基于排隊(duì)論的數(shù)學(xué)模型［4］、多需求點(diǎn)多資源的二層優(yōu)化調(diào)度模型［5］、非線性規(guī)劃模型［6］，采用蟻群算法［7］、遺傳算法［8］、蜂群算法［9］等優(yōu)化算法對(duì)問題進(jìn)行求解，為軍事工程搶修任務(wù)規(guī)劃問題的研究提供了新的思路和方法。本文將針對(duì)軍事工程搶修任務(wù)規(guī)劃問題的特殊性，建立搶修任務(wù)規(guī)劃模型，并采用一種離散粒子群算法對(duì)該模型進(jìn)行求解。

1.軍事工程搶修任務(wù)規(guī)劃模型

1.1問題描述

軍事工程搶修任務(wù)規(guī)劃是根據(jù)戰(zhàn)場(chǎng)態(tài)勢(shì)和軍事工程戰(zhàn)損評(píng)估結(jié)果，確定軍事工程搶修目標(biāo)任務(wù)的搶修時(shí)間窗口及所需搶修資源。針對(duì)每一個(gè)軍事工程搶修項(xiàng)目，結(jié)合戰(zhàn)區(qū)內(nèi)的工程保障力量，科學(xué)合理地組織搶修資源，組建工程搶修分隊(duì)，在軍事工程搶修任務(wù)要求的時(shí)間窗口內(nèi)及時(shí)做好搶修工作，最大限度恢復(fù)軍事工程防護(hù)能力。

軍事工程搶修任務(wù)規(guī)劃問題可以描述為：在某一戰(zhàn)斗區(qū)域內(nèi)有M個(gè)軍事工程搶修保障單位，每個(gè)單位有不同的保障資源，可以組成一個(gè)應(yīng)急工程搶修分隊(duì)。經(jīng)現(xiàn)場(chǎng)調(diào)查評(píng)估，結(jié)合戰(zhàn)場(chǎng)態(tài)勢(shì)，認(rèn)定共有N個(gè)軍事工程受到敵方攻擊受損，急需通過工程保障力量修繕恢復(fù)其防護(hù)能力。由于工程類別以及受損程度各異，同時(shí)，各個(gè)搶修分隊(duì)力量構(gòu)成不同，致使不同搶修分隊(duì)完成同一工程搶修任務(wù)的時(shí)間不同。另外，由于各個(gè)軍事工程在整個(gè)作戰(zhàn)體系中的地位作用差異以及戰(zhàn)場(chǎng)態(tài)勢(shì)的不同，各個(gè)搶修任務(wù)必須在一定時(shí)間范圍內(nèi)執(zhí)行，即任務(wù)時(shí)間窗約束。

1.2模型建立

設(shè)定軍事工程搶修任務(wù)集合N={1,2,L，n }，n為搶修任務(wù)數(shù)目，?j∈ N，[tsj,tej]為其搶修時(shí)間窗，tsj為其允許搶修的最早開始時(shí)刻，tej為其允許搶修的最晚結(jié)束時(shí)刻。Tj表示某個(gè)軍事工程搶修分隊(duì)開始對(duì)目標(biāo)工程j進(jìn)行搶修的開始時(shí)刻。?k∈ N，pk表示軍事工程k的任務(wù)優(yōu)先級(jí)，也可以認(rèn)為是軍事工程k在整個(gè)作戰(zhàn)體系中的重要性指標(biāo)。

軍事工程搶修分隊(duì)集合為M={1,2，L m}，m為搶修分隊(duì)的數(shù)目。?j∈ N，?i∈ M，tij表示搶修分隊(duì)i對(duì)軍事工程j進(jìn)行搶修的時(shí)間長(zhǎng)度。搶修任務(wù)目標(biāo)之間的線路為：，t d k j表示某一搶修分隊(duì)沿線路(k， j)轉(zhuǎn)移的時(shí)間。搶修分隊(duì)與搶修任務(wù)目標(biāo)之間的線路為：。tdik表示搶修分隊(duì)i從駐地出發(fā)，沿線路轉(zhuǎn)移到任務(wù)目標(biāo)(i， k)的時(shí)間。

綜上所述，可建立該問題的數(shù)學(xué)模型，目標(biāo)函數(shù)：

由于資源的有限性及搶修任務(wù)的多樣性，目標(biāo)函數(shù)設(shè)定為完成軍事工程搶修任務(wù)優(yōu)先級(jí)之和最大。

約束條件：

（1）每個(gè)軍事工程至多由一個(gè)搶修分隊(duì)完成搶修一次（小于1意味著沒有針對(duì)該軍事工程進(jìn)行搶修）：

（2）搶修分隊(duì)對(duì)任務(wù)目標(biāo)搶修的時(shí)間必須在時(shí)間窗范圍內(nèi)：

（3）每個(gè)搶修分隊(duì)至少對(duì)一個(gè)軍事工程完成搶修任務(wù)。

2.算法設(shè)計(jì)

2.1基本原理

粒子群優(yōu)化算法（Particle Swarm Optimization， PSO）是由James Kennedy和Russell Eberhart于1955年提出的一種基于群智能的隨機(jī)搜索算法［10］。基本粒子群算法的思想是模擬鳥群覓食的過程，將問題解空間中一個(gè)可行解看作一只鳥及所謂的“粒子”。這些鳥通過不停地改變自己的位置和速度去覓食，直到成功覓食（即最優(yōu)解）［11］?；玖Ｗ尤核惴ㄋ枋龅牧Ｗ游恢煤退俣榷际沁B續(xù)變量，難以求解在離散空間中建模的任務(wù)調(diào)度問題。本文將采用一種適合軍事工程搶修任務(wù)規(guī)劃的離散粒子群算法。

2.2算法求解步驟

針對(duì)軍事工程搶修任務(wù)規(guī)劃問題，每個(gè)粒子代表一個(gè)可行解，即任務(wù)分配方案。用自然數(shù)對(duì)任務(wù)進(jìn)行編碼，粒子編碼中的每一個(gè)自然數(shù)代表?yè)屝薹株?duì)，修任務(wù)數(shù)量為粒子編碼長(zhǎng)度。如圖所示，有10個(gè)搶修任務(wù)，3個(gè)搶修分隊(duì)。分隊(duì)1負(fù)責(zé)任務(wù)3和任務(wù)5，其中任務(wù)2和任務(wù)9沒有完成。得到一個(gè)粒子編碼為（2，0，1，2，1，3，2，3，0，3）。

圖1　離散粒子的編碼方式

結(jié)合軍事工程搶修任務(wù)規(guī)劃問題的特點(diǎn)，本文采用式（5）分步計(jì)算和修改粒子位置，首先是當(dāng)前粒子內(nèi)部分量之間的交換，再根據(jù)粒子的歷史最佳位置修改當(dāng)前位置，然后根據(jù)粒子群體的最佳位置調(diào)整當(dāng)前粒子位置。

其中，ω，c

1

，c

2

為擾動(dòng)因子，其取值范圍為[0,1]。函數(shù)

表示X

i

的第a個(gè)分量與第b個(gè)分量交換，a，b均為1到n之間的隨機(jī)整數(shù)（a＞b）。并以c

1

為概率對(duì)位置交換進(jìn)行擾動(dòng)，

。

經(jīng)過上述3個(gè)步驟，當(dāng)前粒子位置調(diào)整完成，得到一個(gè)新解。利用DPSO算法求解的流程如圖2所示。

圖2　DPSO算法求解流程

3.算例

在某作戰(zhàn)區(qū)域內(nèi)，有10個(gè)軍事工程搶修任務(wù)，分布在不同地里位置。共組建3個(gè)不同的工程搶修分隊(duì)，它們從駐地到各個(gè)軍事工程搶修任務(wù)點(diǎn)的轉(zhuǎn)移時(shí)間如表1所示，搶修分隊(duì)完成各個(gè)搶修任務(wù)的時(shí)間如表2所示，搶修分隊(duì)在各個(gè)搶修任務(wù)點(diǎn)之間的轉(zhuǎn)移時(shí)間如表3所示。各個(gè)搶修任務(wù)接受搶修的時(shí)間窗及任務(wù)優(yōu)先級(jí)如表4所示。

利用DPSO算法對(duì)模型進(jìn)行求解，設(shè)定種群規(guī)模為20，最大迭代次數(shù)為1000次，獨(dú)立運(yùn)行20次，目標(biāo)函數(shù)值穩(wěn)定在53，可得軍事工程搶修任務(wù)方案如表5所示。由于時(shí)間約束的限制，搶修任務(wù)3、任務(wù)5和任務(wù)7未能完成。

4.結(jié)語

現(xiàn)代戰(zhàn)爭(zhēng)中，軍事工程設(shè)施在體系對(duì)抗中具有重要作用，對(duì)戰(zhàn)損軍事工程組織實(shí)施搶修具有較強(qiáng)的時(shí)間限制，即要在規(guī)定時(shí)間范圍內(nèi)完成盡可能多的搶修任務(wù)，最大限度恢復(fù)軍事工程體系對(duì)抗中的防護(hù)能力。本文研究了基于搶修時(shí)間窗的軍事工程搶修任務(wù)規(guī)劃問題，綜合考慮搶修活動(dòng)的時(shí)間約束和邏輯約束，建立了搶修任務(wù)規(guī)劃模型，并利用DPSO算法求解。算例表明，該模型和算法能較好地解決軍事工程搶修任務(wù)規(guī)劃問題。

表1　搶修分隊(duì)到各目標(biāo)的轉(zhuǎn)移時(shí)間

表2　搶修分隊(duì)完成任務(wù)的時(shí)間

表3　各個(gè)搶修任務(wù)目標(biāo)之間的轉(zhuǎn)移時(shí)間

表4　任務(wù)時(shí)間窗及優(yōu)先級(jí)

表5　搶修方案

（作者單位：中國(guó)人民解放軍后勤工程學(xué)院）

參考文獻(xiàn)

［1］王鳳山，吳禮發(fā).軍事工程毀傷評(píng)估與搶修計(jì)劃生成機(jī)制研究［J］.計(jì)算機(jī)與數(shù)字工程，2011，39（10）：96～100.

［2］袁輝，王鳳山.軍事工程毀傷評(píng)估的組合智能模型［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49（9）：23～28.

［3］王鳳山.地下工程搶修作業(yè)計(jì)劃與控制要求及其策略研究［J］.系統(tǒng)科學(xué)學(xué)報(bào)，2010，18（4）：53～57.

［4］王小飛，蘇凡囤，王海濤，鐘曉谷.基于排隊(duì)論的戰(zhàn)時(shí)工程裝備搶修任務(wù)調(diào)度［J］.兵工自動(dòng)化，2012，31（10）：29～32.

［5］曹繼平，宋建社，古西睿，何志德.戰(zhàn)場(chǎng)搶修多需求點(diǎn)多資源二層優(yōu)化調(diào)度模型［J］.系統(tǒng)工程與電子技術(shù)，2008，30（8）：1509～1513.

［6］呂學(xué)志，于永利，張柳，陳樂，董岳，劉文武.資源約束的拼件維修模型與粒子群求解算法［J］.系統(tǒng)工程理論與實(shí)踐，2013，33（4）：1013～1018.

［7］蔡紀(jì)偉，賈云獻(xiàn)，孫曉，張曉康.蟻群算法在戰(zhàn)損裝備搶修任務(wù)指派中的應(yīng)用研究［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012，42 （19）：160～165.

［8］王銳，李羚偉，郭波，馬武彬.一種基于多目標(biāo)多約束的戰(zhàn)時(shí)搶修力量調(diào)度［J］.兵工自動(dòng)化，2010，29（1）：34～37.

［9］王浩.基于蜂群算法的戰(zhàn)時(shí)毀傷裝備維修任務(wù)調(diào)度研究［J］.火力與指揮控制，2009，34（S1）：141～144.