改進(jìn)最短路方法在軍用油料運(yùn)輸中的應(yīng)用

【后勤保障與裝備管理】

改進(jìn)最短路方法在軍用油料運(yùn)輸中的應(yīng)用

蘇濤，郝夢媛

(1.海軍航空工程學(xué)院 控制工程系,山東 煙臺264001；

2.煙臺大學(xué) 信息與計算科學(xué),山東 煙臺264000)

摘要：針對油料運(yùn)輸面臨的風(fēng)險因素很多，事故損失較為嚴(yán)重，安全問題突出的問題。選擇合適的運(yùn)輸路徑是提高油料運(yùn)輸安全的重要途徑。用改進(jìn)的最短路方法求解最安全路線的問題，事故風(fēng)險最小，確保了油料運(yùn)輸?shù)陌踩?/p>

關(guān)鍵詞：油料運(yùn)輸；最短路；安全路線

收稿日期：2014-07-29

作者簡介：蘇濤(1979—)，男，碩士，講師，主要從事軍事物流信息化研究。

doi:10.11809/scbgxb2015.01.022

中圖分類號：O221.3

文章編號：1006-0707(2015)01-0078-03

本文引用格式：蘇濤，郝夢媛.改進(jìn)最短路方法在軍用油料運(yùn)輸中的應(yīng)用[J].四川兵工學(xué)報，2015(1):78-80.

Citationformat:SUTao,HAOMeng-yuan.ApplicationofImprovedShortestPathMethodinMilitaryOilTransportation[J].JournalofSichuanOrdnance,2015(1):78-80.

ApplicationofImprovedShortestPathMethodin

MilitaryOilTransportation

SUTao1, HAO Meng-yuan2

(1.DepartmentofControlEngineering,NavalAeronauticalandAstronauticalUniversity,Yantai264001,China;

2.DepartmentofInformationandComputationalScience,YantaiUniversity,Yantai264000,China)

Abstract:There are many risk factors in oil transportation, such as facing more serious loss, accident, and safety problem. Choosing a right transportation route is an important way to improve the transportation safety. We got the maximum security route with the improved shortest path method to ensure the security of oil transportation.

Keywords：oiltransportation;shortestpathmethod;saferoute

作為一類危險品，軍用油料的運(yùn)輸不同于一般軍用物資運(yùn)輸[1]。由于其自身的理化性能，軍用油料在運(yùn)輸過程中很容易發(fā)生泄漏、著火、爆炸等災(zāi)害事故，造成油料大量損失，產(chǎn)生極為嚴(yán)重的后果，因此對運(yùn)輸?shù)陌踩筝^高[2]。相較于普通物資運(yùn)輸路徑選擇時更為注重對時間最少、路徑最短等目標(biāo)考慮，軍用油料在選擇運(yùn)輸路徑時，更注重總的事故風(fēng)險最小，防止油料運(yùn)輸損失，確保油料數(shù)量安全[3]。

最短路問題優(yōu)化即在一個連通網(wǎng)絡(luò)中，求從某一指定的節(jié)點(diǎn)(始點(diǎn))到另一個指定的節(jié)點(diǎn)(終點(diǎn))的一條路，使其路的長度最短[4]。用最短路問題解法求解最安全路線，則要求一條安全通過概率最高的道路，這時需要對問題做一些數(shù)學(xué)處理，即改進(jìn)的最短路解法[5]。

1最短路算法

求解最短路的算法較多，如狄克斯拉(Dijkstra)算法、福勞德(Floyd)算法、逐次逼近算法等，下面給出常用的狄克斯拉算法[6]。

狄克斯拉算法的基本思想基于如下事實：若路P=(vs,v1,v2,…,vi,…,vn,vt)是vs到vt的最短路，則路P=(vs,v1,v2,…,vi)是vs到vi的最短路[7]。

