地震疏散路徑規劃算法＊

吳正言 張春勤 莫時旭

（桂林理工大學廣西礦冶與環境科學實驗中心1） 桂林 541004）

（桂林理工大學廣西巖土力學及工程重點實驗室2） 桂林 541004）

（上海交通大學安泰經濟與管理學院3） 上海 200052）

目前，應急疏散交通分配主要采用均衡配流［1－2］的方法，不僅所分配的路徑無法保證疏散交通流的安全性，而且算法的計算代價高［3］，缺乏解決突發交通擁堵的應變性.路徑行程安排方法則運用網絡流和路徑搜索算法產生OD路徑，以及每條路徑疏散交通流的行程安排.可見的文獻主要包括考慮時空擁擠度［4］和具有通行能力約束的路徑規劃方法（capacity constrained route planner，CCRP）［5］.考慮時空擁擠度的實質與考慮通行能力是一致的，但需標定的參數影響因素復雜，可操作性差.而CCRP是最著名的路徑行程安排啟發式算法，算法的復雜度低、實時性好，能生成近似最優的疏散路徑規劃方案，并適用于較大規模的路網.但該方法缺少對疏散路徑的危險性、可通行性的考慮，并缺少對突發交通擁堵動態生成疏散路徑的能力，致使所生成的交通組織方案安全性、可通過性和應變性較差.本文針對地震災害的交通條件，以CCRP算法為基礎，考慮路網的危險性和可通行性，以使應急疏散交通流分配到危險性低且可通行性高的最短路徑上.同時，為了提高應急疏散過程中對突發交通擁堵的應變能力，增加了對突發交通擁堵點自動優化生成疏散路徑的能力，進而提出地震疏散路徑規劃（earthquake evacuation route planning，EERP）算法，并進行了實例驗證.

1 EERP算法描述

應急疏散路網中節點和連邊的通行能力具有非負整數約束，連邊還具有非負的行程時間，且其行程時間包括交叉口的延誤.假定疏散的總交通量、初始點位置和疏散目的地位置為已知，并假設可實時接收到路網的狀況信息，包括路網中的安全節點區域，危險節點或路段，以及突發交通擁堵點等.應急疏散條件下，由于疏散路網的大部分路段處于飽和或過飽和狀態，交通流基本不超車，因此，假定連邊的交通量具有先入先出的特性.

EERP算法主要包括一系列由疏散原點到目的地的路徑，以及路徑交通量的時間行程安排，其中路徑交通量的時間行程安排要遵守路徑中節點和連邊的通行能力約束.

EERP在確保疏散危險性較低的前提下，使應急疏散的總時間最小，并使疏散路徑規劃方案的計算效率滿足應急疏散的要求.

2 EERP算法設計

2.1 輸入變量的確定

1）路網G（N，E），其中，N 為交叉口集合，E為路段集合.

任意節點n∈N，具有2個屬性：交叉口的通行能力NC（n）和需疏散交通量NO（n）.

任意連邊e∈E，具有2個屬性：路段的通行能力EC（e）和行程時間Tt（e）.

2）疏散原點集合S，S?N.疏散原點s∈S，具有需疏散的交通量屬性.

3）疏散目的地集合D，D?N.疏散目的地節點d∈D，具有可容納交通量的能力屬性ADC（d）.如果節點d沒有容納能力的限制，則ADC（d）＝∞.

4）應急疏散的安全時限TS.如果安全時限不可知，則TS＝∞.

2.2 EERP算法設計步驟

1）檢查疏散原點是否具有需疏散的交通量.如果沒有交通量則退出程序，反之則進行下一步.

2）路段行程時間的綜合評估.為了充分考慮地震疏散中路段的危險性和可通行性，在路段的行程時間中引入危險性和可通行性懲罰函數，即

式中：CTt（e）為路段e的行程時間估計值，其數值與道路的交通狀況有關，根據交通量與路段行程時間的關系，采用BPR改進模型［6］計算獲得；M為懲罰因子，是充分大的數，表示危險或不可通行的路段，其行程時間充分大；α為路段的危險性懲罰系數；β為路段的可通行性懲罰系數，且α，β∈［0，1］.路段α和β的取值是由其結構狀態決定的，而其結構狀態會因地震的破壞而發生改變，與路段的地質環境和人工環境等因素有關.α的取值可根據路段所在的地層類型、地下水深度、地質構造、建筑物類型與抗震能力、道路兩側建筑物高度與距離之比、道路上的脆弱點等進行綜合評估得到.β的取值與路面的結構、質量有關，可根據路面的損毀程度對可通行性的影響進行評估獲得.如果路段e的危險性較小或可通行性較好，則α，β的取值接近于0；反之，如果e危險性較大或可通行性較差，則α，β的取值接近于1.

