任剛，吳建波，華璟怡，姚夢(mèng)佳，張旻沁

(1.東南大學(xué)江蘇省城市智能交通重點(diǎn)實(shí)驗(yàn)室，南京210096；2.現(xiàn)代城市交通技術(shù)江蘇高校協(xié)同創(chuàng)新中心，南京210096；3.公安部交通管理科學(xué)研究所，江蘇，無錫214151)

基于過飽和控制的疏散網(wǎng)絡(luò)優(yōu)化模型

任剛*1,2，吳建波1,2，華璟怡3，姚夢(mèng)佳1,2，張旻沁1,2

(1.東南大學(xué)江蘇省城市智能交通重點(diǎn)實(shí)驗(yàn)室，南京210096；2.現(xiàn)代城市交通技術(shù)江蘇高校協(xié)同創(chuàng)新中心，南京210096；3.公安部交通管理科學(xué)研究所，江蘇，無錫214151)

應(yīng)急條件下疏散需求呈現(xiàn)短時(shí)爆發(fā)性特點(diǎn)，為提高網(wǎng)絡(luò)優(yōu)化模型在應(yīng)急疏散狀態(tài)下的適用性，本文提出了網(wǎng)絡(luò)過飽和度概念，并結(jié)合疏散交通組織策略建立過飽和控制的疏散網(wǎng)絡(luò)雙層優(yōu)化模型.上層模型從疏散組織者的角度出發(fā)最小化疏散網(wǎng)絡(luò)過飽和度，下層模型以Wardrop用戶平衡準(zhǔn)則模擬疏散參與者的疏散路徑選擇行為.采用禁忌搜索算法求解所建模型，并以Sioux Falls網(wǎng)絡(luò)為平臺(tái)驗(yàn)證其有效性.實(shí)驗(yàn)結(jié)果表明，在應(yīng)急交通疏散狀態(tài)下，基于過飽和控制的疏散網(wǎng)絡(luò)優(yōu)化模型能夠?qū)崿F(xiàn)疏散網(wǎng)絡(luò)通行能力的最大化利用和應(yīng)急交通組織策略的最優(yōu)化配置，具有較強(qiáng)的適用性.

城市交通；疏散網(wǎng)絡(luò)優(yōu)化；過飽和控制；交通網(wǎng)絡(luò)；雙層規(guī)劃模型

1 引言

近些年來，世界各地突發(fā)事件的頻繁發(fā)生給當(dāng)?shù)卦斐闪司薮蟮娜藛T傷亡和財(cái)產(chǎn)損失.為提高區(qū)域疏散效率，降低突發(fā)事件造成的損失，有必要對(duì)應(yīng)急疏散的交通問題進(jìn)行相應(yīng)研究.

根據(jù)美國工程師協(xié)會(huì)研究結(jié)果，應(yīng)急狀態(tài)下疏散交通需求的生成具有短時(shí)爆發(fā)式特性[1]，疏散需求反應(yīng)曲線如圖1所示.疏散0時(shí)刻表示發(fā)布疏散通知，此前，少部分交通需求自行完成疏散，大量交通需求是在疏散通知發(fā)布后短時(shí)間內(nèi)加載至疏散網(wǎng)絡(luò)，因此在疏散通知發(fā)布后一段時(shí)間內(nèi)，城市路網(wǎng)將處于過飽和狀態(tài).

現(xiàn)階段，研究人員對(duì)交通網(wǎng)絡(luò)優(yōu)化模型已進(jìn)行相應(yīng)研究.Sun H等[2]和Gao Z等[3]分別從系統(tǒng)管理者與出行者角度建立雙層網(wǎng)絡(luò)模型對(duì)城市網(wǎng)絡(luò)進(jìn)行優(yōu)化設(shè)計(jì)，并改進(jìn)了模型求解算法.DesaiSen綜合考慮了供需與網(wǎng)絡(luò)交通分配的平衡，在道路通行能力約束的條件下建立了單層網(wǎng)絡(luò)優(yōu)化模型[4]. M iandoabchi等基于網(wǎng)絡(luò)備用容量理論建立了雙層混合整數(shù)規(guī)劃優(yōu)化模型，并采用模擬退火算法進(jìn)行求解[5].劉炳全等[6]也對(duì)網(wǎng)絡(luò)設(shè)計(jì)問題進(jìn)行了相應(yīng)研究.

