1. 引言
随着经济快速发展、社会不断进步,交通拥堵日益成为出行者和管理者们很关注的一个话题,在复杂多变的交通网络中,出行者的出行决策往往是相互影响的。1952年,Wardrop [1] 提出Wardrop第一均衡原则和第二均衡原则。在Wardrop第一均衡即用户均衡(UE)原则中,出行者总是以自身利益最大化而选择出行。而与之对应的是Wardrop第二均衡即系统最优(SO),出行者服从管理者的统一调度以实现系统总出行成本最小化。为了衡量UE时系统总出行成本和SO时系统总出行成本之间的差距。1999年,Koutsoupia等人 [2] 首次用效率损失(PoA)来量化用户自利行为下的低效率。随后,Roughgarden等人 [3] 第一次运用效率损失概念界定交通网络中用户均衡原则导致的损失。
目前,通过对路段实施收费机制,减少二者之间的差距,以降低交通均衡分配的效率损失,是交通网络效率损失的一个重要研究方向。Karakostas等人 [4] 在具有线性路段成本函数或多项式路段成本函数的同质交通网络,得出收费机制下的效率损失上界值要优于Roughgarden等人 [3] 不考虑收费时的效率损失上界。Cominetti和Correa [5] 分析了原子博弈中最优收费和次优收费在古诺纳什均衡下的效率损失问题。
由于随机环境下的效率损失研究更符合实际情况,学者们分别对需求随机和供给随机下的效率损失进行了深入探讨 [6] [7] [8] [9] [10]。冯增哲 [9] 考虑收费机制的随机需求交通网络,采用解析推导和局部光滑性得到古诺纳什均衡下的效率损失上界表达式。Wang等人 [10] 则研究供给随机基于可靠性用户均衡行为下的效率损失问题。
近年来,研究交通网络中采取收费机制的效率损失问题也从逐步同质用户向异质用户方向发展 [11] [12] [13]。出行者并不总是以UE方式选择出行,还可能存在异类用户,CN用户则是以同一类用户的出行者相互合作,不同用户的出行者相互竞争的原则选择出行。
因此,本文研究同时存在利己UE用户和部分合作CN用户所组成的随机交通网络在均衡分配时的效率损失问题,构建收费机制下随机需求UE-CN混合交通均衡分配的变分不等式模型,分别运用非线性规划法和解析推导法得出单项式路段成本函数下该类混合交通均衡分配的效率损失上界表达式,分析二者结论的异同。
2. 收费机制下随机需求UE-CN混合交通均衡分配的效率损失模型
在建立模型之前,对全文假定的随机交通网络均进行如下约束:1) 不同OD对间的随机需求相互独立,各路径流量独立且与相应OD对的随机需求同分布。2) 同一类用户可以使用多个OD对,但每个OD对只能属于一类用户。
2.1. 定义
假设一个由UE和CN两类用户组成的随机交通网络
,令S为点集,A为路段集合;u为UE用户,K为CN用户的集合;
为UE用户u的出行OD对集合,
为CN用户
的出行OD对集合,
;
为OD对
间UE用户u的随机交通需求,
;
为OD对
间CN用户
的随机交通需求,
;
为OD对
间的所有路径集,
为OD对
上的路径;
分别表示UE用户u和CN用户k在路段
上的随机交通流量,
,则
为路段a上的总随机交通流量;
为路段a上的随机流量向量,
为对应路段a上的随机流量期望向量;
为UE用户u的路段随机流量向量(
为网络中有向路段数);
为CN用户k的路段随机流量向量,
;
为路段随机流量向量,
为路段随机流量期望向量;
为UE用户u在路径
,
上的随机交通流量,
;
为CN用户k在路径
,
上的随机交通流量,
;若路段
在路径
上,则
,否则
。
根据流量守恒条件,可得如下UE用户和CN用户
的路段随机流量可行域
,
:
:
(2.1)
(2.2)
(2.3)
:
(2.4)
(2.5)
(2.6)
定义
。
2.2. 构建模型
假设路段出行成本函数
是可分离的连续可微单调递增凸函数。给定一个收费机制
,
为路段a上的收费,则收费机制
下UE用户u和CN用户k在路段a上的理解出行成本分别为
,
。则可得收费机制
下随机需求UE-CN混合交通均衡分配模型:
引理2.1 基于收费机制
下随机需求UE-CN混合交通网络,向量
为该条件下混合交通均衡分配解的充要条件是对任意
,以下变分不等式成立:
(2.7)
其中
,
,
,
。
在收费机制
下随机需求UE-CN混合交通网络中,为得到系统最优解
,则求解如下最优化问题:
(2.8)
设
为(2.7)式混合均衡解,
为(2.8)式系统最优解,则定义如下效率损失
(2.9)
显然,
。
3. 收费机制下随机需求UE-CN混合交通均衡分配的效率损失
为探讨路段出行成本为单项式函数
,
;
下的效率损失。先给出如下假设:
假设3.1 [9] 对任意路段出行成本函数
,均存在递增函数
,
,
,
:
,满足
,
,且对任意随机路段流量
,有
其中
,
。
假设3.2 [7] 对任意随机需求变量
都存在直到
阶的有限矩,即
,则存在常数
和
(
),满足
,使得
(3.1)
若
或1时,
,则有
。
由假设3.1和假设3.2可知,当路段出行成本函数均为
时,可以得到
(3.2)
下面,令
和
分别为(2.7)式的解和对应的期望,
和
为任意的随机流量向量和对应的期望。根据变分不等式(2.7)式,可得
不等式左右两边同时除以
,结合
整理得
(3.3)
根据假设3.1及3.2,可将(3.3)式化简为
(3.4)
由于上式括号中右侧第二项的分母是定值,我们来讨论如下最优化问题:
令
(3.5)
由于函数
的Hessian矩阵为半负定矩阵,故函数
在
的条件下是变量
,
的凹函数,从而
有全局最大值。令
为
的拉格朗日乘子,则(3.5)式的一阶最优条件如下:
(3.6)
(3.7)
(3.8)
(3.9)
结合(3.6)式和(3.7)式,可得
。因此在任意给定路段
,当且仅当满足以下两个条件之一时,(3.5)式可取得最大值,即:
(3.10)
(3.11)
若(3.10)式成立,由(3.6)式和(3.7)式可知
,
。将(3.10)式代入(3.8)式,有
(3.12)
由于(3.12)式中的参数非负,此时
,
、
和n中至少有一个为0。若
或n为0,则(3.5)式为0;因此当
,(3.5)式变为
(3.13)
其中
。
若(3.11)式成立,由(3.6)式和(3.7)式可知
。此时分两种情形讨论(3.5)式的最大值,令
表示交通网络中CN用户的数目。
1)
显然
,设
,
,将
代入(3.8)式有
(3.14)
由(3.5)式,可得
(3.15)
其中
2)
由(3.8)式知,若
,则有
,进而由(3.9)式得
,令
其中
,
,
,已知
,
,由(3.8)和(3.9)式,得
,
,
。根据
,
,则
(3.16)
由(3.5)式,可得
(3.17)
上述(3.17)式的不等式成立的原因是
成立,且
考虑交通网络中同时存在UE和CN两类用户。若
,为使(3.5)式取值最大,(3.13)式或(3.15)式中必有一个成立,令
若
,则(3.5)式取到最大值时,(3.13)式或(3.17)式中必有一个成立,令
根据定义
(3.18)
结合上述假设,此时(3.18)式右边第二项和第三项分别满足
(3.19)
(3.20)
因此可得如下定理。
定理3.1假设随机需求UE-CN交通网络中的路段出行成本为单项式函数
。设
和
分别为VI问题(2.7)式和(2.8)式的解,若假设3.1和假设3.2成立,则收费机制
下随机需求UE-CN混合交通均衡分配的效率损失存在上界,即
(3.21)
其中
为CN用户的数目,参数
的定义如上。
下面,我们探讨解析推导法下的效率损失问题。由于不等式
成立,假设3.1和假设3.2,可将(3.3)式化简为
(3.22)
并结合(3.18)~(3.20)式,此时
式中
。则有如下定理。
定理3.2假设随机需求UE-CN交通网络中的路段出行成本为单项式函数
。设
和
分别为VI问题(2.7)式和(2.8)式的解,若假设3.1和假设3.2成立,则收费机制
下随机需求UE-CN混合交通均衡分配的效率损失存在上界,即
由于
,若
则定义
。
4. 结论
本文在现有文献的基础上,探讨UE和CN两类用户组成的混合随机交通网络在收费机制下的效率损失问题。分别运用非线性规划法和解析推导法得到单项式成本函数下的效率损失上界表达式。研究结果表明,解析推导法下的效率损失上界与路段出行成本函数次幂、路段收费有关,而非线性规划法得到的效率损失上界不仅与路段出行成本函数次幂、路段收费有关,还与CN用户的数目相关。
基金项目
贵州省研究生教育创新计划/Innovative Project of Graduate Education of Guizhou Province (YJSCXJH2020126)。
NOTES
*第一作者。