武警警官學(xué)院信息工程系決策與指揮教研室 哈 達(dá) 劉永利 沈先耿

基于應(yīng)急救援路徑規(guī)劃選擇的研究

武警警官學(xué)院信息工程系決策與指揮教研室 哈 達(dá) 劉永利 沈先耿

在突發(fā)事件發(fā)生之后,應(yīng)急救援人員在規(guī)劃部署開(kāi)進(jìn)事發(fā)地的路線中反映出了較大的問(wèn)題。針對(duì)此類情況,本文旨在研究將Dijkstra算法與層次分析法相結(jié)合,提供給救援決策者一個(gè)有效可行的路徑選擇方案,極大地提高了救援決策者在路徑選擇上的效率,從而使救援決策者能夠及時(shí)應(yīng)對(duì),妥善處置,使損失降到最低。

應(yīng)急救援;路徑規(guī)劃;Dijkstra;層次分析

0 引言

當(dāng)今我國(guó)在處置突發(fā)事件的過(guò)程中,應(yīng)急救援隊(duì)伍雖都能在第一時(shí)間調(diào)動(dòng)起來(lái),但由于各類原因造成救援隊(duì)伍不能在第一時(shí)間到達(dá)受災(zāi)地點(diǎn),導(dǎo)致?lián)p失沒(méi)能及時(shí)控制。究其原因,不難發(fā)現(xiàn),沒(méi)能選擇一條最優(yōu)的路徑是造成這個(gè)被動(dòng)局面的一個(gè)主要原因。所以如何選擇一條最優(yōu)的路線是現(xiàn)在救援人員處置應(yīng)急事件最需要解決的問(wèn)題之一。開(kāi)進(jìn)路線規(guī)劃問(wèn)題的研究與實(shí)現(xiàn)的目的就是為了解決這個(gè)問(wèn)題,為今后救援人員處置應(yīng)急任務(wù)時(shí),選擇一條最優(yōu)的路線提供思路及方法。

1 相關(guān)理論

Dijkstra算法是用來(lái)解決從一個(gè)起始點(diǎn)出發(fā)到其他各個(gè)點(diǎn)的最短路徑問(wèn)題,主要是針對(duì)有向圖的。它解決問(wèn)題的方式是從一個(gè)頂點(diǎn)即起始點(diǎn)出發(fā),并且以這個(gè)點(diǎn)作為中心點(diǎn),一層一層的選擇計(jì)算,最后連接到終點(diǎn)。它是一種具有代表性的很典型的最短路徑算法,發(fā)展較為成熟。如今,常常使用兩種表達(dá)方法,分別是永久和臨時(shí)標(biāo)號(hào)方式以及OPEN,CLOSE表達(dá)方式。本文是使用第一種方式。另外Dijkstra算法還有不能有負(fù)權(quán)邊在圖中的要求。Dijkstra算法的本質(zhì)是一種標(biāo)號(hào)法:也就是給圖的每一個(gè)頂點(diǎn)記一個(gè)數(shù),這些數(shù)被稱為這些頂點(diǎn)的標(biāo)號(hào),這些標(biāo)號(hào)被分為臨時(shí)標(biāo)號(hào)和固定標(biāo)號(hào)兩種。

層次分析法(AHP)是薩蒂在上世紀(jì)70年代初在幫助美國(guó)國(guó)防部研究"根據(jù)各個(gè)工業(yè)部門(mén)對(duì)國(guó)家福利的貢獻(xiàn)大小而進(jìn)行電力分配"課題時(shí)研究出來(lái)的。這位美國(guó)運(yùn)籌學(xué)家、匹茨堡大學(xué)的教授提出的這種方法是一種在面對(duì)多目標(biāo)時(shí),用權(quán)重來(lái)分層次、以權(quán)重來(lái)排序的一種決策分析方法[3]。這種決策分析方法是將定性與定量相結(jié)合,來(lái)應(yīng)對(duì)多目標(biāo)的復(fù)雜問(wèn)題。它是利用決策者累積的經(jīng)驗(yàn)也就是對(duì)事物特征的認(rèn)知來(lái)確定能夠讓目標(biāo)實(shí)現(xiàn)的要素之間的重要程度之比,是將感性認(rèn)識(shí)進(jìn)行定量化的過(guò)程。它給予所有決策方案的所有標(biāo)準(zhǔn)的權(quán)數(shù),而后觀察這些權(quán)數(shù)來(lái)確定方案間的好壞,在處理那些用定量方法很難解決的問(wèn)題上有很大的作用。

2 路徑選擇建模

2.1 基于Dijlstra優(yōu)化算法的選擇

Dijkstra算法是找出從一個(gè)起始點(diǎn)到圖中任意一點(diǎn)的最短路徑,時(shí)間復(fù)雜度為O(n2)當(dāng)其使用鄰接矩陣存儲(chǔ)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時(shí),需要存儲(chǔ)空間為nXn。不難看出,當(dāng)節(jié)點(diǎn)數(shù)n的增大,它所需要的存儲(chǔ)空間就會(huì)成倍的巨漲。這就導(dǎo)致存儲(chǔ)效率和計(jì)算效率的降低。考慮到這個(gè)情況,在查找研究了多種優(yōu)化算法后,選擇了最為適合本文的研究方法。那就是:傳統(tǒng)的Dijkstra算法在選擇節(jié)點(diǎn)時(shí)重復(fù)工作過(guò)多,這就導(dǎo)致算法的效率降低。而選擇的優(yōu)化方法就是讓算法在處理節(jié)點(diǎn)時(shí)是只對(duì)最短路徑上節(jié)點(diǎn)的相鄰點(diǎn)進(jìn)行處理,從而不考慮到其他節(jié)點(diǎn)。這樣所需要的存儲(chǔ)空間就會(huì)減少,從而達(dá)到提高效率的目的。這樣在使用Dijkstra算法處理現(xiàn)實(shí)事件時(shí),效率就會(huì)更高,就更有利于救援隊(duì)伍處理應(yīng)急事件。