然而上述研究背景為常態(tài)交通環(huán)境，所建模型均要求路段疏散流量不超過其通行能力，這與疏散網(wǎng)絡(luò)的過飽和特性相悖.針對(duì)這一問題，Liu Y等[7]與LiX等[8]將疏散需求劃分為數(shù)個(gè)階段，并保證各階段需求均不超過疏散網(wǎng)絡(luò)通行能力.這一方法很難保證疏散網(wǎng)絡(luò)通行能力的充分利用.因此，有必要改進(jìn)網(wǎng)絡(luò)優(yōu)化模型，以實(shí)現(xiàn)疏散需求在疏散網(wǎng)絡(luò)中的一次性加載及交通組織策略的優(yōu)化配置.

圖1 疏散需求曲線[1]Fig.1 Evacuation demand curve

2 網(wǎng)絡(luò)過飽和度概念與作用

為了定量化描述網(wǎng)絡(luò)過飽和狀態(tài)，改進(jìn)傳統(tǒng)網(wǎng)絡(luò)優(yōu)化模型以提高模型在網(wǎng)絡(luò)過飽和狀態(tài)下的適用性，本文提出網(wǎng)絡(luò)過飽和度這一概念.網(wǎng)絡(luò)過飽和度指在不改變路段通行能力限制的前提下，為滿足城市交通需求一次性加載的需求，既定道路通行能力矩陣所要疊加的最小乘數(shù)，定義式為：

式中xij為路段（i,j）分配的交通流量；Cij為路段（i,j）的通行能力；μij為路段過飽和度；μ為網(wǎng)絡(luò)過飽和度.

結(jié)合圖2對(duì)這兩個(gè)概念予以說明.a,b,c,d,e為干路—干路交叉口，l,m,n,k為疏散起點(diǎn)，f為疏散終點(diǎn)，vi為疏散起點(diǎn)i的疏散需求，Cij為路段（i,j）的通行能力.根據(jù)圖中各路段的通行能力和疏散量，可以得到此時(shí)網(wǎng)絡(luò)過飽和度：

由此可見，整個(gè)網(wǎng)絡(luò)的疏散“瓶頸”路段既不是通行能力最小的路段(c,d)，亦不是疏散量最大的路段(e,f)，而是疏散負(fù)荷程度最大的路段(b,e).

圖2 過飽和度計(jì)算網(wǎng)絡(luò)Fig.2 Network foroversaturation calculate

網(wǎng)絡(luò)過飽和度可以定量化描述網(wǎng)絡(luò)過飽和狀態(tài)，同時(shí)可以快速識(shí)別網(wǎng)絡(luò)上的“瓶頸”路段，有利于疏散管理者對(duì)“瓶頸”路段的交通管理；此外，網(wǎng)絡(luò)過飽和度可以評(píng)價(jià)不同的疏散交通組織方案，衡量網(wǎng)絡(luò)的疏散效率.網(wǎng)絡(luò)過飽和度越低，則表明對(duì)應(yīng)的交通組織方案的疏散效率越高.

3 疏散網(wǎng)絡(luò)優(yōu)化模型

針對(duì)網(wǎng)絡(luò)過飽和度可以評(píng)價(jià)不同疏散交通組織方案、衡量網(wǎng)絡(luò)疏散效率的特點(diǎn)，結(jié)合應(yīng)急交通組織策略，以疏散網(wǎng)絡(luò)的過飽和度最低為目標(biāo)，建立疏散網(wǎng)絡(luò)雙層優(yōu)化模型.

3.1 疏散網(wǎng)絡(luò)結(jié)構(gòu)表達(dá)

用于疏散網(wǎng)絡(luò)優(yōu)化模型構(gòu)建的相關(guān)疏散路網(wǎng)變量與定義如表1所示.

表1 疏散路網(wǎng)變量與定義Table 1 Network variable and notation

用網(wǎng)絡(luò)集合G=(N,A)代表城市交通網(wǎng)絡(luò)，如圖3所示.

