裝甲裝備機動搶修路線決策方法

王少華,董原生,呂會強,劉宏祥,彭正軍

(1.裝甲兵學(xué)院 a裝備保障與再制造系； b.科研學(xué)術(shù)處， 北京 100072；2.中國人民解放軍77626部隊， 拉薩 850000)

在信息化戰(zhàn)爭中，武器裝備的威力和命中精度將大大提高，作為陸軍主戰(zhàn)力量，裝甲裝備的損傷機率將隨之提高。作為部隊補充和恢復(fù)戰(zhàn)斗力的主要手段，戰(zhàn)場搶修能否成功組織實施將極大程度地影響成敗。戰(zhàn)場搶修力量前出到陣地現(xiàn)場或損傷點附近的掩蔽處實施搶修，能夠最大程度地縮短搶修時間、提高搶修的時效性[1]。

在快節(jié)奏的戰(zhàn)場上，允許戰(zhàn)場搶修的時間是有限的，有限的戰(zhàn)場搶修力量常常需要在短時間內(nèi)前出搶修多臺損傷裝備，因此承擔(dān)機動搶修任務(wù)的搶修組常常需要按照一定的順序搶修損傷裝備，搶修順序極大地影響著搶修任務(wù)完成的時效性甚至成敗，必須對其進行科學(xué)決策。機動搶修順序的決策受到?jīng)Q策目標(biāo)、機動量和機動難度、機動安全性、搶修任務(wù)量、搶修工期等諸多因素的影響，必須采用客觀決策方法決策，盡量降低主觀決策容易帶來的潛在風(fēng)險[2-5]。

目前，研究者已經(jīng)針對不同類型裝備提出了不少相關(guān)的戰(zhàn)場搶修決策優(yōu)化方法。田冕[2]采用層次分析法、劉利[3]采用貝葉斯網(wǎng)絡(luò)理論、何曉暉[4]采用模糊理論提出了相應(yīng)的多裝備搶修順序決策方法。王雷在考慮搶修時限的條件下提出了搶修順序決策方法，但該模型未從指揮角度區(qū)分裝備搶修時限的個體差異性，影響了決策的合理性。針對這一不足，本研究考慮單裝搶修時限因素，對搶修順序決策優(yōu)化模型進行研究。

1 戰(zhàn)場機動搶修決策問題分析

1.1 問題描述

假設(shè)機動搶修組預(yù)先編成并作為一個整體序貫地?fù)屝迵p傷裝備。因此從理論上可以將機動搶修決策問題視為路徑尋優(yōu)問題，典型的旅行商問題以路徑最短為目標(biāo)進行路徑?jīng)Q策，而戰(zhàn)場搶修決策影響因素不僅包括搶修組與各損傷裝備以及損傷裝備之間距離的影響，而且與路線受威脅程度、任務(wù)量、器材備件滿足程度以及搶修時限等因素緊密相關(guān)，因此決策模型也較復(fù)雜[5]。

問題描述：假設(shè)1個搶修組由其所屬位置出發(fā)，在戰(zhàn)場進行巡回?fù)屝?，假設(shè)戰(zhàn)場共有包含搶修組出發(fā)位置的n個搶修點，以1,2,…,n來表示，其中1為出發(fā)點，其他為搶修點。定義機動搶修頂點向量V，V=(v1,v2,…,vi,…,vn)，其中，vi為機動搶修路線上的第i個搶修點。定義機動時間矩陣Y，Y={yij|vi,vj∈V}，其中i，j分別為機動路線的起止點。定義搶修時間向量P=(p1,p2,…,pi,…,pn)，其中pn是第n個搶修點的搶修耗時，假設(shè)每個搶修點對應(yīng)確定的搶修任務(wù)，每個搶修點所需的搶修資源以及搶修時間是確定的，即P為常值向量。定義搶修時限向量D=(d1,d2,…,di,…,dn)，其中di是第i個搶修點的搶修任務(wù)時限，即該搶修點允許的最晚修竣時間。

