溫惠英,邱映寒,趙 勝

(華南理工大學 土木與交通學院,廣州 510641)

近年來,自然和人為災害頻發(fā),城市路網交通疏散已經成為一個重要的課題。當突發(fā)事件發(fā)生時,確定合適安全的疏散計劃是十分必要的。在疏散問題的影響因素研究中,段曉紅等[1]考慮行程時間、交通負荷、路段長度等因素制定交通疏散策略,保證應急車輛調度和疏散救援路徑的可靠性。Zhang等[2]基于交通網絡系統(tǒng)彈性的特點,以最小化所有用戶總行程時間為優(yōu)化目標,生成突發(fā)事件下的路網交通疏散方案。Cassol等[3]以平均疏散時間、總疏散時間等作為疏散性能指標,制定不同仿真環(huán)境下的疏散計劃并加以評估。分析發(fā)現(xiàn),現(xiàn)有文獻中路段的行程時間通常被認為是疏散過程中重要的影響因素,而少有學者結合交叉口車流沖突這一因素考慮。在應急疏散決策方面,部分學者從交通管理角度出發(fā),考慮交叉口沖突消除、轉向限制等交通組織策略[4],對路網交通疏散問題構建雙層規(guī)劃模型,上層確定合適的交通組織方案,下層進行用戶均衡或系統(tǒng)最優(yōu)的交通流分配[5]。還有學者從實時控制的角度,對交通疏散問題進行研究,通過調整信號配時方案來減少不同疏散方向沖突,從而提升疏散效率,例如Yuan等[6]以元胞傳輸模型模擬疏散網絡的交通流演變規(guī)則,使用信號配時優(yōu)化的策略來降低疏散全部交通所需的時間。上述的模型問題求解常使用元啟發(fā)式算法,雖然能較快實現(xiàn)收斂,但是無法評判所求解與最優(yōu)解的偏離程度。設定參數(shù)敏感性較高且操作性較強,每次運行結果的隨機性較大,實際中運用較為困難。而拉格朗日松弛方法[7]可克服此類缺陷,利用優(yōu)化目標上下界之間的相對差值來評價解的質量,具有調參處理方便、穩(wěn)定性好等優(yōu)點。此外,目前的研究大多為確定性規(guī)劃問題,問題參數(shù)的設置往往是先驗已知的,而參數(shù)改變產生的波動性對疏散計劃的影響較大,可能導致模型不再適用。因此,基于不確定性的路網交通疏散策略研究更具現(xiàn)實意義。在疏散問題不確定性的研究方面,Lim等[8]考慮疏散撤離人員需求的不確定性,構建了一種分布式魯棒機會約束模型來制定可靠的疏散策略。Yang等[9]以多優(yōu)先級元胞傳輸模型為基礎,基于疏散需求的不確定性搭建魯棒優(yōu)化模型,實現(xiàn)疏散響應決策。Lim等[10]則針對道路容量在應急規(guī)劃時的隨機不確定性場景,結合概率弧的容量約束構建最小成本網絡流模型,確保疏散方案的可靠性。以往學者[11]探究的主要是應急疏散需求和道路容量不確定性的影響,往往忽略對交通出行成本不確定性的量化分析。

綜上所述,目前考慮交叉口沖突風險因素的路網交通疏散研究較少,而疏散策略求解大多采用啟發(fā)式算法,且現(xiàn)有針對疏散問題不確定性的研究主要表現(xiàn)在對疏散需求和道路容量的隨機性考慮,較少涉及交通出行成本方面?；诖?本文提出一種考慮出行成本不確定性的路網交通疏散策略。通過創(chuàng)建新型時空耦合網絡圖,引入行程時間和沖突風險因素,從而對交通出行成本不確定性加以量化,結合邊際約束搭建魯棒優(yōu)化模型,運用模型重構技術和改進的拉格朗日近似求解算法對模型進行優(yōu)化求解,最后結合數(shù)值算例驗證了模型的有效性。研究成果豐富了魯棒優(yōu)化和交通疏散決策相結合的有關理論,有助于降低突發(fā)事件造成的生命財產損失,可為應急指揮部門制定疏散處置方案提供依據(jù)。

