基于改進(jìn)標(biāo)號修正的潰壩逃生路徑優(yōu)化

鎖啟鳳

摘 要： 災(zāi)害發(fā)生時(shí)為確保受災(zāi)區(qū)居民疏散到安全區(qū)，建立疏散路徑優(yōu)化模型。依據(jù)潰壩現(xiàn)場情況，以疏散路徑最短同時(shí)路段通行能力最大為目標(biāo)建立逃生路徑規(guī)劃模型?？紤]到模型是一個(gè)多目標(biāo)優(yōu)化模型，對標(biāo)號修正算法的評價(jià)準(zhǔn)則進(jìn)行改進(jìn)以適用于尋找多目標(biāo)優(yōu)化模型的最優(yōu)解集。將該框架應(yīng)用于龍巖市新羅區(qū)，結(jié)果表明：在8組方案中，改進(jìn)的算法找到長度為3741米，路段通行能力評價(jià)函數(shù)值為2.063的路徑最優(yōu)，充分說明提出算法的優(yōu)越性，可以為逃生人員規(guī)劃出可靠的疏散路徑。

關(guān)鍵詞： 應(yīng)急疏散;優(yōu)化問題;逃生;路徑規(guī)劃;標(biāo)號修正

【中圖分類號】F274 【文獻(xiàn)標(biāo)識碼】A 【DOI】10.12215/j.issn.1674-3733.2020.40.264

0 引言

洪水，地震等突發(fā)性自然災(zāi)害事件危及人類的生命安全，面對日益增加的突發(fā)事件，人類的防范意識逐漸增強(qiáng)。近些年大部分災(zāi)害中依然存在人員傷亡情況。分析原因，災(zāi)害發(fā)生時(shí)災(zāi)區(qū)居民無法快速了解災(zāi)害發(fā)展的形勢以至于無法得知哪條路徑安全。因此，在現(xiàn)有的路況條件下，如果決策者在了解災(zāi)害得發(fā)展趨勢的基礎(chǔ)上預(yù)先為受災(zāi)人群提供一條可以順利到達(dá)安全區(qū)域的路徑，可以減少傷亡人數(shù)。

約束最短路問題是多目標(biāo)優(yōu)化問題[1]，Stewart和White發(fā)現(xiàn)現(xiàn)實(shí)世界中許多問題涉及多重，相互沖突的目標(biāo)，從而首次提出了多目標(biāo)泛化算法MOA*，處理多目標(biāo)路徑規(guī)劃問題[2]。大部分文獻(xiàn)使用節(jié)點(diǎn)擴(kuò)展方法實(shí)現(xiàn)多目標(biāo)啟發(fā)式搜索，這樣求解的精確度不足，Mandow等人為解決這個(gè)問題提出了路徑擴(kuò)展的方法 [3-4]。Dasgupta等人系統(tǒng)地將多準(zhǔn)則決策范式推廣到啟發(fā)式搜索領(lǐng)域 [5]。張慧等[6]采用數(shù)字高程模型進(jìn)行地形描述，并通過計(jì)算各柵格的坡度、粗糙度、起伏度對地形進(jìn)行識別，再采用滑動(dòng)窗及增量式A*算法進(jìn)行路徑規(guī)劃。

1 問題描述

在圖1的疏散路網(wǎng)中，灰色區(qū)域是受災(zāi)區(qū)，紅色區(qū)域是安全區(qū)，黑色線段表示路段。假設(shè)發(fā)生災(zāi)難時(shí)每個(gè)逃生人員都能接收到預(yù)警信號，在疏散點(diǎn)到安全點(diǎn)間為逃生人員規(guī)劃出可靠的疏散路徑，確保疏散人員移動(dòng)到安全區(qū)域。根據(jù)受災(zāi)區(qū)域的環(huán)境結(jié)合路徑長度，路段通行能力兩個(gè)因素規(guī)劃出一條安全的疏散路徑。

