復(fù)雜約束條件下伴隨修理任務(wù)多目標(biāo)動(dòng)態(tài)調(diào)度

劉彥， 陳春良， 昝翔， 陳偉龍， 張立君

(陸軍裝甲兵學(xué)院 裝備保障與再制造系， 北京 100072)

0 引言

信息化條件下的現(xiàn)代戰(zhàn)爭(zhēng)突顯出作戰(zhàn)節(jié)奏快、戰(zhàn)場(chǎng)空間廣、保障任務(wù)重等特點(diǎn)，對(duì)戰(zhàn)時(shí)裝備維修的實(shí)效性提出了更高的要求。伴隨修理作為戰(zhàn)時(shí)裝備維修的主要修理方式之一，將修理力量編成伴隨修理組實(shí)施伴隨保障，可使戰(zhàn)損或故障裝備盡快參與戰(zhàn)斗，是快速保持和恢復(fù)作戰(zhàn)部隊(duì)?wèi)?zhàn)斗力的重要手段。

面對(duì)戰(zhàn)時(shí)不斷隨機(jī)出現(xiàn)的修理任務(wù)，保障指揮員如何根據(jù)作戰(zhàn)任務(wù)需求，在有限的維修時(shí)間內(nèi)綜合考慮待修裝備的維修工作量、維修優(yōu)先級(jí)等因素，以及伴隨修理組的修理能力及其變化、轉(zhuǎn)場(chǎng)時(shí)間等因素，科學(xué)合理地確定伴隨修理的修理任務(wù)及修理順序，使維修效益達(dá)到全局最優(yōu)化，是戰(zhàn)時(shí)裝備維修保障亟待解決的關(guān)鍵問題。

由于戰(zhàn)場(chǎng)態(tài)勢(shì)復(fù)雜，戰(zhàn)時(shí)裝備維修任務(wù)調(diào)度方面的研究約束條件多、研究難度大，但眾多學(xué)者對(duì)裝備維修任務(wù)調(diào)度進(jìn)行了深入探索，取得了一定成果，具有一定的指導(dǎo)意義。文獻(xiàn)[1]以盡快恢復(fù)裝備戰(zhàn)斗力為目標(biāo)，分析了動(dòng)態(tài)維修任務(wù)調(diào)度的優(yōu)化方法。文獻(xiàn)[2]考慮時(shí)間約束及負(fù)載能力約束的影響，將裝備維修任務(wù)調(diào)度問題轉(zhuǎn)化為車輛路徑問題(VRP)，并設(shè)計(jì)了基于改進(jìn)最大- 最小螞蟻系統(tǒng)(MMAS)的維修任務(wù)規(guī)劃方法，實(shí)現(xiàn)單修理組的維修任務(wù)調(diào)度。文獻(xiàn)[3]提出了進(jìn)攻作戰(zhàn)搶修任務(wù)動(dòng)態(tài)調(diào)度問題，將其抽象為動(dòng)態(tài)車輛路徑問題，以獲得的二次作戰(zhàn)時(shí)間最大為調(diào)度目標(biāo)構(gòu)造了調(diào)度模型，并設(shè)計(jì)了變體遺傳算法(GA)進(jìn)行模型求解。文獻(xiàn)[4]考慮修復(fù)時(shí)間不確定性以及搶修組轉(zhuǎn)場(chǎng)時(shí)間不確定性，構(gòu)建了機(jī)動(dòng)作戰(zhàn)搶修任務(wù)調(diào)度模型，并通過示例驗(yàn)證了模型和算法的可行性。

目前，裝備維修任務(wù)調(diào)度目標(biāo)主要集中在最大保障時(shí)間[5]、修竣裝備重要度之和最大[6]、獲得的二次作戰(zhàn)時(shí)間最大[3]等，不同調(diào)度目標(biāo)的側(cè)重點(diǎn)不同，但多目標(biāo)優(yōu)化是維修任務(wù)調(diào)度的趨勢(shì)。根據(jù)修理方式特點(diǎn)抽象出的裝備維修任務(wù)調(diào)度問題主要有資源約束項(xiàng)目調(diào)度問題[7]和VRP[8-9]，其中：資源約束項(xiàng)目調(diào)度模型適用于基地級(jí)修理或定點(diǎn)修理；VRP適用于伴隨修理和巡回修理，運(yùn)用也更加廣泛。約束條件方面，現(xiàn)有裝備維修任務(wù)調(diào)度研究在VRP基礎(chǔ)上根據(jù)戰(zhàn)場(chǎng)情況進(jìn)行了延伸，主要聚焦于隨機(jī)需求[10]、時(shí)間不確定性[11]等傳統(tǒng)約束，文獻(xiàn)[7]考慮到維修資源周期性工作問題，提出了考慮休息的維修任務(wù)調(diào)度模型；文獻(xiàn)[12]考慮到戰(zhàn)場(chǎng)搶修時(shí)的修理能力限制，提出了非遍歷型調(diào)度，符合戰(zhàn)時(shí)修理實(shí)際，具有一定的指導(dǎo)意義。然而時(shí)間窗[13-14]等其他約束在裝備維修任務(wù)調(diào)度中的研究較少且不夠深入，有待進(jìn)一步完善對(duì)戰(zhàn)場(chǎng)其他現(xiàn)實(shí)約束的考慮，以使得維修任務(wù)調(diào)度更加合理可靠。

