●李超鵬

(太原市消防支隊(duì)，山西太原 030024)

隨著我國社會(huì)經(jīng)濟(jì)的快速發(fā)展，城市規(guī)模迅速擴(kuò)大，各類型火災(zāi)發(fā)生頻率逐漸增大，這直接威脅人民群眾的生命財(cái)產(chǎn)安全。消防救援作為社會(huì)的保障力量，能否及時(shí)到達(dá)火災(zāi)發(fā)生地點(diǎn)實(shí)施救援至關(guān)重要，因而救援路徑的選擇是關(guān)鍵。目前典型的消防救援路徑選擇算法是Dijkastra算法及其改進(jìn)算法［1－4］，這些算法適用于距離是衡量路線優(yōu)劣惟一標(biāo)準(zhǔn)的情況，這就要求路網(wǎng)暢通度好，道路規(guī)格較高及較少的交叉路口等［5］。但是在實(shí)際的救援工作中，路網(wǎng)中不同路段的暢通度，道路規(guī)格及交叉口數(shù)量差別很大，而且路網(wǎng)是動(dòng)態(tài)變化的，經(jīng)常會(huì)發(fā)生由于無法預(yù)測的因素延誤應(yīng)急救援力量到達(dá)被救援地點(diǎn)的時(shí)間，影響救援效果，造成不必要的人員傷亡或經(jīng)濟(jì)損失。本文提出了一種實(shí)時(shí)的分層分析算法計(jì)算最優(yōu)路徑。該方法不僅考慮了路網(wǎng)中不同路段的暢通度、道路規(guī)格及交叉路口數(shù)量等因素，同時(shí)還充分考慮路網(wǎng)狀態(tài)實(shí)時(shí)變化，使用局部規(guī)劃技術(shù)應(yīng)對(duì)突發(fā)事件，修正全局路徑，保證車輛行駛時(shí)間最短。實(shí)驗(yàn)結(jié)果表明，該算法可以作為應(yīng)急救援路徑選擇的依據(jù)，同時(shí)實(shí)際應(yīng)用證明該算法有效可靠。

1 基于分層分析算法的消防救援路徑規(guī)劃

現(xiàn)有典型的最短路徑算法是Dijkastra算法及其改進(jìn)算法，算法的基本思想是遍歷起點(diǎn)到終點(diǎn)的道路進(jìn)而選擇最短的路徑。然而實(shí)際情況并非如此，如應(yīng)急救援車的車重是否超過橋梁限重，應(yīng)急救援車的車高是否可以穿過高架橋，應(yīng)急車輛經(jīng)過的道路交叉口延誤是否交叉及應(yīng)急車輛通行路段是否進(jìn)行交通管制等等。所以不能只考慮道路長短。使用層次分析法可以將上述情況納入考慮，得出最優(yōu)應(yīng)急救援路徑。

1.1 層次分析法

人們在進(jìn)行社會(huì)的、經(jīng)濟(jì)的以及科學(xué)管理領(lǐng)域問題的系統(tǒng)分析中，面臨的常常是一個(gè)由相互關(guān)聯(lián)、相互制約的眾多因素構(gòu)成的復(fù)雜而往往缺少定量數(shù)據(jù)的系統(tǒng)。層次分析法為這類問題的決策和排序提供了一種新的、簡潔而實(shí)用的建模方法。用層次分析法建模，可分為三個(gè)步驟首先建立遞階層次結(jié)構(gòu)模型，其次構(gòu)造出各層次中的所有判斷矩陣，最后進(jìn)行一致性檢驗(yàn)。

1.2 消防應(yīng)急求援道路層次結(jié)構(gòu)模型

本文將消防求援車輛到達(dá)救援地點(diǎn)時(shí)間最短作為決策目標(biāo)，綜合考慮了道路規(guī)格、道路通行方向，道路行駛時(shí)間，交叉路口延誤時(shí)間作為影響決策因素，得出如下結(jié)構(gòu)模型見圖1。

1.3 構(gòu)造判斷矩陣