圖3 疏散路網(wǎng)表示法Fig.3 Evacuation network representations

網(wǎng)絡(luò)中普通路段定義為擁有基本通行能力、路段長度和其他出行屬性的一般路段；交叉口內(nèi)部路段則定義為阻抗、長度均為0的特殊路段，以免對(duì)交通分配造成影響.

3.2 應(yīng)急交通組織

反向車道控制是指將對(duì)向車道全部或者部分逆向行駛來擴(kuò)大疏散方向的通行能力以提高網(wǎng)絡(luò)疏散效率[9]，該策略在美國颶風(fēng)疏散實(shí)踐中得到多次應(yīng)用[10].

沖突消除策略是指通過在交叉口采用特殊的臨時(shí)性交通管理措施，將主要疏散方向原有的間斷交通流轉(zhuǎn)化為連續(xù)交通流，減少車輛在交叉口產(chǎn)生的延誤，提高網(wǎng)絡(luò)疏散效率[11].該策略在Xie[10,12]，Bretschneider[13]的疏散網(wǎng)絡(luò)優(yōu)化模型中均得到應(yīng)用.

反向車道控制與沖突消除策略分別從路段與交叉口角度提高路網(wǎng)的疏散效率，二者互為補(bǔ)充[12].因此，建立如圖4所示的綜合交通組織以提高應(yīng)急疏散網(wǎng)絡(luò)的疏散效率.

3.3 雙層規(guī)劃模型

結(jié)合應(yīng)急交通組織，分別從疏散組織者和疏散參與者的角度出發(fā)，建立基于過飽和控制的疏散網(wǎng)絡(luò)雙層規(guī)劃模型.

上層模型（UM）：

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

約束條件

圖4 綜合交通組織示意圖Fig.4 Comprehensive traffic organization

上層模型從疏散組織者角度出發(fā)，尋找使得網(wǎng)絡(luò)飽和度最低的交通組織方案.式(5)為虛擬通行能力約束，用于限制基本路段的疏散交通量使其不超過虛擬通行能力.式(6)–式(8)為反向車道利用約束，式(6)保證路段車道方向的一致性；式(7)保證所有車道均被利用；式(8)保證某方向上車道數(shù)為非負(fù).式(9)、式(10)為沖突消除約束，式(9)消除直行車輛與左轉(zhuǎn)車輛的沖突點(diǎn)；式(10)消除交叉口垂直沖突點(diǎn).式(11)為路段連通性約束，式中M為極大數(shù)，描述了路段單向可用車道數(shù)與疏散交通量間的內(nèi)在聯(lián)系.式(12)為流量非負(fù)約束.

下層模型（LM）：

下層模型中從疏散參與者的角度出發(fā)進(jìn)行路徑選擇.式(14)為流量守恒約束.式(15)為流量轉(zhuǎn)換約束，顯示了路徑–路段流量間的轉(zhuǎn)化關(guān)系.式(16)為流量非負(fù)約束.

同時(shí)，下層模型式(13)中的行程時(shí)間計(jì)算引用美國道路局的BPR函數(shù)進(jìn)行計(jì)算，計(jì)算公式為

4 求解算法

禁忌搜索算法引入了靈活的存儲(chǔ)結(jié)構(gòu)，通過禁忌準(zhǔn)則與鄰域記憶機(jī)制來避免迂回搜索，并采用特赦準(zhǔn)則保證搜索的多樣性，從而實(shí)現(xiàn)全局優(yōu)化.禁忌算法因其搜索多樣性與高效性被廣泛應(yīng)用于網(wǎng)絡(luò)優(yōu)化模型求解問題.Tuydes等[14]、Xie等[15]利用禁忌搜索算法求解網(wǎng)絡(luò)優(yōu)化模型并取得良好效果.

利用禁忌搜索算法求解基于過飽和控制的疏散網(wǎng)絡(luò)優(yōu)化模型，具體步驟如下：

Step 1初始可行解的產(chǎn)生.定義禁忌長度、最大迭代步數(shù)、最優(yōu)解滯留步數(shù)、精英列表規(guī)模，設(shè)定迭代步數(shù)t=0，構(gòu)造禁忌列表、搜索列表、精英列表、集約化列表.同時(shí)確定網(wǎng)絡(luò)中各路段交通流量，并且確定初始目標(biāo)函數(shù)值Z(0).

