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

余孝军, 张文专

(贵州财经大学 a.数学与统计学院;b.贵州省经济系统仿真重点实验室, 贵阳 550025)

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

余孝军*a,b, 张文专b

(贵州财经大学 a.数学与统计学院;b.贵州省经济系统仿真重点实验室, 贵阳 550025)

考虑同时存在两类不同用户(自私用户和利他用户)的混合均衡交通网络的效率损失.其中,自私用户按照用户均衡原则选择出行路径,利他用户按照最小化自身的理解出行成本选择出行路径,其理解出行成本是自私项和利他项的线性组合.首先,构建了刻画这类混合均衡交通分配的变分不等式模型;然后,运用解析推导的方法得到了这类混合均衡交通分配的效率损失上界,并分析了效率损失上界和参数之间的关系;最后,给出了数值算例.研究结果表明,效率损失上界和系统的最大、最小利他系数及路段出行成本函数相关.数值算例表明解析方法是可行的.

城市交通;效率损失;变分不等式;混合交通;自私用户;利他用户

1 引 言

近年来,随着对用户均衡相对系统最优效率损失研究的进展,学者们开始研究交通网络中存在异质用户时的效率损失.Roughgarden[1]在作业排序问题中进行了初步研究.刘天亮等人[2]研 究 了ATIS 作用下混合交通均衡的效率损失上界.Yu 和Huang[3]探讨了路段出行成本函数为多项式函数时 UE-CN 混合均衡交通分配的效率损失.Chen 和Kempe[4]研究了用户为利他用户时的效率损失. Karakostas 等人[5]探讨了网络中存在着自私用户和刻板用户(这类用户事先根据网络的硬件指标进行出行决策,而且在出行过程中不更改既定出行方案,这类用户完全忽视了网络拥堵程度对自己的影响)的效率损失.

本文将考虑网络中同时存在着自私用户和利他用户两类不同用户时交通均衡分配的效率损失问题.其中,自私用户根据用户均衡原则选择出行路径,其目的是最小化自己的出行成本,利他用户在出行时不仅考虑自身的实际出行成本,还考虑自身的出行给其他用户带来的拥挤外部性,按照最小化自身的理解出行成本选择出行路径,其理解出行成本是自私项和利他项的线性组合(具体定义见第 2 节).首先,构建自私-利他用户混合均衡交通分配的等价变分不等式模型;在此基础上,界定该类混合均衡的效率损失上界,并分析影响效率损失上界的影响因素;最后,给出数值算例进行验证.

2 混合均衡交通分配模型

有向图 G=(N,A) 表示一个交通网络,其中 N和A分别表示节点集和路段.u表示网络中的自私用户;M表示网络中利他用户集合;Wu是网络中自私用户控制的出行OD对集合;Wm,βm分别表示利他用户m∈M控制的出行OD对集合和利他系数;W≡Wu∪ WM;dw表示OD对w∈W间的出行需求;Rw表示OD对w∈W间的路径集;frw表示路径上的流量;如果路段 a∈A 在路径 r∈ Rw上,则,否则表示 OD对集 Wu在路段 a 上的流量;vu≡ ( …,,…) 表示自私用户产生的路段流量向 量;表示 OD 对集Wm,m∈M在路段a上的流量;…) 表示路段 a 上的流量向量;表示利他用户 m 产生的路段流量向量; vM≡ ( …,vm-1,vm,vm+1,…);v ≡ (vu,vM);表示利他用户在路段 a 产生的总流量;va=表示路段a上的总流量 ; 假设路段出行成本函数 ta(va)是路段流量可分离函数,并且是流量的连续可微单调递增的凸函数.

假设所有 OD 对的出行量是固定的,则自私用户的可行域 Ωu和利他用户 m 的可行域 Ωm分别为:

Ωu={vu|vu满足约束条件(1)-(3)}:

Ωm={vm|vm满足约束条件(4)-(6)},∀m∈M:

定义1利他系数为 β(β ∈ [-1,1])的利他用户选择路径r的目的是最小化自身出行成本函数, 其 中是出行成 本的自 私 项,是出行成本的利他项.(ta(va)va)′是函数 ta(va)va关于变量 va的微分.故可改写为

利他用户的理解出行成本可以认为是其实际的出行成本(自私项)与其认为自身出行会给其他用户带来的外部性(利他项)之和.显然,当利他系数 β =1 时,即用户是完全利他的,则其理解出行成本就是用户按照系统最优原则出行时的出行成本;当利他系数 β =0 时,即用户是自私的,则其理解出行成本就是按照用户均衡原则出行时的出行成本.所以,利他系数为 βm的利他用户 m ∈ M 在路段 a 上的理解出行成本为.本文假设 βm∈ [0,1].

对自私用户而言,其出行决策原则是在利他用户出行决策给定的情况下最小化自己的出行成本,其求解等价于求解下面的优化问题:

