馬 瑩, 吳楠楠

(1. 福建工程學院 信息科學與工程學院, 福建 福州 350118; 2. 福建省地震局, 福建 福州 350003)

近年來,烈度較大、引起次生災(zāi)害較大的地震頻繁發(fā)生,在地震現(xiàn)場應(yīng)急工作人員的調(diào)動以及通信指揮車的實際使用中,應(yīng)急交通路徑的實時尋徑問題日顯突出.其中,當?shù)卣馂?zāi)害發(fā)生后如何提供安全可行的路線引導人員和車輛進入災(zāi)區(qū)是目前面對的首要課題.因此,建立一套系統(tǒng)使其能夠為地震現(xiàn)場的應(yīng)急工作人員提供交通路線選擇及評估判斷將十分必要,以確保現(xiàn)場工作人員及車輛能夠安全、有效、快速地到達災(zāi)區(qū).目前,全球眼監(jiān)控系統(tǒng)在我國城鄉(xiāng)的分布密度日益廣泛,其所能提供的監(jiān)視信息對于緊急情況下的尋徑問題將有極大的幫助.本文主要分析了在烈度較大的地震災(zāi)害發(fā)生時,在不同的破壞程度下,如何在海量的全球眼信息中選取有價值的信息,并結(jié)合該全球眼所在的地理情況給出應(yīng)急救援的最佳有效路徑[1].

1 系統(tǒng)原理

目前的“全球眼”是一個由運營商提供視頻監(jiān)控服務(wù)的基礎(chǔ)業(yè)務(wù)平臺.該平臺可以通過寬帶IP城域網(wǎng)對覆蓋范圍內(nèi)的所有監(jiān)控點實施監(jiān)視和遠程控制,主要用于公共事業(yè)部門的用戶(如司法系統(tǒng)、公安、海關(guān)、計量監(jiān)察、消防、民政局、行政執(zhí)法部門)和企業(yè)業(yè)務(wù)部門(如電力、石化、金融和銀行系統(tǒng)、交通、房地產(chǎn)、大連鎖超市)等單位.“全球眼”系統(tǒng)具備數(shù)字化存儲、網(wǎng)絡(luò)化監(jiān)控、現(xiàn)場語音控制傳輸、遠程圖像實時調(diào)度、現(xiàn)場報警聯(lián)動控制等功能,因此可作為地震現(xiàn)場應(yīng)急救援交通路徑分析的一個平臺.

本系統(tǒng)利用福建省地震局現(xiàn)有的信息系統(tǒng)軟件和硬件平臺以及運營商全球眼服務(wù)平臺,搭建系統(tǒng)開發(fā)環(huán)境和實驗環(huán)境,通過對全球眼工作情況數(shù)據(jù)的處理,正常工作的全球眼所采集的災(zāi)前、災(zāi)后圖像對比處理,以及處理后的數(shù)據(jù)通過人工智能系統(tǒng)(專家系統(tǒng))進行分析,最終給出最佳路徑的選擇方案,從而實現(xiàn)圖1中運算調(diào)度層及服務(wù)層的內(nèi)容[2].

本項目將建立如圖1所示的4層服務(wù)架構(gòu),為現(xiàn)場通信指揮車、現(xiàn)場工作人員以及指揮中心調(diào)度人員提供行經(jīng)路徑查詢和現(xiàn)場視頻接入服務(wù).

應(yīng)用層為現(xiàn)場通信指揮車操作人員、現(xiàn)場工作人員以及指揮中心調(diào)度人員提供WEB或WAP瀏覽器平臺.工作人員可以利用便攜電腦、智能手機或車載計算機等設(shè)備,通過WEB或WAP瀏覽器,利用本課題開發(fā)的客戶端系統(tǒng)發(fā)出交互式查詢請求,并可在相應(yīng)的平臺上顯示運算后的參考路徑電子地圖并配有相關(guān)全球眼的接入鏈接,亦可點擊鏈接察看相關(guān)現(xiàn)場實時視頻圖像.

圖1 行徑選擇系統(tǒng)拓撲圖Fig.1 Topology of the path selection system

