作戰工程保障行動中的一種戰士- 裝備- 任務指派模型及其求解

張超省， 王健， 李政民， 楊鑫

(陸軍工程大學 訓練基地， 江蘇 徐州 221004)

0 引言

信息化戰爭條件下，只有能夠快速實現作戰力量機動、轉移和部署，才能在瞬息萬變的戰場態勢下捕獲制勝先機，這也對承擔機動保障、戰斗支援等一系列作戰工程保障任務的工程保障部隊提出了更高要求。面對具體工程保障行動，指揮員必須精準、高效地制定出指派哪些戰士操作哪些裝備執行哪些任務的決策。通常，制定決策時需要考慮以下3個方面問題：

1)一般情況下，戰士不會徒手完成任務，而是要操作裝備，并且工程保障部隊的戰士多數被培養成多技能操作手。指派戰士完成任務必須既要考慮到戰士的操作水平對裝備作業效率的影響，還要考慮到裝備自身的技術狀態會導致裝備作業效率的差異。比如一個技術熟練的操作手操作一臺裝備顯然比一個技術一般的操作手操作同臺裝備耗時更短、效率更高，同一個戰士操作一臺性能完好的裝備顯然比操作一臺性能堪用的同型裝備耗時更短、效率更高。

2)戰場環境下，上級對工程保障任務完成時間需求非常迫切，通常需要盡可能多的裝備協同作業以求最快完成任務；然而，多臺裝備在同一地域協同作業完成一項任務時，由于場地限制或配合影響，過多裝備甚至會使彼此妨礙。比如兩臺甚至三臺挖掘機協同挖掘大型平底坑，配合過程中不可能完全獨立同步開展，必然有一定程度的彼此干涉，總作業效率顯然比幾臺裝備作業效率簡單相加要小。

3)信息化戰爭條件下，工程裝備也逐漸向多功能方向發展，可以執行多種任務。盡管戰士具備多項技能，然而考慮到長時間操作產生疲勞進而帶來效率降低和安全隱患，允許工程裝備不間斷執行多種任務，但是操作裝備的戰士只能執行一項任務，也就是作戰工程保障行動中常說的“人歇車不歇”原則。比如某型多用途工程車，既可以進行挖掘作業，也可以進行裝載作業，可以讓該裝備連續執行挖掘和裝載兩項任務，盡量不讓操作該裝備的戰士連續疲勞作業去執行兩項任務。

綜上所述，作戰工程保障行動中任務的完成既與操作裝備的戰士相關，又與戰士操作的裝備相關，還與“人歇車不歇”以及協同作業效率相關，本質上是一個多約束、多維度的指派問題，屬于非確定性多項式- 難問題(NP-Hard問題)。

目前，分析作戰工程保障行動中人員任務指派問題的研究文獻尚不多見，但仍有一些其他領域的研究成果對解決前述問題具有一定的參考價值。經典指派模型僅研究一人一事、一事一人的指派問題，既不涉及裝備性能的差異，也不涉及協同作業的情形，因此不能直接被用來解決上述問題[1]。文獻[2]針對柔性生產系統中多技能工人不同技能熟練水平的情況，在不考慮工具影響工人工作效率的情況下，提出了一種多技能工人的分配模型。文獻[3-4]考慮了維修人員的技能分級和休息時間，建立了一個適用于多技能維修人員的任務指派模型。文獻[5]則考慮了維修人員的疲勞積累對維修能力的影響，建立了一個適用于維修單元的任務指派模型。文獻[6]針對任務中存在并行作業環節的情況，設計了一種改進匈牙利算法，從而解決包含并行環節的指派問題，但在并行作業環節中人員是獨立作業，并不存在協同作業的情形。文獻[7]針對某項任務需要多人協同作業的情形，建立了非線性的指派模型，但僅給出了兩人協作完成某項任務的求解過程。文獻[3-7]無一例外都是二維指派問題，只考慮人員和任務之間的指派關系，不涉及其他中間環節的約束。文獻[8-10]針對人力資源管理、多傳感器多目標追蹤、數據融合等領域的問題，分別建立了相應的三維指派模型；雖然其模型形式與本文所描述問題相差較大，但其建模過程值得借鑒。另外，上述研究也從另一角度說明了本文研究的指派問題并不是孤立的理論問題，而是一類極具應用價值的實踐問題。

