趙傳林，焦朋朋

(北京建筑大學(xué) 土木與交通工程學(xué)院，北京100044)

0 引 言

掌握交通流量時(shí)空分布規(guī)律是解決交通擁堵問題的關(guān)鍵.相關(guān)研究主要分為2類：靜態(tài)交通分配模型和動(dòng)態(tài)交通分配模型(動(dòng)態(tài)交通分配模型一直是研究的難點(diǎn)).模型的建立一般基于2類原則：用戶均衡和系統(tǒng)最優(yōu).本文研究并行網(wǎng)絡(luò)的系統(tǒng)最優(yōu)動(dòng)態(tài)交通分配問題.

采用圖解法研究該類問題的并不多.基于動(dòng)態(tài)最優(yōu)性條件并借助變分方法，Munoz等[1]采用圖解法描繪了系統(tǒng)最優(yōu)動(dòng)態(tài)交通分配曲線，得到了并行網(wǎng)絡(luò)路徑流量分配系統(tǒng)最優(yōu)解.最近，Laval等[2]討論了動(dòng)態(tài)實(shí)時(shí)收費(fèi)對(duì)路徑流量分配的影響，并采用圖解法得到了能夠?qū)崿F(xiàn)動(dòng)態(tài)系統(tǒng)最優(yōu)的動(dòng)態(tài)實(shí)時(shí)收費(fèi)水平.這兩篇文章均采用了累計(jì)到達(dá)曲線(是指到達(dá)瓶頸前的累計(jì)到達(dá)曲線，與交通經(jīng)濟(jì)學(xué)相關(guān)研究的含義，即到達(dá)目的地的累計(jì)到達(dá)曲線不同)已知的假設(shè)，即出行者出發(fā)時(shí)間選擇是給定的.此外，Laval[3]還采用圖解法研究了動(dòng)態(tài)用戶均衡(或用戶最優(yōu))解.通過放松累計(jì)到達(dá)曲線已知的假設(shè)，考慮出發(fā)時(shí)刻選擇行為，Arnott等[4]和Shen等[5]研究了出發(fā)時(shí)間和路徑選擇問題.以上研究均采用了瓶頸模型點(diǎn)排隊(duì)假設(shè)，并在并行網(wǎng)絡(luò)上展開研究.借助于圖解法，Zhao等[6]擴(kuò)展了Munoz等[1]的方法，并提出了一種新的基于day-to-day的激勵(lì)策略來實(shí)現(xiàn)動(dòng)態(tài)系統(tǒng)最優(yōu).不同于Zhao等[6]僅考慮單峰的情形，本文考慮多峰值情形.

采用一類擴(kuò)展的圖解方法，本文將研究并行網(wǎng)絡(luò)動(dòng)態(tài)路徑流量分配系統(tǒng)最優(yōu)問題.首先給出研究問題描述，其次介紹擴(kuò)展的求解系統(tǒng)最優(yōu)動(dòng)態(tài)路徑流量分配的圖解方法，并應(yīng)用于多峰值情形.

1 問題描述

考慮包含1個(gè)起訖點(diǎn)和2條路徑的并行網(wǎng)絡(luò)，如圖1所示，連接起點(diǎn)和終點(diǎn)有2條路徑，路徑1(高速公路)和路徑2(城市街道).令A(yù)(t)表示累計(jì)到達(dá)函數(shù)曲線，本文假設(shè)該曲線A(t)是給定的，Ai(t)表示路徑i的累計(jì)到達(dá)函數(shù)曲線(i=1,2)；表示到達(dá)率，λ1(t)+λ2(t)=1.假設(shè)瓶頸靠近起點(diǎn)處，路徑i的瓶頸處容量和自由流時(shí)間分別為μi和τi，明顯地，τ1＜τ2成立.假設(shè)函數(shù)曲線A(t)已知，即假設(shè)每位用戶到達(dá)瓶頸前的時(shí)間是給定的.本文將研究存在多個(gè)早高峰的情形，不失一般性，本文僅考慮含有2個(gè)峰值的累積到達(dá)函數(shù)曲線，即到達(dá)率先增加再減小，然后再增加最后減小，如圖2所示.

圖1 并行網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)示意圖Fig.1 Parallel network with one OD pair and two routes