3）按最短路優先分配規則，運用矩陣迭代算法［11］尋找原點集S到終點集D 的最短路徑R＜s，n1，n2，…，nk，d＞，使 R 的行程時間TR≤TS，并得R中各節點ni（i＝1，2，…，k）對應的時間點T＜t1，t2，…，tk＞.同時，R 連邊的剩余通行能力AEC和節點剩余通行能力ANC要滿足以下條件

4）計算路徑R的分配交通量

式中：s為路徑R的原點；d為疏散目的地節點，i∈｛1，2，…，k－1｝.

5）計算路徑R中連邊、節點的剩余通行能力.為表達方便起見，用計算機編程偽代碼表示為

式中：等號表示將右邊部分的值賦給左邊的變量，i∈｛1，2，…，k－1｝.

6）計算路徑R原點剩余的待疏散交通量，以及疏散目的地節點的剩余容納能力.用計算機編程偽代碼表示為

7）如果AEC（enini＋1，ti）＝0或 ANC（ni＋1，ti＋Tt（enini＋1））＝0，則表示連邊或節點的交通量已達到其可能通行能力，后面分配的交通量必須多等待1個時間單位，因此，對應連邊的當量行程時間自動增加1個時間單位，用計算機編程偽代碼表示為

8）如果由于突發的意外情況，致使路徑R上點j發生嚴重的交通擁堵，若j∈enini＋1則增設j為路網虛擬節點，若j∈N則j為路網的實際節點.為疏散此節點j的擁堵交通量，則將節點j并入疏散原點集，作為臨時疏散原點，用計算機編程的偽代碼表示為

9）如果節點m∈S，且NO（m）＝0，則將節點m從疏散原點集中去除，用計算機編程的偽代碼表示為

式中：等號表示將右邊部分的值賦給左邊的變量.

10）反復執行1）～9），如果安全時限已知，則直到疏散路徑行程時間TR＞TS為止；如果安全時限未知，則直到疏散原點集S中的交通量疏散完畢為止.

3 實證分析

按CCRP算法生成的應急疏散路徑規劃方案如表1所列，為直觀起見，將生成的路徑標記在疏散路網中，見圖1.從中可見，CCRP算法生成的疏散路徑依然通過危險節點9和3，不能繞過危險區域，無法滿足疏散路徑危險性小的前提條件，方案的安全性較差.而且，整個方案的所有規劃路徑，都沒有對突發擁堵的節點8采取任何疏散的措施，缺乏對突發交通擁堵的必要疏散能力.

表1 CCRP算法生成的路徑規劃方案

表2 EERP算法生成的應急疏散路徑規劃方案

圖1 CCRP算法生成的疏散路徑圖

圖2 EERP算法生成的疏散路徑圖

EERP算法生成的路徑規劃方案如表2所列，將生成的疏散路徑規劃方案匯總成節點見圖2.從中可以看出，EERP算法充分考慮了疏散路網的可通行性和安全性要素，可以繞過危險區域，降低了疏散路徑的危險性.而且，對突發交通擁堵點，可按需疏散的交通量動態規劃出相應的疏散路徑，具有必要的應變性和疏散調整能力.

綜上，EERP算法可以彌補CCRP算法在疏散路徑安全性和可通行性方面的不足，且對突發交通擁堵具有自動優化生成疏散路徑的能力，所產生的應急疏散路徑規劃方案具有更好的實用性.

4 結束語

針對地震應急疏散的特殊性，在CCRP算法的基礎上，考慮了疏散路徑的安全性和可通行性要求，并增加了對突發交通擁堵的自動優化生成疏散路徑的能力，提出了地震疏散路徑規劃算法.實證分析表明，EERP算法所規劃的路徑具有安全性和可通行性好的特點，且對突發交通擁堵具有必要的應變性.為了進一步提高本算法的實用性和可操作性，下一步需進一步研究地震疏散路徑的危險性及其可通行性的快速評估方法.

［1］HAN L.D.Global optimization of emergency evacuation assignments［J］.Interfaces，2006，36：502－513.

［2］陳岳明，蕭德云.基于動態交通分配的路網應急疏散模型［J］.清華大學學報：自然科學版，2009，49（8）：1102－1105.

［3］LIU X.，HE Xiaozheng，BAN Xuegang （Jeff）.A cell－based many－to－one dynamic system optimal model and its heuristic solution method for emergency evacuation［C］.The 86th TRB Annual Meeting，Washington D.C，USA，2006：1－19.

［4］李清泉，李秋萍，方志祥.一種基于時空擁擠度的應急疏散路徑優化方法［J］.測繪學報，2011，40：517－523.

［5］KIM Sangho，GEORGE Betsy，SHEKHAR Shashi.Evacuation route planning：scalable heuristics［C］.Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems，2007，LNCS 3633：1－8.

［6］王素欣，王雷震，高 利，等.BPR路阻函數的改進研究［J］.武漢理工大學學報：交通科學與工程版，2009，33（3）：446－449.