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

曾慶福，王孟平

(1.蘇交科集團(tuán)(江蘇)安全科學(xué)研究院有限公司； 2.中國(guó)石化揚(yáng)子石油化工有限公司，江蘇 南京　211100)

0　引言

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

1　經(jīng)典Dijkstra算法的基本思想及數(shù)學(xué)模型

1.1基本思想

Dijkstra算法的基本思想是從某一點(diǎn)(vs)開(kāi)始，依次向外探尋最短路徑。此過(guò)程中，對(duì)于每一個(gè)點(diǎn)，都要記下一個(gè)相應(yīng)的數(shù)(即該點(diǎn)的標(biāo)號(hào))，若此數(shù)表示從起點(diǎn)vs到該點(diǎn)的最短路徑的權(quán)值，則用P標(biāo)號(hào)，反之表示從起點(diǎn)vs到該點(diǎn)的最短路徑的權(quán)值上界，即用T標(biāo)號(hào)，算法的每一步就是修改T標(biāo)號(hào)的點(diǎn)為P標(biāo)號(hào)的點(diǎn)，使賦權(quán)有向圖D中的點(diǎn)全部轉(zhuǎn)化為P標(biāo)號(hào)的點(diǎn)，至多經(jīng)過(guò)p-1步，方可求出從起點(diǎn)vs到終點(diǎn)的最短路徑。

1.2數(shù)學(xué)模型

Dijkstra算法的數(shù)學(xué)模型為：給定賦權(quán)有向圖D=(V,A)。令Si表示P標(biāo)號(hào)節(jié)點(diǎn)集合；P(vs)表示到節(jié)點(diǎn)vs的最短路徑；λ(vs)表示到節(jié)點(diǎn)vs的最短路徑上前一個(gè)點(diǎn)。初始化：i=0，S0={vs}；P(vs)=0；λ(vs)=0；T(v)=+∝，v?Si。

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

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

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

④若V=S，表明vk到所有節(jié)點(diǎn)最短路徑已確定，則算法結(jié)束；否則轉(zhuǎn)入②繼續(xù)確定其他節(jié)點(diǎn)最短路徑。

2　影響消防覆蓋區(qū)域內(nèi)最佳路線選擇的因素

2.1外部因素

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

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

表2　路質(zhì)因素b和路況因素a的取值范圍

2.2內(nèi)部因素

影響消防救援最佳路線選擇的內(nèi)部因素，主要考慮消防人員和消防車輛兩個(gè)方面。而把消防人員作為分析對(duì)象，主要考慮到消防人員對(duì)火災(zāi)現(xiàn)場(chǎng)具體地理位置的熟悉程度，能否迅速、準(zhǔn)確地到達(dá)火災(zāi)現(xiàn)場(chǎng)。再者消防站接到消防力量調(diào)度中心的火警通知，出警的迅速度以及消防車輛駕駛員的駕駛特性和道路熟悉度等都影響消防車輛駕駛?cè)藛T選擇最佳路線通往火災(zāi)現(xiàn)場(chǎng)。另外消防車輛上的設(shè)備安裝，特別是導(dǎo)航設(shè)備和通信設(shè)備是否安裝且保持良好，都會(huì)影響消防救援最佳路線的選擇和消防車輛行駛時(shí)間的控制。

3　消防力量覆蓋區(qū)域內(nèi)最佳救援路線選擇

3.1繪制公路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

為了研究消防力量覆蓋區(qū)域內(nèi)的最佳救援路線，以阜新市海州區(qū)消防力量覆蓋區(qū)域內(nèi)局部交通網(wǎng)絡(luò)圖為研究對(duì)象，利用GIS和Earth-map技術(shù)實(shí)現(xiàn)該區(qū)道路交通網(wǎng)絡(luò)的可視化和地理位置信息獲取[8-10]，并繪制出由點(diǎn)和邊組成的公路網(wǎng)絡(luò)靜態(tài)拓?fù)浣Y(jié)構(gòu)[11]，如圖1所示。圖中節(jié)點(diǎn)v1為消防站所在地，設(shè)定節(jié)點(diǎn)v24為火災(zāi)事故現(xiàn)場(chǎng)。