定義E={(vi,vj)|vi,vj∈V，i≠j}，E為連接各頂點邊的集合，表示搶修點間的機動巡回路線。機動搶修的巡回路線為一條起止均為v1的閉合回路，v1為機動搶修組的出發(fā)點，搶修組在遍歷搶修點之后重新返回出發(fā)點v1。

1.2 決策目標(biāo)

機動搶修決策的目標(biāo)主要是滿足作戰(zhàn)需求，即盡量降低對作戰(zhàn)時間的影響，常用的目標(biāo)有：搶修總耗時最短或維修點的待修延誤時間最短。如果決策目標(biāo)不考慮維修時限對搶修行動的影響，僅考慮搶修總耗時最短，由于各搶修點搶修耗時為確定值，所以搶修總耗時最短問題，即等價為搶修巡回路線最短問題，即在網(wǎng)絡(luò)圖G中尋找一條路徑，該路徑經(jīng)過每個頂點且只經(jīng)過一次，目標(biāo)是使該路徑上的機動時間之和最小。這是一個典型的旅行商問題(Traveling salesman problem，TSP)，在圖論中屬于Hamilton圈問題，是一種NP完全的組合優(yōu)化問題，可用分枝定界、0-1規(guī)劃、蟻群算法或遺傳算法等解析或智能算法進行求解。但是由于需要考慮搶修時限的影響，即單純以搶修總耗時最小并非決策者的唯一關(guān)注點，以恢復(fù)戰(zhàn)斗力為目標(biāo)的戰(zhàn)場搶修，必須在戰(zhàn)術(shù)允許的時間內(nèi)修竣損傷裝備，即搶修時限是不可忽視的決策影響因素。為此在決策目標(biāo)中引入搶修時限因素[6]。

搶修時限因素可以為硬約束或軟約束，硬約束即表示不接受搶修完成時間超出搶修時限的事件發(fā)生，而軟約束則以搶修完成時間超出搶修時限的總延誤時間最短，則硬約束可視為軟約束的一種特殊情況，若軟約束條件下最優(yōu)決策方案能夠滿足硬約束，表示硬約束條件下該問題可解，否則表示該問題無解。

定義步時間矩陣S={sij}，其中i，j=1，2，…，n；i≠j；sij=yij+pj，sij表示搶修組從vi出發(fā)直接到達vj并完成在vj的搶修任務(wù)的“一步”所需要的時間。

對于軟約束來說，決策目標(biāo)是使搶修總耗時和搶修延遲時間都最短，這兩個目標(biāo)值常常無法同時達到最優(yōu)。為此在目標(biāo)函數(shù)中引入系數(shù)，將兩個目標(biāo)值進行線性融合。對于V的一個巡回次序C={c1，c2，…，ci，…，cn}，其中ci∈V(i=1，2，…，n)，則有模型：

(1)

λ1+λ2=1

(2)

式中，λ1和λ2分別表示巡回路線最短和延遲時間最短這兩個目標(biāo)的相對權(quán)重，通常由決策者預(yù)先給定。

2 決策求解算法

由第1節(jié)可知，機動搶修順序決策問題實際上屬于有約束的TSP問題，目標(biāo)函數(shù)不僅考慮步序的問題，而且考慮到了延遲時間最短這一目標(biāo)，用于解決典型TSP問題的許多模型和方法都不再適用，為此采用智能尋優(yōu)算法進行路徑尋優(yōu)，本文采用遺傳算法求解上述模型[7-8]。

遺傳算法(Genetic Algorithm，GA)是模擬生物遺傳學(xué)中自然選擇和迭代進化過程的智能尋優(yōu)算法，它具有廣泛的適應(yīng)性，對于求解復(fù)雜TSP問題有著顯著的效果。

1) 編碼方案