Step 2鄰域搜索與更新搜索列表.鄰域的候選移動(dòng)定義為增加、減少路段弧，迭代次數(shù)t=t+1，確定搜索列表.

Step 3更新禁忌列表.對(duì)候選移動(dòng)進(jìn)行比選判斷，更新禁忌列表.

Step 4搜索列表檢驗(yàn).若搜索列表非空，轉(zhuǎn)入Step 5；反之，轉(zhuǎn)入Step 9.

Step 5確定候選移動(dòng).判斷路段弧(i,k)是否屬于搜索列表，不屬于禁忌列表，決定路段弧(i,k)是否為候選移動(dòng).

Step 6更新精英列表與移動(dòng).基于相應(yīng)的目標(biāo)函數(shù)值，并根據(jù)Step 1中與Step 2中所得結(jié)果中更新目標(biāo)函數(shù)值，并判斷是否接受移動(dòng).

Step 7搜索列表檢驗(yàn).若搜索列表非空，轉(zhuǎn)入步驟8；反之，轉(zhuǎn)入步驟10.

Step 8終止準(zhǔn)則檢驗(yàn).檢驗(yàn)迭代次數(shù)與搜索列表情況，判斷是否滿足停止準(zhǔn)則.若滿足停止準(zhǔn)則，算法結(jié)束，輸出最優(yōu)解；反之，轉(zhuǎn)入步驟2.

Step 9集約化策略.若搜索列表為空，選取滿足特赦準(zhǔn)則的禁忌列表中元素，產(chǎn)生新的列表.

Step 10多樣化策略.若候選集合不能使目標(biāo)函數(shù)得以優(yōu)化，且此時(shí)搜索列表為空，那么對(duì)候選集合進(jìn)行一定的改進(jìn)以保證搜索列表中路段移動(dòng)對(duì)目標(biāo)函數(shù)值產(chǎn)生有利影響.

5 示例驗(yàn)證

通過分別采用新建模型與常規(guī)疏散網(wǎng)絡(luò)優(yōu)化模型對(duì)SiouxFalls網(wǎng)絡(luò)進(jìn)行優(yōu)化，對(duì)比分析實(shí)驗(yàn)結(jié)果驗(yàn)證所建模型的有效性.選用的常規(guī)疏散網(wǎng)絡(luò)優(yōu)化模型亦為雙層規(guī)劃模型，具體模型請(qǐng)參閱文獻(xiàn)[12].

5.1 測(cè)試網(wǎng)絡(luò)設(shè)計(jì)

首先將疏散需求加載于Sioux Falls網(wǎng)絡(luò)的相關(guān)路段中，設(shè)置疏散終點(diǎn)為節(jié)點(diǎn)20，如圖5所示.在網(wǎng)絡(luò)優(yōu)化過程中，所有路段均可進(jìn)行反向車道設(shè)置，而交叉口沖突消除策略僅運(yùn)用于節(jié)點(diǎn)8、11、16內(nèi).各路段的自由流行駛時(shí)間、車道數(shù)及通行能力如表2所示.

圖5 Sioux Falls交通網(wǎng)絡(luò)Fig.5 Sioux Fallsnetwork

表2 各路段的交通屬性Table 2 Properties of roads

可知，疏散需求量超出測(cè)試網(wǎng)絡(luò)承載能力，常規(guī)疏散網(wǎng)絡(luò)優(yōu)化模型無法直接求解.為此，根據(jù)最大可用疏散時(shí)間劃分疏散需求，將全部疏散需求加載至疏散路網(wǎng)的時(shí)間分別設(shè)定為1至10個(gè)單位時(shí)間（unit，簡(jiǎn)稱U），使每個(gè)階段的疏散需求產(chǎn)生量均可以用常規(guī)疏散網(wǎng)絡(luò)優(yōu)化模型進(jìn)行求解.

5.2 結(jié)果分析