根據(jù)圖1層次結(jié)構(gòu)模型以及多位專家對(duì)指標(biāo)的評(píng)價(jià)意見，可得出影響道路權(quán)值因素的重要性排序，B1＞B2＞B3=B4，并構(gòu)造出各層次的判斷矩陣，然后采用和法計(jì)算得到權(quán)重。對(duì)于目標(biāo)O構(gòu)造的各影響力因素Bi的相對(duì)重要性判斷矩陣O－B見表1。同理構(gòu)造出判斷矩陣B－C的權(quán)重，排序見表2。

圖1 消防應(yīng)急求援道路層次結(jié)構(gòu)模型

表1 相對(duì)重要性判斷矩陣O－B

表2 相對(duì)重要性判斷矩陣B－C及特征向量

以上計(jì)算結(jié)果一致性檢驗(yàn)通過。上述結(jié)果表明，在所有影響應(yīng)急救援行動(dòng)到達(dá)被救援地點(diǎn)時(shí)間的因素中，道路限寬、限高、限重是需要首先考慮的因素，其次交通管制、道路通行方向以及交通流量等因素對(duì)救援車輛到達(dá)時(shí)間影響權(quán)重較大。這與實(shí)際情況相符，也從另一個(gè)角度驗(yàn)證了計(jì)算結(jié)果。

1.4 無綱量化屬性數(shù)據(jù)

由于道路屬性是從不同的角度來描述道路形態(tài)，因而各個(gè)道路屬性的單位不同，例如路段車速單位是km·h－1，路段長度單位是km，而左/右轉(zhuǎn)延誤單位是min，為便于將不同屬性數(shù)據(jù)統(tǒng)一進(jìn)行計(jì)算就是屬性數(shù)據(jù)的無綱量化。本文使用成本型屬性集的無綱量化標(biāo)準(zhǔn)函數(shù)進(jìn)行無綱量化，對(duì)于任一屬性pi∈U，其取值范圍為［mi，Mi］，則無綱量化后屬性 ri為:

如果道路屬性 C1，C2，…，C12 對(duì)應(yīng)的權(quán)值為 ω1，ω2，…，ω12，無綱量化后的對(duì)應(yīng)屬性為 r1，r2，…，r12，消防應(yīng)急求援時(shí)間T為:

1.5 基于分層分析法的最優(yōu)路徑

從前文利用層次分析法求得的路段權(quán)值分別賦予各個(gè)路段，因而分層分析法求得最優(yōu)路徑數(shù)學(xué)模型為，將路網(wǎng)定義為一個(gè)賦權(quán)圖G(V，E)，每一邊e(vi，vj)對(duì)應(yīng)權(quán)值表示為w(e)，設(shè)R是起點(diǎn)Vs到終點(diǎn)Vt所有路徑的集合，r為其中一條路徑，r∈R，路徑r的權(quán)為w(r)即w(r)=∑w(e)，目標(biāo)是求得一條起點(diǎn)Vs到終點(diǎn)Vt權(quán)最小的路徑r0，即w(r0)=minw(ri)?；诜謱臃治龇ǖ淖顑?yōu)路徑算法基本流程如下:(1)車輛由起始點(diǎn)S向目標(biāo)節(jié)點(diǎn)T行駛，定義集合S={Vs}，T={其余頂點(diǎn)}，w(Vs，Vi)＜ Vs，Vi＞ 弧上的權(quán)值。T中頂點(diǎn)對(duì)應(yīng)的權(quán)值w(Vs，Vi);(2)從T中選取一個(gè)其權(quán)值為最小的頂點(diǎn)Ti，且該頂點(diǎn)不在S中，將Ti加入S;(3)對(duì)其余T中頂點(diǎn)的權(quán)值進(jìn)行修改，若加進(jìn)W作中間頂點(diǎn)，從V0到Vi的權(quán)值變小，則修改此權(quán)值。重復(fù)步驟(2)、(3)，直到S中包含所有頂點(diǎn)為止。

2 基于分層分析算法的實(shí)時(shí)最優(yōu)消防應(yīng)急救援路徑路徑規(guī)劃

