自私-利他用戶混合均衡交通分配的效率損失

余孝軍, 張文專

(貴州財經(jīng)大學(xué) a.數(shù)學(xué)與統(tǒng)計學(xué)院;b.貴州省經(jīng)濟系統(tǒng)仿真重點實驗室, 貴陽 550025)

自私-利他用戶混合均衡交通分配的效率損失

余孝軍*a,b, 張文專b

(貴州財經(jīng)大學(xué) a.數(shù)學(xué)與統(tǒng)計學(xué)院;b.貴州省經(jīng)濟系統(tǒng)仿真重點實驗室, 貴陽 550025)

考慮同時存在兩類不同用戶(自私用戶和利他用戶)的混合均衡交通網(wǎng)絡(luò)的效率損失.其中,自私用戶按照用戶均衡原則選擇出行路徑,利他用戶按照最小化自身的理解出行成本選擇出行路徑,其理解出行成本是自私項和利他項的線性組合.首先,構(gòu)建了刻畫這類混合均衡交通分配的變分不等式模型;然后,運用解析推導(dǎo)的方法得到了這類混合均衡交通分配的效率損失上界,并分析了效率損失上界和參數(shù)之間的關(guān)系;最后,給出了數(shù)值算例.研究結(jié)果表明,效率損失上界和系統(tǒng)的最大、最小利他系數(shù)及路段出行成本函數(shù)相關(guān).數(shù)值算例表明解析方法是可行的.

城市交通;效率損失;變分不等式;混合交通;自私用戶;利他用戶

1 引 言

近年來,隨著對用戶均衡相對系統(tǒng)最優(yōu)效率損失研究的進展,學(xué)者們開始研究交通網(wǎng)絡(luò)中存在異質(zhì)用戶時的效率損失.Roughgarden[1]在作業(yè)排序問題中進行了初步研究.劉天亮等人[2]研 究 了ATIS 作用下混合交通均衡的效率損失上界.Yu 和Huang[3]探討了路段出行成本函數(shù)為多項式函數(shù)時 UE-CN 混合均衡交通分配的效率損失.Chen 和Kempe[4]研究了用戶為利他用戶時的效率損失. Karakostas 等人[5]探討了網(wǎng)絡(luò)中存在著自私用戶和刻板用戶(這類用戶事先根據(jù)網(wǎng)絡(luò)的硬件指標(biāo)進行出行決策,而且在出行過程中不更改既定出行方案,這類用戶完全忽視了網(wǎng)絡(luò)擁堵程度對自己的影響)的效率損失.

本文將考慮網(wǎng)絡(luò)中同時存在著自私用戶和利他用戶兩類不同用戶時交通均衡分配的效率損失問題.其中,自私用戶根據(jù)用戶均衡原則選擇出行路徑,其目的是最小化自己的出行成本,利他用戶在出行時不僅考慮自身的實際出行成本,還考慮自身的出行給其他用戶帶來的擁擠外部性,按照最小化自身的理解出行成本選擇出行路徑,其理解出行成本是自私項和利他項的線性組合(具體定義見第 2 節(jié)).首先,構(gòu)建自私-利他用戶混合均衡交通分配的等價變分不等式模型;在此基礎(chǔ)上,界定該類混合均衡的效率損失上界,并分析影響效率損失上界的影響因素;最后,給出數(shù)值算例進行驗證.

2 混合均衡交通分配模型