圖2 含2個(gè)峰值的累計(jì)到達(dá)曲線示意圖Fig.2 Cumulative arrival curve with two-peak demand

假設(shè)瓶頸處點(diǎn)排隊(duì)，令τi(t)表示t時(shí)刻到達(dá)瓶頸的用戶到達(dá)目的地的出行時(shí)間，包括兩部分：自由流時(shí)間τi和排隊(duì)時(shí)間wi(t)，即

wi(t)可以表示為

式中：ti和Ti分別表示路徑i排隊(duì)開始和結(jié)束的時(shí)刻.

2 一類擴(kuò)展的圖解方法

式中：ti和Ti分別表示路徑i排隊(duì)開始和結(jié)束的時(shí)刻.

本文通過圖解法來得到系統(tǒng)最優(yōu)時(shí)的每條路徑的流量分配值，即研究A(t)如何在并行路徑上實(shí)

2.1 Munoz和Laval(2006)圖解方法介紹

Ziliaskopoulos[7]介紹了動(dòng)態(tài)情形系統(tǒng)最優(yōu)性條件，即對(duì)于所有的出發(fā)時(shí)刻，具有最小邊際出行成本的路徑會(huì)被用戶選擇.某條路徑的邊際出行成本包括2部分：一是，該路徑上增加1位用戶給整個(gè)系統(tǒng)帶來總延誤的增加；二是，該用戶選擇該路徑的出行時(shí)間.考慮點(diǎn)排隊(duì)模型，如果某條路徑已經(jīng)處于排隊(duì)狀態(tài)，此時(shí)若該路徑增加1位用戶會(huì)影響后續(xù)所有的出行用戶，直至排隊(duì)結(jié)束.

基于最優(yōu)性條件，Munoz等[1]借助變分法采用圖解法首次得到了動(dòng)態(tài)路徑流量分配系統(tǒng)最優(yōu)解.以圖1所示2條路徑為例，令T1為路徑1上排隊(duì)消失的時(shí)間，T2為被分配在路徑2上的最后一個(gè)用戶的出發(fā)時(shí)間.假設(shè)用戶總數(shù)N固定，在系統(tǒng)最優(yōu)時(shí)，一條路徑上(比如路徑1)人數(shù)增加dN所導(dǎo)致的系統(tǒng)總排隊(duì)時(shí)間的增加(即路徑1總排隊(duì)時(shí)間的增加，dN(T1-T2))等于另一條路徑上(即路徑2)人數(shù)減少dN所導(dǎo)致的總自由流出行時(shí)間的減少(即，dN(τ2-τ1)).兩式相等，我們得到系統(tǒng)最優(yōu)性條件的數(shù)學(xué)表達(dá)式為

式(3)的具體細(xì)節(jié)，可參閱文獻(xiàn)[1].

為了實(shí)現(xiàn)系統(tǒng)最優(yōu)性條件，Munoz等[1]介紹了一類圖解方法，當(dāng)路徑2瓶頸處容量無窮大時(shí)，即μ1=c1,μ2=∞，c1表示路徑1瓶頸處的容量為常數(shù)，沿垂直方向自上向下移動(dòng)累計(jì)到達(dá)曲線，直至滿足系統(tǒng)最優(yōu)性條件式(3)，具體圖解法過程如圖3(a)所示；當(dāng)路徑2瓶頸處容量為某一常數(shù)時(shí)，即μ1=c1,μ2=c2，水平延長A(t)，如圖4(a)中水平虛線.在水平虛線上選擇點(diǎn)M為起點(diǎn)，向左畫出斜率為μ1的線段，保證水平投影長度為τ2-τ1；然后，畫出斜率為μ1+μ2的直線.記兩段線段為累計(jì)離開曲線，自右向左移動(dòng)該線，直至再次與A(t)相切，切點(diǎn)對(duì)應(yīng)的時(shí)刻為t2，具體圖解法過程如圖4(a)所示.根據(jù)圖3(a)和圖4(a)，可以直接得到2條路徑流量分配系統(tǒng)最優(yōu)解，如圖3(b)～(c)和圖 4(b)～(c).以圖 3為例，系統(tǒng)最優(yōu)解如表1所示.

圖3 圖解法示意圖(μ1=c1,μ2=∞)Fig.3 Graphical solution method(μ1=c1,μ2=∞)

