何勝學(xué)

(上海理工大學(xué) 管理學(xué)院，上海200093)

0 引言

現(xiàn)有靜態(tài)交通流分配理論假設(shè)路段行程時(shí)間具有對(duì)于路段流量的單調(diào)遞增特征，因此無(wú)法對(duì)擁擠的路段交通狀態(tài)進(jìn)行合理刻畫(huà).根據(jù)交通流量、密度和速度的基本關(guān)系圖，當(dāng)路段處于擁擠狀態(tài)時(shí)，路段流量與行程時(shí)間應(yīng)具有反向變化關(guān)系，即當(dāng)流量增加時(shí)，行程時(shí)間應(yīng)當(dāng)減少.根源于上述缺陷，現(xiàn)有理論難以對(duì)網(wǎng)絡(luò)交通流的演變進(jìn)行描述分析.本文以反λ基本圖為基礎(chǔ)，提出考慮自由流和擁擠2種狀態(tài)的新交通流分配模型.利用新模型給出了分析網(wǎng)絡(luò)交通流演化的新方法.

靜態(tài)交通流分配理論始于1952年Wardrop提出的出行路徑選擇兩原則，即Wardrop第一原則(用戶(hù)均衡)和Wardrop第二原則(系統(tǒng)最優(yōu))[1].1956年Beckman給出了對(duì)應(yīng)Wardrop第一原則的用戶(hù)均衡交通流分配數(shù)學(xué)模型，即有名的Beckman變換[2].1975年，Leblanc首次給出了求解上述模型的實(shí)用有效Frank-Wolfe算法[2].Dafermos和Sparrow探討了如何利用變分不等式構(gòu)建交通流分配模型[3]；Daganzo和Sheffi最早提出了隨機(jī)交通流分配的理念[4].2002年Bar-Gera提出的基于起點(diǎn)的交通流分配算法大大提高了求解靜態(tài)模型的效率[5].近年來(lái)研究者更多關(guān)注動(dòng)態(tài)交通流分配和一些擬動(dòng)態(tài)交通流分配，例如應(yīng)用投影動(dòng)態(tài)理論對(duì)交通流分配問(wèn)題進(jìn)行建模分析[6-7].為了克服經(jīng)典理論中路段流量可超出路段通行能力的缺陷，研究者提出了一系列基于變分不等式理論的有邊約束的交通流分配模型[8-9].靜態(tài)交通流分配理論中，一般假設(shè)路段行程時(shí)間函數(shù)具有對(duì)于路段流量的單調(diào)遞增特征，而該假設(shè)與路段處于擁擠狀態(tài)時(shí)的情景相矛盾.最近的基于靜態(tài)交通流分配理論的研究也沒(méi)有改變上述假設(shè)，例如文獻(xiàn)[10]假設(shè)路段行程時(shí)間函數(shù)為一般的連續(xù)可微單調(diào)增凸函數(shù)；文獻(xiàn)[11]則利用了經(jīng)典BPR單調(diào)增函數(shù)；而文獻(xiàn)[12]則簡(jiǎn)單利用了線(xiàn)性單調(diào)增函數(shù).流量、密度和速度的基本關(guān)系圖是交通流理論的基礎(chǔ)理論之一，廣泛應(yīng)用于交通研究的各個(gè)領(lǐng)域，例如基于該理論建立的經(jīng)典元胞傳播模型[13-14].

本文主要?jiǎng)?chuàng)新為，基于反λ交通流基本圖建立了新的靜態(tài)交通流分配模型；以新模型為基礎(chǔ)，給出了利用靜態(tài)交通流分配模型分析網(wǎng)絡(luò)交通流演化的新方法.

1 問(wèn)題引入