有向圖 G=(N,A) 表示一個交通網(wǎng)絡(luò),其中 N和A分別表示節(jié)點集和路段.u表示網(wǎng)絡(luò)中的自私用戶;M表示網(wǎng)絡(luò)中利他用戶集合;Wu是網(wǎng)絡(luò)中自私用戶控制的出行OD對集合;Wm,βm分別表示利他用戶m∈M控制的出行OD對集合和利他系數(shù);W≡Wu∪ WM;dw表示OD對w∈W間的出行需求;Rw表示OD對w∈W間的路徑集;frw表示路徑上的流量;如果路段 a∈A 在路徑 r∈ Rw上,則,否則表示 OD對集 Wu在路段 a 上的流量;vu≡ ( …,,…) 表示自私用戶產(chǎn)生的路段流量向 量;表示 OD 對集Wm,m∈M在路段a上的流量;…) 表示路段 a 上的流量向量;表示利他用戶 m 產(chǎn)生的路段流量向量; vM≡ ( …,vm-1,vm,vm+1,…);v ≡ (vu,vM);表示利他用戶在路段 a 產(chǎn)生的總流量;va=表示路段a上的總流量 ; 假設(shè)路段出行成本函數(shù) ta(va)是路段流量可分離函數(shù),并且是流量的連續(xù)可微單調(diào)遞增的凸函數(shù).

假設(shè)所有 OD 對的出行量是固定的,則自私用戶的可行域 Ωu和利他用戶 m 的可行域 Ωm分別為:

Ωu={vu|vu滿足約束條件(1)-(3)}:

Ωm={vm|vm滿足約束條件(4)-(6)},?m∈M:

定義1利他系數(shù)為 β(β ∈ [-1,1])的利他用戶選擇路徑r的目的是最小化自身出行成本函數(shù), 其 中是出行成 本的自 私 項,是出行成本的利他項.(ta(va)va)′是函數(shù) ta(va)va關(guān)于變量 va的微分.故可改寫為

利他用戶的理解出行成本可以認為是其實際的出行成本(自私項)與其認為自身出行會給其他用戶帶來的外部性(利他項)之和.顯然,當(dāng)利他系數(shù) β =1 時,即用戶是完全利他的,則其理解出行成本就是用戶按照系統(tǒng)最優(yōu)原則出行時的出行成本;當(dāng)利他系數(shù) β =0 時,即用戶是自私的,則其理解出行成本就是按照用戶均衡原則出行時的出行成本.所以,利他系數(shù)為 βm的利他用戶 m ∈ M 在路段 a 上的理解出行成本為.本文假設(shè) βm∈ [0,1].

對自私用戶而言,其出行決策原則是在利他用戶出行決策給定的情況下最小化自己的出行成本,其求解等價于求解下面的優(yōu)化問題:

同時滿足優(yōu)化問題(7)和(8)的解稱為自私-利他用戶的混合交通均衡解.同時求解優(yōu)化問題(7)和(8)等價于求解如下的變分不等式:

引理1如果路段出行成本函數(shù) ta(va),a ∈ A是嚴格遞增的凸函數(shù),則向量v∈ Ω 是自私-利他用戶混合交通均衡解當(dāng)且僅當(dāng)下面的不等式成立:尋找v,滿足

由于 ta(va) 是嚴格遞增的凸函數(shù),則變分不等式問題(9) 有解[7].進一步,自私用戶和利他用戶在路段 a∈ A上的路段理解出行成本向量為如 果對任意路段a∈A都是嚴格單調(diào)函數(shù),則變分不等式問題(9)至多有一個解[7].

由于 ta(va) 是嚴格遞增凸函數(shù),故問題(10)有關(guān)于路段總流量的唯一解.則系統(tǒng)最優(yōu)下的總出行成本為

定義自私-利他用戶混合均衡交通分配的效率損失分別為

易得, ρ≥ 1.下面,我們來界定路段出行成本函數(shù)在特定條件下的上界值.

3 界定效率損失的上界

在界定自私-利他混合均衡交通分配的效率損失之前,先介紹如下的引理:

引理2假設(shè)路段出行成本函數(shù) ta(va) 是連續(xù)可微嚴格遞增的凸函數(shù),且對任意的 c ∈ [0,1]滿足 ta(cx) ≥ cta(x), 則 對 任 意 的 va≥ 0, 有vat′a(va) ≤ ta(va) 成立.

證由文獻[8]中的(7)式可知對任意 va≥0,有

上式中第二個不等式成立原因是因為 ta(0) ≥ 0.又由于對任意的 c ∈ [0,1] 滿足不等式 ta(cx) ≥cta(x),所以