圖4 圖解法示意圖(μ1=c1,μ2=c2)Fig.4 Graphical solution method(μ1=c1,μ2=c2)

表1 系統(tǒng)最優(yōu)流量分配結(jié)果(μ1=c1,μ2=∞)Table 1 Optimal solution(μ1=c1,μ2=∞)

2.2 擴(kuò)展的圖解方法

不同于Munoz等[1]的圖解方法，本文介紹一類擴(kuò)展的圖解方法，并應(yīng)用于多峰情形：自下向上移動(dòng)累計(jì)離開率曲線，直至滿足最優(yōu)性條件式(3).仍以圖1所示的2條路為例，研究2種情形，一種是μ1=c1,μ2=∞；另一種情形是μ1=c1,μ2=c2.

情形 1μ1=c1,μ2=∞.

圖5給出了具體的圖解法過程，t1時(shí)刻流量到達(dá)率為λ(t1)=μ1.具體的圖解法過程可描述為：

Step 1沿水平方向延長累計(jì)到達(dá)曲線A(t)，如圖5中水平虛線.在時(shí)刻t1，畫斜率為μ1的直線L(t)，即累計(jì)離開率曲線.

Step 2以K1點(diǎn)(t1,A(t1))為起點(diǎn)，沿垂直方向自下向上移動(dòng)L(t)至與A(t)相交于3點(diǎn)，即K2點(diǎn)(t2,A(t2))，K3點(diǎn)(t3,A(t3))和K4點(diǎn)(t4,A(t4)).

Step 3比較t3-t2和t4-t3與τ2-τ1的關(guān)系.存在4種情況：第1種情況，t3-t2≤τ2-τ1和t4-t3≤τ2-τ1，在這種情況下，通過計(jì)算變分，增加或減少路徑1的流量均會(huì)增加系統(tǒng)總時(shí)間，3個(gè)交點(diǎn)K2，K3和K4決定了系統(tǒng)最優(yōu)時(shí)的流量分配結(jié)果，具體結(jié)果如表2所示；第2種情況，t3-t2＞τ2-τ1和t4-t3＜τ2-τ1，這種情況下，只需要繼續(xù)向上移動(dòng)線段K2K3直至t3-t2=τ2-τ1成立，2個(gè)新交點(diǎn)與點(diǎn)K3和點(diǎn)K4共同決定了系統(tǒng)最優(yōu)時(shí)的流量分配結(jié)果；第 3 種情況與第 2 種類似，即t3-t2＜τ2-τ1和t4-t3＞τ2-τ1成立；第 4 種情況，t3-t2＞τ2-τ1和t4-t3＞τ0-τ1，此時(shí)線段K2K3和K3K4均需要繼續(xù)垂直向上移動(dòng)直至t3-t2=τ0-τ1和t4-t3=τ2-τ1成立，得到的4個(gè)新交點(diǎn)決定了系統(tǒng)最優(yōu)時(shí)的流量分配結(jié)果.

圖5 含雙峰的圖解法示意圖(μ1=c1,μ2=∞)Fig.5 Graphical solution method with two-peak demand(μ1=c1,μ2=∞)

表2 一種可能的含雙峰的系統(tǒng)最優(yōu)流量分配結(jié)果(μ1=c1,μ2=∞)Table 2 One possible optimal solution withtwo-peak demand(μ1=c1,μ2=∞)

情形 2μ1=c1,μ2=c2.

圖6給出了具體的圖解法過程，λ(t1)=μ1，λ(t2)=μ1+μ2，記點(diǎn)(t2,A(t2))為K1點(diǎn).具體圖解法過程描述如下：

Step 1 類似于情形1，沿水平方向延長累計(jì)到達(dá)曲線A(t)，如圖6水平虛線.以K1點(diǎn)為起點(diǎn)，畫斜率為μ1和μ1+μ2的直線，分別為K1K2和K1K3.為了保證最優(yōu)性條件式(3)，線段K1K2的水平投影長度為τ2-τ1.與單峰情形不同，直線K1K3與A(t)的位置關(guān)系存在兩種情況，分別如圖6(a)和圖6(b)所示，下面分別分析這兩種情況.

Step 2圖6(a)和圖6(b)分別討論.

