考慮出行成本不確定性的路網(wǎng)交通疏散策略

溫惠英,邱映寒,趙 勝

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

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

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

1 問題描述

1.1 時空耦合網(wǎng)絡(luò)圖創(chuàng)建

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

圖1 疏散網(wǎng)絡(luò)

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

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

圖2 時空耦合網(wǎng)絡(luò)圖

1.2 沖突風(fēng)險成本范圍估計

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

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

σet=μet·p

(1)

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

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

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

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

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

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

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

(2)

2.2 約束條件

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

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

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

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

本文涉及的決策變量:

(11)

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

表1 符號說明

2.3 不確定性成本量化

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

2.3.1 預(yù)算不確定集

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

(12)

(13)

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

2.3.2 min-max模型

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

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

(14)

s.t.

c(3-11)

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

3 方法設(shè)計求解

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

3.1 原模型重構(gòu)

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

(15)

(16)

則原模型等價于:

(17)

(18)

(19)

s.t.

c(3-11)

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

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

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

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

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

s.t.

c(3-11)

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

3.2 拉格朗日松弛

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

3.2.1 模型松弛

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

(20)

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

maxα∈+L(α)

(21)

3.2.2 改進(jìn)次梯度法求解

對于改進(jìn)的次梯度法,求解步驟如下。

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

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

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

(22)

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

(23)

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

設(shè)計流程如圖5所示。

圖5 算法流程

4 算例研究

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

圖6 測試網(wǎng)絡(luò)算例

4.1 結(jié)果分析

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

表2 確定性場景基準(zhǔn)結(jié)果

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

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

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

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

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

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

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

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

4.2 算法評估

為說明改進(jìn)拉格朗日松弛(ALR)方法的優(yōu)點(diǎn),選擇場景1且假定Γ=300,與拉格朗日松弛方法(LR)作對比,結(jié)果如圖8所示。圖8表示的是在迭代過程中,ALR和LR方法的相對差值和步長大小的變化情況。分析發(fā)現(xiàn),在第10次迭代的時候ALR完成收斂,而LR則是在第18次迭代才達(dá)到收斂,收斂速度較快。在收斂過程中,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 不同方法的步長和相對差值對比

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

表4 不同方法在較大規(guī)模網(wǎng)絡(luò)算例的性能指標(biāo)對比

圖9 南京部分路網(wǎng)示意圖

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

5 結(jié) 論

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

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

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

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