徐 薇, 馬簫宇, 徐紅利

(南京大學(xué)工程管理學(xué)院, 南京 210093)

0 引 言

自1952年Wardrop提出用戶均衡(user equilibrium, UE)概念開始，關(guān)于交通網(wǎng)絡(luò)均衡分配的研究就一直在不斷發(fā)展深入，推動著交通科學(xué)的發(fā)展.靜態(tài)交通分配模型通常只關(guān)注交通系統(tǒng)平衡穩(wěn)定的最終狀態(tài)，而動態(tài)交通分配模型則刻畫交通流從非平衡狀態(tài)到平衡狀態(tài)的演化過程.現(xiàn)實中，由于出行者每天的出行選擇都可能會受到過往出行經(jīng)驗和當前網(wǎng)絡(luò)狀態(tài)的影響而發(fā)生改變，因此交通流的分布狀態(tài)是振蕩變化的.對交通流逐日動態(tài)(day-to-day dynamics)演化過程的研究有利于探索交通流演變的內(nèi)在機制，更好地實現(xiàn)交通誘導(dǎo)和對交通網(wǎng)絡(luò)流狀態(tài)的控制.

在現(xiàn)有的交通流逐日動態(tài)演化研究中，大多數(shù)模型假設(shè)出行者根據(jù)前一天的道路通行時間來選擇當天的出行路徑，從而將相鄰兩天同一路徑/路段上的流量更新描述為當天路網(wǎng)狀態(tài)(如路徑/路段通行時間)的一個函數(shù).現(xiàn)有文獻中基于路徑流量更新的模型較多，Yang和Zhang[1]總結(jié)了五類模型，分別是：the simplex gravity flow dynamics[2], the proportional-switch adjustment process (PSAP)[3], the network tatonnement process[4], the projected dynamical system[5], 以及the evolutionary traffic dynamics[6].這些模型都假設(shè)系統(tǒng)的最終穩(wěn)定狀態(tài)是確定的UE.在此基礎(chǔ)上，很多學(xué)者進行了拓展研究，例如考慮：有限理性[7， 8]、參考點依賴[9]、彈性需求[10]、隨機用戶均衡[11, 12]、混合均衡[13]、路徑成本敏感性[14]、路徑剩余容量[15]、誘導(dǎo)信息[16， 17]、社會交互[18]、交通事件影響[19]等.由于路徑流量不易觀測且存在路徑重疊和枚舉量大的問題，He等[20]最早提出了直接基于路段流量更新的逐日動態(tài)演化模型.Han和Du[21]進一步研究了該模型的一些性質(zhì)，如不變集和限制穩(wěn)定性.Guo等[22, 23]給出了一種基于路段的逐日動態(tài)演化的一般框架，并且證明了一些已有模型(例如文獻[4, 5, 20, 21]提出的模型)均為該一般框架的特例.此外，在基于路段的模型中，也有學(xué)者考慮了出行時間不確定性和出行者風(fēng)險行為[24]、道路容量退化[25]等.Xiao等[26]還將逐日交通網(wǎng)絡(luò)動態(tài)演化過程看作是一種物理系統(tǒng)，探究了其中的內(nèi)在規(guī)律.

道路收費是交通誘導(dǎo)和控制的一種重要手段，在交通流逐日動態(tài)分配模型的研究中有不少引入了道路收費策略，例如Tan等[27]、Guo等[28]、Han等[29]、Liu等[30]、Xu等[31]、Rambha和Boyles[32]等.這些研究均假設(shè)出行者將道路通行時間與收費組合為廣義出行成本來考慮路徑選擇，即最小化廣義出行成本.然而，將道路出行時間和收費組合考慮會使二者之間具有某種潛在的轉(zhuǎn)換與互補關(guān)系.Dial[33]較早考慮多目標交通配流問題時就將兩者進行了線性組合，而近來Wang和Ehrgott[34]則真正將道路通行時間和收費分開考慮，定義了雙目標用戶均衡(bi-objective UE，BUE)，即達到均衡時出行者無法通過單方面改變路徑選擇來降低其出行時間或收費.若出行者是理性的，則可以證明達到BUE時任何被使用的路徑都是占優(yōu)路徑(也稱有效路徑)，這些有效路徑包含了Dial[33]在其研究中定義的所有有效路徑，因此BUE更具有一般性.然而，已有的同時考慮道路通行時間和收費的交通流逐日動態(tài)演化模型最終均收斂至廣義出行成本下的單目標用戶均衡，尚無研究對上述雙目標用戶均衡給出交通流的動態(tài)演化過程.因此，本文提出一種新的基于路徑流量更新的逐日動態(tài)演化模型，假設(shè)出行者在逐日的路徑選擇中將路徑出行時間和收費分開比較以決定是否變換路徑，可以證明該演化模型最終收斂的穩(wěn)定狀態(tài)恰好是BUE.本文嚴格證明了模型的收斂性，并用數(shù)值算例驗證了模型的有效性.

