基于道路通行概率的戰時油料前送最優路徑研究

王 強，李 橫，崔子慶，高 諍WANG Qiang,LI Heng,CUI Zi-qing,GAO Zheng

（1.后勤工程學院，重慶 401311；2.汕頭警備區，廣東 汕頭 515038）

(1.Logistical Engineering University,Chongqing 401311,China;2.Shantou Garrison,Shantou 515038,China)

本質上，油料前送最優路徑的求解就是在后方油庫與戰役野戰油庫兩點之間尋找一條軍事效益最好的路徑。無論是路徑的“最優”有哪個因素——距離最短、時間最短、費用最少或者安全性最高，其核心算法都是最短路徑算法。在戰時，要保證油料保障的安全、準確和及時，就要求找出一條 “最優”路徑。戰時油料前送，要求安全順利并且時間最短，所以交通網絡抽象圖的邊權是運油車在該段道路上行駛所需的時間。模型結合戰時的道路損毀情況，采用圖論經典的D算法對最優路徑進行求解。

利用圖論的經典理論和GIS存儲的相關數據信息研究目標區域內的道路戰時通行情況，并由此得出運油車前送油料的最優路徑。首先計算出戰時道路通行概率P，用此概率乘以運油車平時在該路段的行駛速度Si1，得出戰時運油車在該路段的行駛速度Si2，用該路段長度Li除以Si2，得出運油車在該路段所需要的時間Ti。將Ti作為道路抽象網絡圖的路邊的權，得出戰時運油車在目標道路上行駛的時間矩陣，以選擇從后方油庫到戰役野戰油庫所需最短時間的路線為目標，建立最短路徑問題的數學模型，利用經典的D算法確定最短路徑。將此方法應用于某運油分隊執行油料前送任務，尋找出符合要求的最優路徑。

1 模型使用技術和算法

1.1 緩沖區 （Buffer）分析

地理信息空間關系分析主要包括緩沖區分析、疊加分析、空間集合分析和專業分析等。本文所才采用緩沖區分析是油料保障地理信息系統的基本空間操作功能之一。緩沖區分析是圍繞空間的點、線、面實體，自動建立其周圍一定寬度范圍內的多邊形，用以識別這些實體或主體對鄰近對象的輻射范圍，以便為某項分析或決策提供依據。其基本思想就是給定一個空間實體或集合，確定它們的鄰域，鄰域的大小由設定的鄰域半徑R來確定。要分析前送油料的最優路徑，則需對前送油料目標道路建立線緩沖區進行分析。線要素的緩沖區是以線為軸，以R為距離作兩側的平行線，在機動路線的兩端以R為半徑作半圓，平行線和半圓所圍區域就是緩沖區。如圖1所示。

1.2 Dijkstra算法

Dijkstra算法 （簡稱D算法）是尋求從一固定起點到其余各點的最短路徑的最有效算法之一，是一種圖上標記作業法，每次在計算完成一個探索節點就產生一個標記，直至所有路網節點被標記。算法思想是：采用標號作業法，每次迭代產生一個永久標號，從而生長一顆以V0為根的最短路樹，在這顆樹上每個頂點與根節點之間的路徑皆為最短路徑。由于網絡不存在負權，最短路樹的生長過程中各頂點將按照距離的遠近以及頂點的相鄰關系，逐次長入樹中。

圖1 線緩沖區示意圖

2 基于戰時道路通行概率的最短路徑模型

2.1 模型假設

通過地理信息空間幾何關系中的緩沖區分析，對緩沖區內的軍地油料保障力量進行分析后，查找出目標區域內的道路損毀情況，計算出每一段道路的通行概率，并以此計算出運油車前送油料的最短時間路徑，以保證油料保障任務能及時順利的完成。假設：

（1）緩沖區內至少有一條路徑能夠通行 （可以通過更改緩沖區半徑R達到該條件）；

（2）緩沖區內各段道路損毀情況及路段長度已知；

（3）運油車在各路段上的平時行駛速度已知；

（4）彈坑的坑口都為規則的圓。

2.2 模型構建

戰時道路通行概率的假設。根據現代非接觸戰爭的特點，假設戰時道路主要受到以下兩個因素的影響：一是彈坑的大小及分布情況；二是道路本身損毀情況。

第一、彈坑影響下道路通行概率的計算公式為：

B為彈坑的直徑大小，BC為彈坑的臨界直徑大小，BC=K1-K2，K1為道路的可行駛的實際寬度，K2為運油車的寬度。

第二、道路本身損毀影響下道路通行概率：

針對在敵人炸彈落在道路附近造成破壞的情況。根據道路的位置及重要性不同，遭敵襲擊破壞的程度不同，戰時道路損毀程度可分為四個等級，分別為基本完好、輕微破壞、中等破壞和嚴重破壞。可分別給不同的等級賦不同的概率值PB來表示道路的連通性。如表1所示。

表1 戰時道路損毀等級描述

因此，路段的通行概率可以表示如下：

其中，PD為受彈坑影響的路段通行概率，PB為受道路本身破壞程度影響的路段通行概率，β為權值，戰時情況下取β=0.7。

其中，Si1為運油車平時在該路段的行駛速度，Si2為戰時運油車在該路段的行駛速度，Li為該路段長度除以Si2，Ti為戰時運油車通過該路段所需要的時間Ti。