按巡修路線上的維修點順序進行編碼，即染色體中的每個基因代表一個維修點的編號。由于搶修出發(fā)點已經(jīng)確定，即染色體首位皆為1，因此以實際搶修點編碼序列構(gòu)造染色體，染色體長度為n-1，采用隨機排序數(shù)列生成函數(shù)構(gòu)造染色體，采用實值編碼。

2) 適應(yīng)度函數(shù)

初始種群根據(jù)編碼規(guī)則隨機產(chǎn)生一代個體，根據(jù)每個染色體的表現(xiàn)計算出目標(biāo)函數(shù)值，將第j個染色體對應(yīng)目標(biāo)函數(shù)值記為Tj，將個體j的適應(yīng)度定義為：

(3)

其中，N為遺傳種群的規(guī)模，即一代染色體的數(shù)量。

為了有效地控制求解過程的效率，對染色體適應(yīng)度值進行過程修正，修正后的適應(yīng)度表示為f′(j)，則有：

(4)

式中： max(Tj)為本代個體的最大目標(biāo)函數(shù)值；η為適應(yīng)度系數(shù)，η取值越小，淘汰率越高，收斂速度越快，這里采用變適應(yīng)度系數(shù)的策略，從0.95到0.15遞減取值，以防止過早收斂，無法求得全局最優(yōu)解。

3) 選擇算子

為確保種群進行全局尋優(yōu)，采用輪盤賭的方法產(chǎn)生新一代種群，然后進行交叉和變異操作。

4) 雜交算子

雜交算子采用順序交叉的方法，即隨機確定交叉段的起止點位置，對中間段的基因進行交叉操作。為了確保交叉之后的染色體仍然對應(yīng)可行解，在被交叉的兩個染色體中隨機選中一段長度隨機的基因串，進行交叉操作，對基因串進行檢驗和調(diào)換，交叉操作方法示意圖如圖1所示。

如圖1所示，在染色體b中找到將染色體a中被選中的基因段{6，4，5}的位置，按照{(diào)6，4，5}的順序進行重新排序并插回原染色體，同樣，在染色體a中找到染色體b中被選中的基因段，做相同操作，交叉前后的基因段則都能夠?qū)?yīng)決策可行解。

5) 變異算子

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

6) 進化策略

考慮到選擇算子和交叉算子的迭代擇優(yōu)效率不高，為了保存進化成果，每一代經(jīng)過選擇、交叉和變異操作后都保留當(dāng)代最優(yōu)個體，剔除最差個體，以保證算法具有全局收斂性。

3 應(yīng)用實例

假設(shè)在某次聯(lián)合進攻戰(zhàn)役過程中，我數(shù)字化合成部隊與當(dāng)面之?dāng)痴归_攻防作戰(zhàn)，在正面作戰(zhàn)方向上，數(shù)字化合成部隊所屬兩個合成作戰(zhàn)營作為第一梯隊在炮兵防空兵掩護下，突破敵永久防御攻勢向縱深發(fā)展，由于受敵地雷和反坦克武器的攻擊，第一梯隊報告坦克和步兵戰(zhàn)車共戰(zhàn)損15臺，受前方指揮所指示，后方指揮所決定派出一支搶救搶修隊立即前出進行戰(zhàn)場搶修。

已知各戰(zhàn)損裝備的待修位置，前方搶修力量已經(jīng)完成損傷的初步評估，預(yù)測得出各單裝的現(xiàn)地?fù)屝薰r，如表1所示，各搶修點之間的距離換算為時間，如表2所示，為了保證進攻的持續(xù)性，前方指揮所對各臺裝備的修竣時限提出了要求，如表3所示。后方指揮所要為搶救搶修隊規(guī)劃搶修路線，目標(biāo)是使得戰(zhàn)損裝備總延誤時間最小。

表1 損傷裝備現(xiàn)地?fù)屝薰r min