接入層為應(yīng)用層提供相關(guān)網(wǎng)絡(luò)的接入服務(wù),可利用現(xiàn)有的單兵3G網(wǎng)絡(luò)設(shè)備、車載3G網(wǎng)絡(luò)、海事衛(wèi)星電話網(wǎng)絡(luò)設(shè)備和車載VSAT網(wǎng)絡(luò)設(shè)備通過VPN鏈路接入.指揮中心調(diào)度人員可利用局域網(wǎng)接入路徑查詢服務(wù)器.

運算調(diào)度層的查詢服務(wù)器裝有本課題開發(fā)的服務(wù)器端路徑查詢和全球眼視頻調(diào)用軟件.根據(jù)客戶端發(fā)來的查詢請求和全球眼搜索狀態(tài),計算出最佳參考路徑標注在電子地圖上并發(fā)回到客戶端.

服務(wù)層為運營商系統(tǒng)提供的全球眼業(yè)務(wù)平臺,根據(jù)該平臺的全球眼工作狀態(tài)了解所需經(jīng)過道路的暢通狀態(tài).

2 基礎(chǔ)專家信息庫準備

在福建省地震局現(xiàn)有的信息系統(tǒng)軟件和硬件平臺以及運營商全球眼服務(wù)平臺的基礎(chǔ)上搭建系統(tǒng)開發(fā)環(huán)境和實驗環(huán)境.系統(tǒng)擬定始發(fā)地點為福建省地震應(yīng)急指揮中心大樓,建立以南平浦城、龍巖永定、漳州漳浦、寧德霞浦和福州連江為目的地的5個數(shù)據(jù)庫.在分析始發(fā)地至目的地的現(xiàn)有的全部可能通行的路徑、各路徑若遭前來破壞后可能修復的基數(shù)以及修復所需的時間參數(shù)的基礎(chǔ)上,將數(shù)據(jù)內(nèi)容分別提取至矩陣L,T,G,Q中.其中,L為始發(fā)地至目的地的所有可能通行的關(guān)鍵節(jié)點的全球眼工作狀態(tài)(其中包括高速、省道、縣道、鄉(xiāng)道和村道上的分支關(guān)鍵節(jié)點);T為L全球眼所對應(yīng)路段的通行速度指數(shù)(按路況給出的指數(shù)值,高速公路的通行速度最快為1,其他路型根據(jù)該路段的具體情況給出相應(yīng)的系數(shù));G為L全球眼所對應(yīng)路段的危險指數(shù)(包括是否含有隧道、橋梁、易滑坡山體及路邊懸崖等,此矩陣要結(jié)合相關(guān)行業(yè)專家給出相應(yīng)的可能通行的系數(shù));Q為L全球眼所對應(yīng)路段嚴重毀壞后修復的難度系數(shù)(如橋梁斷裂、隧道坍塌、山體滑坡等,此矩陣要結(jié)合相關(guān)行業(yè)專家給出相應(yīng)的修復時間的系數(shù)).由于我國城鄉(xiāng)規(guī)劃建設(shè)項目較多、較快,因此以上數(shù)據(jù)應(yīng)至少半年更新一次,以確保所提供路徑信息的可靠性[3-4].

3 改進的雙向Dijkstra最優(yōu)路徑選擇算法

在災(zāi)害發(fā)生時,根據(jù)烈度的不同,所造成的道路交通損害不同,所造成的全球眼節(jié)點算壞也不同,考慮多種不同程度的破壞下均可以提供最優(yōu)路徑以供應(yīng)急人員及車輛選擇,本文選取改進的雙向Dijkstra算法為動態(tài)路徑求解算法.傳統(tǒng)的Dijkstra算法本身是一種按路徑長度遞增次序所產(chǎn)生的算法,其已被證明是計算一點到所有其他點的最優(yōu)路徑效率最高的算法之一[5-6].它的思想如下.

把頂點集合V分成兩組:

(1)S:已求出的頂點的集合(初始時只含有源點V0);

(2)V-S=T:尚未確定的頂點的集合.

將T中的頂點按遞增的次序加入到S中,保證:

(1) 從源點V0到S中其他各頂點的長度都不大于從V0到T中任何頂點的最優(yōu)路徑的長度;

(2) 每個頂點對應(yīng)一個距離值.

S中的頂點:從V0到此頂點的長度;

T中的頂點:從V0到此頂點的只包括S中的頂點作中間頂點的最優(yōu)路徑的長度.