1 模 型

1.1 符號定義和假設(shè)

考慮一個具有N個節(jié)點，L條直接相連的路段構(gòu)成的交通網(wǎng)絡(luò)G(N,L).令W是網(wǎng)絡(luò)中所有OD對的集合，Pw是連接OD對w∈W的所有路徑的集合.本文研究假設(shè)所有OD對之間的出行需求是固定的，表示為向量d=(dw,w∈W)T，其中dw為OD對w∈W之間的出行需求.路徑流量表示為向量f=(fp,w,p∈Pw,w∈W)T, 其中fp,w是路徑p∈Pw上的流量.路段流量表示為向量x=(xa,a∈L)T,其中xa是路段a∈L上的流量.令Δ=(δa,p,a∈L,p∈Pw,w∈W)表示路段-路徑關(guān)聯(lián)矩陣，其中δa,p=1表示路段a位于路徑p上；否則，δa,p=0.顯然，x=Δf.令Θ=(θp,w,p∈Pw,w∈W)表示OD-路徑關(guān)聯(lián)矩陣，其中θp,w=1表示路徑p連接OD對w；否則，θp,w=0.顯然，d=Θf.因此，可行路段流量和路徑流量的集合為Ω={(x,f)|x=Δf,d=Θf,f≥0}.

本文考慮可分的路段出行時間函數(shù)，即路段a上的通行時間只與該路段上的流量xa相關(guān)，與其他路段的流量無關(guān).并且假設(shè)該函數(shù)連續(xù)可微，關(guān)于路段流量xa嚴格遞增.另外，假設(shè)路段收費與流量無關(guān).用ma和ta分別表示路段a上的收費和通行時間，mp和tp分別表示路徑p上的收費和通行時間.

1.2 雙目標用戶均衡(BUE)

本文同時考慮時間和費用兩個屬性下的出行者路徑選擇行為，在雙目標用戶均衡下，出行者總是盡可能地選擇通行時間短并且通行費用低的路徑[33].文獻[33, 34]中給出了BUE的嚴格定義，為參考方便這里復(fù)述如下.

定義1當交通網(wǎng)絡(luò)流量分布達到BUE時，所有被使用的路徑都是有效的.

定義2令f∈Ω是一個可行路徑流量分布，mp(f)和tp(f)分別為路徑p∈Pw上的收費和通行時間，則

1)如果不存在路徑p′∈Pw，滿足mp′(f)≤mp(f)和tp′(f)≤tp(f)中至少有一個不等式是嚴格不等式，則路徑p∈Pw是有效的.

2)如果mp′(f)≤mp(f)和tp′(f)≤tp(f)中至少有一個不等式是嚴格不等式，則路徑p′占優(yōu)路徑p，且成本向量(tp′(f),mp′(f))占優(yōu)(tp(f),mp(f)).

顯然，由定義2可知，一條路徑是有效的當且僅當這條路徑不被其他的任何路徑占優(yōu).

1.3 逐日動態(tài)演化模型

經(jīng)典的逐日動態(tài)演化模型——PSAP模型由Smith[3]提出，該模型描述了在出行時間較長的路徑上的出行者會在下一天轉(zhuǎn)移到其他的出行時間較短的路徑上，且轉(zhuǎn)換的比率是和該路徑與其他較短時間路徑的時間成本差成比例的.假設(shè)在一個OD對中，p和q分別表示該OD對w∈W之間的不同路徑，則路徑p上的流量變化率定義為