圖1　網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

3.2Dijkstra算法的MATLAB實(shí)現(xiàn)

根據(jù)上文繪制的公路網(wǎng)絡(luò)靜態(tài)拓?fù)浣Y(jié)構(gòu)關(guān)系以及圖中所標(biāo)的道路實(shí)際長(zhǎng)度，運(yùn)用MATLAB編程軟件來(lái)實(shí)現(xiàn)Dijkstra最短路徑算法。由軟件可求得，消防站到消防力量覆蓋區(qū)域內(nèi)各節(jié)點(diǎn)的最短距離及路徑，如表3所示。表3中雖未逐一列出消防站到任意一點(diǎn)的最短距離和路徑，但表中所列舉的最短路徑中已包含網(wǎng)絡(luò)拓?fù)潢P(guān)系中的所有節(jié)點(diǎn)，故消防站到其余節(jié)點(diǎn)的最短路徑無(wú)需再一一列舉。

表3　消防站到消防力量覆蓋區(qū)域內(nèi)任意一點(diǎn)的最短距離及路徑

3.3最佳救援路線選擇

3.3.1時(shí)間修正系數(shù)

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

前文已分析消防力量覆蓋區(qū)域內(nèi)影響消防車輛行駛的各種不確定因素，而在這些因素的影響下，消防車輛的行駛速度隨時(shí)間不斷變化，因此不能僅僅取道路交通網(wǎng)絡(luò)中，任意相鄰兩節(jié)點(diǎn)間實(shí)際道路長(zhǎng)度與速度的比值來(lái)確定消防車輛行駛時(shí)間，而是考慮各種影響因素將道路實(shí)際長(zhǎng)度轉(zhuǎn)化為道路計(jì)算長(zhǎng)度，利用平均速度進(jìn)行行駛時(shí)間計(jì)算[12]，其道路計(jì)算長(zhǎng)度表達(dá)式為：

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

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

(2)

故消防車輛行駛時(shí)間為：

=Kl/v0

(3)

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

(4)

式中，v0表示消防車輛在城鎮(zhèn)道路上行駛的最大速度，一般取50 km·h-1；a1為道路坡度影響系數(shù)，當(dāng)?shù)缆菲露菾>0時(shí)a1>1，當(dāng)J=0時(shí)a1=1，當(dāng)J<0時(shí)01；K為時(shí)間修正系數(shù)；L為道路計(jì)算長(zhǎng)度；l為道路實(shí)際長(zhǎng)度。

3.3.2消防車輛到達(dá)消防力量覆蓋區(qū)域內(nèi)各點(diǎn)的行駛時(shí)間

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

表4　消防車輛行駛時(shí)間、道路計(jì)算長(zhǎng)度和時(shí)間修正系數(shù)

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

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

圖2　最佳救援路線

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

由表5可知，在上述嚴(yán)峻的外部因素影響下，同樣由消防站到火災(zāi)現(xiàn)場(chǎng)這段距離，消防車輛的行駛時(shí)間明顯增加。

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

圖3　行駛時(shí)間與時(shí)間修正系數(shù)

4　結(jié)論

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

4.2結(jié)合阜新市海州區(qū)局部消防力量覆蓋區(qū)域內(nèi)某點(diǎn)火災(zāi)時(shí)的消防車輛行駛路線為例進(jìn)行分析，可知無(wú)論外部環(huán)境條件良好還是惡劣，上述算法實(shí)現(xiàn)的消防力量覆蓋區(qū)域內(nèi)最佳路徑上消防車輛行駛時(shí)間，皆符合我國(guó)《城鎮(zhèn)消防站布局技術(shù)裝備配備標(biāo)準(zhǔn)》規(guī)定的行車到場(chǎng)4 min的要求，能夠及時(shí)進(jìn)行火災(zāi)撲救。但是惡劣環(huán)境條件下同樣的行程所需行車時(shí)間較長(zhǎng)，因此消防力量覆蓋區(qū)域內(nèi)最佳路徑的研究對(duì)消防救援工作意義重大。