目前常用的路段行程時(shí)間函數(shù)一般具有如圖1所示的對(duì)于路段流量的單調(diào)遞增特征.基于該類(lèi)行程時(shí)間函數(shù)所建立的交通流分配模型，例如用戶(hù)均衡(User Equilibrium，UE)和系統(tǒng)最優(yōu)(System Optimization，SO)模型，一般具有良好的數(shù)學(xué)性質(zhì)，因此可以被有效求解.從圖1可知，隨著路段流量的增加，車(chē)輛通過(guò)路段的行程時(shí)間不斷增加.研究者希望通過(guò)增函數(shù)的這一性質(zhì)體現(xiàn)道路的擁擠特征.但是該函數(shù)對(duì)現(xiàn)實(shí)的描述存在3個(gè)明確缺陷.首先，可通過(guò)路段的流量有一個(gè)上限，不可能無(wú)限增加.盡管該問(wèn)題可以通過(guò)增加路段通行能力的邊約束得到處理，但是模型的求解將變得更加復(fù)雜.由于“全有全無(wú)”算法需要將起訖點(diǎn)對(duì)間所有流量一次加載于當(dāng)前連接該起訖點(diǎn)對(duì)的最短路上，因此加載到最短路上的路段流量一般會(huì)超過(guò)路段的通行能力.因此嵌套“全有全無(wú)”算法的均衡算法很難被直接用于求解具有路段通行能力約束的模型.其次，現(xiàn)實(shí)中路段的行程時(shí)間在自由流狀態(tài)下一般會(huì)隨著流量的增大而增加，但是增加的幅度一般較小.而目前常用的路段行程時(shí)間函數(shù)雖然假設(shè)隨著流量的增大行程時(shí)間增加，但是隨著流量的增加，行程時(shí)間增長(zhǎng)幅度變得越來(lái)越大.最后，現(xiàn)實(shí)中當(dāng)路段交通處于擁擠狀態(tài)時(shí)，實(shí)際路段的通行能力下降，即隨著流量的減少，路段的行程時(shí)間變得越來(lái)越大.而這一點(diǎn)在圖1所給出的常用路段行程時(shí)間函數(shù)中完全沒(méi)有體現(xiàn).綜上，我們認(rèn)為利用圖1給出行程時(shí)間函數(shù)得到的交通流分配結(jié)果將與現(xiàn)實(shí)存在較大差異.

圖1 常見(jiàn)的路段行程時(shí)間與流量關(guān)系圖Fig.1 The common relation between link travel time and link flow

針對(duì)上述問(wèn)題，我們認(rèn)為在交通流分配時(shí)應(yīng)當(dāng)使用如圖2所示的兩階段行程時(shí)間函數(shù).兩階段行程時(shí)間函數(shù)包括2個(gè)不連續(xù)部分，分別對(duì)應(yīng)自由流狀態(tài)和擁擠狀態(tài).圖2的兩階段行程時(shí)間函數(shù)對(duì)應(yīng)圖3給出的反λ型流—密—速基本關(guān)系圖.顯然，對(duì)應(yīng)不同的流—密—速基本關(guān)系，例如常見(jiàn)的三角形和梯形關(guān)系圖，兩階段行程時(shí)間函數(shù)的具體形式會(huì)存在一定差異.

圖2 兩階段路段行程時(shí)間函數(shù)Fig.2 Link travel time function with two stages

圖3 反λ型流—密—速基本關(guān)系圖Fig.3 The inverseλfundamental diagram

圖3給出的反λ型流—密—速基本關(guān)系體現(xiàn)了路段交通狀態(tài)從自由流狀態(tài)轉(zhuǎn)為擁擠狀態(tài)時(shí)的通行能力失效特征，即圖中交通狀態(tài)從C到B的突變.現(xiàn)代交通流理論，如三相交通流理論，對(duì)上述突變有更深入的分析.鑒于本文研究面向交通規(guī)劃的宏觀(guān)特征，我們認(rèn)為應(yīng)用類(lèi)似圖3給出的線(xiàn)條形非區(qū)塊化基本關(guān)系圖比較合理.假設(shè)路段的長(zhǎng)度為l，則圖2和圖3中的量存在如下關(guān)系：tfree=l/vfree和tcr=l/vcr.

