韓　飛　程　琳

(東南大學(xué)交通學(xué)院，南京　210096)

?

考慮可交易路票策略的隨機(jī)用戶均衡模型及算法

韓飛程琳

(東南大學(xué)交通學(xué)院，南京210096)

摘要:為了彌補(bǔ)以往路票均衡模型中假設(shè)出行者知道準(zhǔn)確路徑費(fèi)用的不足，對可交易路票策略下的隨機(jī)用戶均衡(SUE)分配問題進(jìn)行了研究．首先，明確了在給定路票策略下交通網(wǎng)絡(luò)達(dá)到均衡狀態(tài)時(shí)的網(wǎng)絡(luò)流量均衡和路票市場均衡條件;然后利用2個(gè)構(gòu)造函數(shù)的相關(guān)數(shù)學(xué)性質(zhì)建立了等價(jià)的通用型路票SUE模型，在出行者感知誤差服從Gumbel分布假設(shè)下，將該模型化簡為Logit型路票SUE模型，并給出了路票均衡價(jià)格唯一性的充分條件．由于傳統(tǒng)MSA算法無法求解路票SUE模型，因此提出一種高效收斂的拉格朗日對偶算法．算例結(jié)果表明，該算法在不同步長序列和離散參數(shù)水平下均具有較好的收斂性，而且步長序列對算法收斂速度的影響比離散參數(shù)的影響更加顯著．

關(guān)鍵詞:可交易路票策略;隨機(jī)用戶均衡;路票價(jià)格;拉格朗日對偶算法

引用本文:韓飛，程琳．考慮可交易路票策略的隨機(jī)用戶均衡模型及算法［J］．東南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016，46(1) : 215－220．DOI: 10．3969/j．issn．1001－0505．2016．01．035．

擁擠收費(fèi)在理論上被多次證明可以有效緩解城市交通擁堵，但在實(shí)際應(yīng)用中卻由于社會(huì)公平性、稅收中性等問題而難以得到廣泛應(yīng)用．為了設(shè)計(jì)出既能有效治堵又能被公眾接受的治堵策略，許多學(xué)者開始研究一種新穎的交通需求管理手段——可交易路票策略，或可交易行駛權(quán)證策略(tradable credit scheme)．由于該行駛權(quán)證的調(diào)控作用類似于我國計(jì)劃經(jīng)濟(jì)時(shí)期中的糧票，因此本文稱為路票．該策略的主要思想是:首先交通部門在特定時(shí)間段(如每季度)初始時(shí)向所有具備資格的出行者免費(fèi)發(fā)放相同數(shù)量的路票，然后出行者使用各路段時(shí)交納相應(yīng)數(shù)量的路票，路票可以在市場中自由交易，路票價(jià)格完全由市場供求關(guān)系決定，路票到期后自動(dòng)失效以避免路票囤積．交通部門只作為監(jiān)管部門，通過調(diào)控路票初始發(fā)放量和每個(gè)路段的路票收取量，從而實(shí)現(xiàn)交通系統(tǒng)的最優(yōu)化目標(biāo)．為了定量描述可交易路票策略對交通網(wǎng)絡(luò)中出行需求的調(diào)控作用，Yang等［1］建立了基于可交易路票策略的用戶均衡(user equilibrium，UE)模型(簡稱路票UE模型)，并討論了實(shí)現(xiàn)系統(tǒng)最優(yōu)(system optimal，SO)的路票策略以及pareto-improving SO路票策略，并拓展到彈性需求情形，由此驗(yàn)證了該策略解決交通擁堵問題的有效性和可行性．Wang等［2］、Zhu等［3］在該研究基礎(chǔ)上進(jìn)一步考慮了不同出行者的時(shí)間價(jià)值異質(zhì)性，并利用變分不等式建立了多用戶類的路票UE模型．Nie［4］研究了在兩類路票市場中交易成本對于SO路票策略調(diào)控能力的影響，發(fā)現(xiàn)在拍賣市場中該策略可以實(shí)現(xiàn)路網(wǎng)系統(tǒng)最優(yōu)，而在議價(jià)市場中不可能實(shí)現(xiàn)路網(wǎng)系統(tǒng)最優(yōu)．另外，其他關(guān)于可交易路票策略下的網(wǎng)絡(luò)均衡模型有混合出行行為下的路票均衡模型［5］、考慮出行者損失厭惡行為下的路票均衡模型［6］等．

