楊曉段，李元左，郭瑞平

(裝備學院基礎(chǔ)系，北京 101416)

裝備保障資源運輸是非戰(zhàn)爭軍事行動裝備保障［1-2］的重要環(huán)節(jié)。調(diào)配方案確定后，如何確?？焖?、高效地運送保障資源是非戰(zhàn)爭軍事行動裝備保障的關(guān)鍵。本文展開對非戰(zhàn)爭軍事行動裝備保障資源運輸方式的選擇與路徑優(yōu)化的模型進行研究。

1 非戰(zhàn)爭軍事行動裝備保障資源運輸方式選擇模型

1.1 問題分析

在道路選擇問題上一般可采用單目標規(guī)劃和多目標規(guī)劃兩種方法，單目標法［3］適用于決策目標只有一個的情況，多目標規(guī)劃法則適用多個決策目標的情況［4-5］。前面已經(jīng)分析過影響運輸?shù)缆愤x擇的因素，可知在實際的非戰(zhàn)爭軍事行動裝備保障資源調(diào)配中，面對道路選擇時要求達到的目標不止一個，如運量要大、運輸時效要高、運輸安全性要好等目標，所以，對比2種方法，多目標規(guī)劃方法更為合適建立道路選擇模型。

在研究多目標路徑選擇的實際應(yīng)用過程中，人們發(fā)現(xiàn)使用通常的預(yù)測方法所計算出的結(jié)果會隨著預(yù)測區(qū)間的推移，誤差迅速增大。這主要是由于選擇系統(tǒng)自身發(fā)展變化的規(guī)律是具有時變性的，而常用選擇路徑的模型方法所用模型往往不是時變的。所以，其選擇誤差越來越大。人工神經(jīng)網(wǎng)絡(luò)理論的發(fā)展和應(yīng)用，為解決上述問題提供了可能。一方面，神經(jīng)網(wǎng)絡(luò)具有良好的非線性品質(zhì)，靈活而有效的學習方式，完全分布式的學習結(jié)構(gòu)，高度并行的處理機制。另一方面，神經(jīng)網(wǎng)絡(luò)能夠?qū)崿F(xiàn)非線性映射，使得神經(jīng)網(wǎng)絡(luò)具有較好的模式識別能力和在任意精度逼近非線性預(yù)測的能力［6-7］。所以，利用人工神經(jīng)網(wǎng)絡(luò)方法可以很好地解決非戰(zhàn)爭軍事行動裝備保障資源運輸方式的選擇問題。

1.2 模型建立

下面以一個例子說明多目標的路徑選擇模型。問題假設(shè):從某倉庫運輸裝備到某部隊，有m條路徑可以選擇，有n個約束目標Vi(i=1，2，…，n)(如運量要求、運輸時效限定、運輸安全要求等)。要做出道路選擇決策，可構(gòu)造一個n+m個神經(jīng)元組成的雙向聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)，如圖1所示。

圖1 雙向聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)

其中，向量 A 的分量 a1，a2，…，ai，…，an神經(jīng)元為目標神經(jīng)元;B 的分量 b1，b2，…，bj，…，bm為決策結(jié)果神經(jīng)元。A、B的每一個分量都屬于集合{-1，1}，Wij為兩種神經(jīng)元之間的連接權(quán)重。根據(jù)聯(lián)想神經(jīng)網(wǎng)絡(luò)理論，用k個決策向量對(A1，B1)、(A2，B2)、…、(Ak，Bk)訓練網(wǎng)絡(luò)，可將 k 種決策模式作為專家的知識或經(jīng)驗聯(lián)想存儲于權(quán)矩陣W(W=［Wij］m×n)中。對于任意給定目標A，都可由網(wǎng)絡(luò)經(jīng)過疊代而得出聯(lián)想決策結(jié)果B。具體過程如下［8］:

(1)選擇訓練模式(Ai，Bi)(i=1，2，…，k)，置連接權(quán)初始值Wij(0)=0，置?W為常數(shù)(一般為10)以及F=F'=2?W。

(2)在固定的F和 F'下疊代。根據(jù)第 t步的估計值Wij(t)，由下式計算t+1步的估計值Wij(t+1)，同時記錄疊代數(shù) n(F，F(xiàn)')。

式(1)中，

(3)如果出現(xiàn)，對進行歸一化，算式為

(4)如果疊代次數(shù)n(F，F(xiàn)')小于某個預(yù)定值(如30)，那么增加F=F+ΔF，F(xiàn)'=F'+ΔF'，其中ΔF=ΔF'=?W轉(zhuǎn)至步驟(2);否則終止運算。

(5)將k種決策模式作為專家知識和經(jīng)驗聯(lián)想存儲于權(quán)矩陣W=［Wij］m×n中。對于給定的目標A，由網(wǎng)絡(luò)聯(lián)想得出決策結(jié)果B:

初始化，置Aold=A，Bold為任意值。計算B的向量新狀態(tài)Bnew。

置換Bold、Bnew，有BOold=Bnew。計算A向量新狀態(tài)Anew:

計算向量A新舊狀態(tài)差異δ:

若 δ＞0或 δ＜0，令 Aold=Anew，返回(2)繼續(xù)疊代。若δ=0，網(wǎng)絡(luò)穩(wěn)定，結(jié)束迭代，得到穩(wěn)態(tài)向量對為(Aold，Bold，此時Aold=A，Bold即為在目標下A的決策結(jié)果。

2 非戰(zhàn)爭軍事行動裝備保障資源運輸路徑優(yōu)化模型

2.1 路徑優(yōu)化模型建立

非戰(zhàn)爭軍事行動中，資源點和儲備點的數(shù)量并非總是單一，因此在建立路徑分析模型時，首先解決任意一個儲備點Ri到任意一個需求點Ri之間的路徑分析模型。假設(shè)由Ri至Ri的交通網(wǎng)絡(luò)圖如圖2所示。

圖2 Ri至Sj的交通運輸網(wǎng)絡(luò)

在非戰(zhàn)爭軍事行動裝備保障資源運輸過程中，根據(jù)運輸環(huán)境的變化需要考慮“禁行點”、“必經(jīng)點”和“必經(jīng)路段”，“禁行點”就是部隊車隊不允許通過的地點(如災(zāi)害損毀的地段等)，“必經(jīng)點”就是部隊車隊必須通過的地點(如裝備需求區(qū)域、軍供站等)，“必經(jīng)路段”指運輸車隊必須經(jīng)過的路段(如任務(wù)中的路段、特殊路段等)。

(1)運輸網(wǎng)絡(luò)圖分析。圖2中圓形、方形、三角形點都為節(jié)點，其中方形節(jié)點代表“必經(jīng)點”，三角形節(jié)點代表“禁行點”。根據(jù)保障資源調(diào)度任務(wù)建立從起點“Ri”到終點“Sj”的運輸網(wǎng)絡(luò)圖記為G=(V，A，B)，其中:V代表節(jié)點集(交通樞紐、城鎮(zhèn)、軍供站、交叉路口或特殊節(jié)點等);A代表弧集(路段);B表示路段和節(jié)點的廣義阻礙強度。

(2)模型基本條件假設(shè)。非戰(zhàn)爭軍事行動裝備保障資源調(diào)配路徑優(yōu)化問題約束因素主要有時間、費用和安全性，而線路里程、行駛速度、交通樞紐和軍供站的裝卸車、生活保障等都會影響著以上的因素。且在執(zhí)行非戰(zhàn)爭軍事行動裝備保障時各因素因任務(wù)實際情況而隨時發(fā)生改變。因此，需要將求解廣義阻礙強度T的多目標問題轉(zhuǎn)化成單目標問題。本章利用線性加權(quán)法定義節(jié)點和弧的廣義阻礙強度:

式(9)中:a為代表弧段長度(當取某一節(jié)點時，a=1);t為通過單位長度弧段或節(jié)點的時間;s為通過弧段或節(jié)點的危險性;Bt，Bh為個目標的權(quán)重，且Bt+Bh=1。

在實際計算中，由于各道路具體情況不同，并且各目標值存在一定的模糊性和不同量綱，可依據(jù)具體的資源運輸方式和任務(wù)情況，采用各種方法對各目標進行量化處理，各目標的權(quán)重也可用類似的方法確定，從而求出道路的廣義阻礙強度。

因為通過運輸網(wǎng)絡(luò)圖節(jié)點集V中節(jié)點的順序并沒有設(shè)定，所以非戰(zhàn)爭軍事行動裝備保障資源運輸不僅必須考慮必經(jīng)點、禁行點和必經(jīng)路段，還必須考慮經(jīng)過節(jié)點的順序問題。即如果要通過某個節(jié)點(稱為后節(jié)點)，則必須先通過它前面的節(jié)點(稱為前節(jié)點)。前面的節(jié)點不一定與后面的節(jié)點直接相鄰，而且前節(jié)點和后節(jié)點可以是一對一、一對多的關(guān)系。對于必經(jīng)路段，將必經(jīng)路段的起止節(jié)點，作為必經(jīng)點并提取位于必經(jīng)路段除起止本節(jié)點外的一個點作為必經(jīng)點，如此，則確定了必經(jīng)路段跟與其對應(yīng)的必經(jīng)節(jié)點的一一對應(yīng)關(guān)系。為了使模型充分考慮必經(jīng)點、禁行點和節(jié)點保序問題，建立必經(jīng)點集合Vk、禁行點集合Vf、前節(jié)點集合Va和后節(jié)點集合Vb。對于節(jié)點Vi(i＞1)∈Vb，則必須存在前節(jié)點∈Vf與之對應(yīng)。其中:Vk?V，Vf?V，Va?V，Vb?V。

(3)建立路徑優(yōu)化模型。根據(jù)運輸網(wǎng)絡(luò)圖G=(V，A，B)，可求解圖中由Ri至Sj的最優(yōu)路徑，只需搜索連接Ri至Sj的具有最小阻礙強度B的路徑即可。故建立路徑優(yōu)化模型如下:

目標函數(shù)為

上述模型中，式(10)為目標函數(shù);式(11)為路徑R的整體道路阻礙強度定義;式(12)表示必經(jīng)點集合一定包含于路徑的節(jié)點集Vr中;式(13)表示禁行點集合一定不包含在路徑的節(jié)點集Vr中，但是其包含于V;式(14)表示如果有后節(jié)點位于路徑上，則至少存在一個對應(yīng)的前節(jié)點也位于路徑上，這是保持按順序經(jīng)過節(jié)點問題;B(i，j)為弧(i，j)的道路阻礙強度;Ar表示路徑R中的弧集;Vr表示路徑R中的節(jié)點集合;Brs表示所求的由Ri到Sj的最優(yōu)路徑。

2.2 遺傳算法在運輸路徑優(yōu)化中的應(yīng)用

對于多因素影響下單運輸方式的多源多匯路徑優(yōu)化問題，其求解算法很多，其中比較經(jīng)典的有Dijkstra算法等。用傳統(tǒng)的最短路徑尋優(yōu)算法解決存在大規(guī)模節(jié)點和路徑中有必經(jīng)點和節(jié)點保序約束要求的路網(wǎng)時，會出現(xiàn)很多難題。特別是在非戰(zhàn)爭軍事行動裝備保障資源調(diào)配問題中，由于在實際調(diào)配中為了保證調(diào)配方案的實施，可能需要多條路徑作為預(yù)選，因此在求解的結(jié)果集中一般要求不僅有最優(yōu)的路徑，還要有次優(yōu)、再次優(yōu)的路徑等。相比之下，遺傳算法(Genetic Algorithms，GA)由于其潛在的并行性和全局尋優(yōu)及算法構(gòu)造簡單等特點更能求解出多因素影響下單運輸方式的多源多匯路徑優(yōu)化模型的理想最優(yōu)解。

假設(shè)基本信息設(shè)置如下:需求點信息S，個數(shù)m;單個需求點 Sj(j=1，2，…，m);儲備點信息R，個數(shù) u;單個儲備點Ri(i=1，2，…，u);路徑信息 W，路徑編號 a:{a1，a2，…，an};節(jié)點編號v:{v1，v2，…，vn};路徑阻力T。則利用遺傳算法，可得出對多源多匯路徑優(yōu)化模型的解法如下。

2.2.1 種群初始化

由于路網(wǎng)中包含了起點、終點和必經(jīng)點，用字母與整數(shù)混合編碼方式構(gòu)造染色體，染色體的基因是網(wǎng)絡(luò)的節(jié)點，而節(jié)點的排列順序代表著起點到終點的路徑。設(shè)路網(wǎng)G的節(jié)點數(shù)為N，則染色體的基因數(shù)也設(shè)定為N。為了解決必經(jīng)點問題，本文中設(shè)計了這樣的染色體基因組成方式:第一個為起點“R”;接下來是中間節(jié)點，分為兩部分，一部分由必經(jīng)點集合Vk中的全部節(jié)點構(gòu)成，設(shè)共有m個節(jié)點，另一部份為k個其他節(jié)點組成，0≤k≤N-m-2;然后是終點“S”。如果k＜N-m-2，則在“S”點后補“0”，使基因總數(shù)保持為 N。這樣，染色體中實際的有效基因長度，即從“R”到“S”為m+k+2。通過產(chǎn)生［m+2，N］之間的隨機整數(shù)來確定染色體的有效基因長度，以及對中間部分基因節(jié)點位置做隨機排列來得到初始種群中的染色體。由于路徑的好壞與基因的排列順序有關(guān)，為了提高遺傳算法的收斂性能，在種群初始化時應(yīng)對染色體做預(yù)處理，當檢查發(fā)現(xiàn)染色體中的兩相鄰基因生成的無效弧數(shù)(沒有實際的弧相連)大于該路徑總弧數(shù)的60%時，則該染色體無效，需重新生成。

2.2.2 節(jié)點保序處理

對每個染色體進行節(jié)點保序檢查，如果有基因點或基因點對沒有滿足要求，則視情況進行處理。如果需保序的兩個基因順序錯誤，則可對需保序的兩節(jié)點互換位置，或直接刪除這兩個節(jié)點(必經(jīng)點除外)，并在“S”后增加兩個“0”基因。如果缺少保序的前節(jié)點，則可以刪除保序后節(jié)點并在“S”后增加一個“0”基因，或當染色體從“R”到“S”的有效基因長度小于N時增加配對的保序前節(jié)點并刪除“S”后的一個“0”基因。

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

對于第t代種群中的每一染色體所代表的路徑，用式(11)求出其對應(yīng)的廣義權(quán) Wti，其中 i=1，2，…，N，如果染色體中存在沒有實際弧相連的基因序列節(jié)點對，則其對應(yīng)的弧權(quán)值取一較大數(shù)Wmax。為了增加優(yōu)秀個體繁殖的機會提高算法的性能，建立帶有自適應(yīng)能力的適應(yīng)度函數(shù):

其中:Wtmin為第t代群中染色體廣義權(quán)值中的最小者，即最優(yōu)者。如果染色體適應(yīng)度函數(shù)值越大，則路徑越好，反之則越差。

2.2.4 染色體選擇

采用改進的輪盤賭選擇法。在選擇新個體時，首先在當前代的可行個體中選擇最佳個體直接進入下一代(若有多個，則隨機選取一個)，然后對其他個體采用輪盤賭方式進行選擇，如果在當前代中沒有可行個體，則全部按輪盤賭方式生成下一代個體。

2.2.5 染色體交叉

由于染色體基因中存在節(jié)點保序要求，交叉方式對算法性能有重要影響，因而采用兩種交叉方式進行算法性能研究。設(shè)有兩個父代染色體A(R12546S0)和B(R234156S)，其中節(jié)點2與節(jié)點4存在“保存關(guān)系”，且節(jié)點2位于節(jié)點4之前，節(jié)點5為“必經(jīng)點”。

(1)部分匹配交叉。(PMX)方式進行染色體的交叉。步驟:從兩個父代選擇的染色體A，B的基因中隨機選擇兩個交叉點，且必須同時位于兩個染色體的“R”點之后，“S”點之前，以保證“R”基因不被交叉。將染色體A，B中的交叉點之間的匹配段互換，得到兩個新染色體A1，B1;交叉后，對新染色體進行合法性檢查。如果染色體A1(或B1)中出現(xiàn)重復節(jié)點，即節(jié)點有可能同時出現(xiàn)在匹配段內(nèi)和匹配段外，則用匹配段內(nèi)重復節(jié)點對應(yīng)于另一染色體相應(yīng)位置節(jié)點去替換匹配段外的節(jié)點，通過反復替換直至染色體中不出現(xiàn)重復節(jié)點;進行保序處理。

PMX交叉過程如表1所示。消除重復基因節(jié)點，有A2:R341256S0，B2:R254316S，為保持 A2的基因數(shù)為 N，刪除一個“0”基因，由于其還不符合保序要求，因此可用互換位置法作保序處理后得到新染色體為R321456S。

表1 PMX交叉過程示意

2.2.6 染色體變異

這里采用的染色體變異方式有3種:第1種是在RS節(jié)點間隨機地刪除一個非必經(jīng)點，同時在“S”后增加一個“0”基因;第2種是當染色體從“R”到“S”的有效基因長度小于N時增加一個基因中沒有的節(jié)點，并刪除一個“0”基因;第3種是互換兩個不存在節(jié)點保序要求的節(jié)點。變異后進行保序處理。在實際操作時，可先分別采用3種方式進行變異，然后取其中適應(yīng)度值最好者。

3 案例分析

3.1 實例驗證

現(xiàn)假設(shè)某戰(zhàn)區(qū)有如圖3所示交通網(wǎng)絡(luò)圖。圖3中有5個儲備點:R1，R2，R3，R4和 R5(分別位于 v1，v20，v30，v3和v5)，3 個需求點:S1，S2和 S3(分別位于 v44，v45和 v48)。

假設(shè)單位器材每千米的運輸費用見表2。

表2 器材運輸費用表

各路段的通過時間、危險性見表3。

圖3 某戰(zhàn)區(qū)交通網(wǎng)絡(luò)

表3 路段屬性表

對以上需求和屬性條件進行建模求解如下。

(1)假設(shè)從資源點到保障點的每條路徑除起止點外至少經(jīng)過一個“必經(jīng)點”，而且每個“必經(jīng)點”至少經(jīng)過一次。對通過“禁行點”的費用、時間和危險性取較大的常數(shù)，比如:f=10000，t=1000，s=10000。

(2)由于非戰(zhàn)爭軍事行動裝備保障以時間保障和危險性為主，因此 3 個權(quán)重 bf、bt、bs的值分別為0.1、0.6 和0.3。根據(jù)遺傳算法計算方法，取基因長度48、種群規(guī)模200、交叉率0.8、變異率0.05、最大迭代次數(shù)為150次，計算得出最優(yōu)路徑。結(jié)果如下:

R1至 S1最優(yōu)路線:v1—v6—v8—v21—v23—v39—v40—v41—v44;R1至 S2最優(yōu)路線:v1—v6—v8—v21—v23—v39—v43—v45;R1至 S3最優(yōu)路線:v1—v6—v8—v20—v19—v18—v29—v28—v31—v48;R2至 S1最優(yōu)路線:v20—v21—v23—v39—v40—v41—v44;R2至 S2最優(yōu)路線:v20—v21—v23—v39—v43—v45;R2至 S3最優(yōu)路線:v20—v19—v18—v29—v28—v31—v48;R3至 S1最優(yōu)路線:v30—v36—v38—v39—v40—v41—v44;R3至 S2最優(yōu)路線:v30—v35—v45;R3至 S3最優(yōu)路線:v30—v29—v28—v31—v48;R4至 S1最優(yōu)路線:v3—v9—v20—v21—v23—v39—v40—v41—v44;R4至 S2最優(yōu)路線:v3—v9—v20—v21—v23—v39—v43—v45;R4至 S3最優(yōu)路線:v3—v9—v20—v19—v18—v29—v28—v31—v48;R5至 S1最優(yōu)路線:v5—v4—v10—v12—v20—v21—v23—v39—v40—v41—v44;R5至 S2最優(yōu)路線:v5—v16—v29—v28—v29—v30—v35—v45;R5至 S3最優(yōu)路線:v5—v16—v29—v28—v31—v48。

(3)結(jié)果分析與比較。對于本文中的最短路徑問題，運籌學中最有效的解法是動態(tài)規(guī)劃法。但是利用動態(tài)規(guī)劃法求解本例中的路徑問題時，需要對每段弧線求出廣義道路阻礙強度，然后按逐步累積進行計算，這樣的計算量隨著節(jié)點數(shù)的增多而急劇增大。特別是在處理“必經(jīng)點”、“禁行點”、“必經(jīng)路段”和節(jié)點保序問題時，利用動態(tài)規(guī)劃法計算則難上加難?？梢?，對于求解最佳路徑時，遺傳算法要比動態(tài)規(guī)劃法更加合理。

4 結(jié)束語

根據(jù)非戰(zhàn)爭軍事行動特殊需求，提高裝備保障快速反應(yīng)能力，合理選擇保障資源運輸方式與運輸路徑，優(yōu)化裝備保障資源配置，在整個非戰(zhàn)爭軍事行動裝備保障鏈中具有關(guān)鍵作用。本文采用神經(jīng)網(wǎng)絡(luò)法選擇保障資源運輸方式，用遺傳算法優(yōu)化保障資源運輸路徑，并結(jié)合實際的交通網(wǎng)絡(luò)圖給出了運輸方式選擇的案例分析，表明模型的可行性與有效性。

［1］楊曉段，李元左.非戰(zhàn)爭軍事行動裝備保障資源儲備模型［J］.價值工程，2013，32(4)：19-21.

［2］李元左，楊曉段，郭瑞平.非戰(zhàn)爭軍事行動裝備保障資源需求預(yù)測模型［J］.價值工程，2013，32(3)：281-282.

［3］施毅，顧毓.基于單目標規(guī)劃的彈藥最佳運輸策略分析［J］.武漢理工大學學報：交通科學與工程版，2006(10)：100-102.

［4］張亮，王端民.戰(zhàn)時裝備保障的多目標運輸問題及其求解［J］.物流科技，2009，28(10)：25-27.

［5］余小川.敏捷制造企業(yè)供應(yīng)物流系統(tǒng)的優(yōu)化研究［D］.重慶：重慶大學，2002.

［6］海金，葉世偉.神經(jīng)網(wǎng)絡(luò)原理［M］.北京：機械工業(yè)出版社，2004.

［7］焦李成.神經(jīng)網(wǎng)絡(luò)的應(yīng)用與實現(xiàn)［M］.西安：西安電子科技大學出版社，1993.

［8］徐德磊，韓曉龍，梁承姬.基于堆存能力的集卡優(yōu)化分派研究［J］.武漢理工大學學報，2011(9)：77-81.