綜上所述，現(xiàn)階段伴隨修理裝備維修任務(wù)調(diào)度的研究存在以下3個(gè)問題：

1)現(xiàn)有研究針對(duì)的背景和問題不完全相同，未深入分析伴隨修理背景下如何基于諸多實(shí)際約束來合理地規(guī)劃伴隨修理組維修任務(wù)以及動(dòng)態(tài)處理不確定性信息，缺乏對(duì)伴隨修理裝備維修任務(wù)調(diào)度這一現(xiàn)實(shí)軍事問題的模型化描述和深入研究。

2)現(xiàn)有研究多以最大保障時(shí)間、最長(zhǎng)二次作戰(zhàn)時(shí)間等作為單一的調(diào)度目標(biāo)進(jìn)行任務(wù)調(diào)度，可能難以全面反映戰(zhàn)時(shí)伴隨修理的維修任務(wù)調(diào)度需求，需要加強(qiáng)復(fù)雜戰(zhàn)場(chǎng)環(huán)境下決策者對(duì)其他調(diào)度目標(biāo)的考慮，從多個(gè)目標(biāo)出發(fā)，以更有利于尋求全局最優(yōu)化。

3)沒有充分考慮復(fù)雜約束對(duì)裝備維修任務(wù)調(diào)度的影響。裝備維修任務(wù)調(diào)度問題作為復(fù)雜優(yōu)化問題，具有諸多現(xiàn)實(shí)約束，而現(xiàn)有的研究較少考慮約束問題，模型過于理想化，降低了調(diào)度模型的適用性和合理性。由于待修裝備修理時(shí)間窗、非遍歷性、修復(fù)狀態(tài)的不確定性以及修理能力的變化等約束客觀存在，會(huì)對(duì)維修任務(wù)調(diào)度產(chǎn)生重要影響，因此需要在調(diào)度過程中深入分析，以使得維修任務(wù)調(diào)度模型更加符合戰(zhàn)場(chǎng)實(shí)際。

本文針對(duì)以上問題，以伴隨修理維修任務(wù)調(diào)度這一復(fù)雜軍事難題為研究對(duì)象，引入修理時(shí)間窗約束和非遍歷性約束，考慮修復(fù)狀態(tài)不確定性和修理能力的變化對(duì)調(diào)度的影響，以修復(fù)裝備數(shù)量、修復(fù)裝備重要度以及獲得的二次作戰(zhàn)時(shí)間為多維調(diào)度目標(biāo)，構(gòu)建伴隨修理的維修任務(wù)多目標(biāo)動(dòng)態(tài)調(diào)度模型，根據(jù)模型特點(diǎn)設(shè)計(jì)改進(jìn)的GA進(jìn)行求解，并通過示例驗(yàn)證模型的科學(xué)性和合理性。

1 基本描述

1.1 問題描述

在現(xiàn)代戰(zhàn)爭(zhēng)中，隨著作戰(zhàn)進(jìn)程的推進(jìn)以及作戰(zhàn)任務(wù)的逐行，在敵方火力打擊下，我方作戰(zhàn)裝備不可避免地會(huì)在不同時(shí)間、不同地點(diǎn)出現(xiàn)不同程度的損傷。為及時(shí)搶修分布在戰(zhàn)場(chǎng)上的眾多受損裝備，我方伴隨修理力量編成伴隨修理組展開伴隨保障。在實(shí)施伴隨保障過程中，為充分利用現(xiàn)有維修資源應(yīng)對(duì)不斷出現(xiàn)的維修任務(wù)，需要對(duì)維修任務(wù)進(jìn)行動(dòng)態(tài)調(diào)度。在調(diào)度過程中，各待修裝備的位置、預(yù)計(jì)修理時(shí)間和修復(fù)到不同狀態(tài)的裝備重要度等信息，在一體化指揮信息平臺(tái)的支撐下已通過相應(yīng)的手段獲知，且各待修裝備均希望在其對(duì)應(yīng)的時(shí)間窗內(nèi)得到修復(fù)，否則將會(huì)影響其修復(fù)后繼續(xù)參戰(zhàn)的重要度。在伴隨修理過程中，保障指揮員會(huì)根據(jù)不斷更新的待修裝備及伴隨修理組信息，對(duì)伴隨修理組的修理計(jì)劃進(jìn)行動(dòng)態(tài)調(diào)度。