1 問題描述

1.1 時空耦合網絡圖創(chuàng)建

本文基于路段出行和節(jié)點等待的時空邏輯關系,提出了一種新型時空耦合網絡圖的創(chuàng)建方法,進而對路網交通疏散問題加以建模。下面以圖1中的示例進行說明[12],G(N,A)表示物理網絡,疏散起點編號為0,疏散需求為20,災害發(fā)生時需要通過指定的計劃將車輛從起點0疏散到安全終點編號為A和B的位置。0到1弧段的標注(2,5)表示的是路段行程時間se=2和通行能力ue=5。

圖1 疏散網絡

時空網絡圖Gx=(Nx,Ax)的創(chuàng)建過程如下:1)首先,將疏散撤離的允許時長離散劃分為多個等長的時間區(qū)間,即用步長集合H={1,…,T}表示,這里T為離散后的最大時間步。2)其次,在每一個時間步內,對道路網絡的所有空間節(jié)點加以復制,即拓展成空間-時間節(jié)點(i,t)形式;同時物理弧段e=(i,j)用關聯(lián)的時空弧代替,即et=((i,t),(j,s)),其中,索引(i,t)表示的是i節(jié)點t時刻,(j,s)表示的是j節(jié)點s時刻,路段行程時間為se=s-t。3)所有的終點需要連接到一個超級虛擬終點vt=(z,T),用以接受所有的疏散交通車流的需求,連接的虛擬弧段通行能力設為無窮大,其出行時間置為0。

簡要的疏散過程如圖2所示,其中弧段邊標注的是通行能力。本文對時空耦合網絡圖作了改進,增加了時空通行弧和等待弧的連接。對于中間的時空節(jié)點來說,在原先單一行程時間弧et=((i,t),(j,s))的基礎上,增加了(i,t)到節(jié)點(j,s-1)和(j,s+1)的通行弧,使得路段行程時間的可選擇范圍變大;另外,對中間時空節(jié)點添加了等待弧,符號表示為((i,t),(i,t+1))。因此,改進的時空耦合網絡圖能更好地描述路段延誤和節(jié)點等待的狀況。

圖2 時空耦合網絡圖

1.2 沖突風險成本范圍估計

時空弧段的成本(費用)通常表示為路段的行程時間,但是如果中間時空節(jié)點的匯入和流出涉及到多條路徑流向,則可能會在該節(jié)點發(fā)生交通沖突。因此,需要對車流沖突風險干擾造成的不確定成本進行度量,記為沖突風險成本。

沖突風險成本定義為基準行程時間下出行效益的增減量。為避免時空出行成本中出現(xiàn)負值,定義沖突風險成本的波動值為

σet=μet·p

(1)

式中:μet為時空弧et索引的路段時間成本,p為沖突風險度量參數(shù),取值為[0,1],若取1,說明沖突風險成本產生的正負增益上限最大;若取0,說明不存在可波動的范圍。為確定p值,本文提出了一種基于沖突信息積的沖突風險度量參數(shù)計算方法,流程如圖3所示。

圖3 沖突風險度量參數(shù)計算過程

圖4 沖突風險度量參數(shù)計算示意

2 優(yōu)化模型構建

本文所構建的模型以最小化總疏散交通的出行成本為目標,網絡流守恒、通行能力等為約束,疏散策略需確定:合適的發(fā)車時間內從疏散起點出發(fā)到安全終點的車輛數(shù),疏散起點出發(fā)到安全終點的疏散路徑以及車道反轉(lane reversal)的部署位置。為便于求解,模型需滿足以下假設:1)疏散過程中道路網絡上車輛的路段行程時間符合預定的區(qū)間范圍;2)根據(jù)合理的預測手段可以事先得出疏散截止時間、路段阻塞時間、通行能力等相關參數(shù)。

2.1 目標函數(shù)

以最小化總交通出行成本為優(yōu)化目標,目標函數(shù):

(2)

2.2 約束條件

模型的建立需考慮如下約束[12-14]:

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