圖6(a)中，沿著K1K3向上移動(dòng)K1K2，直至再次與A(t)相交，記為點(diǎn)K4.點(diǎn)K1，K3和K4決定了流量分配系統(tǒng)最優(yōu)解.基于圖6(a)，詳細(xì)的流量分配結(jié)果如表3所示.需要指出的是時(shí)間區(qū)間(t2,T2) ，p∈(0 ,λ(t)-μ1-μ2)和q∈(0 ,λ(t)-μ1-μ2)，而且p和q同時(shí)滿足約束條件p+q=λ(t)-μ1-μ2.這說明該區(qū)間流量分配結(jié)果不唯一，Munoz等[1]也分析了流量分配系統(tǒng)最優(yōu)解的不唯一性.

圖6 含雙峰的圖解法示意圖(μ1=c1,μ2=c2)Fig.6 Graphical solution method with two-peak demand(μ1=c1,μ2=c2)

表3 含雙峰的系統(tǒng)最優(yōu)流量分配結(jié)果1(μ1=c1,μ2=c2)Table 3 The first possible optimal solution with two-peak demand(μ1=c1,μ2=c2)

圖 6(b)中，直線K1K3與A(t)相交于第1個(gè)峰值段，以K1點(diǎn)為起點(diǎn)，沿K1K3向上移動(dòng)K1K2，直至端點(diǎn)K2與A(t)相交或者K1K2與A(t)相切，切點(diǎn)記為K5，左側(cè)端點(diǎn)記為K4.第2個(gè)峰值段的分析與第1個(gè)峰值段類似，可以找到 3個(gè)點(diǎn)K6，K7和K8，其中在K6點(diǎn)，λ(t6)=μ1+μ2.6個(gè)點(diǎn)Kj,j=1,4,5,…,8，決定了流量分配系統(tǒng)最優(yōu)解，具體結(jié)果如表4所示.

表4 含雙峰的系統(tǒng)最優(yōu)流量分配結(jié)果2(μ1=c1,μ2=c2)Table 4 The second possible optimal solution with two-peak demand(μ1=c1,μ2=c2)

3 算 例

本節(jié)給出2個(gè)算例來說明本文兩種情形的分析結(jié)果.

算例1參數(shù)設(shè)定為μ1=0.5，μ2=∞，累計(jì)到達(dá)曲線A(t)為分段連續(xù)可微函數(shù)，如式(4)所示.

從式(4)可知，曲線的斜率先增后減，然后再增加，再減小.結(jié)合圖5的圖解法求解過程，圖7給出了圖解法的求解結(jié)果.由于A(t)上橫坐標(biāo)為t1點(diǎn)和t3點(diǎn)的斜率為μ1=0.5，可以很容易地求得：t1=0.25，t3=2.25，進(jìn)而可求得：t2=1.75+ 1 8，t4=6.125.根據(jù)A(t)的函數(shù)表達(dá)式和μ1=0.5，可以發(fā)現(xiàn)t4-t3≥t3-t2.按照情形1中Step3的分析，比較t3-t2=0.5- 1 8 和t4-t3=3.875分別與τ2-τ1的關(guān)系.如果τ2-τ1≥3.875成立，則路徑1和路徑2的流量分配結(jié)果如表5所示；如果0.5-1 8≤τ2-τ1≤3.875成立，則需要繼續(xù)垂直向上移動(dòng)圖5中的線段K3K4，直至t4-t3=τ2-τ1成立；如果τ2-τ1≤0.5- 1 8成立，則需要繼續(xù)垂直向上移動(dòng)圖 5 中的線段K2K3和K3K4，直至t3-t2=τ2-τ1和t4-t3=τ2-τ1成立.

