基于MATLAB編程Dijkstra算法的消防救援最佳路線研究

曾慶福，王孟平

(1.蘇交科集團(江蘇)安全科學研究院有限公司； 2.中國石化揚子石油化工有限公司，江蘇 南京　211100)

0　引言

近年來城市火災問題成為困擾社會公共安全的一大難題，特別是人員密集場所，如大型商場、游樂場等，做好公共安全風險管理[1]，配備相應的消防設備、設施及專業安全人員，一旦發生火災，爭取在最短的時間內、使用最有效的措施和最小的能耗來撲救火災，以減少人員傷亡和財產損失。經過對大量火災案例的調查和研究，不難發現，火災發生后，能否及時進行火災撲救也是造成人員傷亡、財產損失和環境污染的重要原因，因此研究消防力量覆蓋區域內的最佳救援路線，建立應急預案體系，使專業消防人員第一時間到達火災現場就成了當務之急[2]。雖然前人已做了大量關于火災和消防的研究，也取得很大成就，但針對火災后專業消防隊如何以最短時間抵達火災現場，即消防站到火災現場最佳路線問題研究較少。而最佳救援路線的選擇又避免不了最短路徑的計算，常用最短路徑算法有：Dijkstra算法[3-4]、A*算法[5]、K-均值算法[6]等。本文運用Dijkstra算法，并綜合考慮影響消防救援的各種不確定因素，結合GIS和Earth-map技術，實現消防救援最佳路線的選擇。

1　經典Dijkstra算法的基本思想及數學模型

1.1基本思想

Dijkstra算法的基本思想是從某一點(vs)開始，依次向外探尋最短路徑。此過程中，對于每一個點，都要記下一個相應的數(即該點的標號)，若此數表示從起點vs到該點的最短路徑的權值，則用P標號，反之表示從起點vs到該點的最短路徑的權值上界，即用T標號，算法的每一步就是修改T標號的點為P標號的點，使賦權有向圖D中的點全部轉化為P標號的點，至多經過p-1步，方可求出從起點vs到終點的最短路徑。

1.2數學模型

Dijkstra算法的數學模型為：給定賦權有向圖D=(V,A)。令Si表示P標號節點集合；P(vs)表示到節點vs的最短路徑；λ(vs)表示到節點vs的最短路徑上前一個點。初始化：i=0，S0={vs}；P(vs)=0；λ(vs)=0；T(v)=+∝，v?Si。

①若Si=V，即v∈Si，v∈V，則算法終止；否則轉入②。

②對于Akj=(vk,vj)∈A，vj∈Si；若T(vj)>P(vk)+tkj，則令T(vj)=P(vk)+tkj；否則轉入③。

③P(vji)=T(vji)=min{T(vj)}，Si+1=Si∪{vji}。

④若V=S，表明vk到所有節點最短路徑已確定，則算法結束；否則轉入②繼續確定其他節點最短路徑。

2　影響消防覆蓋區域內最佳路線選擇的因素

2.1外部因素

關于消防力量覆蓋區域內，影響消防救援最佳路線選擇的外部因素分析，主要是考慮影響消防車輛由消防站到火災現場過程中，存在的各種不確定因素，諸如天氣、路質、路況等。而這些外部因素的不確定性，又進一步加劇消防車輛的行駛難度。一般情況下，道路周邊環境不同，車流、人流量也不同，如居民小區、學校區域及城市主干道的車流、人流量就比較大，車速緩慢；而早晚班點、上下學時段，車流、人流量大，道路擁堵，影響車速；特別是霧霾天氣和雨雪天氣，路面濕滑，摩擦性小，能見度低，易發生事故，車輛行駛速度慢，所以嚴重影響消防車輛行駛，延長行駛時間。文中用m,b和a來表示外部因素天氣、路質和路況[7]，其取值范圍如表1和表2所示[6]。

表1　天氣因素m的取值范圍

表2　路質因素b和路況因素a的取值范圍

2.2內部因素

影響消防救援最佳路線選擇的內部因素，主要考慮消防人員和消防車輛兩個方面。而把消防人員作為分析對象，主要考慮到消防人員對火災現場具體地理位置的熟悉程度，能否迅速、準確地到達火災現場。再者消防站接到消防力量調度中心的火警通知，出警的迅速度以及消防車輛駕駛員的駕駛特性和道路熟悉度等都影響消防車輛駕駛人員選擇最佳路線通往火災現場。另外消防車輛上的設備安裝，特別是導航設備和通信設備是否安裝且保持良好，都會影響消防救援最佳路線的選擇和消防車輛行駛時間的控制。

3　消防力量覆蓋區域內最佳救援路線選擇

3.1繪制公路網絡拓撲結構

為了研究消防力量覆蓋區域內的最佳救援路線，以阜新市海州區消防力量覆蓋區域內局部交通網絡圖為研究對象，利用GIS和Earth-map技術實現該區道路交通網絡的可視化和地理位置信息獲取[8-10]，并繪制出由點和邊組成的公路網絡靜態拓撲結構[11]，如圖1所示。圖中節點v1為消防站所在地，設定節點v24為火災事故現場。

圖1　網絡拓撲結構

3.2Dijkstra算法的MATLAB實現

根據上文繪制的公路網絡靜態拓撲結構關系以及圖中所標的道路實際長度，運用MATLAB編程軟件來實現Dijkstra最短路徑算法。由軟件可求得，消防站到消防力量覆蓋區域內各節點的最短距離及路徑，如表3所示。表3中雖未逐一列出消防站到任意一點的最短距離和路徑，但表中所列舉的最短路徑中已包含網絡拓撲關系中的所有節點，故消防站到其余節點的最短路徑無需再一一列舉。

