考慮路票發(fā)放方式和交易成本的UE模型及算法

韓 飛 程 琳 孫 超 趙建有

(1長(zhǎng)安大學(xué)汽車學(xué)院， 西安 710064)(2東南大學(xué)交通學(xué)院， 南京 210096)(3江蘇大學(xué)汽車與交通工程學(xué)院， 鎮(zhèn)江 212013)

交通擁堵問(wèn)題是目前制約城市經(jīng)濟(jì)社會(huì)發(fā)展的關(guān)鍵瓶頸問(wèn)題之一，而擁擠收費(fèi)作為一種有效的交通需求管理手段，長(zhǎng)期以來(lái)受到經(jīng)濟(jì)學(xué)界和交通學(xué)界專家學(xué)者的持續(xù)關(guān)注.盡管擁擠收費(fèi)從理論上來(lái)說(shuō)十分完美，甚至可以完全消除瓶頸路段的排隊(duì)延誤[1]，但由于其本身的稅費(fèi)屬性及社會(huì)公平性等問(wèn)題，使得擁擠收費(fèi)在實(shí)際應(yīng)用中往往受到社會(huì)公眾的強(qiáng)烈反對(duì)[2]，從而難以廣泛應(yīng)用.

為了設(shè)計(jì)出既能有效改善城市交通擁堵問(wèn)題，又能被社會(huì)公眾廣泛接受的治堵策略，有學(xué)者提出一種基于數(shù)量調(diào)控的交通需求管理手段——可交易“路票”策略(tradable credit scheme，TCS).TCS策略的主要思想是：在每個(gè)周期初始時(shí)，交通部門根據(jù)調(diào)控目標(biāo)設(shè)定路票發(fā)行總量，并按照某種路票初始發(fā)放方式(credit distribution scheme, CDS)向所有具備資格的出行者免費(fèi)發(fā)放，如完全均勻發(fā)放或同一OD對(duì)均勻發(fā)放等；出行者使用某條路段時(shí)需要交納一定數(shù)量的路票，路票可以在市場(chǎng)中供出行者自由交易，路票價(jià)格完全由市場(chǎng)供求關(guān)系決定，路票到期后自動(dòng)失效以避免囤積路票；交通部門只作為監(jiān)管部門，通過(guò)調(diào)整路票發(fā)行總量和每條道路的路票收取量，從而實(shí)現(xiàn)交通系統(tǒng)的最優(yōu)化目標(biāo).早期關(guān)于TCS策略的研究主要是從定性角度探索TCS在治理城市交通問(wèn)題方面的可行性和應(yīng)用前景[3-4].近年來(lái)，為了定量描述TCS對(duì)交通網(wǎng)絡(luò)中出行需求的調(diào)控作用，Yang 等[5]建立了基于TCS的用戶均衡(user equilibrium，UE)模型，討論了實(shí)現(xiàn)系統(tǒng)最優(yōu)(system optimal，SO)的路票策略以及Pareto-improving SO路票策略，并拓展到彈性需求情形，由此驗(yàn)證了TCS解決交通擁堵問(wèn)題的有效性和可行性.Wang等[6]和Zhu等[7]在該研究基礎(chǔ)上進(jìn)一步考慮了不同出行者的時(shí)間價(jià)值異質(zhì)性，并利用變分不等式(variational inequality, VI)建立了基于TCS的多用戶類UE模型.Nie[8]研究了路票交易成本對(duì)均衡路段流量和路票均衡價(jià)格的影響，并給出能使交通網(wǎng)絡(luò)在特定TCS下達(dá)到SO的充分條件.Xu等[9]采用仿真方法分析了TCS在減少北京市小汽車行駛公里和提高公交出行比例方面的效果.此外，關(guān)于TCS治理路網(wǎng)擁堵的均衡模型研究還有混合均衡路徑選擇行為下的路票均衡模型[10]、考慮出行者損失厭惡行為下的路票均衡模型[11]、考慮出行者感知誤差的路票隨機(jī)用戶均衡模型[12]等.關(guān)于TCS更詳細(xì)的綜述可見(jiàn)文獻(xiàn)[13].