盡管上述文獻(xiàn)從不同角度對可交易路票策略治理交通擁堵的有效性展開了研究，但其理論建?；A(chǔ)都是UE模型．UE模型假設(shè)出行者對于出行費(fèi)用具有準(zhǔn)確的認(rèn)知，顯然這與實(shí)際情況并不相符，受現(xiàn)實(shí)中出行者認(rèn)知能力局限性和出行時(shí)間不確定性等因素影響，出行者不可能準(zhǔn)確知道各條路徑的出行費(fèi)用，因而只能根據(jù)其感知的路徑費(fèi)用來選擇路徑．另一方面，SUE模型可以明確考慮出行者對于出行費(fèi)用的感知誤差及其所服從的概率分布，如Gumbel分布、正態(tài)分布等，相比UE模型來說，采用SUE模型來研究可交易路票策略顯然更加合理，也更加符合實(shí)際．由于考慮可交易路票策略的SUE模型(簡稱路票SUE模型)無法像路票UE模型那樣，通過簡單地添加一個(gè)線性路票約束條件來建立，因此，本文首先建立了2個(gè)新的構(gòu)造函數(shù)，通過運(yùn)用這2個(gè)構(gòu)造函數(shù)與原始對應(yīng)函數(shù)之間的數(shù)學(xué)轉(zhuǎn)換關(guān)系建立了一個(gè)極小值模型，并證明了該模型即為等價(jià)的路票SUE模型;其次，由于傳統(tǒng)的MSA(method of successive averaging)算法無法求解路票SUE模型，本文進(jìn)一步設(shè)計(jì)了高效且收斂的拉格朗日對偶算法，并利用算例驗(yàn)證了該算法的有效性．

1　模型

1. 1網(wǎng)絡(luò)均衡條件

假設(shè)有向圖G = (N，A)表示一個(gè)強(qiáng)連通交通網(wǎng)絡(luò)，其中，N為節(jié)點(diǎn)集合，A為路段集合．W為所有OD對集合，qw表示OD對w∈W之間的出行需求．R = (Rw，w∈W)為所有工作路徑集合，其中Rw表示OD對w∈W之間所有工作路徑集合．(K，ka)表示一個(gè)給定的路票策略，K表示交通部門向出行者發(fā)放的總路票數(shù)量，即，其中表示每個(gè)出行者所獲得的初始路票數(shù)量，ka表示路段a∈A上的路票收取數(shù)量．此外，分別表示路徑r∈Rw上的流量和總廣義費(fèi)用，va和ta分別表示路段a∈A上的流量和旅行時(shí)間．由此，可以得到給定路票策略(K，ka)下的可行的網(wǎng)絡(luò)流形態(tài)集合Φ(假設(shè)非空)，其表達(dá)式為

由于現(xiàn)實(shí)生活中出行者對于實(shí)際出行費(fèi)用會(huì)存在感知誤差，因此假設(shè)在給定路票策略為(K， ka)，則出行者感知的路徑廣義費(fèi)用等于真實(shí)的路徑廣義費(fèi)用加上感知誤差，即

式中，θ＞0為描述出行者對路網(wǎng)熟悉程度的離散參數(shù)．至此，可以知道在路票策略(K，ka)下交通網(wǎng)絡(luò)達(dá)到均衡狀態(tài)時(shí)，網(wǎng)絡(luò)流量(frw，va)∈Φ和路票價(jià)格p必然滿足如下網(wǎng)絡(luò)均衡條件:

網(wǎng)絡(luò)均衡條件式(5a)表示當(dāng)交通網(wǎng)絡(luò)達(dá)到均衡狀態(tài)時(shí)，網(wǎng)絡(luò)流量滿足SUE配流原則;式(5b)表示路票市場均衡條件，即只有當(dāng)所有發(fā)放的路票都被完全使用時(shí)，路票均衡價(jià)格才為正數(shù)，此時(shí)路票策略可以有效調(diào)控出行需求．

1. 2等價(jià)的路票SUE模型

傳統(tǒng)無約束SUE模型的特殊性使得相應(yīng)的路票SUE模型的建立無法采用路票UE模型的建立方法，即在傳統(tǒng)SUE模型中添加一個(gè)線性路票約束所得到的最小化模型，其Kuhn-Tucker一階最優(yōu)性條件(KKT條件)不等價(jià)于網(wǎng)絡(luò)均衡條件(5)．為了建立相應(yīng)的等價(jià)最小化問題，本文針對路段旅行時(shí)間函數(shù)ta(x)，a∈A定義如下構(gòu)造函數(shù)［7］:∈Φ，均存在連續(xù)可微的向量函數(shù)

