裝備伴隨搶修任務分配決策方法

王少華， 呂會強， 董原生， 張遠

(1.陸軍裝甲兵學院 裝備保障與再制造系， 北京 100072； 2.陸軍裝備部 信息保障室， 北京 100072)

0 引言

在信息化戰爭中，武器裝備的威力和命中精度將大大提高，裝甲裝備的損傷機率將隨之提高。作為部隊補充和恢復戰斗力的主要手段，戰場伴隨搶修能能夠及時有效地恢復部隊戰斗力，通過科學決策提高伴隨搶修的實施效率，是裝備保障決策者關注的重點。

伴隨搶修主要根據作戰力量部署，在戰場前沿編設多個小規模的伴隨搶修組，利用戰斗間隙，前出至現地的多個搶修作業點遂行搶修任務，搶修具有力量規模小、風險高、任務強度大、時間短的特點。在有限時間內，伴隨搶修力量往往無法完成全部的搶修任務，在此背景下，如何通過科學決策分配伴隨搶修任務，對伴隨搶修任務的成敗起著決定性的作用。對于多搶修組，決策者面臨的決策問題主要有兩個內容，一是如何在搶修任務集合中選擇任務并將其分配給各搶修組，二是為每個搶修組確定最佳的搶修任務實施順序，確保搶修任務又多又快地完成。伴隨搶修決策受到決策目標、搶修任務量、搶修時間、戰場環境等諸多因素的影響，必須采用客觀的決策方法進行決策，以盡量降低主觀決策容易帶來的潛在風險[1-3]。

目前，很多學者已經針對不同類型的決策問題提出了相關的戰場搶修決策優化方法。在未考慮搶修時間限制的情況下，田冕等[4]采用層次分析法、劉利等[5]采用貝葉斯網絡理論、何曉暉等[6]采用模糊理論提出了多裝備搶修順序決策方法。王雷[7]在考慮搶修時限的條件下提出了搶修順序決策方法，但模型未從指揮角度考慮任務匹配問題，而且搶修時限設定為唯一值，與戰場搶修決策者面臨的現實問題還有一定的差距。針對這一不足，本文考慮多搶修組完成多個搶修任務，且考慮單裝搶修時限的獨特性，對典型伴隨搶修任務分配決策方法進行研究。

1 裝備伴隨搶修決策問題分析

裝備伴隨搶修具有時效性強、隨機性和不確定性高的特點[8]。裝備戰場伴隨搶修的基本特點[9]是：

1)一個搶修隊通常包含若干搶修組，保障一個作戰方向或一個作戰地域的裝備搶修任務。每個伴隨搶修通常依車編組，攜帶必要的器材備件和機工具等實施搶修。

2)裝備伴隨搶修任務強度通常較高，即在給定的時間窗口內，搶修組通常無法完成所有的搶修任務。

3)伴隨搶修時機通常是戰斗間隙或戰斗轉換時，搶修作業點通常分散在多個地點，每個作業點通常須在規定的時限內完成搶修，否則需要轉運后送。

根據上述特點，假定當前所有損傷裝備及其位置已經明確，每個損傷裝備的搶修耗時以及修竣時限同時給定，搶修決策者需要在所有的待修裝備中選擇適量的任務，并為每個搶修組分配搶修任務；而后為每個搶修組確定搶修任務的實施順序，以最大限度地修竣損傷裝備。圖1所示為伴隨搶修行動流程。

如圖1所示，從實施過程看，伴隨搶修主要按照技術準備并前出、按既定順序實施搶修作業和撤收的步驟實施。對于一個搶修組，給定搶修任務的情況下，搶修決策的內容主要是各任務的搶修順序。

當面對多個搶修組以及搶修任務時，決策者需要根據各作業點的搶修耗時、修竣時限、所處位置做出決策，其決策目標是最大限度地發揮各搶修組的能力，在修竣時限范圍內完成盡量多的搶修任務[10]。

由上述分析可知，裝備伴隨搶修決策主要是根據搶修組數量，在待修任務集合中選擇任務并確定搶修順序，使修竣裝備數量最大化。

2 裝備伴隨搶修決策建模

如第1節所示，多任務—多搶修組條件下，裝備搶修任務分配決策實際上是搶修任務分組和搶修順序的聯合決策。

2.1 伴隨搶修時序過程模型

