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

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

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

本質(zhì)上，油料前送最優(yōu)路徑的求解就是在后方油庫與戰(zhàn)役野戰(zhàn)油庫兩點(diǎn)之間尋找一條軍事效益最好的路徑。無論是路徑的“最優(yōu)”有哪個(gè)因素——距離最短、時(shí)間最短、費(fèi)用最少或者安全性最高，其核心算法都是最短路徑算法。在戰(zhàn)時(shí)，要保證油料保障的安全、準(zhǔn)確和及時(shí)，就要求找出一條 “最優(yōu)”路徑。戰(zhàn)時(shí)油料前送，要求安全順利并且時(shí)間最短，所以交通網(wǎng)絡(luò)抽象圖的邊權(quán)是運(yùn)油車在該段道路上行駛所需的時(shí)間。模型結(jié)合戰(zhàn)時(shí)的道路損毀情況，采用圖論經(jīng)典的D算法對(duì)最優(yōu)路徑進(jìn)行求解。

利用圖論的經(jīng)典理論和GIS存儲(chǔ)的相關(guān)數(shù)據(jù)信息研究目標(biāo)區(qū)域內(nèi)的道路戰(zhàn)時(shí)通行情況，并由此得出運(yùn)油車前送油料的最優(yōu)路徑。首先計(jì)算出戰(zhàn)時(shí)道路通行概率P，用此概率乘以運(yùn)油車平時(shí)在該路段的行駛速度Si1，得出戰(zhàn)時(shí)運(yùn)油車在該路段的行駛速度Si2，用該路段長度Li除以Si2，得出運(yùn)油車在該路段所需要的時(shí)間Ti。將Ti作為道路抽象網(wǎng)絡(luò)圖的路邊的權(quán)，得出戰(zhàn)時(shí)運(yùn)油車在目標(biāo)道路上行駛的時(shí)間矩陣，以選擇從后方油庫到戰(zhàn)役野戰(zhàn)油庫所需最短時(shí)間的路線為目標(biāo)，建立最短路徑問題的數(shù)學(xué)模型，利用經(jīng)典的D算法確定最短路徑。將此方法應(yīng)用于某運(yùn)油分隊(duì)執(zhí)行油料前送任務(wù)，尋找出符合要求的最優(yōu)路徑。

1 模型使用技術(shù)和算法

1.1 緩沖區(qū) （Buffer）分析

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

1.2 Dijkstra算法

Dijkstra算法 （簡稱D算法）是尋求從一固定起點(diǎn)到其余各點(diǎn)的最短路徑的最有效算法之一，是一種圖上標(biāo)記作業(yè)法，每次在計(jì)算完成一個(gè)探索節(jié)點(diǎn)就產(chǎn)生一個(gè)標(biāo)記，直至所有路網(wǎng)節(jié)點(diǎn)被標(biāo)記。算法思想是：采用標(biāo)號(hào)作業(yè)法，每次迭代產(chǎn)生一個(gè)永久標(biāo)號(hào)，從而生長一顆以V0為根的最短路樹，在這顆樹上每個(gè)頂點(diǎn)與根節(jié)點(diǎn)之間的路徑皆為最短路徑。由于網(wǎng)絡(luò)不存在負(fù)權(quán)，最短路樹的生長過程中各頂點(diǎn)將按照距離的遠(yuǎn)近以及頂點(diǎn)的相鄰關(guān)系，逐次長入樹中。

圖1 線緩沖區(qū)示意圖

2 基于戰(zhàn)時(shí)道路通行概率的最短路徑模型

2.1 模型假設(shè)

通過地理信息空間幾何關(guān)系中的緩沖區(qū)分析，對(duì)緩沖區(qū)內(nèi)的軍地油料保障力量進(jìn)行分析后，查找出目標(biāo)區(qū)域內(nèi)的道路損毀情況，計(jì)算出每一段道路的通行概率，并以此計(jì)算出運(yùn)油車前送油料的最短時(shí)間路徑，以保證油料保障任務(wù)能及時(shí)順利的完成。假設(shè)：