盡管上述文獻(xiàn)從不同角度研究了TCS治理交通網(wǎng)絡(luò)擁堵的有效性，但這些研究大都只聚焦于路票的發(fā)行總量和路段上的路票收取量對(duì)于網(wǎng)絡(luò)均衡分配結(jié)果的影響，而忽視了不同的CDS對(duì)出行者路徑選擇行為的影響.另外，在考慮路票交易成本時(shí)，Nie[8]假設(shè)買、賣路票的交易成本為一個(gè)相同的常數(shù)，從而難以衡量路票交易成本和路票均衡價(jià)格之間的相對(duì)變化趨勢(shì)，也無(wú)法描述買、賣路票的交易成本不同時(shí)的情景.基于此，本文建立一個(gè)可明確描述不同CDS和買、賣交易成本的統(tǒng)一UE模型框架，給出保證UE解唯一的充分條件，并著重分析不同CDS和買、賣交易成本對(duì)于UE路段流量和路票均衡價(jià)格的影響.

1 UE配流模型及其解的唯一性

1.1 基本假設(shè)及UE條件

(1)

r∈Rw,w∈W

(2)

式中，p表示路票價(jià)格(假設(shè)已轉(zhuǎn)換為時(shí)間單位)；ρb和ρs分別表示買、賣路票的交易成本費(fèi)率，0≤ρs,ρb≤1；符號(hào)[·]+表示如下運(yùn)算，當(dāng)a≥0時(shí)，[a]+=a，當(dāng)a<0時(shí)，[a]+=0. 實(shí)際上，式(2)還可以描述更精細(xì)化更公平的路票發(fā)放方式，如基于出行者收入水平來(lái)確定路票初始量，此時(shí)可拓展為多用戶類情形.

顯然，交通網(wǎng)絡(luò)在給定的路票策略 (K,ka,φw)下達(dá)到均衡狀態(tài)時(shí)，必須滿足如下廣義UE條件(簡(jiǎn)稱路票UE條件)：

(3)

(4)

(5)

(6)

1.2 等價(jià)的VI模型

為了便于分析UE解的特性和設(shè)計(jì)求解算法，將上述路票UE條件寫成如下變分不等式(VI)模型：

(7)

定理1在一個(gè)給定的(K,ka,φw)下，VI模型(7)的解(f*,p*)一定滿足于相應(yīng)的路票UE條件.

證明由VI模型(7)不難看出，(f*,p*)是VI模型(7)的解，當(dāng)且僅當(dāng)(f*,p*)是如下線性規(guī)劃問(wèn)題的最優(yōu)解：

(8)

進(jìn)一步地可寫出上述線性規(guī)劃問(wèn)題的拉格朗日函數(shù)，即

(9)

由此可得到上述線性規(guī)劃問(wèn)題的KKT條件，即

(10)

定理2在一個(gè)給定的路票策略 (K,ka,φw)下，VI模型(7)至少存在一個(gè)解.

1.3 UE解的唯一性

Yang等[5]證明了在給定路票策略下UE路段流量解一定唯一，而均衡路票價(jià)格則在相當(dāng)寬松的條件下也能保證唯一，但是由于本文在凈廣義路徑費(fèi)用中明確地考慮了路票初始發(fā)放和交易成本的影響，使得該路徑費(fèi)用非可加(nonadditive)，而且該路徑費(fèi)用函數(shù)的Jacobian矩陣非對(duì)稱(asymmetric)，因此文獻(xiàn)[5]結(jié)論顯然不適用于本文.而且，此時(shí)VI模型(7)不存在等價(jià)的數(shù)學(xué)規(guī)劃(mathematical programming, MP)模型，因此本文中UE路段流量解的唯一性也無(wú)法簡(jiǎn)單地通過(guò)驗(yàn)證MP模型Hessian矩陣的正定性來(lái)判定.通過(guò)研究VI模型(7)不難發(fā)現(xiàn)，VI模型(7)的解(f*,p*)一定也是如下VI模型的解：

c(f*,p*)(f-f*)≥0 ?f∈Ω

(11)

定理3在給定的路票策略 (K,ka,φw)下，若滿足如下2個(gè)條件：

① 路阻函數(shù)ta(·)的單調(diào)性條件，即對(duì)任意v1,v2∈Ω(v1≠v2)，有不等式(t(v1)-t(v2))(v1-v2)>0.

② 路票交易總量關(guān)于路票價(jià)格的p*單調(diào)性條件，即對(duì)任意p1,p2∈R+(p1≠p2)，有

則交通網(wǎng)絡(luò)達(dá)到UE時(shí)，具有唯一的UE路段流量v*.