兩類模型在不同加載時(shí)間下的網(wǎng)絡(luò)總旅行時(shí)間對(duì)比，如圖6所示.可知，當(dāng)疏散需求全部加載至網(wǎng)絡(luò)的時(shí)間為3U時(shí)，兩類模型的總旅行時(shí)間相同.而此時(shí)，節(jié)點(diǎn)19、21、22與疏散終點(diǎn)（節(jié)點(diǎn)20）連接路段的疏散流量等于經(jīng)過反向車道控制后的路段通行能力.這表明基于過飽和度控制的疏散網(wǎng)絡(luò)優(yōu)化模型能夠?qū)崿F(xiàn)疏散網(wǎng)絡(luò)通行能力的最大化利用.

圖6 不同需求加載時(shí)間下網(wǎng)絡(luò)總旅行時(shí)間對(duì)比Fig.6 Comparison of total travel timewith differentdemand loading time

圖6也顯示了常規(guī)疏散網(wǎng)絡(luò)優(yōu)化模型下疏散需求加載至疏散網(wǎng)絡(luò)的時(shí)間對(duì)網(wǎng)絡(luò)疏散總旅行時(shí)間的影響.疏散需求加載時(shí)間過短，即單位時(shí)間內(nèi)加載到疏散網(wǎng)絡(luò)的疏散量過大，會(huì)導(dǎo)致模型無法得到可行解，反之，則不利于反映疏散時(shí)的交通擁堵現(xiàn)象，疏散網(wǎng)絡(luò)的擁擠效應(yīng)將會(huì)被弱化，使網(wǎng)絡(luò)總旅行時(shí)間減少.新建的網(wǎng)絡(luò)優(yōu)化模型不受疏散需求加載至網(wǎng)絡(luò)的時(shí)間影響，更適合在應(yīng)急疏散條件下應(yīng)用.

常規(guī)網(wǎng)絡(luò)優(yōu)化模型控制下的節(jié)點(diǎn)8、11、16處的交通組織方案會(huì)根據(jù)疏散需求加載至疏散網(wǎng)絡(luò)時(shí)間的不同而變化，如圖7(a)–7(c)所示.上文提及的當(dāng)需求加載時(shí)間為3U時(shí)，對(duì)應(yīng)的交通組織方案如圖7(c)所示.此時(shí)交通組織方案與新建模型控制下的交通組織方案完全相同，如圖7(d).由此可見新建模型可以在應(yīng)急疏散條件下實(shí)現(xiàn)交通組織策略的最優(yōu)化配置.

圖7 不同需求加載時(shí)間下交通組織方案對(duì)比Fig.7 Comparison of trafficorganizationwith differentdemand loading time

6 研究結(jié)論

針對(duì)應(yīng)急疏散需求短時(shí)爆發(fā)性的特征，本文提出了網(wǎng)絡(luò)過飽和度這一概念.結(jié)合反向車道與沖突消除策略建立了基于過飽和度控制的疏散網(wǎng)絡(luò)優(yōu)化模型，以使得網(wǎng)絡(luò)疏散能力實(shí)現(xiàn)最大化利用.最后通過Sioux Falls網(wǎng)絡(luò)對(duì)模型的有效性進(jìn)行驗(yàn)證.

實(shí)驗(yàn)結(jié)果表明，該模型有效彌補(bǔ)了常規(guī)網(wǎng)絡(luò)優(yōu)化模型在網(wǎng)絡(luò)過飽和狀態(tài)下適用性不足的缺點(diǎn)，同時(shí)可以確定最佳的交通組織方案，提高網(wǎng)絡(luò)疏散效率，實(shí)現(xiàn)網(wǎng)絡(luò)道路通行能力的最大化利用.如何將過飽和控制與動(dòng)態(tài)交通信息發(fā)布相結(jié)合告知疏散參與者交叉口交通組織方案將是下一步的研究方向.

[1]Fu H.Development of dynamic travel demandmodels for hurricane evacuation[D].Louisiana State University, 2004.

[2]Sun H,Gao Z,Wu J.A bi-level programmingmodel and solution algorithm for the location of logistics distribution centers[J].Applied Mathematical Modelling,2008,32(4):610-616.

[3]Gao Z,Wu J,Sun H.Solution algorithm for the bi-level discrete network design problem[J].Transportation Research PartB:Methodological,2005,39(6):479-495.