其中，x、y為橢圓任意點(diǎn)的坐標(biāo)，xS、yS、xT、yT分別為起點(diǎn)S、終點(diǎn)T的坐標(biāo)。a、b分別為橢圓長短軸。本文章橢圓的a、b值選取過程如下:(1)首先從太原市一中隊(duì)轄區(qū)電子地圖855個(gè)點(diǎn)中隨機(jī)選取30個(gè)點(diǎn)，放入集合A和B中，并計(jì)算其笛卡爾乘積C=A×B={(a，b)|(a∈A)∧(b∈B)};(2)集合C中含有900對(duì)點(diǎn)，求取集合C中900對(duì)點(diǎn)的直線距離與最短路徑比值放入集合R;(3)對(duì)集合R進(jìn)行統(tǒng)計(jì)分析得出特定系數(shù)，該系數(shù)需滿足95%置信水平，且其值不大于5。本算法選取集合R中元素的算術(shù)平均值滿足該條件。經(jīng)計(jì)算，集合R中元素的算術(shù)平均值該值為1.543;(4)按如下公式計(jì)算橢圓長袖2a，短軸 2b。

層次分析法是在給定路網(wǎng)結(jié)構(gòu)和交通流分布信息的情況下，綜合考慮道路規(guī)格、交通管制及交通流量等因素，將路網(wǎng)抽象為不同層，提供從起點(diǎn)到目的地的全局最優(yōu)/最短行駛路徑。但是路網(wǎng)狀態(tài)時(shí)實(shí)時(shí)動(dòng)態(tài)變化的［6］，例如突發(fā)的交通事故。該算法不能充分考慮路網(wǎng)狀態(tài)實(shí)時(shí)變化，難以應(yīng)對(duì)路網(wǎng)中的突發(fā)事件，因而在車輛出行的最短路徑中需要使用局部規(guī)劃技術(shù)應(yīng)對(duì)突發(fā)事件，修正全局路徑，保證救援車輛到達(dá)目的地行駛時(shí)間最短。

現(xiàn)有的局部規(guī)劃技術(shù)是通過限定搜索區(qū)域?qū)崿F(xiàn)的，典型的限定搜索區(qū)域方法包括圓形法［7］、橢圓法［8］、橢圓外切矩陣［9］、橢圓內(nèi)含矩陣［10］等。由于橢圓法被證明具有較高的可信度，同時(shí)橢圓區(qū)域大小依賴于統(tǒng)計(jì)經(jīng)驗(yàn)，由于每個(gè)消防基層中隊(duì)轄區(qū)內(nèi)道路數(shù)量有限，因而具有很強(qiáng)的可行性。綜上兩點(diǎn)本文選用橢圓作為限定搜索區(qū)域。假設(shè)出行的起點(diǎn)為S到目標(biāo)點(diǎn)為T，橢圓方程為:

橢圓限制算法給出的置信水平95%，表明在橢圓內(nèi)找不到全局最短路徑的可能行不大于5%，即使是剩下的5%不是全局最短路徑也至少是局部最短路徑，所以一般認(rèn)為這5%是完全可以忽略的。在獲得了限制搜索區(qū)域的基礎(chǔ)上。具體的算法流程如下。

2.1 算法基本流程

步驟1:車輛沿著層次分析法得出的全局規(guī)劃路徑R，由起始點(diǎn)S向目標(biāo)節(jié)點(diǎn)T行駛，直到如下中某種情況出現(xiàn):(1)到達(dá)目標(biāo)節(jié)點(diǎn)Ti停止搜索;(2)車輛到達(dá)節(jié)點(diǎn)i時(shí)，路段(i，j)出現(xiàn)障礙物(如突發(fā)事件、交通堵塞，該數(shù)據(jù)來源于交通指揮系統(tǒng))，轉(zhuǎn)自步驟2。

步驟2:重置該路段(i，j)權(quán)值Wi

步驟3:在橢圓區(qū)域內(nèi)(節(jié)點(diǎn)i作為新的起點(diǎn)S，目標(biāo)節(jié)點(diǎn)T不變)重新計(jì)算替代路徑。重新計(jì)算好的替代路徑與橢圓區(qū)域外的全局規(guī)劃路徑形成新的全局路徑。

