截?cái)嚯S機(jī)出行時(shí)間下可靠網(wǎng)絡(luò)均衡模型

凃 強(qiáng) 程 琳 孫 超 唐 芳 李嫚嫚

(1東南大學(xué)交通學(xué)院, 南京 210096)(2江蘇大學(xué)汽車與交通工程學(xué)院, 鎮(zhèn)江 212013)

不確定環(huán)境下的交通網(wǎng)絡(luò)建模一直是交通領(lǐng)域的研究熱點(diǎn),受到出行需求和道路通行能力變化的影響,起訖點(diǎn)(origin-destination,O-D)之間的路徑出行時(shí)間也會(huì)在一定范圍內(nèi)波動(dòng)[1].面對(duì)隨機(jī)交通網(wǎng)絡(luò),出行者表現(xiàn)出風(fēng)險(xiǎn)規(guī)避行為,不僅關(guān)注出行時(shí)間的期望值,同時(shí)也關(guān)注出行時(shí)間的可靠性[2],在此基礎(chǔ)上主要有2類路徑選擇行為:① 一定可靠度下,選擇出行時(shí)間預(yù)算最小的路徑[3-4];② 一定出行時(shí)間預(yù)算下,選擇準(zhǔn)時(shí)到達(dá)概率最高的路徑[5-6].相應(yīng)的交通分配模型主要關(guān)注第①類路徑選擇行為,包括出行時(shí)間預(yù)算(travel time budget,TTB)模型、均值-超額出行時(shí)間(mean-excess travel time,METT)模型、遲到懲罰用戶均衡(late arrive penalty user equilibrium,LAPUE)模型等[7-9];針對(duì)第②類路徑選擇行為的交通分配模型較少,僅有Sun等[10]提出的基于可靠性的有限理性用戶均衡模型,但并沒(méi)有考慮隨機(jī)出行時(shí)間的有界性.

現(xiàn)有模型大多使用中心極限定理估計(jì)路徑出行時(shí)間分布,其假設(shè)路段出行時(shí)間相互獨(dú)立,從而路徑出行時(shí)間近似服從正態(tài)分布.但是根據(jù)正態(tài)分布的特征,出行時(shí)間有小概率出現(xiàn)負(fù)值或者無(wú)窮大的極端情況,忽略了路徑隨機(jī)出行時(shí)間的有界性,與現(xiàn)實(shí)情況不符.關(guān)注隨機(jī)出行時(shí)間的有界性,姚志洪等[11]采用實(shí)測(cè)和仿真數(shù)據(jù),對(duì)出行時(shí)間的不確定性進(jìn)行估計(jì),發(fā)現(xiàn)截?cái)嗾龖B(tài)分布具有很好的擬合效果;Xu等[12]考慮路段限速,以限速下的路段出行時(shí)間為下界,將截?cái)嚯S機(jī)出行時(shí)間分布應(yīng)用到了METT模型中,分析了路段限速對(duì)不確定環(huán)境下交通網(wǎng)絡(luò)的影響;在此基礎(chǔ)上,Zhao等[13]將自由流出行時(shí)間作為下界,建立了一個(gè)TTB-SUE(travel time budget based stochastic user equilibrium)模型.綜上,現(xiàn)有交通分配模型對(duì)于出行時(shí)間的有界性考慮較少,且僅考慮了出行時(shí)間下界對(duì)于交通網(wǎng)絡(luò)流量分布的影響,同時(shí)忽略了對(duì)第②類路徑出行選擇行為的影響.

對(duì)于通勤出行者而言,出發(fā)時(shí)刻確定的條件下,更加關(guān)注在出行時(shí)間預(yù)算內(nèi)準(zhǔn)時(shí)到達(dá)目的地的概率,以避免遲到帶來(lái)的懲罰,這種情況下第②類路徑出行選擇行為更具有現(xiàn)實(shí)意義.而出行時(shí)間分布的上界可以視作交通網(wǎng)絡(luò)面對(duì)不確定情況的可靠性,一定程度上反映了交通管理和控制水平,比如地鐵等軌道交通相比地面小汽車交通具有更高的可靠性.基于此,本文將同時(shí)考慮這2個(gè)要素,建立截?cái)嚯S機(jī)出行時(shí)間下的可靠網(wǎng)絡(luò)均衡模型,并對(duì)比分析出行時(shí)間上界對(duì)于網(wǎng)絡(luò)流量分布和準(zhǔn)時(shí)到達(dá)概率的影響.