在待修裝備不斷出現(xiàn)而修理時(shí)間和修理能力有限的前提下，為使得伴隨修理效果實(shí)現(xiàn)全局的最優(yōu)化，亟需為伴隨修理組分配合適的待修裝備，并確定各待修裝備之間的修理順序及修復(fù)狀態(tài)，還需要根據(jù)不斷出現(xiàn)的待修裝備對(duì)維修任務(wù)進(jìn)行動(dòng)態(tài)調(diào)整，以使得作戰(zhàn)部隊(duì)?wèi)?zhàn)斗力得到最及時(shí)有效的恢復(fù)，即為本文研究的伴隨修理裝備維修任務(wù)調(diào)度問題。

1.2 假設(shè)描述

為了簡(jiǎn)化問題，突出重點(diǎn)，做出如下假設(shè)：

1)參與維修任務(wù)調(diào)度的各待修裝備均在伴隨修理組的修理能力范圍內(nèi)；

2)研究對(duì)象為營(yíng)伴隨修理力量，編成一個(gè)伴隨修理組，對(duì)所屬保障對(duì)象開展伴隨修理；

3)維修任務(wù)調(diào)度前，各待修裝備的位置、預(yù)計(jì)修理時(shí)間、裝備重要度、修理時(shí)間窗等信息均已通過技術(shù)偵察獲知；

4)伴隨修理組從初始位置出發(fā)，前往待修裝備地域?qū)ζ溥M(jìn)行伴隨修理，完成修理任務(wù)后不返回初始出發(fā)點(diǎn)，而是等待保障指揮員下達(dá)新的維修任務(wù)指示；

5)待修裝備修復(fù)后直接歸建作戰(zhàn)部隊(duì)參與作戰(zhàn)，忽略歸建時(shí)間。

6)伴隨修理組修理過程中不會(huì)由于任務(wù)調(diào)整而中止當(dāng)前任務(wù)。

2 模型構(gòu)建

2.1 條件假設(shè)

為了方便對(duì)模型進(jìn)行描述，引入以下符號(hào)體系及條件假設(shè)：

1)戰(zhàn)斗開始時(shí)刻為0 min，伴隨修理開始時(shí)刻為Ts，戰(zhàn)斗結(jié)束時(shí)刻為Te.

3)待修裝備修復(fù)至能正常作戰(zhàn)為S1，修復(fù)至能應(yīng)急作戰(zhàn)為S2，待修裝備i修復(fù)至第p(p=1,2)種狀態(tài)的裝備重要度為δi,p，相應(yīng)的預(yù)期維修時(shí)間分別為Ti,S1、Ti,S2.

6)引入0～1變量τi，當(dāng)待修裝備i得到修復(fù)時(shí)τi=1，否則τi=0.

7)隨著修理任務(wù)的開展，勢(shì)必導(dǎo)致修理人員疲勞，從而影響修理效率，記修理效率為ξk，表示執(zhí)行第k(k={1,2,…})次修理任務(wù)時(shí)的修理效率，修理效率隨修理任務(wù)的實(shí)施不斷下降。

8)記O={o1,o2,…,ol}(l為截點(diǎn)，l≤n)為該問題的一個(gè)可行解，表示一個(gè)可行的規(guī)劃路徑，即修理組開展伴隨修理的裝備編號(hào)序列，ol為截點(diǎn)裝備；|O|表示該可行解中包含的元素個(gè)數(shù)，即該規(guī)劃路徑中的裝備數(shù)；om表示該規(guī)劃路徑中的第m(m={1,2,…，l})臺(tái)裝備。

9)將可行解O={o1,o2,…,ol}補(bǔ)充為完整修理任務(wù)規(guī)劃O′={o1,o2,…,ol,ol+1,…,on}，有Tol≤Te

2.2 多目標(biāo)參數(shù)分析

戰(zhàn)時(shí)伴隨修理的目的在于在各種限制條件下盡最大可能修復(fù)待修裝備，使其盡快返回戰(zhàn)場(chǎng)繼續(xù)參與戰(zhàn)斗，以發(fā)揮修竣裝備對(duì)裝備體系的貢獻(xiàn)，使作戰(zhàn)部隊(duì)?wèi)?zhàn)斗力得到最大限度的恢復(fù)。為全面衡量維修任務(wù)計(jì)劃安排的優(yōu)劣，用以下3個(gè)參數(shù)對(duì)維修任務(wù)調(diào)度優(yōu)劣進(jìn)行量化度量：

