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

韓　飛　程　琳

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

?

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

韓飛程琳

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

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

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

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

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

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

1　模型

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

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

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

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

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

1. 2等價的路票SUE模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

從而可以進一步得到均衡路票價格p的表達式:

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

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

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

2　算法

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

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

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

④更新當前路票價格p(n)．按照下式更新當前路票價格p(n):

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

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

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

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

3　算例

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

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

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

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

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

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

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

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

4　結(jié)語

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

參考文獻(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

基金項目:國家自然科學(xué)基金資助項目(51178110，51378119)、江蘇省研究生創(chuà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

文獻標志碼:A

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