本文創新性主要包括以下3個方面：1)通過對作戰工程保障行動特點的分析，將工程保障行動中任務的派遣定義為一個由“戰士- 裝備- 任務”構成的三維指派問題；2)綜合考慮戰士的多技能、裝備的多功能以及多臺裝備協同作業的相互影響，建立了作戰工程保障行動的三維指派模型；3)基于“人歇車不歇”的原則，設計了虛擬裝備法，實現了三維指派模型的快速求解。

1 三維指派模型建立

假設某項工程保障行動可以分為l項階段任務串聯執行，指揮員要指派n名戰士操作m臺裝備完成l項階段任務，其中n>m. 為了解決上述指派問題，按以下步驟構建指派問題的數學模型：

1)定義決策變量為

(1)

式中：xijk=1表示第i個戰士被指派操作第j臺裝備完成第k項任務，xijk=0表示第i個戰士未被指派操作第j臺裝備或未被指派完成第k項任務。

2)按照“人歇車不歇”原則，每名戰士最多被指派去執行一項任務，因此必須滿足如下約束條件：

(2)

3)按照“人歇車不歇”原則，每臺裝備都應該盡量多地參與各個階段的任務，但同時應該滿足該裝備的參與不會導致整體作業效率的降低，也即某臺裝備可能參與多個階段任務，也可能不參與任意一項階段任務，因此必須滿足如下約束條件：

(3)

4)每個階段任務的完成最少需要一臺裝備，參與的裝備數量最多不超過具有完成該項任務功能的裝備數量mk，因此必須滿足如下約束條件：

(4)

5)引入tijk表示第i個戰士操作第j臺裝備獨立完成第k項任務所需的時間，可以通過(5)式計算：

tijk=tjk/(cjeij),

(5)

式中：tjk表示理想狀態下(戰士熟練程度和裝備技術狀態均為最好)第j臺裝備獨立完成第k項階段任務的耗時；cj表示第j臺裝備的技術狀態影響系數，取值區間為[0,1]，數值越大表示作業效率越高；eij表示第i個操作手操作第j臺裝備的熟練程度影響系數，取值區間為[0,1]，數值越大表示熟練程度越高。

6)各階段任務耗時之和便是整個工程保障行動的耗時，優化目標即找到一組決策變量，使得完成工程保障行動耗時最短，即目標函數可表述為

(6)

綜上所述，(6)式描述了指派模型的目標函數，(2)式、(3)式和(4)式則共同組成了指派模型的約束條件。不難發現，本文所描述的模型不僅考慮了戰士的操作水平，還考慮了裝備的技術狀態和協同作業的影響系數。該模型隨著參與協同作業裝備數量mk的增加變成了mk次整數規劃問題，本質上屬于大規模非線性整數規劃問題。

2 快速求解算法設計

對于大規模非線性整數規劃問題，極特殊情形下可以通過變換將指派模型轉換為整數線性規劃問題，進而按照整數線性規劃方法求解；大部分情形下不能求出精確解，通常采用擴展割平面法[11]、廣義Benders分解[12]、分支定界算法[13]、外逼近算法[14]來獲得近似解，這些方法均是通過求解原非線性整數規劃問題的松弛問題或者線性子問題來進行求解[15]。然而，不同于現有的絕大多數非線性整數規劃問題，本文所描述指派模型的目標函數形式復雜且是高階非線性的，既不能變換為整數線性規劃問題，又難以找到對應的松弛問題或線性子問題，因此很多快速求解非線性整數規劃的優秀算法都不能直接用來求解本文模型。

如果沒有快速求解算法，通常的解法是：首先，構建一個由2l×m×n個解構成的較大可行域；然后，逐個判斷是否滿足(2)式、(3)式和(4)式給出的約束條件以縮小可行域；最后，通過(6)式求解可行域中最優化的決策變量。如果按照上述思路，完成求解將相當耗時，不能滿足信息化戰爭條件下快速決策的需要。

通過(3)式，不難發現：由于xijk為0-1變量，該公式所描述的約束條件實際上是無效的，導致不能為模型的求解構建一個較小可行域。進一步，如果將所有多功能裝備看作是多臺單功能裝備的虛擬集合，這樣(3)式所描述的約束條件就可以轉換為