2.2 層次分析法最優(yōu)路選擇

在處理應(yīng)急事件問(wèn)題時(shí)最主要考慮的問(wèn)題就是找到一條最佳的路徑到達(dá)目的地。然而在現(xiàn)實(shí)情況里,最短不一定最優(yōu)。在處理應(yīng)急問(wèn)題時(shí),不能僅僅只考慮時(shí)間。還需要考慮其他影響救援的因素,比如道路的疏通程度。因此本文在用Dijkstra算法找出最短路徑后,再用層次分析法輔助決策,來(lái)確定最優(yōu)路徑。思路如下:

首先要進(jìn)行的是對(duì)災(zāi)難等級(jí)的劃分,不同的災(zāi)難程度對(duì)道路的破壞程度不同,在不同的災(zāi)難情況下,救災(zāi)物資的時(shí)效性、安全性、經(jīng)濟(jì)性的優(yōu)先等級(jí)也不相同。這里是對(duì)每段運(yùn)輸路徑的破壞程度進(jìn)行評(píng)定。隨著衛(wèi)星地圖的發(fā)展,這些工作時(shí)可以迅速評(píng)定出來(lái)。如果衛(wèi)星遭到破壞,用航拍等技術(shù)也能大致確定各條道路的破壞情況。然后根據(jù)破壞程度規(guī)劃出能夠直接使用到的道路和經(jīng)過(guò)維修能夠使用的道路。這里道路的長(zhǎng)度用時(shí)間來(lái)計(jì)算。在路況沒(méi)有受到破壞的情況下,設(shè)計(jì)時(shí)速為60km/h,對(duì)于破壞的道路等級(jí)進(jìn)行劃分為不同的時(shí)速,然后加上需要維修的時(shí)間就是這路徑的長(zhǎng)度權(quán)重。然后用Dijkstra算法找出最短路徑以及次短路徑。

然后使用層次分析法來(lái)對(duì)比最短路徑與次短路徑。根據(jù)路徑的時(shí)效性、經(jīng)濟(jì)性、安全性進(jìn)行評(píng)定,作為層次分析法的一個(gè)比較矩陣。最優(yōu)路徑和次短路徑就是可供選擇的兩個(gè)方案,然后這兩個(gè)方案的時(shí)效性就是其上一步最短路徑算出來(lái)的時(shí)間權(quán)重,安全性指標(biāo)就是對(duì)道路的破壞程度、經(jīng)濟(jì)性就是需要維護(hù)道路的難度。最后對(duì)其進(jìn)行層次分析法就能夠得到最優(yōu)結(jié)果。

3 結(jié)束語(yǔ)

本文以實(shí)用的角度,從根本問(wèn)題的需求出發(fā)。在研究救援隊(duì)伍現(xiàn)在搶險(xiǎn)救災(zāi)物資配送中遇到的實(shí)際問(wèn)題,一個(gè)能夠快速選取最優(yōu)路徑的方法即Dijkstra算法。為了更好的在處置突發(fā)事件時(shí)提供幫助,本文對(duì)算法的優(yōu)化方式進(jìn)行了選擇并找到了最好的優(yōu)化方案,提高了其運(yùn)算速度。然后將Dijkstra算法和層次分析法結(jié)合起來(lái)處理現(xiàn)實(shí)問(wèn)題。該方法是針對(duì)不同的災(zāi)情的實(shí)際需求和災(zāi)情對(duì)路面的破壞程度做出的方法。根據(jù)需要配送到的地方的時(shí)效性、經(jīng)濟(jì)性、安全性進(jìn)行評(píng)定。作為層次分析法的一個(gè)成對(duì)比較矩陣。最優(yōu)路徑和次短路徑就是可供選擇的兩個(gè)方案,然后這兩個(gè)方案的時(shí)效性就是其上一步最短路徑法算出來(lái)的時(shí)間權(quán)重,安全性指標(biāo)就是對(duì)道路的破壞程度、經(jīng)濟(jì)性就是需要維護(hù)道路的難度。然后對(duì)進(jìn)行層次分析法就能夠得到最優(yōu)結(jié)果。

今后對(duì)有關(guān)選擇最優(yōu)路徑還可以從以下幾個(gè)方面進(jìn)一步研究:(1)將數(shù)學(xué)模型與實(shí)際出現(xiàn)的情況相結(jié)合,如汶川、玉樹(shù)地震。研究在實(shí)際情況下是否有更加優(yōu)化的路徑選擇方法解決問(wèn)題。 (2)將理論實(shí)體化,設(shè)計(jì)軟件用于實(shí)現(xiàn)。

哈達(dá),武警警官學(xué)院信息工程系決策與指揮教研室助教。