假設(shè)自由流狀態(tài)下，路段行程時(shí)間函數(shù)為t=tfree+αq；而擁擠狀態(tài)下路段行程時(shí)間函數(shù)為t=γ+βq-1.其 中α、β和γ是待定常數(shù).由tcr=tfree+αqcr=l/vcr和基本關(guān)系q=kv，可以基于圖3的特征參數(shù)確定具體的α=(tcr-tfree)qcr=lkcr/qcr2-tfree/qcr；反之，也可以由給定的α值，確定圖3中自由流階段流量和密度的曲線(xiàn)函數(shù).簡(jiǎn)單的推算可知，擁擠狀態(tài)下路段行程時(shí)間函數(shù)t=γ+βq-1與直線(xiàn)型的路段擁擠階段流量和密度的關(guān)系相對(duì)應(yīng)，且有β=lkjam和γ=l(kmax-kjam)qmax成立.

2 路段交通狀態(tài)已知的交通流分配模型

交通分配模型相關(guān)的參變量如下：

a∈A——指代有向路段a，A為所有的有向路段集合；

n∈N——指代節(jié)點(diǎn)n，N為所有節(jié)點(diǎn)集合；

b∈B——指代起訖點(diǎn)(Origin and Destination，OD)對(duì)b，B為所有OD對(duì)的集合；

qb——OD對(duì)b的交通需求流量；

xa——路段a上的流量；

δa∈{0,1}—— 路段a的交通狀態(tài)指示量，當(dāng)δa=1時(shí)，路段a的交通狀態(tài)為自由流狀態(tài)，否則，路段a的交通狀態(tài)為擁擠狀態(tài)；——擁擠狀態(tài)下路段a的最大通行流量；

Δ＞0——為給定的擁擠狀態(tài)下的路段最小通行流量.

相關(guān)的約束包括：

式(1)～式(3)分別為一般節(jié)點(diǎn)、OD對(duì)起點(diǎn)和OD對(duì)終點(diǎn)的交通流守恒方程；式(4)是路段流量和約束；式(5)和式(6)是路段流量和的上下限約束；式(7)限定路段交通狀態(tài)指示參數(shù)為0-1變量.

與出行者的擇路行為對(duì)應(yīng)，可以給出2個(gè)不同的目標(biāo)函數(shù).式(8)對(duì)應(yīng)SO，式(9)則對(duì)應(yīng)UE.

為了方便表述，將以式(8)為目標(biāo)函數(shù)的配流模型稱(chēng)為新系統(tǒng)最優(yōu)模型，而將以式(9)為目標(biāo)函數(shù)的配流模型稱(chēng)為新用戶(hù)均衡模型.

定理1如果對(duì)于任意路段a在自由流階段的行程時(shí)間函數(shù)為而在擁擠狀態(tài)的行程時(shí)間函數(shù)形式為ta=γa+βa xa-1，且已知路段交通狀態(tài)δa，?a∈A，那么系統(tǒng)最優(yōu)的交通流分配模型為凸二次規(guī)劃.

證明當(dāng)路段交通狀態(tài)δa，?a∈A已知時(shí)，約束集為線(xiàn)性單純形.顯然對(duì)應(yīng)自由流狀態(tài)的目標(biāo)函數(shù)部分為變量的二次函數(shù)，而對(duì)應(yīng)擁擠狀態(tài)的目標(biāo)函數(shù)部分為變量的線(xiàn)性函數(shù).綜上結(jié)論可證.

定理2如果對(duì)于任意路段a在自由流階段的行程時(shí)間函數(shù)為在擁擠狀態(tài)的行程時(shí)間函數(shù)形式為ta=γa+βa xa-1，所有δa，?a∈A已知，且至少有交通狀態(tài)δc=0，?c∈A，那么用戶(hù)均衡的交通流分配模型為非凸規(guī)劃.