證明采用反證法.假設(shè)UE路段流量解不唯一，令其中2個(gè)UE解為(f1,v1),(f2,v2)∈Ω，對(duì)應(yīng)的路票價(jià)格為p1,p2∈R+，顯然有f1≠f2，v1≠v2，p1≠p2≠0.由VI模型(11)可知不等式c(f1,p1)(f2-f1)≥0和c(f2,p2)(f1-f2)≥0一定成立，聯(lián)立可得(c(f1,p1)-c(f2,p2))(f2-f1)≥0，該不等式左邊展開即得

不難看出，由于路票發(fā)行總量相等，上式右邊第2項(xiàng)、第3項(xiàng)均為0，因此只需要判斷第1項(xiàng)和第4項(xiàng)即可.根據(jù)定理3中的2個(gè)充分條件可知，上式中右邊小于0，而左邊大于等于0，顯然出現(xiàn)矛盾.因此當(dāng)定理3中的2個(gè)充分條件滿足時(shí)，交通網(wǎng)絡(luò)的UE路段流量解v*一定唯一.由此證畢.

定理3給出了交通網(wǎng)絡(luò)在給定TCS下， UE流量解唯一性的充分條件，本文進(jìn)一步給出交通網(wǎng)絡(luò)均衡時(shí)，市場(chǎng)中路票均衡價(jià)格的唯一性充分條件.

定理4在給定的路票策略 (K,ka,φw)下，若滿足如下2個(gè)條件：

① UE路段流量解v*唯一；

② 至少存在一個(gè)OD對(duì)，其2條被使用的均衡路徑上收取的路票量不同.

則交通網(wǎng)絡(luò)達(dá)到UE時(shí)，具有唯一的路票均衡價(jià)格p*.

證明令r1,r2∈Rw為OD對(duì)w∈W之間2條被使用的均衡路徑，則交通網(wǎng)絡(luò)在UE狀態(tài)時(shí)，有如下公式成立：

聯(lián)立以上兩式可得

2 基于次梯度投影的啟發(fā)式算法

由于本文中出行者的凈廣義路徑費(fèi)用非可加，而且存在路票邊際約束，傳統(tǒng)的Frank-Wolfe算法難以求解上述UE配流問(wèn)題.本文設(shè)計(jì)如下啟發(fā)式求解算法.

① 初始化.任意給定一個(gè)路票價(jià)格p(1)>0，預(yù)設(shè)的步長(zhǎng)序列為{αn,n=1,2,…}，且該步長(zhǎng)序列滿足：

(12)

同時(shí)，令算法容許誤差ε=10-4，當(dāng)前迭代次數(shù)n=1.

② 求解非可加的UE配流子問(wèn)題.將當(dāng)前路票價(jià)格p(n)替代VI模型(11)中的p*，可得到如下特定的非可加UE配流子問(wèn)題：

c(f*(p(n)))(f-f*(p(n)))≥0 ?f∈Ω

(13)

即尋找一個(gè)可行的網(wǎng)絡(luò)流量形態(tài)(f*(p(n)),v*(p(n)))∈Ω,使得VI模型(13)成立.

③ 收斂判斷.本文算法的收斂準(zhǔn)則為

(14)

若滿足收斂準(zhǔn)則，則算法終止，并輸出當(dāng)前路票價(jià)格p(n)和對(duì)應(yīng)的網(wǎng)絡(luò)流形態(tài)(f*(p(n)),v*(p(n)))；否則，轉(zhuǎn)入步驟④.

④ 更新當(dāng)前路票價(jià)格p(n).更新規(guī)則如下：

(15)

同時(shí)，令n=n+1，并轉(zhuǎn)入步驟②，再次求解UE分配子問(wèn)題.

由于算法中步驟④采用了次梯度投影法的更新策略，根據(jù)文獻(xiàn)[15]中定理2.7次梯度投影法的收斂性可知，上述算法中路票價(jià)格迭代序列{p(n)}必然收斂，最終的收斂值即為均衡路票價(jià)格，且相應(yīng)的UE配流子問(wèn)題的解即為UE路徑流量解.上述算法的主要計(jì)算工作量在于步驟②中求解非可加的UE配流子問(wèn)題，目前關(guān)于求解該UE子問(wèn)題的算法很多，如文獻(xiàn)[16].

3 算例

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