同时满足优化问题(7)和(8)的解称为自私-利他用户的混合交通均衡解.同时求解优化问题(7)和(8)等价于求解如下的变分不等式:

引理1如果路段出行成本函数 ta(va),a ∈ A是严格递增的凸函数,则向量v∈ Ω 是自私-利他用户混合交通均衡解当且仅当下面的不等式成立:寻找v,满足

由于 ta(va) 是严格递增的凸函数,则变分不等式问题(9) 有解[7].进一步,自私用户和利他用户在路段 a∈ A上的路段理解出行成本向量为如 果对任意路段a∈A都是严格单调函数,则变分不等式问题(9)至多有一个解[7].

由于 ta(va) 是严格递增凸函数,故问题(10)有关于路段总流量的唯一解.则系统最优下的总出行成本为

定义自私-利他用户混合均衡交通分配的效率损失分别为

易得, ρ≥ 1.下面,我们来界定路段出行成本函数在特定条件下的上界值.

3 界定效率损失的上界

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

引理2假设路段出行成本函数 ta(va) 是连续可微严格递增的凸函数,且对任意的 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) 成立.

设 vso是最小化问题(10)的解. 在变分不等式(9) 中 用分 别取 代, 则 有

由于可行域 v≥ 0 比可行域 v∈ Ω 大,故式(16) 的最后一个不等式成立.下面我们来考虑(16)最后一个不等式右边第二项的最大值,即考虑下面的非线性规划问题

设 F(va)=(ta(va)-ta(va))va+ ∑βmvat′a(va)(vmam∈M-vma).由于F(va)的 Hessian 矩阵是半负定矩阵,因 此 F(va) 是关于变量vua≥ 0,vma≥0,m∈M 的凹函数.从而 F(va) 有唯一的全局最大值.设 λua,λma,a∈A是变量vua≥0,vma≥0,m∈M的Lagrange乘子,故可得(17)的一阶最优性条件如下:

由于出行成本函数 ta(va) 是严格递增函数,故式(22)有唯一解.设由式(20),易得从 而 ,= 0或如果,我们可以得到 F(va)=0. 若 βm=0,则 有 F(va)=其中不等式成立的原因是因为 ta(cx) ≥ cta(x).设

知如果 βm1＞ βm2,则有再由式(21)可得设 βm和分别是路段 a 上存在正流量的最大和最小利他系数.从而有和

由 ta(va) 是严格递增的凸函数,且1],则式(24) 有唯一解.设0 ≤ μa≤1,,0 ≤ ωa≤ 1,a∈ A,0 ≤ μa+ ωa≤ 1.故有

这里

定义2

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

故可以得到如下关于自私-利他用户混合均衡交通分配的效率损失上界定理:

定理1对任意给定的路段出行成本函数类C,任意 ta(va) ∈ C 是连续可微单调递增的凸函数且对任意的 c ∈ [0,1] 有 ta(cx) ≥ cta(x) 成立,是变分不等式(9) 的解,vso是系统最优问题(10)的解,则自私-利他用户混合均衡交通分配的效率损失上界满足:式中 ζ由式(23),式(26)和式(27)给出.

4 算 例

考虑如下的四节点五路段网络(图1).路段出行成本函数为 t1=1.8,t2=0.1v2,t3=v3,t4=0. 2v4,t5=2.7.网络中有两个 OD 对,分别是(1,4)和(2,4),出行流量为 d14=1,d24=1.

图1 算例所用的简单网络Fig.1 The simple network used in the example

系统最优流量可以通过求解如下优化问题:

下面我们来考虑如下的自私-利他用户混合均衡交通分配的效率损失.假设 OD 对(1,4) 由自私用户控制(用“ u ”表示),OD 对(2,4)由利他用户控制(用“ β ”表示),利他系数为 β = 0. 5.则混合交通均衡等价于同时求解如下两个优化问题:

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

由 ηa,ξa的定义,可知对仿射出行成本函数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 研究结论

本文运用解析推导的方法研究了同时存在自私用户和利他用户混合均衡交通分配的效率损失问题.首先,我们构建了自私-利他用户混合均衡交通分配的变分不等式模型.然后,界定了出行成本函数在满足一定条件下时,这类混合均衡交通分配的效率损失上界.最后,给出了一个简单的数值算例验证我们的结论.研究发现,效率损失上界和系统的最大、最小利他系数,及路段出行成本函数相关.值得注意的是,本文得到的效率损失上界,不一定是最紧的,如何得到更小的上界以及界定弹性需求下的效率损失将是我们下一步研究的方向.

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

[2] 刘天亮, 欧阳恋群, 黄海军.ATIS 作用下的混合交通行为网络与效率损失上界[J]. 系统工程理论与实践,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

国家自然科学基金项目(71161005);贵州省优秀科技教育人才省长专项资金项目(2011067);贵州省科学技术基金(2009J2061).

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