問題描述：假設當前待修裝備的總數量為Ntot，搶修組數量為M(M

將搶修組的出發點編號為1，其他搶修作業點按照從2至Ntot+1的順序賦予唯一的初始任務編號，即搶修作業點初始任務編號為1，2，…，Ntot+1.

定義搶修時間向量P=(p1,p2,…,pi,…,pNtot+1)，其中pi是作業點i的搶修耗時，假設每個搶修作業點所需的搶修時間是確定的，即P為常值向量。

定義修竣時限向量D=(d1,d2,…,di,…,dNtot+1)，其中di是作業點i的搶修任務完成時限，即該作業點允許的最晚修竣時間，這里將修竣時限設為硬約束，即若無法在修竣時限內修復損傷裝備，則不搶修該裝備。

定義機動時間矩陣E={ei,j|1≤i,j≤Ntot+1}，ei,j表示由作業點i向j機動所消耗的時間(min)，有ei,j=ej,i(2≤i,j≤Ntot+1)，ei,i=0.

對于這個給定的任務集合，可以選擇不同的搶修順序，搶修組的機動路線將對應變化，搶修任務的完成狀態和數量也將隨之變化。假定按照作業順序對搶修組1分配到的任務進行排序，排序后的任務為{vl,1，…，vl,k，…，vl,NAi+1|1≤vl,k≤Ntot+1},其中vl,k為搶修組l所分配任務中排序優先度為k的作業點初始任務編號，由于各搶修組必須從配置點出發，因此對于任何搶修組有vl,1=1，其他任務的順序為隨機變量，且1個搶修組內各任務編號不重復，即保證一個任務只能被執行一次。

定義修復時間向量Sl，與給定的任務分配方案相對應，Sl={sl,k|k∈1,2,…,NAl+1}，sl,k表示作業點vl,k的任務完成時刻，隨搶修順序逐步累加。由于搶修時出發點都相同，因此有

(1)

不同的搶修任務排序方案決定著每個任務的完成時間，當任務完成時間早于預設的修竣時限時，表示該任務可如期完成，否則表示該任務將延遲完成。

根據作業點編號可得到搶修組l中第k個任務vl,k的修竣時限dvl,k.

對于當前搶修組l，搶修任務的如期完成數量為Nl，則有

(2)

式中：w(l,k)用來標識分配給搶修組l的第k個搶修任務能否如期完成，如果完成時刻sl,k早于給定的時限dvl,k，則該任務能夠如期完成，w(l,k)=1，反之w(l,k)=0.

若裝備修竣時限視為硬約束，則每個搶修任務都應在修竣時限之前完成，即如期完成的裝備數量應與分配的任務數量一致。為確保決策求解過程中得到可行解，這里用Ql標識任務完成狀態，Ql=1表示搶修組l能按要求完成全部任務，Ql=0表示該組不能按要求完成全部任務，即

(3)

在修竣裝備數量相同的情況下，裝備越早修竣越好，這里以被修裝備的修竣時刻與修竣時限之間的差值之和DLl作為對應的指標，DLl的計算公式為

(4)

從任務的角度，每個任務最多只能被執行一次，因此引入Xi,l表示作業點i搶修任務是否被賦予搶修組l，Xi,l=1表示搶修組l的任務中有作業點i搶修任務，Xi,l=0表示該組的任務中不包含作業點i搶修任務。

從決策角度，如期完成的任務數量越多越好，修復節約的總時間越長越好，根據決策者的決策偏好，可以將上述指標進行組合，建立相應的決策目標函數。

2.2 多搶修組條件下的搶修決策目標

搶修任務分配決策的目的是充分利用有限的時間和資源通過一次行動盡可能多地完成搶修任務。因此，一次行動能夠如期完成的搶修任務數量是最重要的決策變量，當任務完成量相同時，被修裝備的修竣時刻越早越好，即裝備修竣時刻與裝備修竣時限的時間差DL值越大越好。因此在給定V、P、D、E的前提下，綜合上述兩類決策指標構建決策目標函數：

(5)

式中：目標函數ObjV的第1部分為各搶修組選定任務數量之和，第2部分為裝備修竣時刻與裝備修竣時限的時間差DL與總修竣時限之比。當任務能夠如期完成時，DL的總和應低于總修竣時限，因此第2部分取值區間為0～1，而每多完成一個任務，目標函數即增1，因此確保了任務完成量作為主要決策變量，DL作為決策變量主要用來在選定任務的基礎上，對任務的執行順序進行優化。因此從權重上看，修復任務數對目標函數影響較大，當修復數量相同時，總節約時間越長的越好。第1個約束條件表示每個搶修組所分配的任務能夠全部如期完成；第2個約束條件表示每個待修任務只能唯一地分配一次，由一個搶修組進行搶修；第3個約束條件表示待修任務可以不分配。約束條件確保決策的解都是可行的，同時為任務分配和排序提供一定的尋優空間。

3 決策求解算法

上述決策問題屬于獎金收集車輛路徑問題(PCRVP)中的一類，目前已有啟發式算法、禁忌搜索和多階段算法等用于求解此類問題[11-13]。但該決策模型將任務完成數量和總節約時間作為目標函數，且將任務完成率作為約束條件，使模型具有一定的特殊性，因此設計遺傳算法進行優化求解。

根據第2節確定的決策優化模型，模型的目標是在多搶修組、多任務的條件下，求得任務分配的組合及每個任務組的優先排序方案，求解空間維度極高，求解難度較高，為了降低計算難度，本文選擇將遺傳算法與隨機遍歷算法相結合，對任務組合和子任務排序進行聯合求解[14]。求解思路如圖2所示。

圖2 決策求解過程Fig.2 Solving procedure of optimal decision-making

如圖2所示，采用遺傳算法進行決策尋優，對搶修任務進行隨機分配和排序，并將對應的搶修方案通過編碼表示為染色體，以2.2節提出的目標函數構建適應度函數，并進行迭代求解。由于受修竣時限的約束，染色體的隨機交叉、變異會產生許多不可行解。因此在每代種群迭代后，對染色體進行整理，以確保在當前任務分組的前提下，搶修序列是相對較優的。

1)染色體編碼方案。一個染色體應包含搶修方案的所有信息，即任務分配和排序。對于給定的Ntot個搶修任務和M個搶修組，按順序將搶修任務進行唯一的數值編號，即染色體中數值為i的基因對應表示作業點i搶修任務，將所有任務編號隨機排序，由于搶修出發點已經確定，即染色體首位皆為1；而后根據搶修組的數量和編號，確定染色體分段位置，并進行標識。分段標識數量與搶修組數量相同，且按照搶修組編號從小到大排列于染色體末尾，分段標識對應數值即為對應搶修組的任務隊尾所處位置。假定當前共2個搶修組遂行6個搶修任務，圖3示例所示即為一隨機染色體。