1)修竣裝備總數(shù)F1. 修竣裝備總數(shù)是整個(gè)戰(zhàn)斗過程中伴隨修理組修復(fù)的待修裝備數(shù)量總和，反映了戰(zhàn)時(shí)伴隨修理力量在給定時(shí)間域內(nèi)逐行修理任務(wù)的快慢程度，直接影響了裝備參戰(zhàn)率。對(duì)于遍歷型修理，待修裝備得到全部修復(fù)，此時(shí)F1即為待修裝備總數(shù)；對(duì)于非遍歷型修理，待修裝備并非全部得到修理，F(xiàn)1是保障指揮員最看重的因素之一。

2)修竣裝備總重要度F2. 修竣裝備重要度反映地是所修竣裝備對(duì)整個(gè)裝備體系的貢獻(xiàn)程度，是修竣裝備重要度的總和。重要度越高的裝備對(duì)裝備體系及整個(gè)戰(zhàn)斗的影響越大，也是待修裝備的優(yōu)先級(jí)反映。

3)獲得的二次作戰(zhàn)總時(shí)間F3. 二次作戰(zhàn)時(shí)間總時(shí)間是指伴隨修理組修竣的待修裝備二次作戰(zhàn)時(shí)間的代數(shù)和。二次作戰(zhàn)時(shí)間是指戰(zhàn)斗持續(xù)進(jìn)程中，修竣裝備從修竣時(shí)刻至戰(zhàn)斗結(jié)束時(shí)刻的時(shí)間長(zhǎng)度，反映了待修裝備得到及時(shí)修復(fù)的程度以及修竣后裝備發(fā)揮有效作用的時(shí)長(zhǎng)，是修理及時(shí)程度的體現(xiàn)。修理越及時(shí)，待修裝備修竣后返回戰(zhàn)場(chǎng)所參加的二次作戰(zhàn)時(shí)間越長(zhǎng)，對(duì)本次戰(zhàn)斗的貢獻(xiàn)就越大，相應(yīng)的伴隨修理也就越有意義。

以上三者相互制約、相互影響，難以同時(shí)達(dá)到最優(yōu)，因此需要構(gòu)建維修任務(wù)調(diào)度的多目標(biāo)優(yōu)化模型，以實(shí)現(xiàn)全局的最優(yōu)化。

2.3 約束條件分析

2.3.1 修理時(shí)間窗分析

對(duì)于戰(zhàn)時(shí)伴隨修理，各待修裝備均希望盡快得到修復(fù)、返回戰(zhàn)場(chǎng)繼續(xù)完成任務(wù)，然而受修理能力的限制，并不能實(shí)現(xiàn)各待修裝備在第一時(shí)間均得到修復(fù)。隨著時(shí)間的推移，由于作戰(zhàn)階段、作戰(zhàn)任務(wù)的改變，當(dāng)超過某一時(shí)刻待修裝備仍未得到修復(fù)時(shí)，待修裝備的重要程度就會(huì)受到影響。因此本文引入待修裝備修理時(shí)間窗概念對(duì)這一現(xiàn)實(shí)問題進(jìn)行刻畫，對(duì)超出修理時(shí)間窗而未得到修復(fù)的待修裝備重要度進(jìn)行懲罰，具體懲罰公式如下：

(1)

式中：ηi,p為經(jīng)時(shí)間窗懲罰后待修裝備i修復(fù)至第p種狀態(tài)的裝備重要度。

2.3.2 非遍歷分析

非遍歷是指沿某一搜索路徑對(duì)集合中的部分元素做一次且僅做一次訪問，被訪問元素具有不確定性。與傳統(tǒng)維修任務(wù)分配不同，戰(zhàn)時(shí)伴隨修理由于時(shí)間緊、任務(wù)重，難以對(duì)散布在戰(zhàn)場(chǎng)的各待修裝備實(shí)現(xiàn)全部修復(fù)，即伴隨修理組只能完成部分維修任務(wù)，屬于非遍歷任務(wù)調(diào)度。非遍歷性描述的是各待修裝備是否均得到修復(fù)，其對(duì)調(diào)度模型的影響通過待修裝備修竣時(shí)刻的時(shí)間約束實(shí)現(xiàn)。對(duì)于遍歷型維修任務(wù)的動(dòng)態(tài)調(diào)度，其相關(guān)約束為Tok≤Te,?k,k≤|ol|，而非遍歷維修任務(wù)調(diào)度對(duì)約束條件松弛為Tok≤Te

2.3.3 修理能力分析

戰(zhàn)時(shí)伴隨修理的修理環(huán)境惡劣，受戰(zhàn)場(chǎng)環(huán)境等諸多因素影響，修理能力并非固定值，而是會(huì)不斷發(fā)生變化，具有不確定性。隨著修理任務(wù)的實(shí)施，勢(shì)必會(huì)造成修理人員的疲勞，從而影響修理效率，使修理能力發(fā)生變化。為解決修理人員疲勞帶來的修理能力變化問題，本文引入修理效率概念，確定每次修理任務(wù)的完成對(duì)修理效率的影響，從而確定修理能力的變化，修理效率計(jì)算公式為