1 問(wèn)題描述與網(wǎng)絡(luò)建模

1.1 截?cái)嚯S機(jī)出行時(shí)間

考慮隨機(jī)交通網(wǎng)絡(luò)G(N,A),其中,N為節(jié)點(diǎn)集合,A為路段集合,路段出行時(shí)間Ta采用BPR函數(shù)表示,即

(1)

(2)

(3)

(4)

(5)

式中,δa,k為路段路徑關(guān)聯(lián)系數(shù),當(dāng)路徑k經(jīng)過(guò)路段a時(shí),δa,k=1,否則δa,k=0.

采用正態(tài)分布描述路徑出行時(shí)間的明顯缺陷在于出行時(shí)間可能出現(xiàn)較小(甚至負(fù)值)和無(wú)窮大的情況,考慮到路徑出行時(shí)間的有界性,采用截?cái)嗾龖B(tài)分布描述出行時(shí)間分布更加符合真實(shí)情況,其概率密度函數(shù)可表示為

(6)

(7)

(8)

1.2 準(zhǔn)時(shí)到達(dá)概率

對(duì)于通勤出行者而言,制定完成出行時(shí)間預(yù)算后,會(huì)選擇準(zhǔn)時(shí)到達(dá)概率更高的路徑以避免遲到懲罰.出行時(shí)間預(yù)算定義為最小路徑期望出行時(shí)間和緩沖時(shí)間之和,其表達(dá)式如下:

(9)

式中,bw為O-D對(duì)w的出行時(shí)間預(yù)算;ε為緩沖時(shí)間,表示期望出行時(shí)間之外的預(yù)留時(shí)間,以避免期望之外的延誤而造成遲到.

(10)

式中,Pr{B}為事件B的概率.

1.3 可靠網(wǎng)絡(luò)均衡模型

在隨機(jī)交通網(wǎng)絡(luò)中,給定出行時(shí)間預(yù)算下,每個(gè)出行者都試圖選擇準(zhǔn)時(shí)到達(dá)概率最大的路徑,交通網(wǎng)絡(luò)將達(dá)到這樣一個(gè)均衡狀態(tài):同一O-D對(duì)中所有使用路徑的準(zhǔn)時(shí)到達(dá)概率相等且最大,不小于所有未使用路徑的準(zhǔn)時(shí)到達(dá)概率,任何出行者都不可以通過(guò)單方面調(diào)整路徑提高準(zhǔn)時(shí)到達(dá)概率,即

(a) 概率密度分布

(b) 累積概率分布

(11)

令h∈Ω={Δh=q,h≥0,q≥0},其中,h為路徑流量向量,Ω為可行域,q為交通需求向量,Δ為路徑流量和交通需求關(guān)系矩陣,則均衡條件可以等價(jià)表示為如下的變分不等式模型:

〈ρT,(h*-h)〉≥0

(12)

式中,h*為均衡狀態(tài)下的路徑流量向量;ρ為路徑準(zhǔn)時(shí)到達(dá)概率向量.

式(12)等價(jià)于ρTh≤ρTh*,因此,h*是變分不等式模型式(12)的解,當(dāng)且僅當(dāng)h*是如下線性規(guī)劃問(wèn)題的解:

(13)

進(jìn)一步考慮上述線性規(guī)劃問(wèn)題標(biāo)量形式的拉格朗日函數(shù),即

(14)

式中,W為O-D對(duì)集合;Kw為O-D對(duì)w間的路徑集合;qw為O-D對(duì)w間的交通需求.

由此可以得到上述線性規(guī)劃問(wèn)題的Karush-Kuhn-Tucker(KKT)條件為

(15)

顯然式(15)等價(jià)于均衡條件式(11)，由此證明了變分不等式模型式(12)等價(jià)于均衡條件式(11).

2 求解算法