狄克斯拉算法是一種標(biāo)號法，它的基本思路是從起點(diǎn)vs出發(fā)，逐步向外尋找最短路。在尋找的過程中，給每一個頂點(diǎn)vj進(jìn)行標(biāo)號(λj,lj)[8]。其中，λj表示獲得此標(biāo)號的前一個頂點(diǎn)的下標(biāo)，lj表示從起點(diǎn)vs到該點(diǎn)vj的最短路的權(quán)(稱為固定標(biāo)號，記為P標(biāo)號)或表示從起點(diǎn)vs到該點(diǎn)vj的最短路的權(quán)的上界(稱為臨時標(biāo)號，記為T標(biāo)號)[9]。

算法開始時除vs外對所有頂點(diǎn)進(jìn)行T標(biāo)號，算法每進(jìn)行一步都把一個頂點(diǎn)的T標(biāo)號改為P標(biāo)號，當(dāng)終點(diǎn)vt得到P標(biāo)號后，計算過程停止[10]。Si表示在第i步已具有P標(biāo)號點(diǎn)的集合。若圖中有n個頂點(diǎn)，則最多進(jìn)行(n-1)次標(biāo)號就求得從vs到vt的最短路。再根據(jù)每個點(diǎn)標(biāo)號的第一個數(shù)λj反向追蹤找出最短路徑，計算步驟如下[11]。

2) 若Si=V，則算法終止，此時對任vj∈Si,lj=P(vj)；否則轉(zhuǎn)下一步[11]。

2改進(jìn)的最短路算法

當(dāng)把指標(biāo)參數(shù)看成是通過每段道路的成功概率時，則可用最短路問題解法求解選擇最安全路線的問題。不過，這時需要對問題做一些數(shù)學(xué)處理。

為說明這點(diǎn)，設(shè)vi、vj表示任一條道路兩端的頂點(diǎn)，從vi到vj的安全通過概率為pij。由于一條路線是多條道路的串接，由概率論知，一條路線的安全通過概率應(yīng)等于組成該路線的各條道路安全通過概率的乘積。例如，若把v1→v4→v5v6這條路線記為π，則有

P(π)=p14p45p56

(1)

應(yīng)用最短路問題解決，需要使沿路線的指標(biāo)參數(shù)等于各組成道路指標(biāo)參數(shù)的和。對式(1)兩邊取對數(shù)并乘以負(fù)號，得

-lgP(π)=-lgp14-lgp45-lgp56

(2)

由對數(shù)函數(shù)特性知，使P(π)最大，等價于-lgP(π)最小，也就是使式(2)右邊諸項和最小。所以，如果以-lgpij作為每條道路的指標(biāo)參數(shù)，那就可用最短路問題解法求解了。

3實例求解

某航材油料的運(yùn)輸路線如圖1所示，在圖1中標(biāo)示的各條道路安全通過概率下，用改進(jìn)的最短路方法求v1到v6的最安全路線。

圖1　運(yùn)輸路線

2) 考察與v1相鄰的點(diǎn)v2、v4。因(v1,v2)∈A,v2?S0,故把v2的臨時標(biāo)號修改為

同理得

v2、v4的標(biāo)號分別為(1,0)、(1,-lg0.95)，其余點(diǎn)的標(biāo)號不變。

i=1:

3) v2為剛獲得P標(biāo)號的點(diǎn)?？疾榕cv2相鄰的點(diǎn)v3、v4。因為(v2,v3)∈A,v3?S1，故把v3的臨時標(biāo)號修改為

同理得

v3、v4的標(biāo)號分別為(2,-lg0.9),(2,0)，其余點(diǎn)的標(biāo)號不變。

i=2:

4) v4為剛獲得P標(biāo)號的點(diǎn)?？疾榕cv4相鄰的點(diǎn)v3、v5。因為(v4,v3)∈A,v3?S2,故把v3的臨時標(biāo)號修改為

同理得