證明對(duì)應(yīng)δc=0的目標(biāo)函數(shù)加和項(xiàng)為而該項(xiàng)為變量x的凹函c數(shù).易知結(jié)論成立.

由定理1可知新系統(tǒng)最優(yōu)模型為凸二次規(guī)劃.該類(lèi)問(wèn)題可以被非常有效的求解.而由定理2可知新用戶(hù)均衡模型實(shí)質(zhì)上均為帶有線(xiàn)性約束的非凸規(guī)劃問(wèn)題.對(duì)于該類(lèi)問(wèn)題目前也已有一些比較有效的算法，例如可以通過(guò)KKT松弛或半定規(guī)劃松弛得到相應(yīng)的線(xiàn)性模型，利用分支定界法求解.在已知各種函數(shù)的具體形式后，也可以采取更有針對(duì)性地求解算法.例如當(dāng)約束為線(xiàn)性緊約束時(shí)，可以結(jié)合KKT條件松弛與正交變換變量替代設(shè)計(jì)更加有效的分支定界法對(duì)問(wèn)題求解.

3 基于新模型的網(wǎng)絡(luò)交通狀態(tài)演化分析法

如果已知路段的交通狀態(tài)，可以利用上節(jié)的優(yōu)化模型求解具體的網(wǎng)絡(luò)流量分布.但是如果δa，?a∈A未知，就不能直接利用已有模型求解流量分布.

靜態(tài)配流模型假設(shè)OD對(duì)需求流量在一定時(shí)間段內(nèi)維持穩(wěn)定，因此模型求解的結(jié)果反映了穩(wěn)定OD需求下交通流的網(wǎng)絡(luò)分布狀態(tài).從實(shí)際網(wǎng)絡(luò)交通演化的角度看，如果發(fā)生擁堵，必然存在一個(gè)路段交通狀態(tài)由自由流轉(zhuǎn)變?yōu)閾頂D狀態(tài)的過(guò)程，且根據(jù)OD需求持續(xù)時(shí)間的長(zhǎng)度，擁擠區(qū)域會(huì)存在一個(gè)擴(kuò)大與消減的過(guò)程.可以利用上節(jié)給出的已知路段交通狀態(tài)的交通流分配模型對(duì)上述演化過(guò)程進(jìn)行模擬.下面定義中的新分配模型可根據(jù)實(shí)際指代新系統(tǒng)最優(yōu)模型或新用戶(hù)均衡模型.

定義 1令δa=1，?a∈A，求解新分配模型.如果得到的路段流量滿(mǎn)足則稱(chēng)該網(wǎng)絡(luò)為自由流網(wǎng)絡(luò)；如果則稱(chēng)該網(wǎng)絡(luò)為一級(jí)擁擠網(wǎng)絡(luò)；如果模型無(wú)解，則稱(chēng)該網(wǎng)絡(luò)為一級(jí)失效網(wǎng)絡(luò).對(duì)于一級(jí)擁擠網(wǎng)絡(luò)，稱(chēng)路段集合為網(wǎng)絡(luò)一級(jí)瓶頸.

定義 2在得到n級(jí)擁擠網(wǎng)絡(luò)后，令δa=0，求解對(duì)應(yīng)上述δa值的新分配模型.如果得到的路段流量滿(mǎn)足則稱(chēng)該網(wǎng)絡(luò)為完全n級(jí)擁擠網(wǎng)絡(luò)；如果則稱(chēng)該網(wǎng)絡(luò)為n+1級(jí)擁擠網(wǎng)絡(luò)；如果模型無(wú)解，則稱(chēng)該網(wǎng)絡(luò)為n+1級(jí)失效網(wǎng)絡(luò).對(duì)于n+1級(jí)擁擠網(wǎng)絡(luò)，稱(chēng)集合為網(wǎng)絡(luò)n+1級(jí)瓶頸.

