劉　蕊　李　峰

摘要：文章從我國的火災(zāi)形勢出發(fā)，以優(yōu)化城市道路交通網(wǎng)中路段的權(quán)值為出發(fā)點，結(jié)合消防工作實際情況的特點，介紹了消防力量調(diào)集路徑最優(yōu)指標(biāo)的選取方案，著重分析了Dijkstra最短路徑算法的基本原理，并給出了算法優(yōu)化方案。優(yōu)化后的算法能夠有效降低Dijkstra算法的時間復(fù)雜性，提高運行效率。實例應(yīng)用表明，該方法兼具靈活性和實用性，能夠滿足消防滅火救援工作中實現(xiàn)消防力量優(yōu)化調(diào)集的要求。

關(guān)鍵字：Dijkstra算法；最短路徑；力量調(diào)集

中圖分類號：TP311.1文獻(xiàn)標(biāo)識碼：A文章編號：1009-2374（2009）02-00734-02

火災(zāi)是城市中較為頻繁的災(zāi)害，其損失經(jīng)常是巨大的。如果在火災(zāi)發(fā)生后的短暫時間內(nèi)，消防力量能有效地控制火勢，則火災(zāi)損失會大大減少。火災(zāi)的經(jīng)濟(jì)損失有很大的波動性，它與火災(zāi)的持續(xù)時間、燃燒物的類別、過火面積等因素有關(guān)。但是，對于一個具體的建筑物子系統(tǒng)，火災(zāi)損失的變化主要與火災(zāi)持續(xù)時間有關(guān)。消防隊必須在15分鐘內(nèi)達(dá)到火場出水，這是基于我國通訊、道路和消防裝備的實際情況以及對大量的火災(zāi)案例的分析得出的，這樣才能有效地?fù)渚然馂?zāi)并防止火勢繼續(xù)蔓延。但在實際工作中往往由于消防資源調(diào)度不當(dāng)?shù)雀鞣N遲滯因素使得消防人員不能盡早趕到火災(zāi)事故現(xiàn)場，喪失了對早期火災(zāi)撲救的良好時機(jī)。為將損失降低到最低程度，消防部門面臨的問題是如何迅速調(diào)動消防救援力量到達(dá)事故地點及時撲滅火災(zāi)，這就涉及到調(diào)集路徑選取的問題。地理信息系統(tǒng)中的DIJKSTRA最短路徑算法可以很好的解決這個問題。

一、消防力量調(diào)集路徑最優(yōu)指標(biāo)的選取

Dijkstra算法在通用路徑選擇算法中，對最短路徑的衡量標(biāo)準(zhǔn)是通過計算路徑的邊權(quán)來決定的。如何確定邊權(quán)，使設(shè)定的邊權(quán)更符合系統(tǒng)實際的需要，是建立算法參數(shù)標(biāo)準(zhǔn)的重要因素，其值設(shè)定的好壞，直接決定了算法的適用性。在實際城市交通網(wǎng)絡(luò)中，道路長度最短的路徑不一定是耗時最短的。如何設(shè)定最優(yōu)路徑的標(biāo)準(zhǔn)也是設(shè)計權(quán)值的重要前提。影響消防車輛到達(dá)火災(zāi)事故現(xiàn)場時間的因素很多，如車流量、車道數(shù)、時間段、路面狀況等等。將救援時間最短作為最優(yōu)目標(biāo)，相應(yīng)的道路權(quán)重如何標(biāo)定是一個非常值得研究的問題。一般而言，確定以出行時間度量的道路權(quán)重建議采用以下方案：

引進(jìn)表征路段行程時間與交通流量之間關(guān)系的路阻函數(shù)模型以及交叉口延誤模型，計算當(dāng)前時段的路段行程時間及交叉口延誤，以此確定道路權(quán)重。這樣既考慮了交通流的特性，體現(xiàn)了實時因素，又在當(dāng)前基礎(chǔ)設(shè)施狀況允許的范圍內(nèi)。該方案較好地反映了現(xiàn)實情況，且技術(shù)上切實可行，綜合考慮了實用性與可行性。

因此，本文選取時間作為路徑權(quán)值的最優(yōu)指標(biāo)，并用路阻函數(shù)求出道路交通網(wǎng)中各路段的權(quán)值，在此基礎(chǔ)上利用DIJKSTRA最短路徑算法實現(xiàn)消防力量調(diào)集的最優(yōu)化。