v3、v5的標(biāo)號分別為(4,-lg0.9),(4,-lg0.95)，其余點(diǎn)的標(biāo)號不變。

i=3:

5) v5為剛獲得P標(biāo)號的點(diǎn)?？疾榕cv5相鄰的點(diǎn)v3、v6。因為(v5,v3)∈A,v3?S3，故把v3的臨時標(biāo)號修改為

同理得

v3、v6的標(biāo)號分別為(5,-lg0.9),(5,-lg0.76)。

i=4:

6) v3為剛獲得P標(biāo)號的點(diǎn)。v6與v3相鄰，因為(v3,v6)∈A,v6?S4，故把v6的臨時標(biāo)號修改為

i=5:

7) v6為剛獲得P標(biāo)號的點(diǎn)。因沒有與v6相鄰的點(diǎn)，算法終止。這樣就得到了最優(yōu)解，根據(jù)終點(diǎn)v6的標(biāo)號可知(5,-lg0.76) 從v1到v6的距離是-lg0.76，其最短路徑中v6的前面一點(diǎn)是v5，從v5的標(biāo)號(4,-lg0.95)可知v5的前面一點(diǎn)是v4，從v4的標(biāo)號(2,0)可知v4的前面一點(diǎn)是v2，從v2的標(biāo)號(1,0)可知v2的前面一點(diǎn)是v1，即此最短路徑為v1→v2→v4→v5→v6，其安全通過的概率為P(π)=1.0×1.0×0.95×0.80=0.76。

4結(jié)束語

改進(jìn)的最短路算法巧妙地解決了求解最安全路線的問題，最大程度地保障了航材運(yùn)輸?shù)陌踩Ｔ撍惴ú粌H可以用來解決軍用油料運(yùn)輸路線問題，對于其他領(lǐng)域的危險品運(yùn)輸也同樣適用，且有很強(qiáng)的實用性。

參考文獻(xiàn)：

[1]王鐵寧.裝備管理信息系統(tǒng)原理與應(yīng)用[M].北京：國防工業(yè)出版社,2013.

[2]郭文暉.軍事裝備管理創(chuàng)新[M].北京：國防工業(yè)出版社,2010.

[3]趙經(jīng)成，祝華遠(yuǎn)，王文秀.航空裝備技術(shù)保障運(yùn)籌分析[M].北京：國防工業(yè)出版社，2010.

[4]張麗葉.裝備更新經(jīng)濟(jì)性分析[J].裝備學(xué)院學(xué)報,2012,23(5): 36-39.

[5]WayneL.Winston.Operationsresearch[M].北京：清華大學(xué)出版社，2011.

[6]李維錚，甘應(yīng)愛，田豐.運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，2005.

[7]傅清祥，王曉東.算法與數(shù)據(jù)結(jié)構(gòu)[M].北京：電子工業(yè)出版社，1998.

[8]DreyfusSE,LawAM.TheartandtheoryofDynamicProgramming[M].AcademicPress, 1977.

[9]馬仲蕃，魏權(quán)齡，賴炎連.數(shù)學(xué)規(guī)劃講義[M].北京：中國人民大學(xué)出版社，1981.

[10]俞玉森.數(shù)學(xué)規(guī)劃的原理和方法[M].武漢：華中工學(xué)院出版社，1985.

[11]王曉迪.高等學(xué)校教育裝備管理決策支持研究[D]. 哈爾濱:哈爾濱工程大學(xué),2011.

[12]沈貴林.基于動態(tài)規(guī)劃的物流裝備更新決策方法[J].物流科技，2006,29(12): 74-76.

[13]楊媛媛.裝備更新決策綜合方法[J].裝備指揮技術(shù)學(xué)院學(xué)報，2002,13(4): 25-28.

[14]陳慶華.裝備運(yùn)籌學(xué)[M].北京：國防工業(yè)出版社，2005.

(責(zé)任編輯周江川)