圖3 染色體編碼示例Fig.3 Example of chromosome coding

圖3中，染色體后兩位為分段標識，其數值分別為3和5，表示1至3所列任務為第1搶修組的任務，4至5所列任務為第2搶修組的任務，第1搶修組按照{1,2,6}的順序進行搶修，第2搶修組按照{4,5}的順序進行搶修，任務3未列入搶修計劃。

2)適應度函數。初始種群根據編碼規則隨機產生第1代個體，根據每個染色體的表現計算出適應度值，將第n個染色體對應適應度值記為Tn，將個體n的適應度定義為

(6)

(7)

式中：max(Tn)為本代個體的最大目標函數值；η為適應度系數，η取值越小，淘汰率越高，收斂速度越快，這里采用變適應度系數的策略，對η遞減取值，以防止過早收斂，無法求得全局最優解。

3)選擇算子。為確保尋優效率，采用輪盤賭策略進行種群迭代選擇，然后進行染色體交叉和變異。

4)雜交和變異算子。由于染色體編號屬于混合編碼，因此染色體不應隨機交叉。為了保證交叉后的染色體仍然對應可行解，采用整體交叉的方法，即被交叉的染色體中任務編碼子段整體交叉，如圖4所示。

圖4 染色體交叉操作方法Fig.4 Crossing rule of chromosome

圖4中，a和b都是2個搶修組、5個搶修任務條件下的待交叉染色體，交叉時對應將前6個位置的基因整體對調，即完成了染色體交叉。操作，按照{6，4，5}的順序進行重新排序并插回原染色體，同樣，在染色體a中找到染色體b中被選中的基因段，作相同操作，交叉前后的基因段則都能夠對應決策可行解。

變異算子采用雙位變異操作模式，在個體染色體中隨機抽取2個基因位進行交換而產生新的個體。

5)整理染色體。在不改變給定任務分組的情況下，采用隨機遍歷方式調整任務的排序，以提高節約時間的長度。

6)進化策略?？紤]到選擇算子和交叉算子的迭代擇優效率不高，為了保存進化成果，每一代經過選擇、交叉和變異操作后都保留當代最優個體，剔除最差個體，以保證算法具有全局收斂性。