式(3)為路徑連續(xù)性約束,對于某一疏散路徑的起點途徑的任意中間節(jié)點來說,其前序和后序的激活路段的拓撲總數(shù)需保持一致。式(4)和式(5)是網絡流守恒約束,對于疏散起點來說,對應的疏散需求等于出發(fā)的時空起點所連接的所有出度弧車流之和;對于疏散終點,由于終點的到達量未知,因此設置一個虛擬終點來連接。

式(6)、(7)分別代表的是不部署和可部署逆流操作的對應約束。當y(i,j)=1時,則y(j,i)=0,即路段(i,j)被部署逆流,路段通行能力為0,反向路段(j,i)的屬性則是原兩個方向的路段通行能力之和。式(8)說明的是對于一個雙向車輛行駛的路段來說,最多僅允許一個方向被部署車道反轉的逆流操作[15]。式(9)為路段-流量對應約束,如果道路網絡的路段(i,j)不屬于被激活使用的疏散路徑序列,則從疏散起點出發(fā)的時空網絡對應弧的車輛數(shù)為0。式(10)是邊際約束,即各關聯(lián)路段資源權重之和不超過各疏散起點對應路徑資源權重的上限,具體測度可以是路徑距離、行駛所需油耗或排放等。

本文涉及的決策變量:

(11)

文中詳細的符號釋義,可參見表1。

表1 符號說明

2.3 不確定性成本量化

本文對目標函數(shù)中的成本系數(shù)進行了不確定性闡釋[16],令疏散計劃不因出行成本的不確定性而在實施過程中失去意義的同時,不過度影響目標函數(shù)的值。

2.3.1 預算不確定集

不確定性的出行成本變量需借助不確定集來表達,這里以預算不確定集的形式來刻畫,即

(12)

(13)

式中:ret為真實情況的波動程度,Γ為表現(xiàn)不確定性的預算參數(shù),用于調節(jié)優(yōu)化解的魯棒性,以控制解的保守程度。換句話說,Γ的取值也反映出決策者對不確定性因素的態(tài)度。取值越大,說明對成本不確定性波動的顧慮越高,態(tài)度選擇傾向越保守的情況。

2.3.2 min-max模型

因此,考慮不確定性的魯棒對應式(robust counterpart)表達為

minx∈|ε×Ax|,y∈{0,1}n′,z∈{0,1}n″maxr∈ε

(14)

s.t.

c(3-11)

式中c(3-11)表示的是模型約束條件為文中公式(3)～(11),n′與n″分別對應的是對應決策變量下所屬集合的空間長度,n為不確定參數(shù)集的空間長度,小于對應決策變量的集合,原因是考慮到存在部分時空弧始終無風險沖突的情況。

3 方法設計求解

針對上述提出的魯棒優(yōu)化問題,先進行原模型重構[17],將其轉換為等價的混合整數(shù)線性規(guī)劃形式,進而選用改進拉格朗日松弛(adapted Lagrangian relaxation,ALR)方法加以求解。

3.1 原模型重構

引入輔助變量來處理不確定集的絕對值約束,即

(15)

(16)

則原模型等價于:

(17)

(18)

(19)

s.t.

c(3-11)

固定外層變量作為固定參數(shù),將內層線性模型進行對偶,得到內層對偶模型為

上式對偶模型的所有變量均為0時,存在一個有界可行解,即強對偶條件成立。綜上,原min-max問題可等價轉化為

π+λet≥σetxet,?et=1,…,n

π+θet≥-σetxet,?et=1,…,n

π,λet,θet≥0,?et=1,…,n

s.t.

c(3-11)

經推導整理,本文的魯棒優(yōu)化問題可轉化成等價的混合整數(shù)線性規(guī)劃問題。

3.2 拉格朗日松弛

對于混合整數(shù)線性規(guī)劃問題,可采用拉格朗日松弛方法[7]松弛復雜約束,其思想是將原問題解耦為易求解的子問題,為原問題提供下界;并運用啟發(fā)式算法構造原問題的可行解作為上界,不斷更新上下界去收斂逼近高質量的解。

