徐 薇, 馬簫宇, 徐紅利

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

0 引 言

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

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

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

1 模 型

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

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

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

1.2 雙目標(biāo)用戶均衡(BUE)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[mp-mq]+)

(1)

其中運(yùn)算符“*”定義為

并且

[mp-mq]+}+1

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

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

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

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

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

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

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

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

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

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

2.2 演化模型的收斂性

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

fp≥0,?p∈Pw

(2)

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

圖1 無(wú)差異曲線示意圖

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

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

(證明見(jiàn)附錄)

定理2在定義3下，對(duì)任意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).

分別對(duì)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知，對(duì)任意的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.于是，當(dāng)λ(n)=0時(shí)

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

(4)

由于對(duì)每條路段a∈L，ta(xa)連續(xù)可微并且關(guān)于路段流量xa嚴(yán)格遞增，因此對(duì)于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)于收費(fèi)的嚴(yán)格遞增函數(shù)，因此，gT(f(n+1)-f(n))≤0也成立，即

綜上，存在適當(dāng)?shù)摩?n)，使得

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

2)若t(f(n))T(f(n+1)-f(n))=0，則由定義3可知，在第n天至第n+1天的變化過(guò)程中，人們只是從收費(fèi)較高的路徑調(diào)整到了收費(fèi)更低但時(shí)間相同的路徑上.即存在路徑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天仍然不會(huì)發(fā)生變化，因?yàn)樗鼈兣c其他路徑的出行時(shí)間的大小關(guān)系未發(fā)生變化，即fi(n+2)=fi(n+1),fj(n+2)=fj(n+1).又因?yàn)閠p(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)成立.此時(shí)收斂至穩(wěn)定點(diǎn)，即BUE狀態(tài).

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

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

3 數(shù)值算例

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

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

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

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

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

3.1 算例1

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

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

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

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

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

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

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

表2 算例1的BUE解析解

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

圖5 算例1的BUE解集

3.2 算例2

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

圖7展示了使用策略1，取λ=0.001時(shí)，從不同初始可行流開始的流量演化過(guò)程.圖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].可以看到當(dāng)初始流量分布不同時(shí)，流量的演化過(guò)程不同，最終的收斂結(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].可以驗(yàn)證，這兩個(gè)最終流量分布都滿足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)時(shí)的演化過(guò)程，此時(shí)最終流量為f*=[1 000, 2 000, 1 980, 1 980, 1 435, 1 605]，同樣容易驗(yàn)證該流量分布中所有被使用的路徑均不被其他任何路徑占優(yōu)，因此也是一個(gè)BUE解.另外，對(duì)比圖7(a)和圖8可以發(fā)現(xiàn)，使用策略2比使用策略1收斂速度快很多.

(a)

4 結(jié)束語(yǔ)

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