裝備器材保障資源調(diào)度決策模型及算法*

于雙雙，王鐵寧，李　寧，鄖　超

（1.裝甲兵工程學(xué)院，北京100072；2.解放軍78416部隊，重慶　401300；3.北京軍區(qū)通信網(wǎng)絡(luò)技術(shù)管理中心，北京　100041）

裝備器材保障資源調(diào)度決策模型及算法*

于雙雙1，王鐵寧1，李寧2，鄖超3

（1.裝甲兵工程學(xué)院，北京100072；2.解放軍78416部隊，重慶401300；3.北京軍區(qū)通信網(wǎng)絡(luò)技術(shù)管理中心，北京100041）

裝備器材保障資源調(diào)度問題是一個非常復(fù)雜的問題，根據(jù)其優(yōu)化目標(biāo)要求，從保障時間最短、保障耗費最低、安全性最高3個方面建立了該問題的多目標(biāo)優(yōu)化模型，并通過目標(biāo)優(yōu)先度決策將其轉(zhuǎn)化為單目標(biāo)模型；接著，采用兩階段法進(jìn)行求解，將其分為最優(yōu)路徑?jīng)Q策、器材分配決策兩個階段進(jìn)行決策優(yōu)化，在明確資源點到需求點之間的最優(yōu)路徑后再進(jìn)行器材資源的分配；并分別采用基于小生境的自適應(yīng)遺傳算法和基于生成樹的遺傳算法進(jìn)行求解。通過實例分析，求解結(jié)果能夠滿足裝備器材保障的要求，表明所構(gòu)建的決策模型和算法是有效的。

裝備器材保障，資源調(diào)度，最優(yōu)路徑?jīng)Q策，器材分配決策，多目標(biāo)優(yōu)化模型，遺傳算法

0　引言

裝備器材保障資源調(diào)度，是指在明確器材保障需求、掌握器材資源儲備和分布的前提下，對器材資源的供應(yīng)進(jìn)行動態(tài)控制，并通過確定供應(yīng)量、供應(yīng)方式和運輸路徑等內(nèi)容，以期實現(xiàn)軍事效益的最優(yōu)化。文獻(xiàn)［1-6］分別研究了隨機條件下的、應(yīng)急條件下的、需求可分解的、多配送中心的車輛路徑問題，文獻(xiàn)［7-11］分別研究了裝備保障資源的配置問題、戰(zhàn)時維修保障的資源優(yōu)化問題。由于裝備器材保障的軍事特殊性，使得裝備器材保障資源調(diào)度問題的模型構(gòu)建及求解比較復(fù)雜，至今對該問題進(jìn)行系統(tǒng)研究的文獻(xiàn)較少。

1　裝備器材保障資源調(diào)度問題的數(shù)學(xué)模型

1.1問題描述

裝備器材保障資源調(diào)度是一個多目標(biāo)的、復(fù)雜的綜合調(diào)度過程，根據(jù)資源調(diào)度任務(wù)，采用自然數(shù)序列編碼，以V=｛Vi|i=1，2，…，K，K≥2｝作為頂點集，建立從資源點到需求點的有向網(wǎng)絡(luò)圖G=（V，A）。其中，資源點、需求點分別為R=｛Rm|m=1，…，M，M∈ ［1，K-1］｝，S=｛Sn|n=N，…，K，N，N∈ ［2，K］｝，M＜N。裝備器材保障資源調(diào)度問題可以描述為：由M個資源點Rm向N個需求點Sn提供器材保障，第m個資源點對器材Ev存儲量是Pmv，第n個需求點對Ev的需求量是Nnv；在道路aij上的車輛行駛速度與道路等級和路阻有關(guān)；要求將Rm中的器材分配給Sn，且在滿足約束條件下，器材保障綜合效益最高。

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

裝備器材保障資源調(diào)度的優(yōu)化目標(biāo)可簡化為保障時間最短、保障成本最低、安全性最高3個目標(biāo)。1.2.1保障時間最短目標(biāo)

保障時間包括運輸時間和裝卸載時間。運輸時間包括兩部分：理想狀態(tài)下的運行時間和受交通擁堵、氣象條件影響產(chǎn)生的時間損耗。裝卸載時間包括兩部分：理想狀態(tài)下的裝卸時間和保障能力不足產(chǎn)生的時間損耗，即

式中：Pmni∈ ｛0, 1｝為從Rm到Sn是否經(jīng)過路段ai，為ai的長度；為車輛在ai上的平均速度；，分別為在ai上交通堵塞、氣象條件對車輛行駛速度的影響系數(shù)；xmnv為Rm向Sn供應(yīng)Ev的數(shù)量；為Ev的單位裝載時間；bm為Rm保障能力水平。