3.2.1 模型松弛

為降低求解難度和保證松弛解質量,將邊際約束加以松弛,則松弛問題的目標函數(shù)為

(20)

相比對原問題作連續(xù)松弛的處理,拉格朗日松弛方法能夠提升解的質量。根據(jù)弱對偶理論,對于任意給定的拉格朗日乘子,松弛問題的最優(yōu)值是原問題的下界。為得到逼近原目標最優(yōu)解的下界,其對偶問題應定義為最大化對偶函數(shù)的形式,即

maxα∈+L(α)

(21)

3.2.2 改進次梯度法求解

對于改進的次梯度法,求解步驟如下。

1)參數(shù)初始化。令拉格朗日乘子α≥0,迭代次數(shù)i=0,上界UB=+∞、下界LB=-∞。

2)子問題求解并求出目標上下界。對松弛子問題計算求解,進而代入松弛問題得出目標數(shù)值,從而更新原問題的模型下界(LB)并判斷:如果松弛子問題的解對于原問題可行(即不違反松弛約束),代入并更新原問題的模型上界(UB);否則,構造啟發(fā)式算法修復,尋找可行解來更新原模型上界。

3)對偶問題求解。利用次梯度法求解對偶問題,即

(22)

式中:g(i)為第i次迭代的次梯度,δ(i)為第i次迭代的步長。次梯度法作為經典的方法,存在收斂速度慢、效果差等問題,為提升收斂效率,本文改進步長[18]計算的方法,公式為

(23)

4)計算差值。輸出上下界的相對差值(Gap),并結合終止條件判決,若收斂精度滿足,算法中止;否則,返回第2)步繼續(xù)。

設計流程如圖5所示。

圖5 算法流程

4 算例研究

為驗證模型及算法的有效性,本文選用SiouxFalls網絡[2]來測試(圖6)并附加設定5個疏散起點,4個安全終點,疏散的時間步長間隔設為20 s,此外還包括有路段通行能力、道路長度、路段阻塞時間、截止出發(fā)時間、邊際約束相關的路段資源權重等參數(shù)的設定。路段通行能力和道路長度可根據(jù)實際道路及交通條件設定,通過地圖數(shù)據(jù)接口獲取。路段阻塞時間[19]是路段因突發(fā)事件(如惡劣天氣、交通事故等)可能發(fā)生交通中斷的時刻,截止出發(fā)時間則結合實際疏散的限制時間確定。邊際約束相關的路段資源權重[13]根據(jù)實際疏散要求,可以是路段長度、路段允許訪問資源點數(shù)等。

圖6 測試網絡算例

4.1 結果分析

實驗設定3種確定性疏散問題的場景,并進行不同場景優(yōu)化的效果對比。其中,場景編號越大,疏散總需求和疏散仿真運行的時間也在增加。經計算求解,結果見表2。

表2 確定性場景基準結果

4.1.1 不確定集規(guī)模對出行成本的影響

3個場景下的不確定集規(guī)模大小n分別對應是31 000,63 805,97 775。假定Γ為500,收斂精度為10%,分析不同建模場景的不確定集規(guī)模對出行成本的影響。

由圖7可知,隨著不確定集和模型規(guī)模的增加,交通疏散的總行程時間成本和總沖突風險成本也增大。對于行程時間成本來說,不確定集規(guī)模小范圍(31 000,63 805)的增長速率為2.30,不確定集規(guī)模大范圍(63 805,97 775)的增長速率為2.97,增長速率提升約29.13%。對于沖突風險成本來說,不確定集規(guī)模的范圍較小時,沖突風險成本從51.35增長到63.62,增長速率較慢;而不確定集規(guī)模的范圍較大時,沖突風險成本從63.62增長到了106.37,增長速率較快,增速提升約236.46%。模型和不確定集的規(guī)模越大,疏散模型的總出行成本增速就越快,沖突風險成本的增速提高相比于行程時間成本的增速提高較為明顯,約為8∶1。因此,在預算參數(shù)為定值的情況下,將不確定集大小與模型規(guī)模穩(wěn)定在合理的范圍內,能控制模型的不確定性成本維持在一定的水平。