4 應用實例

假設在某次聯合進攻戰役過程中，我數字化合成部隊與當面之敵展開攻防作戰，在正面作戰方向上，數字化合成部隊所屬兩個合成營突破敵永久防御攻勢向縱深發展，期間受敵地雷和反坦克武器的攻擊，兩營報告坦克和步兵戰車共戰損15臺，受前方指揮所指示，某伴隨保障隊指揮2個搶修組，準備前出進行戰場搶修。已知各戰損裝備的待修位置，前方搶修力量已經完成損傷的初步評估，預測得出各單裝的現地搶修工時(見表1)，各作業點之間的距離換算為時間(見表2)，為了保證進攻的持續性，前方指揮所對各臺裝備的修竣時限提出了要求(見表3)。

表1 各作業點現地搶修耗時

目前部署地域準備前出完成搶修任務，需為各組明確任務和搶修順序。

應用數學分析軟件MATLAB編寫遺傳算法求解程序，進行決策優化求解，主要計算過程如下：

1)利用表1～表3中的數據建立機動時間矩陣、修復時間矩陣和修竣時限矩陣，設定遺傳算法參數，隨機生成初始種群。

2)根據(5)式計算初始種群中各個個體的適應度值。

3)根據設定的種群保留概率隨機生成相應數量的子代個體，根據輪盤賭的策略選擇父代個體生成新種群。

4)根據雜交概率進行交叉操作。

5)根據變異概率進行變異操作。

6)根據當次種群保留概率用當代最優個體替換最差個體。

7)更新群體，用新種群替代父代種群，更新種群保留概率。

8)判斷是否達到最大遺傳代數或代際適應度最優值變化量低于閾值，則算法終止，并輸出最優結果；否則轉第2步。

根據案例中決策問題的特點，設定遺傳算法參數：群體規模為500，最大迭代次數為100，種群初始保留概率為0.95，雜交概率為0.7，變異概率為0.8.

表2 作業點之間的機動耗時

表3 各作業點修竣時限

按照上述參數進行決策求解，求解結果如圖5所示，由圖5可知，在約40次迭代后，最優解即收斂到相對最優值。

圖5 決策優化求解結果Fig.5 Iterated output results of decision-making algorithm

最優的染色體為{1,6,8,13,12,4,2,15,9,7,5,10,14,16,11,3,5,10}，得到最佳的任務分配方案和搶修順序為：第1搶修組{1,6,8,13,12,4}；第2搶修組{1,2,15,9,7}。按照該方案，搶修1組和2組分別能夠如期完成5個和4個裝備搶修任務。各搶修任務的具體修竣時間如表4所示。

表4 最優搶修方案搶修時序及修竣時刻

各任務的修竣時間和修竣時限的對比圖如圖6所示。

圖6 任務修竣時間與修竣時限對比圖Fig.6 Time-limit and estimated finishing time of selected spots

由上述方案可知，2個搶修組能夠如期完成10個搶修任務，在給定的15個搶修任務中，仍有5個作業點無法如期完成搶修任務，若無其他搶修組可用，可組織相應裝備后送。若有其他搶修組可用，可改變本案例中的相關參數，實施優化求解，得出最優的求解方案。

通過上述分析，可知本文提出的裝備搶修任務分配決策方法能夠有效地解決時間硬約束條件下裝備伴隨搶修任務的多組別分配問題，能夠有效地提高裝備搶修過程中的指揮決策效率。而且與簡單的搶修優先排序和單搶修組路線尋優相比，本模型考慮了裝備修竣時限的差異性以及多搶修組并行執行任務的現實需求，更符合作戰需要和戰場實際。

5 結論

本文主要以在規定時間內完成盡可能多的搶修任務為目標，在考慮多搶修組的條件下，對裝備搶修任務的選擇和分配問題開展研究，首先根據決策目標，確定了以任務完成數量為主，以時間消耗為輔的決策尋優目標，在搶修任務數量可變、搶修順序可變的前提下確定了多搶修組搶修決策優化模型。針對決策求解難度大的問題，通過改進遺傳算法，提出了可行的求解方法，并通過案例驗證了求解方法的有效性。

由于戰時裝備搶修態勢處于持續變化之中，一次搶修決策往往無法符合戰場實際需求，在下一步的研究中，有必要針對搶修任務分配的動態決策展開研究，以充分考慮搶修組的能力變化和搶修任務的實時變化。