1.2.2保障成本最低目標(biāo)

1.2.3安全性最高目標(biāo)

安全性包括很多方面的內(nèi)容，例如敵方火力攻擊造成的不安全因素、運輸過程中事故造成的不安全因素，以及人為因素等等。為便于求解，將各種因素的影響簡化為與路段有關(guān)的一個系數(shù)。為統(tǒng)一目標(biāo)函數(shù)，將其轉(zhuǎn)化為危險程度最低，即minf3

1.3約束條件

需求點保障時間的約束：Tn1≤tmn≤Tn2，tmn表示Rm向Sn供應(yīng)器材的運輸時間；Tn1，Tn2分別為Sn要求器材供應(yīng)的最早、最晚時間。一般取Tn1=0。

路徑選擇約束：ai=（vk，vh），Pmni∈ 0,1｛｝，ai=（vk，vh）為由節(jié)點vk到vh的路徑。

非負(fù)約束：Pmv≥0，Nnv≥0，xmnv≥0。

1.4總體模型

綜上，裝備器材保障資源調(diào)度問題的總體模型為

2　模型求解算法

裝備器材保障資源調(diào)度問題包含兩個方面的決策：器材分配決策和最優(yōu)路徑?jīng)Q策，即要合理確定每個資源點對需求點器材分配情況，并指定代價最小的運輸路徑。擬采用兩階段法分別對兩個子問題進(jìn)行求解，首先尋找資源點到需求點之間的最優(yōu)路徑，再進(jìn)行器材資源的分配。最優(yōu)路徑?jīng)Q策模型為：

式中：αmn為Rm到Sn的器材裝載時間，βmn為Rm到Sn的裝載費用，Cmn為Rm到Sn的器材運輸所需的車輛數(shù)。

器材分配決策模型為：

針對兩個決策問題的特點和模型的不同，分別采用基于小生境的自適應(yīng)遺傳算法、基于生成樹的遺傳算法對最優(yōu)路徑?jīng)Q策、器材分配決策模型進(jìn)行求解。

2.1最優(yōu)路徑?jīng)Q策模型求解的基于小生境的自適應(yīng)遺傳算法設(shè)計

2.1.1初始群體的產(chǎn)生

根據(jù)保障任務(wù)內(nèi)容確定的資源點和需求點作為染色體的第一個和最后一個節(jié)點產(chǎn)生初始種群。假設(shè)資源點為節(jié)點1，需求點為節(jié)點6，即搜索從節(jié)點1到節(jié)點6的路徑。首先，搜索出發(fā)節(jié)點為節(jié)點1的出發(fā)節(jié)點，如果節(jié)點中存在節(jié)點6，則完成搜索；否則在這些節(jié)點中隨機取一個節(jié)點，作為下一個節(jié)點，再搜索以該節(jié)點為出發(fā)節(jié)點的指向節(jié)點，以此類推，直到完成初始種群的選擇。

2.1.2適應(yīng)值共享

1）個體濃度

個體之間的密切程度主要體現(xiàn)在個體基因型和表現(xiàn)型的相似性上。因此，引入個體濃度的概念來考慮種群中個體之間的密集程度。

定義1共享函數(shù)：設(shè)X→（t）為第t代進(jìn)化種群，其第i個體為Xi（t），i=1，…，N，Xi（t）與Xj（t）之間的距離為d（i，j），則共享函數(shù)為

式中：Δ（t）表示Xi（t）與Xj（t）的接近程度；a為控制共享函數(shù)形狀的參數(shù)。當(dāng)個體之間比較相似時，共享函數(shù)值就比較大；反之，比較小。

定義2個體濃度：Xi（t）的個體濃度定義為

Ci（t）取值范圍為［1/N，1］，Ci（t）較大時說明X→（t）中與Xi（t）構(gòu)造基因相近的個體較多，此時種群較集中，失去了多樣性。

2）適應(yīng)值共享

根據(jù)個體濃度的定義，可假設(shè)在一定范圍Δ（t）內(nèi)的個體集合為一個物種。如果某物種包含的個體數(shù)較大，則對該物種中個體的適應(yīng)值進(jìn)行調(diào)整，減小其幅值，降低該物種個體被選擇的概率。定義第t代種群第i個體共享后的適應(yīng)值為

式中：f（it），（t）分別為個體共享前、后的適應(yīng)值。

2.1.3自適應(yīng)變異