圖7 不確定集規(guī)模對出行成本的影響

4.1.2 預算參數(shù)對模型魯棒性的影響

以場景2為例,通過調節(jié)預算參數(shù)Γ,來分析對模型魯棒性的影響。根據(jù)魯棒性指標[13],為保證擾動下的解大概率可行,對違背不確定性的邊界概率進行估計。這里的違背意味的是當目標成本系數(shù)不確定時,目標函數(shù)值較為敏感,優(yōu)化效果不佳,即難以在可接受程度內制定疏散任務計劃的含義,近似認為模型失效,結果見表3。

表3 預算參數(shù)對模型魯棒性影響

表3顯示的是隨著Γ取值增加,違背邊界概率降低,解的魯棒性增大,總出行成本呈現(xiàn)波動上升趨勢。當取值過大時,如500以上,模型考慮的魯棒性較強,違背概率較低,但目標函數(shù)最優(yōu)性較差,偏離標稱值在1 800以上;當取值過小時,如低于100,則違背概率值較高,在35%以上,模型魯棒性較差,參數(shù)波動導致模型失效的可能性較大。因此,本實驗Γ取值在300～400之間,模型綜合性能評估較好,兼顧解的魯棒性和最優(yōu)性。

4.2 算法評估

為說明改進拉格朗日松弛(ALR)方法的優(yōu)點,選擇場景1且假定Γ=300,與拉格朗日松弛方法(LR)作對比,結果如圖8所示。圖8表示的是在迭代過程中,ALR和LR方法的相對差值和步長大小的變化情況。分析發(fā)現(xiàn),在第10次迭代的時候ALR完成收斂,而LR則是在第18次迭代才達到收斂,收斂速度較快。在收斂過程中,ALR的相對差值從10.72%逐漸減小到4.44%,LR則從17.63%到4.51%。在步長選擇上,在前8次迭代時LR的步長搜索范圍較大,數(shù)值振蕩較明顯,在0～40之間;而ALR步長數(shù)值的更新較為平穩(wěn),搜索范圍在0～2之間,搜索方向更為精確。因此,ALR方法相比于LR方法的收斂速度和收斂精度明顯較優(yōu)。

圖8 不同方法的步長和相對差值對比

為驗證所述算法在更大規(guī)模算例中的適用性,本文選取南京部分路網(圖9),在兩種疏散需求和疏散時間設置的場景下,對程序的運行時間、迭代收斂次數(shù)和相對差值的性能指標進行對比,結果見表4。

表4 不同方法在較大規(guī)模網絡算例的性能指標對比

圖9 南京部分路網示意圖

結果表明,相比于LR方法,ALR方法的迭代收斂次數(shù)和相對差值指標更小,且運行時間更少。不同場景對比下,ALR方法的運行時間相比LR方法分別減少了24.8%和11.1%,ALR方法的相對差值相比LR方法分別減少了13.0%和17.8%。在較大規(guī)模網絡的算法性能測試中,隨著問題規(guī)模的增大,運行時間和相對差值指標隨之增加,ALR方法在收斂速度和收斂精度方面仍能表現(xiàn)出較為明顯的優(yōu)勢。

5 結 論

本文在考慮出行成本不確定性的基礎上,構建基于邊際約束的城市路網交通疏散模型并設計算法求解驗證,豐富了以往相關問題的理論研究,對現(xiàn)實中疏散策略的制定更具參考價值。得出主要結論如下:

1)模型的總出行成本受不確定集大小和模型規(guī)模所影響,數(shù)值越大則行程時間和沖突風險成本增速均有提高,且沖突風險成本的增速提高值大于行程時間成本的增速提高值。

2)場景2實驗結果表明,預算參數(shù)控制在300～400之內,能較好地保證解的魯棒性和最優(yōu)性。

3)所提出的ALR算法性能表現(xiàn)良好,能在一定的迭代次數(shù)內收斂到近似最優(yōu)解。相比于傳統(tǒng)LR方法,在收斂速度和收斂精度方面有一定的提升。