依據(jù):可以證明,V0到T中頂點Vk的,或是從V0到Vk的直接路徑的權(quán)值,或是從V0經(jīng)S中的頂點到Vk的路徑權(quán)值之和.

求得最優(yōu)路徑的算法步驟如下:

(1) 初始時令S=V0,T=其余頂點,T中頂點對應(yīng)的距離值如下:

若存在〈V0,Vi〉,則dV0,Vi為〈V0,Vi〉弧上的權(quán)值;

若不存在〈V0,Vi〉,則dV0,Vi為∞.

(2) 從T中選取一個其距離值為最小的頂點W且不在S中,加入S.

(3) 對其余T中頂點的距離值進行修改:若加進W作中間頂點,從V0到Vi的距離值縮短,則修改此距離值.

重復上述步驟(2)、步驟(3),直到S中包含所有的頂點,即W=Vi為止[5].

由于Dijkstra算法本身沒有方向性,因此整個搜索過程有很大的盲目性,這樣的搜索會增加搜索開銷,也會增大算法的復雜度,使得系統(tǒng)的實時性變差.因此,選擇雙向Dijkstra算法,即在始發(fā)端和目的端分兩個子過程同時開始最優(yōu)路徑尋址,當兩個子過程相遇時,搜索結(jié)束,得出最終起止點間的最優(yōu)路徑;若兩個子過程不相遇,則在兩個逆向的搜索過程結(jié)束后,取兩個子路線較優(yōu)者為最優(yōu)路徑. 下面簡單說明改進的雙向Dijkstra算法的具體計算過程.

對于網(wǎng)絡(luò)G=L,E,其中,L為節(jié)點集,E為邊集,起始點為S,終點為D,連接節(jié)點a和節(jié)點b的邊的權(quán)值為Ta b,da b表示節(jié)點a和節(jié)點b的最優(yōu)路徑的長度. 對于任意節(jié)點a,設(shè)置節(jié)點的屬性為(dS a,pS a,dD a,pD a,m,n),其中,dS a,dD a分別表示起始點S和終點D到節(jié)點a的最優(yōu)路徑的長度. 由于經(jīng)典的Dijkstra算法中用pa標記起始點S到節(jié)點的最優(yōu)路徑中節(jié)點a的前一個節(jié)點,對應(yīng)的pS a標記起始點S到節(jié)點a的最優(yōu)路徑中節(jié)點a的前一個節(jié)點,pD a標記終點D到節(jié)點a的最優(yōu)路徑中節(jié)點a的前一個節(jié)點,對每個節(jié)點設(shè)置兩個標記位m,n,用于表征是否求出了起始點S和終點D至節(jié)點a的最優(yōu)路徑,如m=1代表已求出起始點S到該節(jié)點的最優(yōu)路徑,m=0則代表還未求出起始點S到該節(jié)點的最優(yōu)路徑. 同理,n=1代表已求出終點D到該節(jié)點的最優(yōu)路徑,n=0則代表還未求出終點D到該節(jié)點的最優(yōu)路徑.設(shè)置鏈表v和鏈表w分別用于存儲與已經(jīng)標記的節(jié)點相鄰接的節(jié)點,雙向Dijkstra算法的具體步驟如下.

(1) 初始化網(wǎng)絡(luò),dS S=0,dD D=0,pS S=pD D=∧,設(shè)置起始點S的標記位:S(m=1,n=0);設(shè)置終點D的標記位:D(m=0,n=1).對于a∈V-S-D,dS a=∞,dD a=∞,標記位:a(m=0,n=0),將鏈表v和鏈表w清空后,分別將與起始點S和終點D鄰接的節(jié)點加入鏈表v和鏈表w.