(7)

式中：mv表示將多功能裝備拆分為虛擬裝備之后實際裝備與虛擬裝備數量之和，因此mv≥m.

上述方法之所以稱為虛擬裝備法，是因為分解后具有單功能的裝備物理上是不存在的，即虛擬的集合。通過虛擬裝備法，(3)式的約束力得到了增強，從而極大地縮小了指派模型的可行域。不僅如此，基于虛擬裝備法修改指派模型的約束條件后，本文設計了一套快速求解算法，以下是具體實現步驟：

1) 按階段任務進展的時間順序，給各階段任務進行編號，得到階段任務編號數組。

2)引入Ik,mk表示能夠協同完成第k項階段任務所有可能的裝備組合方案，可以指派到第k項階段任務中裝備組合方案的數量為

(8)

進一步，引入I表示整個工程保障行動中裝備組合方案的組合，由于整個工程保障行動是由各階段任務串聯而成，因此I=I1,m1∪I2,m2∪…∪Il,ml，整個工程保障行動對應的裝備組合方案數量為

(9)

3)從所有裝備組合方案選擇某一個裝備組合方案，并按裝備編號順序排列得到裝備編號數組。

4) 按照“人歇車不歇”的原則，要求每名戰士只需要執行一項任務，因此戰士的指派要綜合考慮工程保障行動的裝備組合和戰士的數量。那么，被指派到某一裝備組合方案中戰士組合方案的數量為

(10)

式中：mw=card(I)表示某一裝備方案組合對應的裝備數量，由于每臺裝備分配一名戰士，實際上也就是某一裝備方案對應的戰士數量。

5)從所有戰士組合方案中選擇某一個戰士組合方案，并按戰士編號進行全排序得到戰士編號數組。

6) 由于決策變量矩陣中元素的坐標是根據戰士編號、裝備編號和任務編號而給定的，可以根據步驟2、步驟4、步驟6確定決策變量中戰士、裝備、任務的坐標，可以得到一組決策變量x.

7)遍歷所有裝備組合方案的集合，再遍歷該裝備組合方案對應戰士組合方案的集合，可以得到所有決策變量x，逐次代入(6)式計算，得到最優決策變量及對應的任務耗時。

3 實例分析

某班要執行一項構筑掩蔽工事的行動，該行動主要由開挖平地坑(挖坑)、設置支撐結構(起重)、覆土作業(覆土)3個階段任務串聯而成，必須完成上一個階段任務之后才能進入下一個階段。該班共編有8名戰士，配備5類6臺工程裝備(2臺挖掘機、1臺挖坑機、1臺起重機、1臺推土機和1臺裝載機)。各階段任務出動最多工程裝備的組合可以由這些裝備的功能明確給出，進而給出整個構筑掩蔽工事一種可能的裝備組合方案，稱為最大裝備組合方案，如圖1所示。由圖1可以看出，裝載機既可以參與挖掘作業，又可以參與覆土作業。

圖1 最大裝備組合方案圖Fig.1 Maximum combination scheme of equipment

每名戰士的編號和操作各類工程裝備的熟練程度如表1所示，其中，熟練程度A、B、C、D對應的影響系數分別是1.0、0.8、0.6、0.

表1 戰士編號和操作水平

每臺工程裝備的技術狀態如表2所示，其中，技術狀態A、B、C對應的影響系數分別是1.0 、0.8、0.6.

表2 工程裝備技術狀態

結合測算和經驗，可以得到理想狀態下(熟練程度為A的操作手操作單臺技術狀態為A的工程裝備)完成各階段任務耗時，如表3所示。

表3 理想狀態下各階段任務耗時

采用虛擬裝備法，將裝載機看作兩臺虛擬裝載機(裝載機v1和裝載機v2)，一臺只能進行挖坑，另一臺只能進行覆土，按照圖1所示的最大裝備組合方案，由左到右、由上到下給出工程裝備的編號，如表4所示。

表4 基于虛擬裝備法的裝備編號及任務耗時

各階段任務的編號及在該階段內多臺裝備協作的影響系數，如表5所示，數值越大表示越礙事。

表5 各階段任務的協作影響系數