ξk=βξk-1,

(2)

式中：ξk為執(zhí)行第k(k≥2)次修理任務(wù)時(shí)的修理效率，ξ1=1；β為修理效率衰減系數(shù)。

由上述分析可以看出，修理能力對(duì)待修裝備的影響還可以通過修理順序的不同來實(shí)現(xiàn)，即待修裝備的修理時(shí)間會(huì)由于修理順序的不同而受到修理效率的影響，從而使得裝備維修任務(wù)調(diào)度更為復(fù)雜。

2.3.4 修復(fù)狀態(tài)分析

伴隨修理的目的是在規(guī)定時(shí)間域內(nèi)修復(fù)戰(zhàn)損或故障裝備或恢復(fù)其部分功能，使其盡快返回戰(zhàn)場(chǎng)參戰(zhàn)?？紤]到戰(zhàn)時(shí)修理任務(wù)的時(shí)效性，待修裝備的修復(fù)狀態(tài)具有不確定性，從而使維修任務(wù)調(diào)度更復(fù)雜，求解難度更大。

從裝備完成任務(wù)的角度分析，有效的伴隨修理應(yīng)使修竣裝備能夠正常作戰(zhàn)或應(yīng)急作戰(zhàn)，因此待修裝備的修復(fù)狀態(tài)可以分為能正常作戰(zhàn)S1和能應(yīng)急作戰(zhàn)S2兩類，將待修裝備恢復(fù)至不同狀態(tài)一方面所需的修理時(shí)間明顯不同，另一方面獲得的裝備重要度也有所差異，因此會(huì)對(duì)維修任務(wù)調(diào)度產(chǎn)生較大影響。通過引入待修裝備修復(fù)狀態(tài)這一現(xiàn)實(shí)約束，可以使維修任務(wù)調(diào)度更加貼合實(shí)際，也更具有實(shí)用性。

2.4 調(diào)度模型建立

在分析伴隨修理裝備維修任務(wù)調(diào)度目標(biāo)的基礎(chǔ)上，結(jié)合伴隨修理特點(diǎn)及相關(guān)現(xiàn)實(shí)約束，構(gòu)建裝備維修任務(wù)調(diào)度模型。

目標(biāo)函數(shù)：

maxF=max (F1,F2,F3)，

(3)

(4)

(5)

(6)

約束條件：

(7)

(8)

(9)

(10)

(11)

(3)式表示面向伴隨修理的裝備維修任務(wù)調(diào)度目標(biāo)是修竣裝備總數(shù)最大、修竣裝備總重要度最大、獲得的二次作戰(zhàn)總時(shí)間最多；(4)式、(5)式、(6)式分別表示3個(gè)目標(biāo)參數(shù)；(7)式表示伴隨修理組從初始位置出發(fā)前往修竣第1臺(tái)待修裝備的時(shí)間關(guān)系；(8)式表示伴隨修理組修理可行解中相鄰兩待修裝備的修竣時(shí)刻的約束關(guān)系；(9)式表示修理時(shí)間以及修理能力的約束關(guān)系；(10)式表示伴隨修理組在戰(zhàn)斗結(jié)束之間進(jìn)行的修理才有效，反映了非遍歷約束關(guān)系；(11)式表示對(duì)裝備是否修復(fù)做0～1約束。

2.5 調(diào)度模型分析

1)多目標(biāo)分析。不同于傳統(tǒng)維修任務(wù)調(diào)度單純追求某一目標(biāo)而導(dǎo)致調(diào)度方案在其他需求方面存在較大偏離，本文所構(gòu)建的裝備維修任務(wù)調(diào)度模型通過修理數(shù)量、修理對(duì)象重要程度和修理及時(shí)性3個(gè)方面權(quán)衡維修任務(wù)調(diào)度方案的優(yōu)劣，在多個(gè)目標(biāo)中協(xié)調(diào)平衡，獲得一組可接受解(即Pareto最優(yōu)解集[15])，增加了保障指揮員的決策余地，可以根據(jù)戰(zhàn)場(chǎng)實(shí)際需求和決策者偏好從Pareto最優(yōu)解集中選擇合理的調(diào)度方案。

2)動(dòng)態(tài)驅(qū)動(dòng)策略分析。裝備維修任務(wù)動(dòng)態(tài)調(diào)度的實(shí)質(zhì)是根據(jù)調(diào)度需求進(jìn)行多次維修任務(wù)調(diào)度的過程。而動(dòng)態(tài)驅(qū)動(dòng)策略就是設(shè)定某一驅(qū)動(dòng)條件，用以判斷該時(shí)刻是否需要對(duì)維修任務(wù)進(jìn)行再次調(diào)度。因此，動(dòng)態(tài)驅(qū)動(dòng)策略是動(dòng)態(tài)調(diào)度的基礎(chǔ)。