二、Dijkstra最短路徑經(jīng)典算法及分析

（一）問題定義

我們討論的問題是城市消防單源點的最短路徑，即對于給定帶時間權(quán)的無向圖G、源點Vi和終點Vj，求得源Vi和終點Vj之間路徑中的最短路徑。

（二）Dijkstra 算法

我們設(shè)定一個輔助向量D[i]。D[i]表示當(dāng)前從源點V到每個終點Vi的最短路徑的時間長度。它的初始值為：如果V到Vi有直接相聯(lián)的路徑，則D[i]為這條路徑的時間權(quán)值。否則，設(shè)定D[i]=∞，設(shè)D[j]=min{ D[i]|Vi∈V }。顯然，D[j]為從V出發(fā)的一條最短路徑。下一條次短路徑的長度一定是：D[j] = min{ D[i]|Vi∈V-S }，其中S為已求得最短路徑的終點的集合。根據(jù)對以上求出的最短時間路徑序列的查詢，我們可得出兩地的最短時間路徑。

（三）Dijkstra算法優(yōu)化及分析

1．優(yōu)化Dijkstra算法的思路

根據(jù)以上對Dijkstra算法的分析，我們可以知道，當(dāng)n較大時，Dijkstra算法的運行時間急劇增加。如果能有效地減小n值，就能大大地減少運行時間，提高效率。基于以上考慮，為了有效地減小n值，我們把需要計算兩節(jié)點最佳時間路徑的公路網(wǎng)圖分成若干個子圖，對每個子圖分別采用Dijkstra算法進(jìn)行計算，再把每段計算的節(jié)點連接起來，就是我們需要的結(jié)果。在把一個圖劃分成若干個子時遵循以下原則：

（1）根據(jù)幾何中關(guān)于兩點間的時間距離最短的原理，我們用直線連接源點和終點，最佳路徑一般情況應(yīng)在這條直線附近。劃分子圖應(yīng)順著這條直線來進(jìn)行。

（2）每個子圖應(yīng)盡可能均勻，即每個子圖的節(jié)點數(shù)基本上接近。否則，本優(yōu)化算法效果不明顯。如果在劃分子圖時，每個子圖的節(jié)點數(shù)相差懸殊，則子圖查找效率低，造成優(yōu)化算法效果不明顯。

（3）劃分子圖盡可能使圖的邊接近連接源點和終點這條直線附近，以減少重復(fù)計算的次數(shù)，提高命中率。

2．優(yōu)化Dijkstra算法的描述

（1）依據(jù)以上原則，把一個公路網(wǎng)圖劃分成若干個子圖。

（2）劃分時，每個子圖的節(jié)點最接近連接源點和終點的直線。

（3）分別對每個子圖采用Dijkstra算法進(jìn)行計算。

（4）我們把相鄰子圖的源點和終點分別進(jìn)行核對。如果前一子圖的終點就是后一子圖的源點，那么我們連接這兩段，并且認(rèn)為這段就是最佳路徑中的一段；如果前一子圖的終點不是后一子圖的源點，那么我們修改前一子圖的終點，把它定義成后一子圖的源點，再對前一子圖采用Dijkstra算法進(jìn)行計算，同時，修改后一子圖的源點，把它定義成前一子圖的終點，再對后一子圖采用Dijkstra算法進(jìn)行計算，連接這兩段。根據(jù)計算結(jié)果，取這兩段中權(quán)值最小的一段，作為最佳路徑中的一段。

（5）重復(fù)以上步驟，直到找出連接源點和終點的最佳路徑。

采用以上方法找出的路徑不一定是最短路徑，但它是最接近或就是最短路徑。

三、結(jié)語

通過對消防力量調(diào)集最短路徑算法的研究，了解Dijkstra基本算法和優(yōu)化算法。同時，我們也注意到，優(yōu)化Dijkstra算法適應(yīng)等級較高的公路，對于等級較低的公路，若公路線型過于彎曲，可能效果不理想。

參考文獻(xiàn)

[1]黃偉東，萬義玲．公路網(wǎng)最佳路徑算法的研究[J]．南昌大學(xué)學(xué)報（工科版），2003，（3）．

[2]魏新宇．消防滅火救援最優(yōu)路徑算法研究[D]．西安科技大學(xué)，2006，（4）．

[3]李斌．基于GIS的城市消防信息系統(tǒng)[D]．貴州大學(xué)，2006，（5）．