(2) 對于標記位m和標記位n已標記的節(jié)點k和l,求出k節(jié)點與之鄰接但其標記位m未標記的節(jié)點a的最優(yōu)路徑的長度(這些節(jié)點已經(jīng)存儲在鏈表v中),求出l節(jié)點與之鄰接但標記位n未標記的節(jié)點b的最優(yōu)路徑的長度(這些節(jié)點已經(jīng)存儲在鏈表w中),且dS a=min{cdS a,c(dk a+wk a)},dD b=min{cdD b,c(dl b+wl b)}. 其中,c為引入的各全球眼關(guān)鍵節(jié)點處路況的通行加權(quán)值,其數(shù)值為c=T·G·Q.在對應(yīng)的全球眼關(guān)鍵節(jié)點為正常工作點時,可通過調(diào)節(jié)T值的權(quán)重來確定是選擇路徑最短還是速度最快;在對應(yīng)的全球眼關(guān)鍵節(jié)點為壞點(即不能通信或通過圖像處理獲得的判定結(jié)果為嚴重損壞)時,可通過調(diào)節(jié)G,Q值的權(quán)重來選擇可以通行的最佳路徑.

(3) 在鏈表v和鏈表w中,選取dS a最小的節(jié)點f和dD a最小的節(jié)點h,則f為起始點S正向搜尋最優(yōu)路徑上的一個節(jié)點,h為終點D的逆向搜索最優(yōu)路徑上的一個節(jié)點,分別找到節(jié)點f和節(jié)點h的前驅(qū)節(jié)點f*和h*,則pS f=f*,pD f=h*,標記節(jié)點f的標記位m=1,標記位n不變.標記節(jié)點h的標記位n=1,標記位m不變.

(4) 判斷新標記的節(jié)點f,h的標記位:

若f(m=1,n=0),h(m=0,n=1),則轉(zhuǎn)至步驟(5);

若f(m=1,n=1)或h(m=1,n=1),則判斷兩者是否有一個為起始節(jié)點或終止節(jié)點:

若兩者均不是起始節(jié)點或終止節(jié)點,則轉(zhuǎn)向步驟(6);

若任意一個是起始節(jié)點或終止節(jié)點,表明正向?qū)?yōu)和逆向?qū)?yōu)兩個子過程未相遇,則轉(zhuǎn)向步驟(7).

(5) 分別把與節(jié)點f和節(jié)點h相連接但標記位未標記的節(jié)點加入鏈表v和鏈表w,在鏈表v和鏈表w中刪除節(jié)點f和節(jié)點h,轉(zhuǎn)至步驟(2).

(6) 若節(jié)點f(m=1,n=1),找出其前驅(qū)節(jié)點f*,則dS D=dS f*+df*f+dD f;

若節(jié)點h(m=1,n=1),找出其前驅(qū)節(jié)點h*,則dS D=dS h+dh*h+dD h*.

dSD即為起始點S和終點D的最優(yōu)路徑的長度.

注:當存在多于一個最小節(jié)點h或f時,分別計算每個最小節(jié)點的前驅(qū)節(jié)點h*和f*,選取和值最小的點為前驅(qū)節(jié)點,后續(xù)以此類推.

4 實例分析

為驗證改進的雙向Dijkstra最優(yōu)路徑選擇算法的有效性,在福建省地震局應(yīng)急通信車日常應(yīng)急演練中,對本系統(tǒng)進行了不同烈度情況下的模擬實驗.福建省地形地貌復雜,導致路況在災(zāi)害條件下受其影響的因素較多;考慮試驗地貌涵蓋福建省地域常見的地貌路況(包含橋梁、隧道、路邊易滑坡山體及河流等),以及實驗結(jié)果的利用價值(試驗地2013年發(fā)生過3次4級以上的地震),實驗選擇福建省莆田市仙游縣石蒼鄉(xiāng)為模擬災(zāi)害地,實驗演練路徑選擇情況如下.

(1) 低烈度、全球眼無壞點的情況下,在系統(tǒng)操作界面下選擇路徑最短的選項,如圖2所示. 系統(tǒng)經(jīng)計算給出的最優(yōu)路徑如圖3所示.

圖2 系統(tǒng)操作界面Fig.2 Operation interfaces of the system

圖3 距離最短的路徑尋址結(jié)果Fig.3 Addressing result of the shortest path

(2) 大烈度、全球眼有壞點的情況下,在系統(tǒng)操作界面下選擇用時最短的選項. 系統(tǒng)經(jīng)計算給出的最優(yōu)路徑如圖4所示.

圖4 用時最短的路徑尋址結(jié)果Fig.4 Addressing result of the shortest time