結(jié)合伴隨修理特點(diǎn)，本文設(shè)定面向伴隨修理的裝備維修任務(wù)動(dòng)態(tài)調(diào)度動(dòng)態(tài)驅(qū)動(dòng)策略為：伴隨修理組每修復(fù)一臺(tái)裝備且有新的待修裝備出現(xiàn)時(shí)，便根據(jù)該時(shí)刻時(shí)間點(diǎn)、伴隨修理組位置信息、待修裝備信息(包括新出現(xiàn)的待修裝備信息)進(jìn)行一次重調(diào)度，并將該修竣裝備記為關(guān)鍵點(diǎn)，將該時(shí)刻記為重調(diào)度時(shí)刻。該動(dòng)態(tài)驅(qū)動(dòng)策略可以消除待修裝備的實(shí)際修理時(shí)間與計(jì)劃修理時(shí)間差異所導(dǎo)致的調(diào)度誤差，通過每次重調(diào)度前的信息更新實(shí)現(xiàn)動(dòng)態(tài)調(diào)度的可靠性。

3 模型求解

由第2節(jié)分析可知，伴隨修理裝備維修任務(wù)調(diào)度問題是多約束條件下的多目標(biāo)動(dòng)態(tài)調(diào)度問題，下面針對(duì)其特點(diǎn)，設(shè)計(jì)改進(jìn)GA進(jìn)行模型求解。

3.1 Pareto最優(yōu)解集構(gòu)建

傳統(tǒng)多目標(biāo)優(yōu)化方法如權(quán)重系數(shù)法、目標(biāo)規(guī)劃法和約束法等，通過將多目標(biāo)問題轉(zhuǎn)化為1個(gè)或一系列單目標(biāo)優(yōu)化問題進(jìn)行求解，存在依賴先驗(yàn)知識(shí)、難以處理Pareto最優(yōu)前端非凸等問題。而帶精英策略的非支配排序遺傳算法(NSGA-Ⅱ)作為最優(yōu)秀的多目標(biāo)進(jìn)化算法之一，在保證種群多樣性和保護(hù)種群優(yōu)良個(gè)體的同時(shí)降低了計(jì)算復(fù)雜度[16]。因此，本文通過NSGA-Ⅱ算法的精英策略，采用非支配排序方法并結(jié)合擁擠度比較算子，獲得多個(gè)Pareto最優(yōu)解，從而為保障指揮員提供決策依據(jù)。保障指揮員可根據(jù)戰(zhàn)場(chǎng)態(tài)勢(shì)和實(shí)際需求，依托決策偏好和決策策略，在Pareto最優(yōu)解集中選擇最滿意解。

設(shè)定決策策略為：通過對(duì)Pareto最優(yōu)解集中的解進(jìn)行規(guī)范化處理，采用加權(quán)法進(jìn)行排序優(yōu)選，從而選擇滿意解：

(12)

3.2 編碼與解碼設(shè)計(jì)

為實(shí)現(xiàn)伴隨修理裝備維修任務(wù)調(diào)度的非遍歷約束，設(shè)計(jì)兩段式編碼：前段采用順序編碼，用以表示伴隨修理組的修理順序；后段采用1～2整數(shù)編碼，用以表示待修裝備的修復(fù)狀態(tài)，1表示修復(fù)狀態(tài)為S1，2表示修復(fù)狀態(tài)為S2. 該編碼方式能實(shí)現(xiàn)非遍歷約束及修復(fù)狀態(tài)約束，且染色體與解一一對(duì)應(yīng)，避免了遺傳操作中不可行解的產(chǎn)生，大大提高了算法收斂速度。選取目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，通過相關(guān)約束求得截點(diǎn)的信息和相應(yīng)適應(yīng)值，從而實(shí)現(xiàn)解碼。

編碼和解碼示例分別如圖1、圖2所示，染色體為X=(4,8,2,6,3,1,7,5,1,1,2,1,2,2,1,2,5)，n=8，根據(jù)所求得的截點(diǎn)信息實(shí)現(xiàn)解碼，其含義為：受相關(guān)約束影響，對(duì)8臺(tái)待修裝備中的5臺(tái)進(jìn)行了修理，伴隨修理組的任務(wù)安排及修理順序?yàn)?4,8,2,6,3)，修復(fù)狀態(tài)為(S1,S1,S2,S1,S2,S2,S1,S2)，適應(yīng)值分別為F1(t)、F2(t)、F3(t).

圖1 編碼示例Fig.1 Encoding example

圖2 解碼示例Fig.2 Decoding example

3.3 遺傳算子設(shè)計(jì)

3.3.1 選擇