由 式 (12)、 式 (13) 可 得 vat′a(va/2) ≤2ta(va/2).用 va取代 vat′a(va/2) ≤ 2ta(va/2) 中的va/2,可得 vat′a(va) ≤ ta(va) 成立.

設(shè) vso是最小化問題(10)的解. 在變分不等式(9) 中 用分 別取 代, 則 有

由于可行域 v≥ 0 比可行域 v∈ Ω 大,故式(16) 的最后一個不等式成立.下面我們來考慮(16)最后一個不等式右邊第二項的最大值,即考慮下面的非線性規(guī)劃問題

設(shè) F(va)=(ta(va)-ta(va))va+ ∑βmvat′a(va)(vmam∈M-vma).由于F(va)的 Hessian 矩陣是半負定矩陣,因 此 F(va) 是關(guān)于變量vua≥ 0,vma≥0,m∈M 的凹函數(shù).從而 F(va) 有唯一的全局最大值.設(shè) λua,λma,a∈A是變量vua≥0,vma≥0,m∈M的Lagrange乘子,故可得(17)的一階最優(yōu)性條件如下:

由于出行成本函數(shù) ta(va) 是嚴格遞增函數(shù),故式(22)有唯一解.設(shè)由式(20),易得從 而 ,= 0或如果,我們可以得到 F(va)=0. 若 βm=0,則 有 F(va)=其中不等式成立的原因是因為 ta(cx) ≥ cta(x).設(shè)

知如果 βm1＞ βm2,則有再由式(21)可得設(shè) βm和分別是路段 a 上存在正流量的最大和最小利他系數(shù).從而有和

由 ta(va) 是嚴格遞增的凸函數(shù),且1],則式(24) 有唯一解.設(shè)0 ≤ μa≤1,,0 ≤ ωa≤ 1,a∈ A,0 ≤ μa+ ωa≤ 1.故有

這里

定義2

由式(16)和式(27)可得

故可以得到如下關(guān)于自私-利他用戶混合均衡交通分配的效率損失上界定理:

定理1對任意給定的路段出行成本函數(shù)類C,任意 ta(va) ∈ C 是連續(xù)可微單調(diào)遞增的凸函數(shù)且對任意的 c ∈ [0,1] 有 ta(cx) ≥ cta(x) 成立,是變分不等式(9) 的解,vso是系統(tǒng)最優(yōu)問題(10)的解,則自私-利他用戶混合均衡交通分配的效率損失上界滿足:式中 ζ由式(23),式(26)和式(27)給出.

4 算 例

考慮如下的四節(jié)點五路段網(wǎng)絡(luò)(圖1).路段出行成本函數(shù)為 t1=1.8,t2=0.1v2,t3=v3,t4=0. 2v4,t5=2.7.網(wǎng)絡(luò)中有兩個 OD 對,分別是(1,4)和(2,4),出行流量為 d14=1,d24=1.

圖1 算例所用的簡單網(wǎng)絡(luò)Fig.1 The simple network used in the example

系統(tǒng)最優(yōu)流量可以通過求解如下優(yōu)化問題:

下面我們來考慮如下的自私-利他用戶混合均衡交通分配的效率損失.假設(shè) OD 對(1,4) 由自私用戶控制(用“ u ”表示),OD 對(2,4)由利他用戶控制(用“ β ”表示),利他系數(shù)為 β = 0. 5.則混合交通均衡等價于同時求解如下兩個優(yōu)化問題:

則可得自私-利他混合均衡交通分配的解為

由 ηa,ξa的定義,可知對仿射出行成本函數(shù)ta(va)=ta(0)+ αava有故η=1η2=η3= η4= η5=0.5,ξ1= ξ2=0,ξ3= ξ4= ξ5=0.75由 μa, ωa的定義以及混合均衡解可得 μ1= μ2=

5 研究結(jié)論