表1 輸入數(shù)據(jù)

首先，為了綜合分析路票的初始發(fā)放方式對(duì)于UE解的影響，本文對(duì)比了3種不同的路票發(fā)放方式情景下的UE路段流量和均衡路票價(jià)格.當(dāng)采用完全均勻發(fā)放的方式(情景1)時(shí)，每個(gè)出行者的路票初始發(fā)放量均為6個(gè)單位，即φw=6，而采用同一OD對(duì)路票均勻發(fā)放方式時(shí)，出行者的路票初始發(fā)放量有無(wú)數(shù)種情況，從中隨機(jī)選取2種情況，即φw1=5，φw2=7.2(情景2)和φw1=7，φw2=4.8(情景3).假設(shè)3種情景下買、賣路票的交易成本費(fèi)率均相同，分別為ρb=0.2，ρs=0.1.為了充分說(shuō)明路票初始發(fā)放方式對(duì)于網(wǎng)絡(luò)UE解的影響，本文以文獻(xiàn)[5]中路票UE模型(原始模型)下的均衡解作為參照，結(jié)果見(jiàn)表2，算法收斂趨勢(shì)如圖2所示.

表2 不同的路票初始發(fā)放方式下的UE解

圖2算法收斂趨勢(shì)圖

由表2可以看出，當(dāng)存在路票交易成本時(shí)，路票初始發(fā)放方式不同，則對(duì)應(yīng)的UE解也不相同，如情景1、情景2和情景3；當(dāng)交易成本為零時(shí)，路票初始發(fā)放方式不影響UE解，如原始模型.此外，從表2還可以看出在部分情景(如情景3)下，考慮交易成本時(shí)的路票均衡價(jià)格甚至比不考慮交易成本時(shí)的路票價(jià)格更低，即合適的路票發(fā)放方式和交易成本有可能使得出行者的凈廣義路徑費(fèi)用更低，從而為設(shè)計(jì)帕累托改進(jìn)的路票策略提供了可能.

從圖2中可以看出，不同的預(yù)定步長(zhǎng)序列{αn,n=1,2,…}對(duì)于算法的收斂速率影響較大.在情景3的路票初始發(fā)放方式下，當(dāng)αn分別為0.5/n，1/n，1.5/n時(shí)，算法達(dá)到收斂分別需要迭代19，32，46次，顯然，若能夠確定最優(yōu)步長(zhǎng)序列，則算法收斂速率將進(jìn)一步提高.

其次，為了分析交易成本對(duì)于UE解的影響，本文分別對(duì)比不同交易成本下的UE路徑流量和均衡路票價(jià)格.假設(shè)此時(shí)的路票初始發(fā)放方式采用路票完全均勻發(fā)放方式，即φw=6；路票交易成本ρb，ρs分別在0～1之間取值，取值間隔均為0.1，則有121個(gè)交易成本組合，分別計(jì)算各個(gè)組合(ρs，ρb)下的UE解，相應(yīng)的計(jì)算結(jié)果如圖3和圖4所示.圖中，A點(diǎn)對(duì)應(yīng)情景1的結(jié)果，B點(diǎn)為原始模型的結(jié)果.

圖3 路徑1的流量隨TC的變化趨勢(shì)

圖4 路票價(jià)格隨TC的變化趨勢(shì)

4 結(jié)論

1) 提出了在給定路票發(fā)放方式、路票收費(fèi)費(fèi)率以及交易成本下，交通網(wǎng)絡(luò)達(dá)到均衡狀態(tài)時(shí)的UE條件，并建立了等價(jià)的VI模型，進(jìn)一步給出了UE路段解以及均衡路票價(jià)格唯一性的充分條件.

2) 設(shè)計(jì)了一種快速收斂的求解算法，該算法涉及到雙層迭代循環(huán)，其中外層循環(huán)為基于次梯度投影法的路票價(jià)格更新過(guò)程，內(nèi)層循環(huán)為非可加UE配流子問(wèn)題的求解過(guò)程.

3) 算例結(jié)果表明，當(dāng)路票交易成本為零時(shí)，路票初始發(fā)放方式則對(duì)配流結(jié)果無(wú)影響；當(dāng)路票交易成本非零時(shí)，路票初始發(fā)放方式不同，則對(duì)應(yīng)的UE路段流量解、路票價(jià)格也不相同，且路票均衡價(jià)格隨賣路票的交易成本的增大而增大，而隨買路票的交易成本的增大而減小；在部分情景下，考慮交易成本時(shí)的路票均衡價(jià)格甚至比不考慮交易成本時(shí)的路票價(jià)格更低，這為進(jìn)一步設(shè)計(jì)帕累托改進(jìn)的路票策略提供了可能.