同時(shí)，根據(jù)文獻(xiàn)［8］可知，對于任意正的可行路徑流量形態(tài)(，滿足如下條件:

通過分析以上相關(guān)數(shù)學(xué)式的數(shù)學(xué)特性，可以為網(wǎng)絡(luò)均衡條件式(5)建立如下等價(jià)的最小化數(shù)學(xué)模型(即路票SUE模型P1) :

定理1模型P1與路票策略(K，ka)下的SUE分配問題等價(jià)．

證明模型P1的拉格朗日函數(shù)為

式中，μw，ρ為相應(yīng)約束條件的對偶變量．由KKT條件有

將式(10a)、(7)代入式(8)，可以得到

顯然，由式(10b)、(11)可知，上述所建立模型P1的KKT條件正好是路票策略(K，ka)下的網(wǎng)絡(luò)均衡條件，且對偶變量ρ即為路票均衡價(jià)格，故定理1得證．

模型P1是一個(gè)通用的路票SUE模型，當(dāng)假設(shè)出行者感知誤差服從正態(tài)分布時(shí)，可以得到Probit型的路票SUE模型;而假設(shè)感知誤差服從Gumbel分布時(shí)，可以得到Logit型的路票SUE模型，此時(shí)由文獻(xiàn)［8］可知

將式(12)、(13)代入模型P1，經(jīng)過簡單推導(dǎo)可以得到如下Logit型路票SUE模型(模型P2)的解析表達(dá)式:

可以看出，模型P2和傳統(tǒng)Logit型SUE模型［9］非常類似，除了目標(biāo)函數(shù)中多了一個(gè)常數(shù)項(xiàng)外，唯一的區(qū)別就在于模型P2多了一個(gè)線性的路票約束條件．由于傳統(tǒng)的Logit型SUE模型是一個(gè)凸規(guī)劃問題，具有唯一最優(yōu)解，因此，模型P2顯然也是凸規(guī)劃問題［9］，同樣也具有唯一最優(yōu)解．

相對于模型P1來說，模型P2具有明確的解析表達(dá)式，同時(shí)大幅減少了計(jì)算量．因此，下面本文在模型P2的基礎(chǔ)上進(jìn)一步展開研究．

盡管在網(wǎng)絡(luò)均衡狀態(tài)時(shí)SUE網(wǎng)絡(luò)流量解唯一，但是路票價(jià)格并不一定唯一，下面給出路票價(jià)格p唯一性的充分條件．

定理2當(dāng)交通網(wǎng)絡(luò)在路票策略(K，ka)下達(dá)到網(wǎng)絡(luò)均衡狀態(tài)時(shí)，如果至少存在一個(gè)OD對有2條路徑上的路票收取總量不同，那么均衡路票價(jià)格p必定唯一．

證明當(dāng)路票總量發(fā)放過多時(shí)，路票會(huì)有剩余，即路票總量約束為非活性約束，此時(shí)路票價(jià)格唯一，且p = 0．當(dāng)所有路票被完全使用時(shí)，路票總量約束為活性約束，此時(shí)p＞0．不失一般性，假設(shè)OD對w之間存在2條路票收取量不同的路徑r1，r2∈Rw，根據(jù)Logit型SUE配流原則，可以得到

從而可以進(jìn)一步得到均衡路票價(jià)格p的表達(dá)式:

顯然，此時(shí)路票均衡價(jià)格p由式(16)唯一確定．故定理2得證．

在實(shí)際交通網(wǎng)絡(luò)中，由于備選路徑的多樣性，定理2通常都是成立的．另外，路票價(jià)格p =0意味著對應(yīng)的路票策略沒有起到調(diào)控交通需求的作用，即是一個(gè)無效的路票策略，因此需要盡量避免．本文假設(shè)所給定的路票策略均有效，即可用如下有效路票策略集合Ψ來界定:

確認(rèn)發(fā)生雞痘的情況下，首先要對雞痘的類型進(jìn)行辨別。如果發(fā)生的是皮膚型雞痘，在病情不嚴(yán)重的情況下可以不予管理，病情較重的可以通過對痘痂進(jìn)行消毒和剝離，并涂抹紫藥水的方式進(jìn)行治療。

2　算法

由于路票SUE模型P1和P2都帶有額外的線性約束，因此求解傳統(tǒng)SUE模型的MSA算法無法適用，為了設(shè)計(jì)一種通用的高效收斂的求解算法，本文提出如下拉格朗日對偶算法．

①初始化．令初始路票價(jià)格p0＞0，令迭代次數(shù)n =1，容忍誤差ε=10－4．

②計(jì)算路段旅行時(shí)間修正后的SUE解．將原始路段旅行時(shí)間函數(shù){ ta(va)，a∈A}修正為{ ta(va) +kap(n)，a∈A}，然后調(diào)用一次MSA算法，得到相應(yīng)的SUE路段流量解{ va(p(n))，a∈A}．

④更新當(dāng)前路票價(jià)格p(n)．按照下式更新當(dāng)前路票價(jià)格p(n):

式中，{αn，n = 1，2，…}為預(yù)設(shè)的步長序列，且滿足條件0＜αn＜1，＜∞，本文取αn= 1/n．

⑤進(jìn)行下一次迭代．令n = n +1，然后返回步驟②．

上述算法中，P+［p(n)+αnL'(p)］為非負(fù)投影，L(p)為模型P1的拉格朗日對偶函數(shù)，即L(p)，其對p求導(dǎo)可得，因此將其代入后可得到非負(fù)投影表達(dá)式．由文獻(xiàn)［10］中定理

2. 7關(guān)于次梯度投影法的收斂性可知，上述拉格朗日對偶算法必然會(huì)收斂到最優(yōu)解．

3　算例

本文選擇經(jīng)典的Nguyen-Dupuis網(wǎng)絡(luò)［11］作為算例，該網(wǎng)絡(luò)有13個(gè)節(jié)點(diǎn)、19條邊和4個(gè)OD對，如圖1所示．路段阻抗函數(shù)為標(biāo)準(zhǔn)的BPR函數(shù)，即

圖1　Nguyen-Dupuis網(wǎng)絡(luò)及路段屬性參數(shù)

表1　Nguyen-Dupuis網(wǎng)絡(luò)各路段自由旅行時(shí)間及容量

為了說明可交易路票策略對交通網(wǎng)絡(luò)擁擠狀況的改善作用，本文將路票策略實(shí)施前后的SUE路段流量進(jìn)行對比，結(jié)果見表2．從表中可以看出，給定的路票策略可以有效緩解網(wǎng)絡(luò)中部分路段的擁堵狀況，如路段9，10的交通飽和度分別由1. 31，1. 20降為1. 17，1. 09．同時(shí)，路網(wǎng)總出行時(shí)間由77 227. 66減少為76 145. 72，由此可以說明設(shè)計(jì)合理的可交易路票策略不僅能夠改善路網(wǎng)中部分瓶頸路段的擁堵狀況，還能提高整個(gè)交通系統(tǒng)的出行效率．

為了說明拉格朗日對偶算法的收斂特性，本文分別對不同步長序列和不同離散參數(shù)水平下的算法收斂趨勢進(jìn)行對比(見圖2和圖3)．由圖2可以看出，當(dāng)固定θ=1時(shí)，在不同步長序列{αn}下，算法均可以收斂到相同的穩(wěn)定點(diǎn)p = 0. 987 8，其中αn= 0. 5/n時(shí)收斂速度最快;由圖3可以看出，當(dāng)固定αn=1/n時(shí)，算法在不同離散參數(shù)θ水平下均可以收斂到相應(yīng)的穩(wěn)定點(diǎn)，說明出行者對路網(wǎng)的熟悉程度并不會(huì)影響算法的收斂性．另外，對比圖2和圖3還可以看出，步長序列對于算法收斂性的影響要比離散參數(shù)的影響更加顯著，選取合適的步長序列可以減少計(jì)算的迭代次數(shù)．

表2　路票策略實(shí)施前后的SUE路段流量對比

圖2　不同步長序列{αn}下的收斂趨勢

圖3　不同離散參數(shù)θ下的收斂趨勢

4　結(jié)語

本文主要研究了可交易路票策略下的隨機(jī)用戶均衡分配模型和算法．首先運(yùn)用2個(gè)構(gòu)造函數(shù)的相關(guān)性質(zhì)建立了一個(gè)等價(jià)的通用型路票SUE模型，在Gumbel分布的感知誤差假設(shè)下可得到Logit型路票SUE模型，并給出了路票價(jià)格唯一性的充分條件．其次提出一種高效且收斂的拉格朗日對偶算法，并通過算例說明該算法在不同情況下均具有較好收斂性．由于本文路票SUE模型明確考慮了出行者的隨機(jī)感知誤差，因此相對于路票UE模型來說可以更合理更準(zhǔn)確地刻畫出行者在給定路票策略下的路徑選擇行為．本文研究工作為城市交通擁堵治理提供一種新的思路和手段，并為可交易路票策略的定量評價(jià)和優(yōu)化設(shè)計(jì)提供了理論基礎(chǔ)．

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

［1］Yang H，Wang X L．Managing network mobility with tradable credits［J］．Transportation Research Part B: Methodological，2011，45 (3 ) : 580－594．DOI: 10. 1016/j．trb．2010. 10. 002．

［2］Wang X L，Yang H，Zhu D L，et al．Tradable travel credits for congestion management with heterogeneous users［J］．Transportation Research Part E: Logistics and Transportation Review，2012，48(2) : 426－437． DOI: 10. 1016/j．tre．2011. 10. 007．

［3］Zhu D L，Yang H，Li C M，et al．Properties of the multiclass traffic network equilibria under a tradable credit scheme［J］．Transportation Science，2015，49 (3) : 519－534．

［4］Nie Y．Transaction costs and tradable mobility credits ［J］．Transportation Research Part B: Methodological，2012，46 (1 ) : 189－203．DOI: 10. 1016/j．trb．2011. 10. 002．

［5］He F，Yin Y F，Shirmohammadi N，et al．Tradable credit schemes on networks with mixed equilibrium behaviors［J］．Transportation Research Part B: Methodological，2013，57(5) : 47－65．DOI: 10. 1016/j．trb．2013. 08. 016．

［6］Bao Y，Gao Z Y，Xu M，et al．Tradable credit scheme for mobility management considering travelers' loss aversion［J］．Transportation Research Part E: Logistics and Transportation Review，2014，68: 138－154．DOI: 10. 1016/j．tre．2014. 05. 007．

［7］Meng Q，Lam W H K，Yang L．General stochastic user equilibrium traffic assignment problem with link capacity constraints［J］．Journal of Advanced Transportation，2008，42(4) : 429－465．

［8］Maher M，Stewart K，Rosa A．Stochastic social optimum traffic assignment［J］．Transportation Research Part B: Methodological，2005，39 (8) : 753－767．DOI: 10. 1016/j．trb．2004. 10. 001．

［9］Fisk C．Some developments in equilibrium traffic assignment［J］．Transportation Research Part B: Methodological，1980，14(3) : 243－255．

［10］Larsson T，Patriksson M，Str?mberg A B．Conditional subgradient optimization—theory and applications［J］．European Journal of Operations Research，1996，88: 382－403．

［11］Sang N，Dupuis C．An efficient method for computing traffic equilibria in networks with asymmetric transportation costs［J］．Transportation Science，1984，18 (2) : 185－202．

Stochastic user equilibrium model and its algorithm considering tradable credit scheme

Han Fei Cheng Lin
(School of Transportation，Southeast University，Nanjing 210096，China)

Abstract:In order to compensate the deficiency that the travelers are assumed to know the accurate route costs in previous credit equilibrium models，the stochastic user equilibrium (SUE) assignment with tradable credit scheme (TCS) was investigated．First，the equilibrium conditions of network flows and the credit market were presented to describe the equilibrium state of transportation network on a given TCS．Then an equivalent general SUE model with TCS was established based on the mathematical properties of two constructed functions．Under the assumption that travelers' perception errors are Gumbel distributed，the general SUE model with TCS was simplified to the Logit-based SUE model with TCS，and a sufficient condition for unique equilibrium credit price was provided．Since the traditional method of successive averaging (MSA) was not feasible，an efficiently convergent Lagrangian dual method (LDM) was proposed to solve the models．The numerical example results show that the LDM has good convergence on different step size sequences and dispersion parameters，and the step size sequences have a significant impact at the convergence speed than the dispersion parameters．

Key words:tradable credit scheme; stochastic user equilibrium; credit price;Lagrangian dual method

基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(51178110，51378119)、江蘇省研究生創(chuàng)新基金資助項(xiàng)目(KYLX 0178)．

收稿日期:2015-07-05．

作者簡介:韓飛(1986—)，男，博士生;程琳(聯(lián)系人)，男，博士，教授，博士生導(dǎo)師，gist@ seu．edu．cn．

DOI:10．3969/j．issn．1001－0505．2016．01．035

中圖分類號:U491

文獻(xiàn)標(biāo)志碼:A

文章編號:1001－0505(2016) 01-0215-06