表3　消防站到消防力量覆蓋區域內任意一點的最短距離及路徑

3.3最佳救援路線選擇

3.3.1時間修正系數

時間修正系數是指在考慮影響消防車輛行駛的各種不確定因素情況下，消防車輛行駛時間與消防車輛在理想情況下行駛時間的比值，用K值表示。

前文已分析消防力量覆蓋區域內影響消防車輛行駛的各種不確定因素，而在這些因素的影響下，消防車輛的行駛速度隨時間不斷變化，因此不能僅僅取道路交通網絡中，任意相鄰兩節點間實際道路長度與速度的比值來確定消防車輛行駛時間，而是考慮各種影響因素將道路實際長度轉化為道路計算長度，利用平均速度進行行駛時間計算[12]，其道路計算長度表達式為：

L=l*[1+b(1+m)+a](1)

消防車輛行駛的平均速度表達式為：

(2)

故消防車輛行駛時間為：

=Kl/v0

(3)

K=[1+b(1+m)+a]a1a2a3

(4)

式中，v0表示消防車輛在城鎮道路上行駛的最大速度，一般取50 km·h-1；a1為道路坡度影響系數，當道路坡度J>0時a1>1，當J=0時a1=1，當J<0時01；K為時間修正系數；L為道路計算長度；l為道路實際長度。

3.3.2消防車輛到達消防力量覆蓋區域內各點的行駛時間

根據《城鎮消防站布局與技術裝備配備標準》和《城市消防站建設標準》規定，消防車輛的平均行駛速度取30～36 km·h-1；而市內道路無明顯坡路，故坡度影響系數a1=1；且路面多為瀝青路面或水泥路面，多數情況路面平整，故路面影響系數a3=1；由于阜新市是小型城市，人口密集且街道狹窄，道路曲折(曲度系數一般為1.3～1.5)，故車輛行駛速度慢，曲度系數可取最大值a2=1.5；上述計算在天氣晴朗、能見度良好、路況正常的城市道路上進行，即m=a=0和b=0.2，則其消防車輛行駛時間、道路計算長度和時間修正系數如表4所示。

表4　消防車輛行駛時間、道路計算長度和時間修正系數

由表4可知，在天氣晴朗、能見度良好和路況正常的城市道路條件下，消防站到火災現場的最佳救援路線選擇，可以用消防車輛的行駛時間來表示，即消防車輛在消防力量覆蓋區域內各點到消防站的最短路徑上行駛，所需用的時間來表示。而消防救援講究把握有利戰機，需要嚴格控制消防車輛行駛時間，因此消防車輛行駛時間最短的路線，即為消防救援最佳路線。故消防站(v1)到火災現場(v24)的最短距離為828 m，消防車輛行駛時間為107.308 8 s，最佳救援路線為v1,v2,v6,v7,v14,v18,v23,v24，具體如圖2所示。

下文將在上述基礎上討論幾種惡劣氣候條件，如大霧、中霧和大雨雪、中雨雪等對道路交通的影響，分析比較節點v1到節點v24間最佳救援路線上消防車輛行駛時間。其中兩節點間的道路實際長度一致(l=828 m)，但考慮外部因素及其取值不同，故得到的時間修正系數K值也不同，并且不同的外部因素影響下消防車輛的行駛速度不盡相同，從而使得道路計算長度和消防車輛行駛時間發生變化，而《道路交通安全法實施條例》規定駕駛機動車輛遇到霧、雨、沙塵、冰雹等天氣，能見度在50 m以內時，最高行駛速度不得超過30 km·h-1，具體計算結果見表5所示。

圖2　最佳救援路線

表5　幾種特殊的外部因素對消防車輛行駛的影響

由表5可知，在上述嚴峻的外部因素影響下，同樣由消防站到火災現場這段距離，消防車輛的行駛時間明顯增加。

為了清楚反映消防車輛的行駛時間與外界環境間的密切關系，使用origin繪圖軟件，繪制行駛時間和時間修正系數K值的關系，如圖3所示。圖3中反映了時間修正系數隨著外界環境條件的不同而改變，并且行駛時間隨著時間修正系數的增大而不斷延長，不利于消防人員第一時間到達火災現場實施火災撲救。

圖3　行駛時間與時間修正系數

4　結論

4.1采用經典的Dijkstra算法，運用MATLAB編程軟件實現消防力量覆蓋區域內消防站到火災現場間的最短路徑。綜合分析各種影響因素將實際道路長度轉化為道路計算長度，使用平均速度，引進時間修正系數(K)，使消防車輛行駛時間的求解精確度提高，而行車時間最短的路徑為最佳路徑，更有利于消防人員到達火災現場撲救火災。

4.2結合阜新市海州區局部消防力量覆蓋區域內某點火災時的消防車輛行駛路線為例進行分析，可知無論外部環境條件良好還是惡劣，上述算法實現的消防力量覆蓋區域內最佳路徑上消防車輛行駛時間，皆符合我國《城鎮消防站布局技術裝備配備標準》規定的行車到場4 min的要求，能夠及時進行火災撲救。但是惡劣環境條件下同樣的行程所需行車時間較長，因此消防力量覆蓋區域內最佳路徑的研究對消防救援工作意義重大。