網(wǎng)絡(luò)均衡問(wèn)題的求解方法包括基于路段和基于路徑的算法.基于路段的求解算法中,每次迭代都需要對(duì)網(wǎng)絡(luò)中的每個(gè)O-D求解一次最短路徑問(wèn)題,由于隨機(jī)網(wǎng)絡(luò)中可靠最短路徑求解過(guò)程較為復(fù)雜且耗時(shí)較長(zhǎng)(尤其在大規(guī)模網(wǎng)絡(luò)中)[14],因此,基于路段的求解算法實(shí)現(xiàn)較為困難,其應(yīng)用也較少.目前,求解隨機(jī)網(wǎng)絡(luò)中的均衡問(wèn)題主要采用基于路徑的方法,其主要思想是預(yù)先生成一個(gè)工作路徑集合,每次迭代過(guò)程中只需要比較O-D間路徑集合中所有路徑的目標(biāo)函數(shù)值(如本文為準(zhǔn)時(shí)到達(dá)概率),然后選出最優(yōu)路徑,從而簡(jiǎn)化了最短路徑的求解過(guò)程[15],大大縮減了均衡問(wèn)題的求解時(shí)間.工作路徑集合的生成大多采用Bekhor等[16]提出的方法.此外,隨著數(shù)據(jù)檢測(cè)技術(shù)的發(fā)展,基于GPS等高精定位技術(shù)的車輛軌跡識(shí)別也為O-D間的工作路徑集合生成提供了新的思路[17].

MSA算法是一類求解網(wǎng)絡(luò)均衡問(wèn)題的通用迭代算法框架,具有很好的收斂特性[18].結(jié)合前文所述,本文采用基于路徑的MSA算法求解網(wǎng)絡(luò)均衡問(wèn)題,其步驟如下：

① 初始化.計(jì)算零流量下,路徑初始準(zhǔn)時(shí)到達(dá)概率ρ,對(duì)交通需求q在路網(wǎng)上進(jìn)行全有全無(wú)分配,得到初始路徑流量h(0),設(shè)置迭代次數(shù)m=0.

② 更新路徑準(zhǔn)時(shí)到達(dá)概率.根據(jù)路徑和路段流量關(guān)系,計(jì)算第m次迭代的路段流量x(m),按照式(2)～(10)更新路徑準(zhǔn)時(shí)到達(dá)概率ρ.

③ 確定方向.根據(jù)更新的路徑準(zhǔn)時(shí)到達(dá)概率,進(jìn)行全有全無(wú)分配,得到第m次迭代的輔助路徑流量h(m)′.

④ 更新路徑流量.計(jì)算第m+1次迭代的路徑流量h(m+1)=h(m)+λ(m)(h(m)′-h(m)),其中λ(m)為步長(zhǎng),λ(m)=1/m.

⑤收斂判斷.若‖h(m+1)-h(m)‖/‖h(m)‖≤e,e為預(yù)定義的收斂精度，算法終止,h(m+1)為最優(yōu)解;否則令m=m+1,轉(zhuǎn)至步驟②.

3 算例分析

表1 Nguyen-Dupuis網(wǎng)絡(luò)路段數(shù)據(jù)

首先對(duì)算法的收斂性和結(jié)果的有效性進(jìn)行分析.如圖3所示,在運(yùn)算時(shí)間0.15 s左右算法的整體精度達(dá)到了10-3,在1 s左右精度達(dá)到10-4左右.

(a) 整體精度收斂速度

(b) 路徑準(zhǔn)時(shí)到達(dá)概率收斂速度

以路徑1和路徑10(路徑編號(hào)見(jiàn)表2)為例,分析路徑準(zhǔn)時(shí)到達(dá)概率收斂情況,可知在0.3 s左右均能收斂到最優(yōu)解附近,表明算法能夠在短時(shí)間內(nèi)收斂到較高的精度.如表2所示,不管是在ND和TND下,計(jì)算結(jié)果均滿足可靠網(wǎng)絡(luò)均衡狀態(tài)的定義,即所有使用路徑的準(zhǔn)時(shí)到達(dá)概率都是最大且相等的,說(shuō)明了可靠網(wǎng)絡(luò)均衡模型和MSA算法的有效性.

以O(shè)-D對(duì)1-3和4-2為例,表2對(duì)比了ND和TND下模型的路徑數(shù)據(jù)結(jié)果.對(duì)比發(fā)現(xiàn),2個(gè)模型的路徑數(shù)據(jù)結(jié)果存在較大差異:考慮隨機(jī)出行時(shí)間的有界性時(shí),O-D對(duì)1-3的OTAP由0.752上升到0.817,同時(shí)使用路徑由4條變?yōu)?條;O-D對(duì)4-2的OTAP由0.762上升到0.800,同時(shí)使用路徑由3條變?yōu)?條,相應(yīng)地路徑流量分布也發(fā)生了變化.