當(dāng)個體的濃度Ci（t）較大時，為保持和提高進(jìn)化種群的多樣性，應(yīng)以較大的變異概率對個體實施變異操作。考慮到種群進(jìn)化代數(shù)和個體濃度的共同作用，同時為保證算法收斂，要對變異概率進(jìn)行限制，基于此，對個體Xi（t）提出如下的自適應(yīng)變異概率：

當(dāng)t相對較小或Ci（t）相對較大時，t/Ci（t）值較小，說明種群失去多樣性，極有可能出現(xiàn)早熟收斂，此時變異概率自適應(yīng)地增大，增強了種群探索新的解空間的能力，增加了種群多樣性。反之，變異概率自適應(yīng)減小，保證種群的收斂性。

2.1.4基于擁擠思想的個體替換

擁擠思想源于當(dāng)物種繁衍到一定規(guī)模，以至于生存空間變得非常擁擠時，各種不同的生物為了能夠延續(xù)生存，必須相互競爭各種有限的生存資源。隨著擁擠過程的進(jìn)行，種群中的個體被分類，從而形成各個小的生存環(huán)境，并維持種群的多樣性。基于上述思想，在替換階段選擇那些適應(yīng)值較高而且個體濃度較低的個體作為下一代個體。

式中：β為加權(quán)系數(shù)，個體調(diào)整后的適應(yīng)值是原來適應(yīng)值和個體濃度的加權(quán)值。按f'（t）由大到小的順序排序，選取前N個個體進(jìn)入下一代種群。由此可見，基于擁擠思想的個體替換策略可以使種群分布較為均勻，較好地保持了種群多樣性。

2.1.5基于小生境的自適應(yīng)遺傳算法

由圖5可知：根據(jù)區(qū)域III內(nèi)的距離分布和給定的顯著性水平α，可以確定在90°方向(正橫右)距目標(biāo)船中心的距離D，即可得到該方向上的一個領(lǐng)域邊界點。按上述方法給定α值為0.05，分別計算橫駛船舶和直航船舶各個方向上的領(lǐng)域邊界點，然后對領(lǐng)域邊界點進(jìn)行擬合，為便于觀察，將目標(biāo)船周圍的他船分布以密度的形式表現(xiàn)出來，所得橫駛船舶與直航船舶領(lǐng)域結(jié)果見圖6。

根據(jù)上述分析，建立基于小生境的自適應(yīng)遺傳算法，其流程如圖1所示。

圖1　基于小生境自適應(yīng)遺傳算法流程圖

2.2器材分配決策模型求解的基于生成樹的遺傳算法設(shè)計

分配問題是在最優(yōu)路徑已經(jīng)確定的基礎(chǔ)上把資源點的器材資源合理地分配到需求點以使總代價最低，屬于運輸問題的一種。設(shè)有m個資源點，其器材儲備為Pi，n個需求點，其器材需求為Nj，Cij，xij分別為Ri到Si之間的運輸代價、器材數(shù)量，即結(jié)合運輸問題的結(jié)構(gòu)特點，采用基于生成樹的遺傳算法對器材資源分配問題進(jìn)行求解。

2.2.1遺傳算子的編碼設(shè)計

設(shè)資源點為集合R=｛1,2，…，m｝的元素，需求點為集合S=｛m+1,m+2，…，m+n｝的元素。采用基于生成樹的Prufer數(shù)編碼。它可以表示所有可能的樹，且對于擁有P個節(jié)點的完備圖，有PP-2棵標(biāo)號不同的樹。運輸圖可以表示如圖2所示的一棵生成樹。

圖2　生成樹和它的Prufer數(shù)

圖3　編碼過程

樹的Prufer數(shù)構(gòu)造過程為：①令i為樹T中數(shù)字最小的葉子節(jié)點，j為i的關(guān)聯(lián)節(jié)點，則j為Prufer 數(shù)P（T）最左邊的數(shù)組；②移除i和?。╥，j）；③如果只剩下兩個節(jié)點，則完成構(gòu)造；否則，返回①。

圖3即為將圖2中的運輸樹圖轉(zhuǎn)化為相應(yīng)的Prufer數(shù)的過程。