染色體選擇采用Binary Tournament Selection，并根據(jù)比較算子(由NSGA-II計(jì)算非支配排序和個(gè)體間擁擠距離得到)從上一代染色體中選取20%的個(gè)體作為父染色體，進(jìn)行后續(xù)交叉變異操作。

3.3.2 交叉變異

由于染色體采取兩段式編碼，各段編碼方式以及對(duì)應(yīng)的實(shí)際意義不同，其交叉變異無法直接采用傳統(tǒng)交叉變異方式進(jìn)行。為了增大搜索范圍、提高收斂速度，針對(duì)編碼特點(diǎn)，確定“前段僅進(jìn)行變異操作，后段可進(jìn)行交叉及變異操作”的思路，設(shè)計(jì)混合策略遺傳算子如下：1)前段和后段均采用隨機(jī)更新操作；2)前段采取隨機(jī)更新，后段采取倒置操作；3)前段采用倒置操作，后段采用隨機(jī)更新操作；4)前段采用倒置操作，后段采用滑動(dòng)平移操作；5)前段不采取操作，后段采用隨機(jī)更新操作。

3.4 算法流程設(shè)計(jì)

模型求解算法的流程如下：

步驟1初始化相關(guān)參數(shù)(種群規(guī)模pop_size、最大迭代次數(shù)num_gen等)。

步驟2隨機(jī)產(chǎn)生初始種群P0.

步驟3對(duì)種群P0中任一染色體進(jìn)行解碼，計(jì)算其適應(yīng)值和截點(diǎn)信息Cl，得到初始化可行解種群O，記為pop_chrom.

步驟4由NSGA-II對(duì)可行解種群O進(jìn)行快速非支配排序，計(jì)算非支配集個(gè)體間擁擠距離。

步驟5令gen=1.

步驟6根據(jù)Binary Tournament Selection,從pop_chrom中隨機(jī)選出數(shù)量規(guī)模為pool_size的父代染色體種群parent_chrom.

步驟7采用混合策略遺傳算子進(jìn)行遺傳操作，產(chǎn)生子代染色體種群offspring_chrom.

步驟8計(jì)算offspring_chrom中任一染色體的截點(diǎn)信息及其適應(yīng)值。

步驟9采用NSGA-II算法對(duì)pop_chrom及offspring_chrom進(jìn)行快速非支配排序，計(jì)算非支配集個(gè)體間擁擠距離。

步驟10根據(jù)Binary Tournament Selection,從pop_chrom及offspring_chrom中篩選出規(guī)模為pop_size的基因較優(yōu)新一代染色體pop_chrom，從而實(shí)現(xiàn)父代優(yōu)秀個(gè)體基因的精英保留。

步驟11判斷gen

步驟12令gen=gen+1，轉(zhuǎn)步驟6，繼續(xù)尋優(yōu)。

步驟13停止迭代，獲得本次維修任務(wù)調(diào)度的Pareto最優(yōu)解集，依據(jù)決策策略從中計(jì)算出F′，轉(zhuǎn)步驟14.

步驟14判斷重調(diào)度驅(qū)動(dòng)策略是否滿足？若滿足則轉(zhuǎn)步驟1進(jìn)行重調(diào)度，否則轉(zhuǎn)步驟15.

步驟15運(yùn)算終止，輸出調(diào)度結(jié)果。

4 示例仿真與分析

4.1 示例仿真

某合成營(yíng)受上級(jí)指示執(zhí)行機(jī)動(dòng)進(jìn)攻作戰(zhàn)任務(wù)，受故障和敵方火力打擊，陸續(xù)出現(xiàn)待修裝備，該營(yíng)配屬一個(gè)伴隨修理組對(duì)所屬部隊(duì)逐行伴隨修理任務(wù)，負(fù)責(zé)修理120 min內(nèi)能完成的待修裝備，在一體化指揮信息平臺(tái)的支撐下，各待修裝備相關(guān)信息已知。而隨著進(jìn)攻作戰(zhàn)的持續(xù)，待修裝備不斷出現(xiàn)，保障指揮員需要為伴隨修理組分配合適的待修裝備，確定各待修裝備之間的修理順序及修復(fù)狀態(tài)，并根據(jù)不斷出現(xiàn)的待修裝備對(duì)維修任務(wù)進(jìn)行動(dòng)態(tài)調(diào)整。

戰(zhàn)斗初期(t≤200 min)，需要更多更重要的裝備及時(shí)參戰(zhàn)，取μ1=0.1，μ2=0.6，μ3=0.3；戰(zhàn)斗后期(t>200 min)，需要提供更多的作戰(zhàn)時(shí)間，取μ1=0.2，μ2=0.3，μ3=0.5.

根據(jù)伴隨修理組實(shí)際機(jī)動(dòng)時(shí)間、實(shí)際修理時(shí)間以及調(diào)度策略對(duì)裝備維修任務(wù)進(jìn)行調(diào)度，得到調(diào)度規(guī)劃結(jié)果如表2所示。