本文運用解析推導(dǎo)的方法研究了同時存在自私用戶和利他用戶混合均衡交通分配的效率損失問題.首先,我們構(gòu)建了自私-利他用戶混合均衡交通分配的變分不等式模型.然后,界定了出行成本函數(shù)在滿足一定條件下時,這類混合均衡交通分配的效率損失上界.最后,給出了一個簡單的數(shù)值算例驗證我們的結(jié)論.研究發(fā)現(xiàn),效率損失上界和系統(tǒng)的最大、最小利他系數(shù),及路段出行成本函數(shù)相關(guān).值得注意的是,本文得到的效率損失上界,不一定是最緊的,如何得到更小的上界以及界定彈性需求下的效率損失將是我們下一步研究的方向.

[1] Roughgarden T.Stackelberg scheduling strategies[C]. Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing,2001:104-113.

[2] 劉天亮, 歐陽戀群, 黃海軍.ATIS 作用下的混合交通行為網(wǎng)絡(luò)與效率損失上界[J]. 系統(tǒng)工程理論與實踐,2007,27(4):154-159.[LIU T L,OUYANG L Q,HUANG H J.Mixed travel behavior in networks with ATIS and upper bound of efficiency loss[J]. Systems Engineering Theory&Practice,2007,27(4): 154-159.]

[3] Yu X J,Huang H J.Efficiency loss of mixed equilibrium behaviors with polynomial cost functions[J].Promet Traffic&Transportation,2010,22(5):325-331.

[4] Chen P A,Kempe D.Altruism,selfishness,and spite in traffic routing[C].Proceedings of the 9th ACM Conference on Electronic Commerce.Chicago,Illinois, USA,2008:140-149.

[5] Karakostas G,Kim T,Viglas A,et al.On the degradation of performance for traffic networks with oblivious players [J].Transportation Research Part B,2011,45(2): 364-371.

[6] Ledyard J.Public goods:A survey of experimental research[C]//Kagel J.,Roth A.(Eds.)Handbook of Experimental Economics.Princeton University Press, 1997:111-194.

[7] Kinderlehrer D,Stampacchia G.An introduction to variational inequalities and their applications[M]. Academic Press,New York,1986.

[8] Karakostas G,Kolliopoulos S G.The efficiency of optimal taxes[C].Proceedings of the First Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN),2004:3-12.

Bounding the Efficiency Loss of Mixed Equilibrium in the Transportation Network with Selfish and Altruistic Users

YU Xiao-juna,b,ZHANG Wen-zhuanb
(a.School of Mathematics and Statistics;b.Guizhou Key Laboratory of Economic System Simulation,Guizhou University of Finance and Economics,Guiyang 550025,China)

Existing research mainly focuses on the efficiency loss of homogeneous users in the transportation network while little effort has been made to explore the efficiency loss of heterogeneous users.The aim of this article is to investigate the efficiency loss of mixed traffic assignment in the transportation network with selfish and altruistic users.The selfish user chooses a travel path based on the classical user equilibrium(UE) principle and the altruistic user aims to minimize their perceived travel cost(here,the perceived travel cost of each altruistic user is a linear combination of a selfish and altruistic component).Firstly,this article establishes a Variational Inequality(VI)model to depict this mixed traffic assignment.Secondly,the upper bound of this mixed equilibrium traffic assignment is derived by analytic derivation and the relation between the upper bound and the network parameters is obtained.Finally,a numerical example is carried out to validate the analytical result.The analytical and numerical results show that the upper bound of efficiency loss is related to the maximal altruism coefficient,the minimal altruism coefficient and the link travel cost functions.

urban traffic;efficiency loss;variational inequality;mixed equilibrium;selfish user;altruistic user

1009-6744(2014)01-0059-06

U491

A

2013-05-14

2013-06-25錄用日期:2013-07-16

國家自然科學(xué)基金項目(71161005);貴州省優(yōu)秀科技教育人才省長專項資金項目(2011067);貴州省科學(xué)技術(shù)基金(2009J2061).

余孝軍(1974-), 男,湖南新邵人,教授,博士.*通訊作者:xjyu-myu@163.com