1、路網(wǎng)疏散路徑規(guī)劃的求解方法曾麥脈人口應(yīng)急疏散的兩種研究方法：2. 基于網(wǎng)絡(luò)流的方法 把疏散隊(duì)伍抽象為流，將問題建模為節(jié)點(diǎn)和邊帶容量限制的網(wǎng)絡(luò)模型。從而將問題轉(zhuǎn)化為網(wǎng)絡(luò)流領(lǐng)域的研究。 主要用于區(qū)域范圍內(nèi)的人口疏散問題研究。1. 基于微觀仿真模型的方法 對單個人或者是交通工具的行為進(jìn)行建模仿真來反映整個疏散的狀態(tài)過程。 特點(diǎn)是體現(xiàn)個體特性，體現(xiàn)個體與周圍環(huán)境之間的相互作用，計(jì)算量大，計(jì)算結(jié)果受到驅(qū)動個體行為的算法和程序的影響。主要用于建筑物內(nèi)的疏散。 本講的疏散路徑規(guī)劃就是采用第二種方法，將交通流建模為網(wǎng)絡(luò)流問題來求解疏散問題。目標(biāo)是在盡可能短的時間內(nèi)將人員疏散出去。建模方式： 邊的建模：將路段建

2、模為網(wǎng)絡(luò)上的邊，道路的寬度特性建模為邊上的容量，通過路段所需的時間建模為通過時間。 節(jié)點(diǎn)的建模：將有一定量疏散人口聚集的地方建模為節(jié)點(diǎn)，包括源節(jié)點(diǎn)、目的節(jié)點(diǎn)和中間節(jié)點(diǎn)。節(jié)點(diǎn)的容量代表可以容納的疏散人口。 具體的數(shù)量標(biāo)準(zhǔn)的確定、路段的取舍、節(jié)點(diǎn)所代表的范圍的界定、初始人口數(shù)據(jù)的獲取與建模等等規(guī)則，需要對實(shí)際區(qū)域進(jìn)行分析和細(xì)致的探討，這里不深入討論。已知條件： 在一個由節(jié)點(diǎn)和邊組成的有向網(wǎng)絡(luò)上，已知：(1) 節(jié)點(diǎn)和邊上的容量限制；(2) 邊上的通過時間；(3) 待疏散人口的數(shù)量及其他們所在的源節(jié)點(diǎn)；(4) 疏散的目的地節(jié)點(diǎn)。 包括已知條件、解的表達(dá)、優(yōu)化目標(biāo)和限制條件四個部分。疏散路徑規(guī)劃問題的網(wǎng)

3、絡(luò)模型描述：限制條件： (1) 在任何時刻，疏散者所在的路徑上必須滿足節(jié)點(diǎn)和邊的容量限制； (2) 節(jié)點(diǎn)和邊遵守先入先出的原則； (3) 有限的計(jì)算機(jī)計(jì)算能力和內(nèi)存資源。 優(yōu)化目標(biāo)： 最小化疏散所需的時間。 解的表達(dá)： 疏散路徑規(guī)劃結(jié)果的表達(dá)包括一系列的條目，每個條目包括一條從源節(jié)點(diǎn)到目的地節(jié)點(diǎn)的路徑、到達(dá)路徑上各個節(jié)點(diǎn)的時間、本次通過這條路徑的人口數(shù)量。 一個例子：一種可行解：源節(jié)點(diǎn)疏散數(shù)目路徑規(guī)劃節(jié)點(diǎn)ID（到達(dá)時間）-節(jié)點(diǎn)ID（到達(dá)時間）- 到達(dá)時間N86N8(0)-N10(3)-N13(4)4N86N8(1)-N10(4)-N13(5)5N83N8(0)-N11(3)-N14(5)5N1

4、3N1(0)-N3(1)-N4(4)-N6(8)-N10(13)-N13(14)14N13N1(0)-N3(2)-N4(5)-N6(9)-N10(14)-N13(15)15N11N1(0)-N3(1)-N5(4)-N7(8)-N11(13)-N14(15)15N22N2(0)-N3(1)-N5(4)-N7(8)-N11(13)-N14(15)15N23N2(0)-N3(3)-N4(6)-N6(10)-N10(15)-N13(16)16N13N1(1)-N3(2)-N5(5)-N7(9)-N11(14)-N14(16)16求解以上疏散路徑規(guī)劃的兩類方法：2. 啟發(fā)式算法 如：CCRP算法。它不能

5、保證得出的是最優(yōu)解，卻能夠在次優(yōu)解的前提下獲得計(jì)算性能上改善。 1. 線性規(guī)劃方法 需要借助時間擴(kuò)充圖將時間過程規(guī)避掉，轉(zhuǎn)化為最小代價流問題(Minimum cost flow theory)。由于計(jì)算量過大，主要用于小型網(wǎng)絡(luò)，如小型建筑物內(nèi)的疏散。時間擴(kuò)充圖(Time expended Graph)的例子：最小費(fèi)用流問題(Minimum cost flow theory)：Minimize Subject to for all for all 其中：代表每單位流的費(fèi)用 代表從i到j(luò)的容量上限 代表節(jié)點(diǎn)i的網(wǎng)絡(luò)流。如果 0，說明是源節(jié)點(diǎn)，如果 0，說明是目的節(jié)點(diǎn)；如果 =0，說明是中間的轉(zhuǎn)運(yùn)節(jié)

6、點(diǎn)。 將最小費(fèi)用流問題應(yīng)用到時間擴(kuò)充圖時，單位流量的費(fèi)用 是分段函數(shù)。多項(xiàng)式時間算法（Polynomial Algorithms） Geometric improvement approach (2) Scaling approach (3) Dynamic programming approach (動態(tài)規(guī)劃) (4) Binary search 2. 網(wǎng)絡(luò)簡化算法（Network Simplex Algorithms） 在初始生成樹的基礎(chǔ)上不斷改進(jìn)生成樹結(jié)構(gòu)直到最優(yōu)。 最小費(fèi)用流的求解算法：CCRP 算法：CCRP： Capacity constrained routing plannin

7、g來源于：Department of Computer Science, University of Minnesota (美國明尼蘇達(dá)州大學(xué)計(jì)算機(jī)科學(xué)系) 。該系長期致力于大規(guī)模人口疏散規(guī)劃的研究，有美國軍隊(duì)高性能計(jì)算研究中心和NASA的研究課題。從2003年至今，發(fā)表過一些有延續(xù)性的研究論文。輸入：輸出：我做過的研究工作：實(shí)現(xiàn)CCRP算法細(xì)節(jié)。用不同的啟發(fā)規(guī)則來改進(jìn)CCRP算法。國際人群安全工程會議（International conference on engineering for crowd safety）人群疏散動態(tài)學(xué)會議（Conference on Pedestrian and Evacuation Dynamics ), 簡稱PED。 前者1993年在倫敦舉辦過一屆，后來是否舉辦，未查到相關(guān)資料。后者已經(jīng)舉辦了四屆，最近的一屆是2008年二月在德國的University of Wuppertal舉行。 尤其是2003年P(guān)edestrian and Evacuation Dynam