步驟4:沿著新得到的路徑前進(jìn)，直到如下中某種情形出現(xiàn):(1)到達(dá)目標(biāo)節(jié)點(diǎn)Ti停止搜索;(2)車輛到達(dá)節(jié)點(diǎn)i時(shí)，路段(i，j)出現(xiàn)障礙物(如突發(fā)事件、交通堵塞)，轉(zhuǎn)自步驟2。

2.2 實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

實(shí)驗(yàn)過程中本文首先使用MapInfo建立太原市一中隊(duì)轄區(qū)的消防救援電子地圖，該電子地圖主要圖層有:重要道路圖層，一般道路圖層，小路圖層，消防中隊(duì)圖層，消防安全重點(diǎn)單位圖層，一般單位圖層，水源分布圖層及消火栓分布圖層。

實(shí)驗(yàn)假設(shè)太原市一中隊(duì)轄區(qū)內(nèi)某大廈發(fā)生火災(zāi)，以太原市一中隊(duì)為起點(diǎn)，該大廈為終點(diǎn)選取最優(yōu)路徑。該大廈位于師范街中段，黨校路東側(cè)，塢城中路西側(cè)，該大廈南側(cè)緊鄰居民區(qū)，且樓間距較近。該大廈共32層，1－3層是商場，4－10層為寫字樓層，10層之上為居民住宅。由于人口密度大，不易疏散，極易造成人員傷亡，需調(diào)派高空消防云梯車、搶險(xiǎn)救援消防車和水罐消防車前往救援。消防車參數(shù)見表3。

表3 消防車參數(shù)表

消防一中隊(duì)位于起火點(diǎn)西北部，有多條路徑可通往救援。圖2為未出現(xiàn)局部堵塞時(shí)最優(yōu)路徑方案，其中虛線路徑為分層分析算法與實(shí)時(shí)分層分析算法計(jì)算得到的結(jié)果，實(shí)線路徑為Dijkastra算法計(jì)算得到的結(jié)果。表4是圖2對(duì)應(yīng)的計(jì)算結(jié)果。圖3為黨校路出現(xiàn)堵塞時(shí)最優(yōu)路徑方案，其中虛線路徑(小間隔)為分層分析算法計(jì)算得到的結(jié)果，虛線路徑(大間隔)為實(shí)時(shí)分層分析算法計(jì)算得到的結(jié)果，實(shí)線路徑為Dijkastra算法計(jì)算得到的結(jié)果。橢圓是以軍民路與黨校路十字路口為新的起點(diǎn)和起火點(diǎn)為終點(diǎn)形成的橢圓搜索區(qū)。表5對(duì)應(yīng)圖3計(jì)算結(jié)果。

圖2 未出現(xiàn)局部堵塞時(shí)最優(yōu)路徑方案

表4 在未出現(xiàn)局部堵塞時(shí)最優(yōu)路徑方案比較表

圖3 出現(xiàn)局部堵塞時(shí)最優(yōu)路徑方案

表5 出現(xiàn)局部堵塞時(shí)最優(yōu)路徑方案比較表