fp[tp(f)-tq(f)]+)

其中 [x]+=max{0,x}.

上述模型是基于連續(xù)時間的，文獻[20]中則提到了PSAP的離散形式，具體如下

fp(n+1)-fp(n)=

fp(n)[tp(n)-tq(n)]+)

這里Tw(n)可以視為一個離散化的步長；M是一個參數(shù)，在取值較大時意味著出行者更愿意保持原來的路線.

以上是基于傳統(tǒng)單目標UE的逐日動態(tài)演化模型.本文從雙目標用戶均衡的路徑選擇決策規(guī)則出發(fā)，依據(jù)PSAP的思想，對相鄰兩天路徑流量的變化調(diào)整給出了如下的定義.

定義3基于雙目標用戶均衡的逐日動態(tài)演化模型定義為

fp(n+1)-fp(n)=

[mq-mp]+-fp(n)[tp(n)-tq(n)]+*

[mp-mq]+)

(1)

其中運算符“*”定義為

并且

[mp-mq]+}+1

這里Tw(n)可以保證fp(n+1)非負，且作為分母不為零；λ(n)∈(0,1]是調(diào)整系數(shù)，在現(xiàn)實中，它代表愿意調(diào)整路徑的出行者所占的比例.λ(n)取值越小，表示有調(diào)整路徑意愿的出行者越少，即更多的人愿意保持原來的出行路徑.后文會詳細討論λ(n)的取值.由運算符“*”的定義，式(1)表示只有當路徑的時間成本和金錢成本均不增加且至少有一個減少時，出行者才可能改變路徑選擇，符合BUE下的路徑選擇決策規(guī)則.

2 穩(wěn)定點和收斂性分析

2.1 穩(wěn)定點與BUE解的等價性

文獻[34]的研究已經(jīng)表明，BUE解不唯一，令BUE的解集集合為B.

定理1如果路徑流量分布f(n)是演化模型(1)的穩(wěn)定點，則f(n)是BUE解，即f(n)∈B.

證明顯然，演化模型(1)的穩(wěn)定點滿足

[tp-tq]+*[mp-mq]+=0,

?fp,fq>0,p,q∈Pw

因此要證明穩(wěn)定點f(n)是BUE解，即需要證明所有流量大于零(fp(n)>0)的路徑是有效路徑.

采用反證法假設(shè)存在流量大于零的路徑p不是有效路徑，即存在路徑p′占優(yōu)路徑p，那么由定義2可得，tp′(n)≤tp(n)和mp′≤mp成立，且至少有一個是嚴格不等式.那么，[tp(n)-tp′(n)]+*[mp-mp′]+>0，此時f(n+1)≠f(n)，即f(n)不是穩(wěn)定點，與假設(shè)矛盾.因此，如果f(n)是穩(wěn)定點，則f(n)∈B.

2.2 演化模型的收斂性

考慮文獻[34]中的優(yōu)化問題(23)，具體如下

fp≥0,?p∈Pw

(2)

其中g(shù)∶R→R是關(guān)于收費的嚴格遞增函數(shù)，由時間和金錢的無差異曲線決定.無差異曲線(indifference curve)是經(jīng)濟學(xué)中的一個概念，它是一條表示給消費者相同滿足程度的商品組合的曲線.本文研究中的無差異曲線考慮時間和金錢的不同組合，即在同一條無差異曲線上，雖然不同的點表示不同的時間和金錢組合，但是這些點對于出行者來說感受到的效用是相同的.例如，在圖1給出的無差異曲線示意圖上，假設(shè)A點代表出行時間為30 min、收費為20元的路徑，B點代表出行時間為60 min、收費為10元的路徑，那么對于符合此無差異曲線的出行者來說，路徑A和路徑B對他們的吸引力是相同的.由文獻[34]可知，給定任意一個函數(shù)g(即給定任意一個無差異曲線)，上述優(yōu)化問題是一個嚴格凸優(yōu)化，其最優(yōu)解對應(yīng)的路徑流量分布f*是一個BUE解.

圖1 無差異曲線示意圖