（1）緩沖區(qū)內(nèi)至少有一條路徑能夠通行 （可以通過更改緩沖區(qū)半徑R達(dá)到該條件）；

（2）緩沖區(qū)內(nèi)各段道路損毀情況及路段長度已知；

（3）運(yùn)油車在各路段上的平時(shí)行駛速度已知；

（4）彈坑的坑口都為規(guī)則的圓。

2.2 模型構(gòu)建

戰(zhàn)時(shí)道路通行概率的假設(shè)。根據(jù)現(xiàn)代非接觸戰(zhàn)爭(zhēng)的特點(diǎn)，假設(shè)戰(zhàn)時(shí)道路主要受到以下兩個(gè)因素的影響：一是彈坑的大小及分布情況；二是道路本身損毀情況。

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

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

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

針對(duì)在敵人炸彈落在道路附近造成破壞的情況。根據(jù)道路的位置及重要性不同，遭敵襲擊破壞的程度不同，戰(zhàn)時(shí)道路損毀程度可分為四個(gè)等級(jí)，分別為基本完好、輕微破壞、中等破壞和嚴(yán)重破壞?？煞謩e給不同的等級(jí)賦不同的概率值PB來表示道路的連通性。如表1所示。

表1 戰(zhàn)時(shí)道路損毀等級(jí)描述

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

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

其中，Si1為運(yùn)油車平時(shí)在該路段的行駛速度，Si2為戰(zhàn)時(shí)運(yùn)油車在該路段的行駛速度，Li為該路段長度除以Si2，Ti為戰(zhàn)時(shí)運(yùn)油車通過該路段所需要的時(shí)間Ti。

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

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

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

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

2.3 模型求解

結(jié)合GIS中存儲(chǔ)的道路情況計(jì)算出彈坑的分布情況和彈坑大小的分布情況，運(yùn)用公式 （1）和 （2）計(jì)算出緩沖區(qū)內(nèi)目標(biāo)道路的通行概率P，并結(jié)合目標(biāo)道路長度Li和已知的道路平時(shí)速度Si1，運(yùn)用公式 （3）計(jì)算出戰(zhàn)時(shí)運(yùn)油車在路段i的通行時(shí)間Ti，輸入以Ti為權(quán)的帶權(quán)鄰接矩陣w=［w（ vi, vj）］：

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

③重復(fù)步驟②，直到所有頂點(diǎn)都在S中為止。

3 模型算例

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

圖2 抽象路網(wǎng)道路編號(hào)圖

運(yùn)用公式 （1）、（2）和 （3）求出戰(zhàn)時(shí)運(yùn)油車在編號(hào)為1至22的道路上的行駛時(shí)間分別為：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；單位為小時(shí)。將得到的時(shí)間作為抽象路網(wǎng)的邊權(quán)，作為鄰接矩陣，并用matlab編程實(shí)現(xiàn)得到結(jié)果如下：

即最短路路徑為從點(diǎn)V1→點(diǎn)V2→點(diǎn)V3→點(diǎn)V7→點(diǎn)V10→點(diǎn)V9→點(diǎn)V11；最短路路徑值為2.45小時(shí)，約為兩個(gè)半小時(shí)。

4 結(jié) 論

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

[1]王海英,等.圖論算法及其MATLAB實(shí)現(xiàn)[M].北京：北京航空大學(xué)出版社，2010.

[2]陳子俠,等.基于GIS物流配送線路優(yōu)化與仿真[M].北京：經(jīng)濟(jì)科學(xué)出版社，2007.

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

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

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

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

[7]邊文質(zhì).航炮射擊彈著點(diǎn)的分布特性研究及試驗(yàn)規(guī)范的討論[J].西安工業(yè)大學(xué)學(xué)報(bào)，1983(2)：33-47.