除了路徑數(shù)據(jù)結(jié)果的變化,路段流量分布的變化情況同樣值得關(guān)注.令ND和TND下路段流量分別為xa,ND和xa,TND,則路段a的流量相對(duì)變化值

表2 ND和TND下模型的路徑數(shù)據(jù)結(jié)果對(duì)比

Ra的計(jì)算方法為

(16)

圖4展示了在ND和TND下19條路段的流量分布的絕對(duì)值和相對(duì)變化值.由圖可知,不同分布假設(shè)下,路段流量分布產(chǎn)生了較大的變化,其中路段8流量的絕對(duì)值和相對(duì)變化值均增長(zhǎng)最多,分別為52.1和38.5%;路段10流量的絕對(duì)值和相對(duì)變化值均減少最多,分別為63.8和15.8%;路段18流量的絕對(duì)變化值和相對(duì)變化值最小,均接近于零.緩沖時(shí)間代表了出行者面對(duì)不確定性的風(fēng)險(xiǎn)規(guī)避水平[8],其取值越大,說(shuō)明出行者風(fēng)險(xiǎn)規(guī)避水平越高;而隨機(jī)出行時(shí)間的上界一定程度上反映了交通管理控制水平,下面對(duì)2個(gè)參數(shù)進(jìn)行敏感性分析.圖5展示了O-D對(duì)1-3和4-2的準(zhǔn)時(shí)到達(dá)概率隨緩沖時(shí)間ε和上界參數(shù)λ的變化情況的曲面圖,可知隨著緩沖時(shí)間的增加和上界參數(shù)的降低,O-D間的準(zhǔn)時(shí)到達(dá)概率將增加.

圖6則展示了準(zhǔn)時(shí)到達(dá)概率的變化曲線圖.首先固定ε=10,上界參數(shù)λ由2變?yōu)?,隨著λ變大,O-D間的準(zhǔn)時(shí)到達(dá)概率逐漸趨于穩(wěn)定,這是由于當(dāng)λ增加到一定程度,出行時(shí)間上界的正態(tài)分布累積概率都很接近于1,由式(7)可知,準(zhǔn)時(shí)到達(dá)概率將趨于穩(wěn)定,其結(jié)果約等于不考慮隨機(jī)出行時(shí)間上界的情況;然后固定λ=2,緩沖時(shí)間ε由零變到15 min,隨著ε變大,O-D間的準(zhǔn)時(shí)到達(dá)概率都將趨于1,并最終等于1,比如當(dāng)ε=15 min時(shí)O-D對(duì)1-2的準(zhǔn)時(shí)到達(dá)概率等于1,而在正態(tài)分布隨機(jī)出行時(shí)間下,準(zhǔn)時(shí)到達(dá)概率只能無(wú)限接近于1.

(a) 路段流量絕對(duì)值

(b) 路段流量相對(duì)變化值

(a) O-D對(duì)1-3

(b) O-D對(duì)4-2

(a) 準(zhǔn)時(shí)到達(dá)概率隨上界參數(shù)變化情況

(b) 準(zhǔn)時(shí)到達(dá)概率隨緩沖時(shí)間變化情況

4 結(jié)論

1) 考慮了隨機(jī)出行時(shí)間分布的有界性,采用截?cái)嗾龖B(tài)分布來(lái)描述路徑出行時(shí)間,分析了路徑準(zhǔn)時(shí)到達(dá)概率的變化情況.

2) 基于準(zhǔn)時(shí)到達(dá)概率建立了可靠網(wǎng)絡(luò)均衡模型,同時(shí)建立了等價(jià)的變分不等式模型,分析了解的存在性,采用MSA算法對(duì)模型進(jìn)行求解.

3) 在Nguyen-Dupuis網(wǎng)絡(luò)中驗(yàn)證了可靠網(wǎng)絡(luò)均衡模型和MSA算法的有效性,ND和TND下的模型結(jié)果存在較大差異,其中最大路段流量相對(duì)變化值達(dá)到38.5%.提高緩沖時(shí)間或者降低出行時(shí)間上界均可有效提升O-D間的OTAP,并最終趨于1.

4) 本文進(jìn)一步可拓展的研究方向有:交通需求不確定下的可靠網(wǎng)絡(luò)均衡模型,多交通模式下的可靠網(wǎng)絡(luò)均衡模型,考慮出行者異質(zhì)性的可靠網(wǎng)絡(luò)均衡模型,日變動(dòng)態(tài)交通網(wǎng)絡(luò)演化模型,以及交通網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題等.