本研究未來(lái)的拓展方向有：考慮需求彈性、考慮出行者時(shí)間價(jià)值異質(zhì)性、考慮公交和小汽車等多種交通方式的路票UE模型，以及算法收斂速率的進(jìn)一步改進(jìn)等.

參考文獻(xiàn)(References)

[1] Knockaert J, Verhoef E T, Rouwendal J. Bottleneck congestion: Differentiating the coarse charge[J].TransportationResearchPartB:Methodological, 2016,83: 59-73. DOI:10.1016/j.trb.2015.11.004.

[2] Raux C, Souche S. The acceptability of urban road pricing: A theoretical analysis applied to experience in lyon[J].JournalofTransportEconomics&Policy, 2004,38(2):191-215.

[3] Verhoef E, Nijkamp P, Rietveld P. Tradeable permits: Their potential in the regulation of road transport externalities [J].EnvironmentandPlanningB:PlanningandDesign, 1997,24(4): 527-548. DOI:10.1068/b240527.

[4] Kockelman K M, Kalmanje S. Credit-based congestion pricing: A policy proposal and the public’s response [J].TransportationResearchPartA:PolicyandPractice, 2005,39(7/8/9)：671-690. DOI:10.1016/j.tra.2005.02.014.

[5] Yang H, Wang X L. Managing network mobility with tradable credits [J].TransportationResearchPartB:Methodological, 2011,45(3): 580-594. DOI:10.1016/j.trb.2010.10.002.

[6] Wang X L, Yang H, Zhu D L, et al. Tradable travel credits for congestion management with heterogeneous users [J].TransportationResearchPartE:LogisticsandTransportationReview, 2012,48(2): 426-437. DOI:10.1016/j.tre.2011.10.007.

[7] Zhu D L, Yang H, Li C M, et al. Properties of the multiclass traffic network equilibria under a tradable credit scheme [J].TransportationScience, 2015,49(3):519-534. DOI:10.1287/trsc.2013.0508.

[8] Nie Y. Transaction costs and tradable mobility credits [J].TransportationResearchPartB, 2012,46(1): 189-203. DOI:10.1016/j.trb.2011.10.002.

[9] Xu M, Grant-Muller S. Trip mode and travel pattern impacts of a tradable credits scheme: A case study of Beijing[J].TransportPolicy, 2016,47:72-83. DOI:10.1016/j.tranpol.2015.12.007.

[10] He F , Yin Y F , Shirmohammadi N , et al. Tradable credit schemes on networks with mixed equilibrium behaviors [J].TransportationResearchPartB:Methodological, 2013,57(5):47-65.

[11] Bao Y, Gao Z, Xu M, et al. Tradable credit scheme for mobility management considering travelers’ loss aversion[J].TransportationResearchPartE:LogisticsandTransportationReview, 2014,68:138-154. DOI:10.1016/j.tre.2014.05.007.

[12] Han F, Cheng L. Stochastic user equilibrium model with a tradable credit scheme and application in maximizing network reserve capacity [J].EngineeringOptimization, 2017,49(4): 549-564. DOI:10.1080/0305215x.2016.1193357.

[13] Grant-Muller S, Xu M. The role of tradable credit schemes in road traffic congestion management[J].TransportReviews, 2014,34(2):128-149. DOI:10.1080/01441647.2014.880754.

[14] Facchinei F, Pang J S.Finite-dimensionalvariationalinequalityandcomplementarityproblems[M]. London, United Kingdom: Springer-Verlag London Ltd, 2003:148-149.

[15] Larsson T, Patriksson M, Str?mberg A B. Conditional subgradient optimization—Theory and applications[J].EuropeanJournalofOperationalResearch, 1996,88(2): 382-403. DOI:10.1016/0377-2217(94)00200-2.

[16] ChenA, Lo H K, Yang H. A self-adaptive projection and contraction algorithm for the traffic assignment problem with path-specific costs [J].EuropeanJournalofOperationalResearch,2001,135(1): 27-41. DOI:10.1016/s0377-2217(00)00287-3.