表2 損傷裝備之間的距離 min

續(xù)表(表2)

表3 損傷裝備修竣時限 min

應(yīng)用Matlab編寫遺傳算法求解程序，進行決策優(yōu)化求解，主要計算過程如下：

1) 利用表1～3中的數(shù)據(jù)得到步時間矩陣和修竣時間矩陣，給定λ1和λ2的值，設(shè)定遺傳算法參數(shù)，隨機生成初始種群。

2) 根據(jù)式(4)計算初始種群中各個個體的適應(yīng)度值。

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

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

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

6) 根據(jù)當(dāng)次種群保留概率用當(dāng)代最優(yōu)個體替換最差個體。

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

8) 判斷是否達到最大遺傳代數(shù)或代際適應(yīng)度最優(yōu)值變化值低于閾值，則算法終止并輸出最優(yōu)結(jié)果；否則轉(zhuǎn)第2)步。

根據(jù)案例中決策問題的特點，設(shè)定λ1=0.3，λ2=0.7，設(shè)定遺傳算法參數(shù)為：群體規(guī)模為50，最大迭代次數(shù)為 2 000，適應(yīng)度系數(shù)為0.95，種群初始保留概率為0.95，雜交概率為0.7，變異概率為0.25。

按照上述參數(shù)進行決策求解，求解過程如圖2所示，由圖2可知，在約300次迭代后，最優(yōu)解即收斂到最優(yōu)值。

得到最佳的巡修路線為：

{1→9→6→2→3→4→8→12→16→15→11→7→5→10→14→13}

按照該巡修路線實施搶修，本次任務(wù)預(yù)計耗時 1 184min。但由于作戰(zhàn)需求，無法在給定搶修時限內(nèi)完成全部搶修任務(wù)，各搶修任務(wù)的修竣時間與修竣時限的對比圖如圖3所示。

如圖3所示，對于個搶修點來說，若修竣時間低于修竣時限，表示及時完成了該任務(wù)，此類事件越多，越符合決策者的需求。由圖中可知共有5個搶修任務(wù)及時完成，分別為任務(wù)9、6、2、3、4。由于采用式(1)中的決策目標(biāo)函數(shù)，綜合了搶修總時間和搶修延遲時間最短這兩類目標(biāo)，因此該決策解是權(quán)衡這兩類目標(biāo)的最優(yōu)解，與λ1和λ2的取值有關(guān)。

當(dāng)λ1=1，λ2=0時，則決策目標(biāo)為搶修總時間最短，當(dāng)λ1=0，λ2=1時，則決策目標(biāo)為搶修總延誤時間最短。

按照上述參數(shù)進行求解，可分別得到兩種情況下的最優(yōu)決策解，將圖2所示方案標(biāo)識為方案1，結(jié)果如表4所示。

表4 不同條件下巡修路線決策最優(yōu)解 min

由表4所示數(shù)據(jù)可知，若僅以搶修總時間最短為目標(biāo)，則搶修總時間最小可達到1 173 min，若僅以總延誤時間最短，該值最小可達到3 576 min，若λ1和λ2取0～1之間數(shù)值的話，則這兩類指標(biāo)將得到權(quán)衡。

4 結(jié)論

在信息化戰(zhàn)爭條件下，對于有限的戰(zhàn)場搶修力量來說，戰(zhàn)場機動搶修順序決策直接關(guān)系著搶修人員的安全性和搶修效益。在戰(zhàn)術(shù)允許的時間內(nèi)完成搶修，是作戰(zhàn)指揮員關(guān)注的重點，必須綜合考慮總搶修時間與搶修延遲時間，使戰(zhàn)場搶修效益最大化。由于搶修行動本身在資源消耗、時間消耗上存在較大的不確定性，本文對其進行了簡化處理，在下一步的研究中，有必要針對單裝搶修時間與資源的隨機特性確定最優(yōu)的搶修順序。