上述的2個(gè)定義暗含了如何利用新配流模型對(duì)網(wǎng)絡(luò)交通流的演化進(jìn)行分析的方法.網(wǎng)絡(luò)實(shí)際的交通擁堵區(qū)域的形成應(yīng)與上述定義的遞增式的擁堵區(qū)求解一致，實(shí)際擁堵區(qū)域的范圍與OD間交通需求量持續(xù)的時(shí)間長(zhǎng)短有關(guān).而網(wǎng)絡(luò)擁堵消散的過(guò)程應(yīng)與遞增式的擁堵區(qū)求解相逆.當(dāng)兩階段優(yōu)化模型無(wú)解時(shí)，表示網(wǎng)絡(luò)最大瓶頸通行能力小于OD對(duì)間的交通需求，流量不能完全加載上網(wǎng)，部分流量必須在起點(diǎn)排隊(duì)等待.

4 算例分析

本節(jié)以新用戶(hù)均衡模型為例對(duì)第3節(jié)的網(wǎng)絡(luò)交通狀態(tài)演化分析方法進(jìn)行驗(yàn)證.設(shè)時(shí)間單位為h，距離單位為km，流量單位為pcu/h，速度的單位為km/h，這里pcu表示標(biāo)準(zhǔn)小汽車(chē)單位.求解算法利用Lingo語(yǔ)言實(shí)現(xiàn)，其中的二次規(guī)劃模型的求解直接利用Lingo軟件的自帶程序?qū)崿F(xiàn).因此計(jì)算的效率與軟件自帶的算法密切相關(guān)，對(duì)于隨后給出的簡(jiǎn)單算例，得到最終結(jié)果需要的時(shí)間少于6 s.

圖4給出了一個(gè)簡(jiǎn)單交通網(wǎng)絡(luò).其中路段的交通流方向用箭頭表示.假設(shè)節(jié)點(diǎn)1和3為起點(diǎn)，節(jié)點(diǎn)5、6和7為終點(diǎn).網(wǎng)絡(luò)存在4對(duì)OD對(duì)，分別為(1,6)、(1,7)、(3,5)和(3,7).對(duì)應(yīng)上述OD對(duì)的交通需求量分別為1 200、1 800、500和600 pcu/h.表1給出了對(duì)應(yīng)10條路段的各種參變量值.表1中第1列用路段的前后2個(gè)端點(diǎn)構(gòu)成有序?qū)Ρ硎緦?duì)應(yīng)路段.

圖4 有7個(gè)節(jié)點(diǎn)的交通網(wǎng)絡(luò)Fig.4 Traffic network with 7 nodes

表1 路段相關(guān)參數(shù)Table 1 Coefficients of links

表2 路段不同狀態(tài)下的計(jì)算平衡流量Table 2 The equilibrium link flow under different link states

按照第3節(jié)給出的分析思路，首先假設(shè)所有路段處于自由流狀態(tài)，計(jì)算得到路段的平衡流量，如表2中情景1下的xa列，此時(shí)路段(1,2)和(3,6)達(dá)到了自由流流量的上限.因此假設(shè)上述2條路段處于擁擠狀態(tài)，計(jì)算得到路段的平衡流量，如表2中情景2下的xa列.情景2下，路段(3,4)達(dá)到自由流流量上限，因此進(jìn)一步假設(shè)該路段也進(jìn)入擁擠交通流狀態(tài)，即設(shè)定新的情景3.情景3的計(jì)算表明，路段(1,3)達(dá)到自由流流量上限，因此進(jìn)一步假設(shè)該路段也進(jìn)入擁擠交通流狀態(tài)，得到情景4.對(duì)情景4進(jìn)行計(jì)算，得到結(jié)果如表2中情景4下的xa列.此時(shí)沒(méi)有新的路段平衡流量達(dá)到自由流流量上限.因此，可以得出網(wǎng)絡(luò)在完全4級(jí)擁擠網(wǎng)絡(luò)，對(duì)應(yīng)的4級(jí)擁擠瓶頸包括路段(1,2)、(3,6)、(3,4)和(1,3).上述 4種情景對(duì)應(yīng)的UE目標(biāo)函數(shù)值分別為544.22、5 418.69、7 131.43和10 362.75.