從視覺測量(圖2、3)及數(shù)理統(tǒng)計(jì)(表4、5)兩方面進(jìn)行分析比較可知:(1)在未出現(xiàn)局部堵塞時(shí)，分層分析算法與實(shí)時(shí)分層分析算法得到最優(yōu)路徑方案相同，且都比Dijkastra算法得到的最優(yōu)路徑方案距離較長。但是Dijkastra算法得到的最優(yōu)路徑方案經(jīng)過八一路是縣道，且路口較多，因而交叉路口延誤時(shí)間較長，會(huì)增加車輛行駛時(shí)間。同時(shí)，八一路較窄，僅能通過搶險(xiǎn)救援消防車，而高空消防云梯車、水罐消防車無法順利通過，因而Dijkastra算法得到的最優(yōu)路徑方案不可行。而分層分析算法與實(shí)時(shí)分層算法得到最優(yōu)路徑方案經(jīng)過平陽路與學(xué)府街是兩條省道，路口較少，可通過交通流量更大，同時(shí)路面寬敞，搶險(xiǎn)救援消防車，高空消防云梯車及水罐消防車都可以順利通過，是該情況下的最優(yōu)路段選擇。(2)在出現(xiàn)局部堵塞時(shí)，以黨校路堵塞為例，Dijkastra算法得到路徑方案與未出現(xiàn)局部堵塞時(shí)相同，因而不具有可行性。實(shí)時(shí)分層分析算法得到的路徑方案在距離上較分層分析算法得到的路徑方案較長，但是分層分析算法路徑方案在堵塞路段等待通行時(shí)間未知，而實(shí)時(shí)分層分析算法得到的路徑方案是較分層分析算法得到的路徑方案的局部次優(yōu)方案，且到達(dá)起火點(diǎn)時(shí)間明確，因而實(shí)時(shí)分層分析算法得到的路徑方案是該情況下的最優(yōu)路段選擇。(3)將以上兩種情況生成的最優(yōu)路徑與實(shí)際情況進(jìn)行比對(duì)，基本符合實(shí)際。

3 結(jié)論

本文在基于對(duì)分層分析算法最優(yōu)路徑的原理和特點(diǎn)的基礎(chǔ)上進(jìn)行研究和分析，提出了一種實(shí)時(shí)的分層分析算法計(jì)算最優(yōu)路徑。該方法充分考慮路網(wǎng)狀態(tài)實(shí)時(shí)變化，使用局部規(guī)劃技術(shù)應(yīng)對(duì)突發(fā)事件，修正全局路徑，保證車輛行駛時(shí)間最短。實(shí)驗(yàn)結(jié)果及實(shí)際經(jīng)驗(yàn)均表明，與典型的Dijkastra算法及分層分析算法比較，該方法得到的最優(yōu)路徑方案均具有更強(qiáng)的可行性。

［1］AHUJA R K，MEHLHORN K，ORLIN J B，TARJAN R E.Faster algorithms for the shortest path problem［J］.Journal of the Association f or Computing Machinery，1990，37(2):213 －223.

［2］嚴(yán)寒冰，劉迎春.基于GIS的城市道路網(wǎng)最短路徑算法研討［J］.中國計(jì)算機(jī)學(xué)報(bào)，2002，(2):210 －215.

［3］魏新宇.消防滅火救援最優(yōu)路徑算法研究［D］.西安:西安科技大學(xué)，2006.

［4］唐文武，施曉東，朱大奎.GIS中使用改進(jìn)的Dijkstra算法實(shí)現(xiàn)最短路徑的計(jì)算［J］.中國圖象圖形學(xué)報(bào)，2000，5(12):1019－1023.

［5］龍科軍，LEE D.HAN，王賽政.路網(wǎng)信息不完備條件下的動(dòng)態(tài)最短路搜索［J］.計(jì)算機(jī)應(yīng)用，2011，3(3):651 －653.

［6］王曉麗，楊兆升，呂旭濤，等.平行四邊形限制最短路徑算法及其在道路網(wǎng)絡(luò)中的應(yīng)用［J］.吉林大學(xué)學(xué)報(bào)，2006，36(1):123～127.

［7］YAO Xin，LIU Yong，LIN Guang－ming.Evolutionary programming made faster［J］.IEEE Transactions on Evolutionary Computation，1999，3(2):82 －102.

［8］ZHONG Wei－cai，LIU Jing，XUE Ming－ zhi.A multi－ Agent genetic algorithm for global numerical optimization［J］.IEEE Transactions on Systems，Man，and Cybernetics Part B:Cybernetics，2004，34(2):1128－1141.

［9］LEUNG Y W，WANG Y P.An orthogonal genetic algorithm with quantization for global numerical optimization［J］.IEEE Transactions on Evolutionary Computation，2001，5(1):41 －53.

［10］SHANG Yun －wen，QIU Yu－h(huán)uang.A note on the extended rosenbrock function［J］.IEEE Transactions on Evolutionary Computation，2006，14(1):119 －126.