如果在由定義3給出的逐日動態(tài)演化過程中，對任意的n，f(n)?B，以及任意嚴格遞增函數(shù)g，都有W(f(n))>W(f(n+1))成立，那么該演化過程一定會收斂到某個函數(shù)g對應(yīng)的優(yōu)化問題(2)的最優(yōu)解，即某個BUE解.因此，接下來將證明存在適當?shù)恼{(diào)整系數(shù)λ(n)，使得定義3給出的演化過程滿足W(f(n))單調(diào)下降.

引理1在定義3下，對任意f(n)?B，總有t(f(n))T(f(n+1)-f(n))≤0，以及mT(f(n+1)-f(n))≤0成立.

(證明見附錄)

定理2在定義3下，對任意f(n)?B，

t(f(n+1))T(f(n+1)-f(n))≤0,

(3)

2)若f(n)滿足t(f(n))T(f(n+1)-f(n))=0，則存在λ(n)→0，使得演化模型(1)收斂至BUE狀態(tài).

證明令

V(x(n+1))=V(λ(n))

U(f(n+1))=U(λ(n))

則W(f)=V(x)+U(f).

分別對V(λ(n))和U(λ(n))關(guān)于λ(n)求導(dǎo)，有

=gTz(n)

其中向量g=(g(mp),p∈Pw,w∈W)，z(n)=df(n+1)/dλ(n).由引理1知，對任意的n，f(n)?B，有t(f(n))T(f(n+1)-f(n))≤0，因此下面分兩種情況討論.

1)若t(f(n))T(f(n+1)-f(n))<0，那么易得t(f(n))Tz(n)<0.于是，當λ(n)=0時

=t(f(n))Tz(n)<0

(4)

由于對每條路段a∈L，ta(xa)連續(xù)可微并且關(guān)于路段流量xa嚴格遞增，因此對于x∈Ω，t(x)是正定矩陣，即

>0

(5)

=t(f(n+1))Tz(n)

即式(3)成立，并且V(0)>V(λ(n))，即V(x(n))>V(x(n+1)).

另根據(jù)引理1，mT(f(n+1)-f(n))≤0，且函數(shù)g是關(guān)于收費的嚴格遞增函數(shù)，因此，gT(f(n+1)-f(n))≤0也成立，即

綜上，存在適當?shù)摩?n)，使得

即W(f(n))>W(f(n+1))成立.

2)若t(f(n))T(f(n+1)-f(n))=0，則由定義3可知，在第n天至第n+1天的變化過程中，人們只是從收費較高的路徑調(diào)整到了收費更低但時間相同的路徑上.即存在路徑p,q∈Pw，tp(n)=tq(n),mp>mq，因此部分流量從p調(diào)整到q.調(diào)整后，有tp(n+1)

(6)

注意到該情形下式(6)中的路徑i和路徑j(luò)在第n+1天是不發(fā)生流量變化的，因此在第n+2天仍然不會發(fā)生變化，因為它們與其他路徑的出行時間的大小關(guān)系未發(fā)生變化，即fi(n+2)=fi(n+1),fj(n+2)=fj(n+1).又因為tp(n+1)mq，所以路徑p和路徑q之間也不再發(fā)生流量轉(zhuǎn)換，即fp(n+2)=fp(n+1)，fq(n+2)=fq(n+1).綜合可得，f(n+2)=f(n+1)成立.此時收斂至穩(wěn)定點，即BUE狀態(tài).

顯然，當λ(n)充分小時，式(3)條件一定成立.因此，由上述證明可以直接推出下面的推論1.

推論1在模型假設(shè)下，如果λ(n)→0,n=1,2,…，那么演化模型(1)可以收斂至BUE狀態(tài).

3 數(shù)值算例

本節(jié)將通過數(shù)值算例來檢驗上節(jié)中提出的模型，其中λ(n)的取值會根據(jù)推論1和定理2給出的如下兩種策略來確定.

策略1調(diào)整系數(shù)λ(n)取一個趨于0的固定值.

策略2當t(f(n))T(f(n+1)-f(n))=0時，調(diào)整系數(shù)λ(n)取一個趨于0的固定值；當t(f(n))T(f(n+1)-f(n))<0時，取λ(n)∈(0,1]滿足