步履如飛，精神抖擻，思維敏捷，67歲的楊宗祥狀態絲毫不輸給年輕人。與很多出生于五十年代的人一樣，楊宗祥的童年也是充滿艱辛。13歲無奈輟學回家掙工分，17歲時，他被分到安寧洪源養殖場工作，他摸索出了魚苗的孵化技術，當時在昆明屬于領先技術。他又充分利用養殖場的資源，養雞、養豬，自己焊雞籠，挑雞糞、豬糞，配飼料，直至當上了場長。

彈坑大小的分布——假設彈坑的直徑大小介于0到K1之間，所以符合參數λ2=K1的指數分布：其中λ=K1，為道路的可行駛的實際寬度。且x為從戰役野戰油庫到后方油庫的道路編號1,2,3,…,n。

設在緩沖區內有n個道路節點 （包含起點后方油庫和終點戰役野戰油庫），分別為ai（i=1,2,…,n）。V0：路徑起點，S：具有永久標號的頂點集，u：路徑抽象途中暫未永久標號的定點，l（V）：V的標記，f（V）：V的父頂點，用以確定最短路徑。為了便于計算機的計算和處理，需要將GIS相關信息數字化，系統采用鄰接矩陣來表示網絡圖。其基本方法是：設G=（V,E）是一個無向圖，V=｛v1,v2,…,vn｝， 則G的鄰接矩陣A=（aij）n×n。其中：

用鄰接矩陣表示圖，很容易判定兩個頂點之間是否有邊相連，也容易求出各頂點的次數。且無向圖是對稱的，只考慮上三角矩陣即可。

2.3 模型求解

結合GIS中存儲的道路情況計算出彈坑的分布情況和彈坑大小的分布情況，運用公式 （1）和 （2）計算出緩沖區內目標道路的通行概率P，并結合目標道路長度Li和已知的道路平時速度Si1，運用公式 （3）計算出戰時運油車在路段i的通行時間Ti，輸入以Ti為權的帶權鄰接矩陣w=［w（ vi, vj）］：

②更新 l（v）,f（v）—— 尋找不在S中的頂點u，使l（u）為最小。把u加入到S中，然后對所有不在S中的頂點v，如l（v ）＞l（u）+w（ u,v）， 則更新l（v）,f（v）,即 l（v ）←l（u）+w（ u,v）,f（v ）←u；

③重復步驟②，直到所有頂點都在S中為止。

3 模型算例

在戰時，某部隊油料部門從后方油庫往戰役野戰油庫前送油料。后方油庫為點V1，戰役野戰油庫為點V11，中間共有道路節點11個，22段道路，每段道路的長度已在道路網絡圖中標注，單位為km，抽象的道路網道路編號如圖2所示。18號、11號、4號和1號道路寬度為10m，其余道路的寬度為7m，運油車的寬度為2.5m，運油車在V1→V3→V6→V9→V11的干路上的行駛速度為80km/h，在其余支路上的行駛速度為50km/h。1號道路至22號道路的里程分別為：20、90、40、60、70、10、20、90、30、10、10、30、40、10、50、20、90、80、20、60、70、10；單位為km。求前送油料的最短時間路徑。

圖2 抽象路網道路編號圖

運用公式 （1）、（2）和 （3）求出戰時運油車在編號為1至22的道路上的行駛時間分別為：0.317,2.118,0.941,0.882,1.647,0.235,0.471,2.278,0.941,0.235,0.158,0.706,0.8,0.2,1,0.4,1.8,1.266,0.4,1.2,1.4,0.2；單位為小時。將得到的時間作為抽象路網的邊權，作為鄰接矩陣，并用matlab編程實現得到結果如下：

即最短路路徑為從點V1→點V2→點V3→點V7→點V10→點V9→點V11；最短路路徑值為2.45小時，約為兩個半小時。

4 結 論

本文結合緩沖區分析，根據戰時目標區域內道路損毀情況，對戰時運油車通行概率的模型和最短時間路線選擇模型進行了分析，利用D算法求出了后勤部隊油料分隊從后方油庫往戰役野戰油庫前送油料的時間最短的路線，對戰時油料保障有一定的指導意義。本文最大的特點是考慮了戰時道路的通行概率，更加貼近實戰，使油料運輸分隊戰時油料保障更具針對性。但是在算法上還存在一些不足，需要手動輸入起點、終點和路網帶權鄰接矩陣，計算量稍大、占用資源較多等，將在下步的研究中將進行進一步的改進。

[1]王海英,等.圖論算法及其MATLAB實現[M].北京：北京航空大學出版社，2010.

[2]陳子俠,等.基于GIS物流配送線路優化與仿真[M].北京：經濟科學出版社，2007.

[3]李萌.西藏軍區油料保障智能決策支持系統研究[D].重慶：解放軍后勤工程學院 （碩士學位論文），2006.

[4]孫衛東，殷武,等.油料管理理論與方法[M].北京：解放軍出版社，2004.

[5]李軍，郭耀煌,等.物流配送車輛優化調度理論與方法[M].北京：中國物資出版社，2001.

[6]姚娜,等.GIS、MapInfo與MapBasic學習教程[M].北京：北京大學出版社，2000.

[7]邊文質.航炮射擊彈著點的分布特性研究及試驗規范的討論[J].西安工業大學學報，1983(2)：33-47.