5 結(jié)論

以反λ型流—密—速基本關(guān)系圖為基礎(chǔ)，得到新的兩階段路段行程時(shí)間函數(shù)，進(jìn)而建立對(duì)應(yīng)靜態(tài)交通流分配模型.依據(jù)新模型給出了不斷更新網(wǎng)絡(luò)路段交通狀態(tài)，動(dòng)態(tài)分析網(wǎng)絡(luò)交通演變的方法.算例分析驗(yàn)證了新模型與分析方法的可行性.理論提供了網(wǎng)絡(luò)交通流分析的新思路，但理論的完善還有待進(jìn)一步的實(shí)證數(shù)據(jù)驗(yàn)證.

[1]WARDROP J.Some theoretical aspects of road traffic research[J].Proceedings of the Institution of Civil Engineers,1952,1(36):325-378.

[2]SHEFFI Y.Urban transportation networks:equilibrium analysis with mathematical programming methods[M].New Jersey：Prentice-Hall,1985.

[3]DAFERMOSS C,SPARROW F T.The traffic assignment problem for a general network[J].J.Res.Natl.Bureau Stand.,Ser.B,1969,73(2):91-118.

[4]DAGANZO C F,SHEFFI Y.On stochastic models of traffic assignment[J].Transportation Science,1977,11(3):253-274.

[5]BAR-GERA H.Origin-based algorithm for the traffic assignment problem[J].Transportation Science,2002,36(4):398-417.

[6]何勝學(xué),范炳全.多用戶(hù)動(dòng)態(tài)交通流分配模型及算法研究[J].上海理工大學(xué)學(xué)報(bào),2006,28(5):460-464.[HE S X,FAN B Q.Multi user dynamic traffic assignment model and relevant algorithm[J].Journal University of Shanghai for Science and Technology,2006，28(5):460-464.]

[7]何勝學(xué),董瓊,徐福緣.基于網(wǎng)絡(luò)對(duì)偶均衡的交通流分配模型[J].公路交通科技，2010,27(9):105-110.[HE S X,DONG J,XU F Y.Traffic assignment model based on network dual equilibrium[J].Journal of Highway and Transportation Research and Development,2010,27(9):105-110.]

[8]何勝學(xué),何建佳,徐福緣.基于網(wǎng)絡(luò)對(duì)偶均衡的有邊約束的交通流分配模型[J].交通運(yùn)輸系統(tǒng)工程與信息,2011,11(2):100-105.[HE S X,HE J J,XU F Y.Side constrained traffic assignment model based on network dual equilibrium[J].Journal of Transportation Systems Engineering and Information Technology,2011,11(2):100-105.]

[9]何勝學(xué),李秋曼.考慮邊約束的網(wǎng)絡(luò)交通流分配及應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究,2011,28(7):2595-2598.[HE S X,LIQ M.Side constrained network traffic assignment and application[J].Application Research of Computers,2011,28(7):2595-2598.]

[10]XIE J,XIE C.New insights and improvements of using paired alternative segments for traffic assignment[J].Transportation Research Part B,2016,93(4):406-424.

[11]MA W,QIAN S.On the variance of recurrent traffic flow for statistical traffic assignment[J].Transportation Research Part C,2017,81(1):57-82.

[12]GUO R Y,HUANG H J.A discrete dynamical system of formulating traffic assignment:Revisiting Smith’s model[J].Transportation Research Part C,2016,71(1):122-142.

[13]DAGANZO C F.The cell transmission model:a dynamic representation of highway traffic consistent with the hydrodynamic theory[J].Transportation Research Part B,1994,28(4):269-287.

[14]HE S X.Will a higher free-flow speed lead us to a less congested freeway?[J].Transportation Research Part A，2016,85(1):17-38.