多目標(biāo)優(yōu)化問題是指在給定約束條件的情況下，目標(biāo)多于一個(gè)并且需要同時(shí)極大（?。┗@些目標(biāo)值的問題。一個(gè)目標(biāo)達(dá)到最優(yōu)會使其它目標(biāo)劣化。因此，多目標(biāo)優(yōu)化問題的最優(yōu)解不止一個(gè)，而是存在一個(gè)包含多個(gè)解的Pareto最優(yōu)解集合。解決實(shí)際的問題時(shí)Pareto 最優(yōu)解集合中解的數(shù)量很大不可能逐一求出，況且實(shí)際問題只需要一個(gè)或幾個(gè)解，因此需要解決問題者從實(shí)際問題出發(fā)在Pareto 最優(yōu)解集合中挑選出一個(gè)解作為最終解。

為了更完整描述Pareto最優(yōu)解，引入兩個(gè)相關(guān)定義[7]：

定義1：令x（x1，x2，…，xn），y（y1，y2，…，yn）為兩組解，若x1

定義2：如果x（x1，x2，…，xn）無法被其它解支配，那么x（x1，x2，…，xn）為Pareto最優(yōu)解。

2 模型建立

定義符號：

V：節(jié)點(diǎn)集合;A：弧集合;i，j：節(jié)點(diǎn)，i，j∈V;

O：起點(diǎn);D：終點(diǎn);

cij=（c（1）ij，c（2）ij），c（1）ij，c（2）ij分別表示路段（i，j）的路徑長度和路段通行能力.

2.1 目標(biāo)函數(shù)

mints=∑（i，j∈A）c（1）ijxij+1c（2）ij（1）

式中，ts是影響因素累積成本，c（1）ij是路段（i，j）的長度，c（2）ij是路段（i，j）的通行能力，xij是一個(gè)定義如下的二元決策變量：

xij∈{0，1}，i，j∈A（2）

若選擇了路段（i，j），xij=1，否則xij=0.

2.2 約束條件

|∑（i，j）∈Axij-∑（j，i）∈Axji|=1，i∈{O，D} 0，否則.（3）

每個(gè)逃生人員有唯一的起點(diǎn)并且選擇唯一的終點(diǎn)，公式（3）保證各場景下選擇的路徑是一段通暢的路徑。

2.3 數(shù)據(jù)準(zhǔn)備

本文通過無人機(jī)航拍獲得研究區(qū)域地圖數(shù)據(jù)，如圖二（a）的圖片格式。通過ArcGIS軟件處理，得到如圖2（b）所示的點(diǎn)線路網(wǎng)表示，點(diǎn)表示人員聚集的區(qū)域或安全區(qū)域，線表示路徑。路網(wǎng)信息包含路徑長度和路段通行能力。路徑長度是實(shí)際長度值，路段通行能力根據(jù)路段寬度以升序的方式生成。路段的長度和寬度皆由ArcGIS軟件緩沖得到。根據(jù)水源地確定人員逃生的方向，因此相鄰兩節(jié)點(diǎn)間是不可逆的有向路徑。

3 算法設(shè)計(jì)

標(biāo)號修正算法的思路是[8]：設(shè)是G（V，A）一個(gè)有向圖。首先初始化研究區(qū)域路網(wǎng)圖中的節(jié)點(diǎn)數(shù)據(jù)和弧長數(shù)據(jù)，令起點(diǎn)標(biāo)號為us，對于圖中節(jié)點(diǎn)集合V中任意一個(gè)節(jié)點(diǎn)i，賦予兩個(gè)數(shù)值：一個(gè)是距離標(biāo)號ui，存儲的信息是起點(diǎn)到該點(diǎn)的累積費(fèi)用的上界，該費(fèi)用包括前面提到的路徑長度以及路段通行能力。另一個(gè)是前趨標(biāo)號pred[i]，記錄的是當(dāng)起點(diǎn)us到該節(jié)點(diǎn)i的一條路徑的累積費(fèi)用取到上界時(shí)，該條路徑中節(jié)點(diǎn)i的直接前趨節(jié)點(diǎn)。這樣，算法通過不斷修改這些標(biāo)號進(jìn)行迭代計(jì)算直到找到終點(diǎn)，此時(shí)這些標(biāo)號不再改變成為永久標(biāo)號?；厮菟械墓?jié)點(diǎn)標(biāo)號可以求出最優(yōu)路徑。基于以上描述，筆者對經(jīng)典標(biāo)號修正算法的標(biāo)號選擇準(zhǔn)則改進(jìn)，改進(jìn)的標(biāo)號修正算法適用于尋找Pareto最優(yōu)解，改進(jìn)的標(biāo)號修正算法步驟如下：