實踐中，工程保障部隊所屬的單位、人員和裝備在相應的軟件系統中都會事先賦予唯一的標識碼，而戰士操作裝備的熟練程度、裝備的技術狀態和多臺裝備協作對作業效率的影響系數一般通過部隊日常訓練考核、演習演練考核或裝備在役考核等方式獲取后錄入系統。為便于計算和分析，本文中戰士、裝備和任務的編號均是人為指定，而熟練程度影響系數、技術狀態影響系數、協作影響系數則屬假設已知條件。因此，上述各種影響系數僅用來驗證算法，不作其他用途。

最后，在搭載Intel Core i7 7th Gen處理器的Windows 7 64位平臺上，采用本文所描述的指派模型和求解算法，基于數學仿真軟件MATLAB 2017a求解上述實例，求得最優化的指派方案，如表6所示，最優指派方案對應的行動耗時為142.24 min.

表6 最優化戰士- 裝備- 任務指派方案

從表6中可以看出：最優化指派方案中，E4和E7分別參與了T1和T3兩個階段任務，也就是裝載機共參與了挖坑和覆土兩個階段任務；而E2代表的挖掘機2并沒有被指派參與挖坑作業。實際上，如果按最大裝備組合方案，挖掘機2也被指派參與挖坑作業，此時最優指派方案對應的行動耗時為142.80 min，說明挖掘機2的參與并沒有加快挖坑作業反而稍微妨礙了挖坑作業，也即最大裝備組合方案并不一定是最優的裝備組合方案。進一步分析不難發現，挖掘機2的技術狀態為C，作業效率本來就不高，再加上4臺工程裝備協同挖坑作業的影響系數為0.3，因此才會出現“幫倒忙”的現象。不難得出結論：表6所示的決策方案更加符合實際情況，從而驗證了指派模型的實用性和有效性。

另一方面，如果采用遍歷全部決策變量的做法，直接在2l×m×n個決策變量構成的可行域內搜索滿足約束條件的解(共28×6×3個決策變量，每個決策耗時約9.4×10-5s)，在同樣配置的計算平臺中估計耗時約2.1×1039s，這幾乎是不可接受的；而采用本文所描述的快速求解算法可以極大地減小可行域(共284 928個決策變量)，耗時僅為26.85 s. 因此，基于虛擬裝備法的快速算法能夠極大地降低計算消耗，是解決上述指派模型的一種切實有效地解法。

4 結論

本文分析了作戰工程保障行動的特征，設計了工程保障行動的戰士- 裝備- 任務的三維指派模型及其快速求解算法，并用實例對模型和求解算法進行了驗證。所得主要結論如下：

1)工程保障行動中的任務指派問題應考慮戰士操作水平、裝備技術狀態和任務協作影響等因素，因此，該問題是一個由“戰士- 裝備- 任務”構成的三維指派問題。

2)基于“人歇車不歇”原則的虛擬裝備法，可以增強三維指派模型的約束條件，降低決策變量的可行域，從而實現指派模型的快速求解。

3)實例證明了本文建立模型及快速求解算法的實用性和有效性。

值得注意的是，根據戰士和裝備是否安排休息的情況，約束條件可以有4種情況：“人歇車不歇”、“人歇車歇”、“人不歇車歇”、“人不歇車不歇”。因為“人歇車不歇”是作戰工程保障行動中符合作戰原則的典型場景，因此本文僅針對這一種場景制定約束條件。在實際作戰行動中，如果該工程裝備具有完成某階段任務的能力而且其自身技術狀態是正常的，除非經過計算該裝備參與協作時導致整體作業效率降低，否則是不會出現“車歇”這種場景的。反倒是在任務非常緊急的情況下，極可能出現“人不歇車不歇”的場景。關于“人不歇車不歇”這種場景下的求解，可以按作戰工程保障行動中階段任務的劃分，逐階段求解，是一種相對比較簡單的情況，感興趣的讀者可以自行研究。

與所有“指派戰士完成任務”的指派模型最大區別在于，本文所提出的指派模型能夠幫助指揮員在考慮“指派哪些戰士完成哪些任務”時，還綜合考慮了裝備技術狀態和協作影響因素帶來的影響。然而，本文尚沒有考慮一臺裝備有多個工位需要多名戰士協同作業完成某項任務的情形，這些問題將在以后的研究中繼續深入。