此次伴隨修理裝備維修任務(wù)調(diào)度共經(jīng)歷了5次調(diào)度過程，在MATLAB軟件平臺(tái)用時(shí)分別為12.05 s、11.97 s、12.08 s、13.21 s、14.01 s. 最終維修方案的規(guī)劃路徑如圖3所示。

4.2 結(jié)果分析

根據(jù)分析以上示例仿真結(jié)果，可以得到以下結(jié)論：

表1 待修裝備信息

1)從伴隨修理組開始實(shí)施伴隨修理至戰(zhàn)斗結(jié)束，修理任務(wù)的路徑規(guī)劃為2-1-4-3-5-10-11-9，共修復(fù)裝備8臺(tái)，獲得的裝備重要度總和為3.94，獲得的二次作戰(zhàn)時(shí)間為1 392 min，在很大程度上恢復(fù)了部隊(duì)?wèi)?zhàn)斗力，間接證明了戰(zhàn)時(shí)伴隨修理的重要性。

2)調(diào)度時(shí)間均在15 s以內(nèi)，滿足戰(zhàn)時(shí)裝備維修任務(wù)調(diào)度的實(shí)效性要求，同時(shí)也證明了所構(gòu)模型和算法的可行性。

3)受動(dòng)態(tài)驅(qū)動(dòng)策略的影響，一共進(jìn)行了5次調(diào)度，實(shí)現(xiàn)了待修裝備不斷出現(xiàn)情況下的維修任務(wù)動(dòng)態(tài)調(diào)整。其中，前3次調(diào)度屬于遍歷型調(diào)度，后2次調(diào)度屬于非遍歷型調(diào)度；待修裝備6、7、8、12未納入最終的伴隨修理裝備維修任務(wù)規(guī)劃中，這主要是因?yàn)閼?zhàn)時(shí)修理時(shí)間的限制導(dǎo)致修理任務(wù)無法全部完成，反映了伴隨修理的非遍歷性。

表2 調(diào)度規(guī)劃結(jié)果

圖3 伴隨修理裝備維修路徑規(guī)劃圖Fig.3 Equipment repair route plan with accompanying repair

4)規(guī)劃路徑中出現(xiàn)了折線1-4-3，這是因?yàn)樵跁r(shí)刻67 min進(jìn)行第2次調(diào)度時(shí)，參與調(diào)度的裝備是1、3、4，而待修裝備3相對(duì)于待修裝備4的重要度低且修理時(shí)間長(zhǎng)，因此伴隨修理組修完待修裝備1后，舍棄較近的待修裝備3，而先修理重要度高且更易修復(fù)的待修裝備4，能夠滿足戰(zhàn)時(shí)修理時(shí)“先修重要裝備”以及“先修易修裝備”的要求，也從側(cè)面反映了調(diào)度模型的合理性。

5)前2次調(diào)度，待修裝備的修復(fù)狀態(tài)均為S1，這是因?yàn)榍捌诖扪b備較少，預(yù)計(jì)的修理時(shí)間相對(duì)充裕，而μ2取值較大，將裝備修復(fù)至S1狀態(tài)能獲得更多的重要度，且前期修竣裝備參戰(zhàn)時(shí)間相對(duì)較長(zhǎng)，更高的重要度有利于發(fā)揮作戰(zhàn)效能。后3次調(diào)度，待修裝備的修復(fù)狀態(tài)多為S2，因?yàn)榇藭r(shí)參與調(diào)度的待修裝備數(shù)量多，且在戰(zhàn)斗后期，μ3取值較大，希望能獲得更多裝備二次作戰(zhàn)時(shí)間，因此將待修裝備修復(fù)至S2狀態(tài)既能節(jié)約修理時(shí)間以完成更多修理任務(wù)，又能迅速使其返回戰(zhàn)場(chǎng)以獲得更多的二次作戰(zhàn)時(shí)間。

5 結(jié)論

本文提出了伴隨修理裝備維修任務(wù)動(dòng)態(tài)調(diào)度軍事問題，構(gòu)建了復(fù)雜約束條件下的伴隨修理多目標(biāo)動(dòng)態(tài)調(diào)度模型，設(shè)計(jì)了相關(guān)求解算法，并通過示例驗(yàn)證了該模型及算法的合理性。本文所構(gòu)建的模型更加符合復(fù)雜約束這一戰(zhàn)場(chǎng)實(shí)際，為伴隨修理裝備維修任務(wù)調(diào)度難題提供了模型及方法參考，為戰(zhàn)時(shí)保障指揮員維修決策提供了數(shù)學(xué)支撐。

下一步將對(duì)巡回修理中多巡回修理組的裝備維修任務(wù)動(dòng)態(tài)調(diào)度問題展開研究。