鎖啟鳳

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

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

【中圖分類號】F274 【文獻標識碼】A 【DOI】10.12215/j.issn.1674-3733.2020.40.264

0 引言

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

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

1 問題描述

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

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

為了更完整描述Pareto最優(yōu)解，引入兩個相關定義[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é)點集合;A：弧集合;i，j：節(jié)點，i，j∈V;

O：起點;D：終點;

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

2.1 目標函數(shù)

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

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

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）

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

2.3 數(shù)據(jù)準備

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

3 算法設計

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

步驟1：初始化，將兩個影響因素的總體費用存儲在距離標號集合U中;

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

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

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

4 實驗分析

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

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

5 結論

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

參考文獻

[1] 王莉.動態(tài)不確定路徑優(yōu)化模型與算法[D].北京：北京交通大學，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] 張慧，榮學文，李貽斌，李彬，丁超，張俊文，張勤.四足機器人地形識別與路徑規(guī)劃算法[J].機器人，2015，37（5）： 546-556.

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

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