步驟1：初始化，將兩個(gè)影響因素的總體費(fèi)用存儲在距離標(biāo)號集合U中;

步驟2：令起點(diǎn)的距離標(biāo)號us=0，前趨標(biāo)號pred（O）=0;對所有其他節(jié)點(diǎn)j，令uj為無窮大。

步驟3：若對所有權(quán)重為cij的弧（i，j），ujui+cij，算法結(jié)束，uj為從起點(diǎn)至節(jié)點(diǎn)j的最小總體費(fèi)用路徑，最短路可通過依次尋找前趨標(biāo)號（pred）獲得。

步驟4：尋找滿足ui+cijuj的?。╥，j），令uj=ui+cij，pred（j）=i，轉(zhuǎn)至步驟3。

4 實(shí)驗(yàn)分析

將框架應(yīng)用于圖2中龍巖市新羅區(qū)67個(gè)節(jié)點(diǎn)99條路徑的路網(wǎng)中驗(yàn)證算法的有效性。用ArcGIS軟件生成疏散路段的長度（米）以及路段寬度（米）。路段通行能力根據(jù)路段寬度在區(qū)間[2：12]內(nèi)以升序的方式生成。

對于節(jié)點(diǎn)61-16計(jì)算出前8條最優(yōu)路徑，結(jié)果如圖3所示，圖的右上角給出了8次計(jì)算得到的路徑對應(yīng)的路徑長度累積費(fèi)用以及路徑通行能力累積費(fèi)用，綜合這兩個(gè)因素，本文算法給出的最優(yōu)解為第6組解。回溯8條路徑得到的可行路徑如表1所示：

5 結(jié)論

針對潰壩發(fā)生水災(zāi)時(shí)受災(zāi)區(qū)域人員需要在復(fù)雜的環(huán)境中轉(zhuǎn)移至安全區(qū)域事件，建立逃生路徑規(guī)劃模型?？紤]到該問題是一個(gè)多目標(biāo)優(yōu)化問題，筆者對標(biāo)號修正算法的評價(jià)標(biāo)準(zhǔn)進(jìn)行改進(jìn)，改進(jìn)的算法可以找到Pareto最優(yōu)解。最后，將該框架應(yīng)用到龍巖市新羅區(qū)示例中，結(jié)果表明提出的模型與算法能為災(zāi)區(qū)居民規(guī)劃出路徑長度最短同時(shí)路段通行能力較大的最優(yōu)路徑，可以有效解決應(yīng)急疏散問題。

參考文獻(xiàn)

[1] 王莉.動(dòng)態(tài)不確定路徑優(yōu)化模型與算法[D].北京：北京交通大學(xué)，2017.8.

[2] Bradley，S，Stewart，et al.Multiobjective A*[J].Journal of the Acm，1991.

[3] Dasgupta P，Chakrabarti P P，Desarkar S C.Multiobjective Heuristic Search in AND/OR Graphs[J].Journal of Algorithms，1996，20（2）：282-311.

[4] L.Mandow and J.L.Pérez de la Cruz.Multicriteria heuristic search[J].European Journal of Operational Research，2003.

[5] Harikumar S，Kumar S.Iterative deepening multiobjective A*[M].Elsevier North-Holland，Inc.1996.58（1）：11-15.

[6] 張慧，榮學(xué)文，李貽斌，李彬，丁超，張俊文，張勤.四足機(jī)器人地形識別與路徑規(guī)劃算法[J].機(jī)器人，2015，37（5）： 546-556.

[7] 秦玉鑫，張高峰，王裕清.礦災(zāi)害環(huán)境下多目標(biāo)路徑規(guī)劃方法[J].控制工程，2017（11）：2337-2342.

[8] 邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].清華大學(xué)出版社，2006.62-77.