t(f(n+1))T(f(n+1)-f(n))≤0

以下算例中均采用BPR(bureau of public roads)路段行駛時間函數(shù)

3.1 算例1

圖2 算例1網(wǎng)絡(luò)

表1 算例1網(wǎng)絡(luò)的路段特征參數(shù)

首先，使用策略1，固定取λ=0.001.圖3展示了以任意可行流量為初始流量，按照演化模型(1)演化到BUE狀態(tài)的過程.在圖3中，橫縱坐標分別為路徑1和路徑2的流量，圓點為起始點，方點為終止點，從圓點到方點之間的線條表示演化軌跡，方點連線圍住的空白區(qū)域均為滿足BUE的路徑流量分布.可以看到，該算例的所有BUE解構(gòu)成一個集合，未達BUE狀態(tài)的流量分布會逐漸演化至BUE集合.

圖3 使用策略1取λ=0.001時，路徑1和路徑2上以任意可行流為起點的路徑流量演化軌跡

圖4展示了使用策略2確定λ(n)取值時的路徑流量演化軌跡.同樣地，圖中圓點為起始點，方點為終止點，星點代表演化過程中的點，方點連線圍住的空白區(qū)域均為BUE解集.由于策略2是一種自適應(yīng)策略，因此從任意可行流量開始，只需要迭代相對較少的次數(shù)即可演化至BUE狀態(tài).和策略1相比，由于每天的調(diào)整系數(shù)不同，因此演化軌跡相對凌亂無規(guī)律.

根據(jù)BUE的定義，可推出該算例BUE解析解所滿足的條件.表2列出了構(gòu)成該算例BUE解集的7個子集.

圖4 使用策略2確定λ(n)時，路徑1和路徑2上以任意可行流為起點的路徑流量演化軌跡

表2 算例1的BUE解析解

圖5展示了表2中7個BUE子集的并集，即整個BUE解集(左下角陰影部分，不含上邊界和右邊界).這與前面圖3和圖4中方點連線圍住的空白區(qū)域是一致的，故進一步驗證了演化模型(1)收斂到BUE集合.

圖5 算例1的BUE解集

3.2 算例2

算例1中的交通網(wǎng)絡(luò)較為簡單和特殊，即路段和路徑是一樣的.下面考慮如圖6所示的交通網(wǎng)絡(luò)[34]，該網(wǎng)絡(luò)具有4個結(jié)點、8條路段和6條路徑.該網(wǎng)絡(luò)的路段和路徑特征參數(shù)分別由表3和表4給出.注意到路徑1和路徑2是直達路徑，路徑1是行駛時間最短但收費最多的路徑，而路徑6是唯一不收費但卻最慢的路徑.OD對間的出行需求假設(shè)為10 000輛車/h.

圖7展示了使用策略1，取λ=0.001時，從不同初始可行流開始的流量演化過程.圖7(a)的初始流量分布為f= [1 000, 2 000, 3 000, 1 000, 1 500, 1 500]，圖7(b)的初始流量分布為f=[ 2 700, 1 700, 2 500, 1 000, 800, 1 300].可以看到當初始流量分布不同時，流量的演化過程不同，最終的收斂結(jié)果也不同，分別為f*= [1 000, 2 000, 1 997, 1 997, 1 458, 1 548]和f*=[2 700, 1 700, 1 750, 1 750, 800, 1 300].可以驗證，這兩個最終流量分布都滿足BUE條件.

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

表3 算例2網(wǎng)絡(luò)的路段特征參數(shù)

表4 算例2網(wǎng)絡(luò)的路徑特征參

圖8展示了初始流量為f= [1 000, 2 000, 3 000, 1 000, 1 500, 1 500]，使用策略2確定λ(n)時的演化過程，此時最終流量為f*=[1 000, 2 000, 1 980, 1 980, 1 435, 1 605]，同樣容易驗證該流量分布中所有被使用的路徑均不被其他任何路徑占優(yōu)，因此也是一個BUE解.另外，對比圖7(a)和圖8可以發(fā)現(xiàn)，使用策略2比使用策略1收斂速度快很多.

(a)

4 結(jié)束語

圖8 使用策略2確定λ(n)時的路徑流量演化過