反過來，利用Prufer數(shù)可以產(chǎn)生唯一的一棵運輸樹。運輸問題中的每個節(jié)點都有它的庫存量和需求量的限制，因此，構(gòu)建運輸樹時應(yīng)該考慮節(jié)點的限制。將Prufer數(shù)轉(zhuǎn)化為運輸樹的過程為：①令P（T）是原始Prufer數(shù)，P（T）是所有不在P（T）中的可考慮的節(jié)點集合；②令i是P（T）中數(shù)字最小的可考慮的節(jié)點，j是P（T）最左邊的數(shù)字，如果i,j不同在R或S中，則添加?。╥，j）到樹T，否則，令j為P（T）中的下一個數(shù)字，依此類推；從P（T）中移除j，從P（T）移除i，如果j不在P（T）中余下的任何位置出現(xiàn)，則將其放入（T）；指定?。╥，j）的器材數(shù)量為xij=min｛Pi，Nj｝，更新剩余庫存和需求數(shù)量 ai=ai-xij，bj=bj-xij。重復(fù)上面步驟直至P（T）中沒有數(shù)字；③當(dāng)P（T）中沒有數(shù)字時，P（T）中還存在兩個可考慮的節(jié)點，設(shè)為i、j，添加邊（i，j）到樹T，形成m+n-1條邊的樹T，指定邊的運輸量為xij=min｛ Pi，Nj｝；④如果Pi＞0，?i，Nj＞0?j則添加邊（i，j）到樹T，并指定邊的運輸量xij=min｛ Pi，Nj｝，更新剩余庫存和需求數(shù)量ai=ai-xij，bj=bj-xij。重復(fù)上述步驟直至沒有任何需求點有需求未被滿足或資源點有庫存還未分配。

2.2.2初始群體的產(chǎn)生

初始染色體由［1，m+n］中隨機產(chǎn)生的m+n-2個數(shù)字組成。但這樣很可能產(chǎn)生無效的染色體，故必須對生成的染色體進(jìn)行合法性檢驗。設(shè)LR為由Prufer數(shù)P（T）定義的生成樹中與資源點相關(guān)的邊的總數(shù)，LS為同一生成樹中與需求點相關(guān)的邊的總數(shù)，LR，LS分別為包含在中P（T）的資源點、需求點的數(shù)量，LR+LR=LS+LS當(dāng)成立時，P（T）是可行的，否則，不可行。

2.2.3選擇

選擇過程結(jié)合（μ+λ）選擇和最優(yōu)性輪盤賭選擇。這種混合選擇策略從μ個父代和λ個子代中選擇μ個最佳染色體。如果不存在可行的μ個不同的染色體，則使用最優(yōu)性輪盤賭選擇補充剩余不足。

2.2.4交叉

使用單點交叉方法，并在運算后對子代染色體進(jìn)行合法性驗證，如圖4所示。

圖4　單點交叉運算

2.2.5變異

利用反轉(zhuǎn)變異，隨機選擇染色體中的兩個位置，將這兩個位置間的子串反轉(zhuǎn)；利用位移變異，隨機選擇位移子串，插入隨機選定的位置。如圖5所示。

3　實例分析

現(xiàn)有一裝備器材保障資源調(diào)度任務(wù)，需要從道路節(jié)點中隨機抽取的30個資源點（其中最高級1級資源點3個，2級資源點7個和3級資源點20個）中選擇器材滿足4個需求點（節(jié)點編號為16、52、159、189）的保障需求。資源點的相關(guān)數(shù)據(jù)見表1，需求點的器材需求數(shù)據(jù)見表2。道路平均行駛速度（km/h）為：高速公路100、快速公路80、國道公路60、省道公路50、縣/鄉(xiāng)道30、鐵路120；單位器材的平均裝載時間（h）為：標(biāo)準(zhǔn)集裝箱0.1、一類箱0.08、二類箱0.06、三類箱0.04、其他類型箱0.03；單位器材的平均裝載費用（元）為：標(biāo)準(zhǔn)集裝箱10、一類箱8、二類箱6、三類箱4、其他類型箱2；單車平均運輸成本（元/km）為：鐵路15、公路20；交通條件、氣象條件對行駛速度的影響系數(shù)為：無影響0、輕微0.2、一般0.4、較嚴(yán)重0.6、嚴(yán)重0.8、阻斷1；道路危險系數(shù)為：無危險0、輕微0.2、一般0.4、較嚴(yán)重0.6、嚴(yán)重0.8、很嚴(yán)重1。

圖5　變異運算

表1　資源點相關(guān)數(shù)據(jù)

表2　需求點器材數(shù)據(jù)

問題的求解分為3個步驟：①確定資源點。按照保障原則，由1級資源點進(jìn)行保障，故從3個資源點（編號為23、145、218）進(jìn)行保障；②搜索資源點到需求點的最優(yōu)路徑。設(shè)種群規(guī)模為30、最大染色體編碼長度為100，交叉概率為0.8，變異采用自適應(yīng)變異，最大迭代次數(shù)為100，可求得最優(yōu)路徑如表3所示；③器材分配。設(shè)種群規(guī)模為20、染色體編碼長度為5，交叉概率為0.85，變異為0.01，最大迭代次數(shù)為50。以器材Xs為例的器材分配情況如表4所示。

