非戰爭軍事行動裝備保障資源運輸方式選擇模型

楊曉段，李元左，郭瑞平

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

裝備保障資源運輸是非戰爭軍事行動裝備保障［1-2］的重要環節。調配方案確定后，如何確保快速、高效地運送保障資源是非戰爭軍事行動裝備保障的關鍵。本文展開對非戰爭軍事行動裝備保障資源運輸方式的選擇與路徑優化的模型進行研究。

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

1.1 問題分析

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

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

1.2 模型建立

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

圖1 雙向聯想記憶神經網絡

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

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

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

式(1)中，

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

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

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

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

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

計算向量A新舊狀態差異δ:

若 δ＞0或 δ＜0，令 Aold=Anew，返回(2)繼續疊代。若δ=0，網絡穩定，結束迭代，得到穩態向量對為(Aold，Bold，此時Aold=A，Bold即為在目標下A的決策結果。

2 非戰爭軍事行動裝備保障資源運輸路徑優化模型

2.1 路徑優化模型建立

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

圖2 Ri至Sj的交通運輸網絡

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

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

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

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

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

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

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

目標函數為

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

2.2 遺傳算法在運輸路徑優化中的應用

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

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

2.2.1 種群初始化

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

2.2.2 節點保序處理

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

2.2.3 適應度函數

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

其中:Wtmin為第t代群中染色體廣義權值中的最小者，即最優者。如果染色體適應度函數值越大，則路徑越好，反之則越差。

2.2.4 染色體選擇

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

2.2.5 染色體交叉

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

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

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

表1 PMX交叉過程示意

2.2.6 染色體變異

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

3 案例分析

3.1 實例驗證

現假設某戰區有如圖3所示交通網絡圖。圖3中有5個儲備點:R1，R2，R3，R4和 R5(分別位于 v1，v20，v30，v3和v5)，3 個需求點:S1，S2和 S3(分別位于 v44，v45和 v48)。

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

表2 器材運輸費用表

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

圖3 某戰區交通網絡

表3 路段屬性表

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

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

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

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

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

4 結束語

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

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

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

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

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

［5］余小川.敏捷制造企業供應物流系統的優化研究［D］.重慶：重慶大學，2002.

［6］海金，葉世偉.神經網絡原理［M］.北京：機械工業出版社，2004.

［7］焦李成.神經網絡的應用與實現［M］.西安：西安電子科技大學出版社，1993.

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