[4]Desai J,Sen S.A global optimization algorithm for reliable network design[J].European Journal of OperationalResearch,2010,200(1):1-8.

[5]Miandoabchi E,Farahani R Z.Optimizing reserve capacity of urban road networks in a discrete network design problem[J].Advances in Engineering Software, 2011,42(12):1041-1050.

[6]劉炳全,黃崇超.一種新的離散型網(wǎng)絡(luò)平衡設(shè)計(jì)模型與算法[J].系統(tǒng)工程,2008,26(4):83-87.[LIU B Q, HUANG C C.A novelmodel and algorithm for discrete network equilibrium design[J].Systems Engineering. 2008,26(4):83-87.]

[7]LiuY,Lai X,Chang G L.Cell-based network optimizationmodel for staged evacuation planning under emergencies[J].Transportation Research Record: Journal of The Transportation Research Board,2006, 1964(1):127-135.

[8]Li X,Huang B,Liu Z,et al.A novel method for planning a staged evacuation[J].Journal of Systems Scienceand Complexity,2012,25(6):1093-1107.

[9]Wolshon B.“One-way-out”:Contraflow freeway operation for hurricane evacuation[J].Natural Hazards Review,2001,2(3):105-112.

[10]Xie C,Lin D,Waller S T.A dynamic evacuation network optimization problem with lane reversal and crossing elimination strategies[J].Transportation Research Part E:Logistics and Transportation Review, 2010,46(3):295-316.

[11]Cova T J,Johnson JP.A network flow model for lanebased evacuation routing[J].Transportation Research PartA:Policy and Practice,2003,37(7):579-604.

[12]Xie C,Turnquist M A.Lane-based evacuation network optimization:An integrated Lagrangian relaxation and tabu search approach[J].Transportation Research Part C:Emerging Technologies,2011,19(1):40-63.

[13]Bretschneider S,Kimms A.A basic mathematical model for evacuation problems in urban areas[J]. Transportation Research Part A:Policy and Practice, 2011,45(6):523-539.

[14]Tuydes H,Ziliaskopoulos A K.Tabu-based heuristic approach for optimization of network evacuation contraflow[J].Transportation Research Record,2006, 1964:157-168.

[15]Xie C,TurnquistM A.Integrated evacuation network optimization and emergency vehicle assignment[J]. Transportation Research Record,2009,2091:79-90.

Oversaturation Control-based Model for Evacuation Network Optimization

REN Gang1,2,WU Jian-bo1,2,HUA Jing-yi3,YAOMeng-jia1,2,ZHANGM in-qin1,2

(1.Jiangsu Key Laboratory of Urban ITS,SoutheastUniversity,Nanjing 210096,China; 2.Jiangsu Province Collaborative Innovation CenterofModern Urban Traffic Technologies,Nanjing 210096,China; 3.Traffic ManagementResearch Instituteof TheM inistry of Public Security,Wuxi214151,Jiangsu,China)

A large number of evacuation demands emerged in a short time under the emergency condition. In order to improve the applicability of optimal network design model,the concept of oversaturation of network is proposed.Combined with comprehensive traffic management strategy under emergency conditions,a bi-level network optimalmodelwith oversaturation control is established.The up-levelmodel m inim izes the oversaturation of evacuation network with comprehensive traffic management as the goal of traffic organizers,while the low-levelmodel applies user equilibrium model tom im ic the evacuation routes choice behavior of evacuees.A Tabu Search(TS-based)solution method is used to solve the optimization model.The numerical testswith Sioux Falls network validated the applicability of the bi-level programm ing model.And the results show that the new model can make the best use of network capacity as well as determ ine the optim izing trafficmanagementplanwith betterapplicability underemergency evacuation.

urban traffic;evacuation network optim ization;oversaturation control;transportation network; bi-levelprogrammingmodel

1009-6744（2015）03-0107-07

U491.2

A

2015-01-15

2015-03-06錄用日期：2015-03-17

國家自然科學(xué)基金資助項(xiàng)目（51278101）；交通運(yùn)輸部建設(shè)科技項(xiàng)目（2015318J3308）.

任剛(1976-)，男，浙江上虞人，教授，博士.＊通信作者：rengang@seu.edu.cn