表3　最優(yōu)路徑

表4　器材分配結(jié)果

分析表3，由資源點23、145、218向需求點159供應(yīng)器材的保障時間分別為8.1、7.5、10.9，保障成本分別為1 176、664、1 038，危險系數(shù)分別為0、0.2、0.488，綜合3個目標(biāo)，由資源點145供應(yīng)器材給需求點145最優(yōu)，與表4一致。器材的供應(yīng)分配結(jié)果與實際供應(yīng)情況一致，說明所建立的模型可信，采用的算法有效。

4　結(jié)論

本文將裝備器材保障資源調(diào)度分為兩個階段進(jìn)行建模求解，提出了基于小生境的自適應(yīng)遺傳算法解決最優(yōu)路徑?jīng)Q策問題，基于生成樹的遺傳算法解決器材分配決策問題。為裝備保障資源的合理優(yōu)化調(diào)度提供了依據(jù)，具有一定的應(yīng)用價值，有利于提高裝備器材保障的效率。

［1］李相勇，田澎.帶時間窗和隨機時間車輛路徑問題：模型和算法［J］.系統(tǒng)工程理論與實踐，2009，29（8）：81-90.

［2］YUAN Y，WANG D.Path selection model and algorithm for emergency logistics management［J］.Computers and Industrial Engineering，2008，56（3）：1081-1094.

［3］李三彬，柴玉梅，王黎明.需求可拆分的開放式車輛路徑問題研究［J］.計算機工程，2011，37（6）：168-171.

［4］張軍，唐加福，潘震東，等.分散搜索算法求解帶貨物權(quán)重的車輛路徑問題［J］.系統(tǒng)工程學(xué)報，2010，25（1）：91-97.

［5］張群，顏瑞.基于改進(jìn)模糊遺傳算法的混合車輛路徑問題［J］.中國管理科學(xué)，2012，20（2）：121-128.

［6］鄒明，姜禮平，蘇思.基于遺傳算法的航空裝備保障資源調(diào)度［J］.兵工自動化，2009，28（11）：24-27.

［7］陳格非，史文山，李德臣，等.多階段裝備保障過程的資源配置模型［J］.四川兵工學(xué)報，2009，30（8）：107-109.

［8］REVELLE C S，EISELT H A.Location analysis：a synthesis and survey［J］.European Journal of Operational Research，2005，165（1）：1-19.

［9］GONG Q，BATTA R.Allocation and reallocation of ambulances to casualty clusters in a disaster relief operation［J］.IIE Transactions，2007,39（1）：27-39.

［10］王正元，曹繼平，朱昱，等.考慮維修能力的戰(zhàn)時備件資源配置方法研究［J］.兵工學(xué)報，2014，35（5）：719-724.

［11］孫寶琛，賈希勝，程中華.戰(zhàn)時裝備維修保障資源優(yōu)化模型［J］.火力與指揮控制，2013，38（6）：159-162.

Decision Model and Method for Equipment Materiel Support Resources Dispatch

YU Shuang-shuang1,WANG Tie-ning1,LI Ning2,YUN Chao3
（1.Academy of Armored Force Engineering，Beijing 100072，China；2.Unit 78416 of PLA，Chongqing 401300，China；3.Beijing Military Communication Network Technology Management Center，Beijing 100041，China；）

Equipmentmaterielsupportresourcesdispatchisaverycomplicatedproblem. According to the optimizationrequirements，the multi-objective optimization model is established with three targets such as the shortest support time，the lowest support expend，and the highest safety，and is converted to a single-objectiveoptimization model through target important degree decision.Then twostage method is adopted to carry out the solution immediately viadividing the problem into two problems，one is the route optimization decision，the other is the materiel distribution decision.The solving strategy is just to determine the superior path between the resources department and the demand troops before the materiel distribution.Design the self-adaption genetic algorithm based on small niche to figure out the route optimization decision model and the improved genetic algorithm based on generated tree to work out the materiel distribution decision respectively.At last through an example analysis，the result can satisfy the request of equipment materiel support.The result shows that the decision model and method are effective.

equipment materiel support，resourcesdispatch，route optimization decision，materiel distribution decision，multi-objective optimization model，genetic algorithm

E92，TP301

A

1002-0640（2016）07-0071-06

2015-06-07

2015-07-04
*

軍隊科研計劃基金資助項目

于雙雙（1987-），女，湖北棗陽人，博士研究生。研究方向：裝備信息管理與決策。