為了比較本路徑分析系統(tǒng)的有效性,在演練時同時出發(fā)三輛車:一輛應(yīng)急通信車,采用本系統(tǒng)推薦的最優(yōu)路徑行駛;兩輛普通的同性能轎車,一輛無導航行駛,一輛有導航行駛.

在不同的模擬災(zāi)害情況下,三輛車同時從福建省地震局應(yīng)急指揮大樓出發(fā),開至目的地(福建省莆田市仙游縣石蒼鄉(xiāng))的耗時對照表如表1所示.

表1 全行程耗時對照表Table 1 Comparison table of time-consuming of the whole trip

由表1中的實驗數(shù)據(jù)可得,使用本系統(tǒng)測算所得的最優(yōu)路徑,在不同災(zāi)害情況下,行程耗時均較其他兩車短,并且災(zāi)害越嚴重,優(yōu)勢越明顯.

5 結(jié) 語

災(zāi)害發(fā)生后通往現(xiàn)場的道路情況如何,現(xiàn)場通信指揮車和現(xiàn)場工作人員該如何進入災(zāi)區(qū),這些都是人們需要面對的問題.遠程無人機是可以解決上述問題的辦法之一,但是購買成本高、操作風險大、使用條件受天氣影響等問題也隨之突出.基于“全球眼”的地震現(xiàn)場應(yīng)急救援交通路徑分析系統(tǒng)的開發(fā)和運用為解決上述問題提供了一種較為有效的辦法.

該分析系統(tǒng)主要研究開發(fā)適合我國地震現(xiàn)場工作實際的基于全球眼的地震現(xiàn)場應(yīng)急救援交通路徑分析系統(tǒng),實現(xiàn)地震現(xiàn)場應(yīng)急救援資源管理信息化,實現(xiàn)地震現(xiàn)場各車輛和人員行經(jīng)路線的動態(tài)追蹤、管理.系統(tǒng)的完成和推廣應(yīng)用,將大大提高地震現(xiàn)場資源的使用效率,提高現(xiàn)場救援隊伍的管理水平和救援能力.在完善地震現(xiàn)場應(yīng)急救援交通路徑分析系統(tǒng)的同時,也能夠提高現(xiàn)場車輛和人員的安全調(diào)度技術(shù)水平.這一研究還將推動全球眼技術(shù)在防震減災(zāi)領(lǐng)域的應(yīng)用,促進防震減災(zāi)科技進步.

參考文獻:

[1]吳楠楠,洪惠群,黃宏生,等. 福建地震現(xiàn)場應(yīng)急通信指揮車集成改裝項目的實施[J]. 華南地震, 2012,32(2):87-91.

(Wu Nannan,Hong Huiqun, Huang Hongsheng, et al. Implementation of Integrated Modification to In-situ Emergency Communication Command Vehicle in Fujian Province[J]. South China Journal of Seismology, 2012,32(2):87-91.)

[2]吳楠楠,黃宏生,郭進波,等. 福建地震現(xiàn)場應(yīng)急通信系統(tǒng)的運行維護管理[J]. 華南地震, 2011,31(1):81-85.

(Wu Nannan,Huang Hongsheng, Guo Jinbo, et al. Operation and Maintenance Management of Earthquake Field Emergency Communication System in Fujian[J]. South China Journal of Seismology, 2011,31(1):81-85.)

[3]Zhang Yiwen,Qi Jiayin,Fang Binxing, et al. The Indicator System Based on BP Neural Network Model for Net-mediated Public Opinion on Unexpected Emergency[J]. China Communications, 2011,8(2):42-51.

[4]Juels A,Weis S A. Defining Strong Privacy for RFID[J]. ACM Transactions on Information and System Security, 2009,13(1):1-23.

[5]姜蕊. 融合預(yù)測信息的動態(tài)路徑選擇算法研究[D]. 北京:北京交通大學, 2011:38-43.

(Jiang Rui. Study of Dynamic Route Choice Algorithm Integration of Forecasting Information [D]. Beijing: Beijing Jiaotong University, 2011:38-43.)

[6]黃緯. 基于平面圖的改進Dijkstra算法研究[J]. 江蘇大學學報:自然科學版, 2003,24(6):70-72.

(Huang Wei. Research on Improved Dijkstra Algorithm Based on Ichnography[J]. Journal of Jiangsu University: Natural Science, 2003,24(6):70-72.)