算例2考慮圖6(a)情形，參數(shù)設(shè)定為μ1=0.3，μ2=0.2，τ2-τ1分別取1.0和1.5；A(t)仍然為式(4)所示.當(dāng)τ2-τ1=1.0時(shí)，按照圖6(a)的圖解法過程，計(jì)算可以得到：t1=0.15，t2=0.25，tk=1.25，T2=7.525，T1=8.525.斜率為0.5的直線橫坐標(biāo)為T2點(diǎn)對(duì)應(yīng)的縱坐標(biāo)為3.7；求解A(t)=3.7得到tj=3.45.當(dāng)τ2-τ1=1.5時(shí)，可計(jì)算得到：t1=0.15，t2=0.25，tk=1.75，T2=7.225，T1=8.225；斜率為0.5的直線橫坐標(biāo)為T2點(diǎn)對(duì)應(yīng)的縱坐標(biāo)為3.55；求解A(t)=3.55得到tj=3.33.系統(tǒng)最優(yōu)路徑流量分配結(jié)果如表6和表7所示，p值的取值范圍均為p∈(0 ,λ(t)-0.5)，且p+q=λ(t)-0.5.從表6和表7的結(jié)果可以發(fā)現(xiàn)，τ2-τ1取值的不同僅僅影響到tj的值.

圖7 情形1圖解法算例(μ1=0.5,μ2=∞)Fig.7 Graphical solution method for case 1(μ1=0.5,μ2=∞)

表6 情形2系統(tǒng)最優(yōu)路徑流量分配結(jié)果(μ1=0.3,μ2=0.2,τ2-τ1=1.0)Table 6 Optimal solution for case 2(μ1=0.3,μ2=0.2,τ2-τ1=1.0)

表7 情形2系統(tǒng)最優(yōu)路徑流量分配結(jié)果(μ1=0.3,μ2=0.2,τ2-τ1=1.5)Table 7 Optimal solution for case 2(μ1=0.3,μ2=0.2,τ2-τ1=1.5)

4 結(jié)論

Zhao等[6]研究了一類擴(kuò)展的圖解法求解動(dòng)態(tài)路徑流量分配系統(tǒng)最優(yōu)解，但僅僅考慮單峰的情形，本文擴(kuò)展至多峰情形.基于瓶頸模型點(diǎn)排隊(duì)假設(shè)、系統(tǒng)最優(yōu)性條件和圖解方法的具體實(shí)施過程，擴(kuò)展的圖解方法可以應(yīng)用于含有1個(gè)OD的一般并行網(wǎng)絡(luò)[6]，不適用于一般結(jié)構(gòu)網(wǎng)絡(luò).

本文考慮了兩種情形，即高速公路瓶頸容量為常數(shù)，城市街道瓶頸容量分別為無窮大和常數(shù)，給出了每種情形下的路徑流量分配結(jié)果.但是結(jié)果的獲得是基于瓶頸處點(diǎn)排隊(duì)和累計(jì)到達(dá)曲線已知的假設(shè)，在后續(xù)的研究中，將綜合考慮出發(fā)時(shí)間和路徑選擇問題，進(jìn)一步分析流量分配結(jié)果.此外，放松點(diǎn)排隊(duì)和固定需求假設(shè)，結(jié)合宏觀基本圖的流量—速度—密度關(guān)系，采用圖解法研究動(dòng)態(tài)流量分配結(jié)果也是即將開始的工作.

[1]MUNOZ J C,LAVAL J A.System optimum dynamic traffic assignment graphical solution method for a congested freeway and one destination[J].Transportation Research Part B：Methodological,2006,40(1)：1-15.

[2]LAVAL J A,CHO H W,MUNOZ J C,et al.Real-time congestion pricing strategies for tollfacilities[J].Transportation Research Part B：Methodological,2015(71)：19-31.

[3]LAVAL JA.Graphicalsolution and continuum approximation for the single destination dynamic user equilibrium problem[J].Transportation Research Part B：Methodological,2009,43(1)：108-118.

[4]ARNOTT R,DE PALMA A,LINDSEY R.Departure time and route choice for the morning commute[J].Transportation Research Part B：Methodological,1990,24(3)：209-228.

[5]SHEN W,ZHANG H M.On the morning commute problem in a corridor network with multiple bottlenecks：Its system-optimal traffic flow patterns and the realizing tolling scheme[J].Transportation Research Part B：Methodological,2009,43(3)：267-284.

[6]ZHAO C L,LECLERCQ L.Graphical solution for system optimum dynamic traffic assignmentwith day-to-day incentive routing strategies[C].The 9th International Workshop on Computational Transportation Science,Lanzhou Jiaotong University,Lanzhou,2017.

[7]ZILIASKOPOULOS A K.A linear programming model for the single destination system optimum dynamic traffic assignment problem[J].Transportation Science,2000,34(1)：1-12.