【后勤保障與裝備管理】

改進最短路方法在軍用油料運輸中的應用

蘇濤，郝夢媛

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

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

摘要：針對油料運輸面臨的風險因素很多，事故損失較為嚴重，安全問題突出的問題。選擇合適的運輸路徑是提高油料運輸安全的重要途徑。用改進的最短路方法求解最安全路線的問題，事故風險最小，確保了油料運輸的安全。

關鍵詞：油料運輸；最短路；安全路線

收稿日期：2014-07-29

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

doi:10.11809/scbgxb2015.01.022

中圖分類號：O221.3

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

本文引用格式：蘇濤，郝夢媛.改進最短路方法在軍用油料運輸中的應用[J].四川兵工學報，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

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

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

1最短路算法

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

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

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

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

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

2改進的最短路算法

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

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

P(π)=p14p45p56

(1)

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

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

(2)

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

3實例求解

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

圖1　運輸路線

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

同理得

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

i=1:

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

同理得

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

i=2:

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

同理得

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

i=3:

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

同理得

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

i=4:

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

i=5:

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

4結束語

改進的最短路算法巧妙地解決了求解最安全路線的問題，最大程度地保障了航材運輸的安全。該算法不僅可以用來解決軍用油料運輸路線問題，對于其他領域的危險品運輸也同樣適用，且有很強的實用性。

參考文獻：

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

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

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

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

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

[6]李維錚，甘應愛，田豐.運籌學[M].北京：清華大學出版社，2005.

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

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

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

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

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

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

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

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

(責任編輯周江川)