收费机制下随机需求UE-CN混合交通均衡分配的效率损失 Efficiency Loss of UE-CN Mixed Traffic Equilibrium Assignment with Stochastic Demand under Charging Mechanism

doi:10.12677/AAM.2022.114183

Advances in Applied Mathematics
Vol. 11 No. 04 ( 2022 ), Article ID: 50337 , 10 pages
10.12677/AAM.2022.114183

收费机制下随机需求UE-CN混合交通均衡分配的效率损失

毛君竹^*，顾重秀，王才正，尚美欣

●How to Cite this Article

贵州财经大学数统学院，贵州贵阳

收稿日期：2022年3月14日；录用日期：2022年4月8日；发布日期：2022年4月18日

摘要

基于交通网络中出行者路径决策原则的异质性，分析由user equilibrium (UE)用户和Cournot-Nash (CN)用户所组成的UE-CN混合交通均衡分配在收费机制下的效率损失问题。构建了收费机制下随机需求该类混合均衡分配的变分不等式模型，分别运用非线性规划法和解析推导法得到路段出行成本为单项式函数时的效率损失上界表达式。研究结果表明，解析推导法下的效率损失上界依赖于路段出行成本函数次幂、路段收费，而非线性规划法下的效率损失上界不仅与路段出行成本函数次幂、路段收费有关，还与CN用户的数目相关。

关键词

效率损失，变分不等式，UE-CN混合交通均衡分配，路段收费，随机需求

Efficiency Loss of UE-CN Mixed Traffic Equilibrium Assignment with Stochastic Demand under Charging Mechanism

Junzhu Mao^*, Chongxiu Gu, Caizheng Wang, Meixin Shang

School of Mathematics and Statistics, Guizhou University of Finance and Economics, Guiyang Guizhou

Received: Mar. 14^th, 2022; accepted: Apr. 8^th, 2022; published: Apr. 18^th, 2022

ABSTRACT

Based on the heterogeneity of traveler path decision-making principles in traffic network, the efficiency loss of UE-CN mixed traffic equilibrium assignment composed of user equilibrium (UE) user and Cournot-Nash (CN) users undercharging mechanism is analyzed. The variational inequality model of this kind of mixed equilibrium assignment of stochastic demand under the charging mechanism is constructed. The upper bound formula of efficiency loss when the road travel cost is a monomial function is obtained by using nonlinear programming method and analytical derivation method respectively. The results show that the upper bound of efficiency loss under analytical derivation method depends on the power of link travel cost function and link charge, while the upper bound of efficiency loss under nonlinear programming method is related not only to the power of link travel cost function and link charge, but also to the number of CN users.

Keywords:Efficiency Loss, Variational Inequality, UE-CN Mixed Traffic Equilibrium Assignment, Road Charging, Stochastic Demand

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

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两类用户组成的随机交通网络 $G = (S, A)$ ，令S为点集，A为路段集合；u为UE用户，K为CN用户的集合； $W^{u}$ 为UE用户u的出行OD对集合， $W^{k}$ 为CN用户 $k \in K$ 的出行OD对集合， $W \equiv W^{u} \cup W^{K}$ ； $D_{w}^{u}$ 为OD对 $w \in W^{u}$ 间UE用户u的随机交通需求， $d_{w}^{u} = E (D_{w}^{u})$ ； $D_{w}^{k}$ 为OD对 $w \in W^{k}$ 间CN用户 $k \in K$ 的随机交通需求， $d_{w}^{k} = E (D_{w}^{k})$ ； $I_{w}$ 为OD对 $w \in W$ 间的所有路径集， $i \in I_{w}$ 为OD对 $w \in W$ 上的路径； $V_{a}^{u}, V_{a}^{k}$ 分别表示UE用户u和CN用户k在路段 $a \in A$ 上的随机交通流量， $V_{a}^{K} = \sum_{k \in K} V_{a}^{k}$ ，则 $V_{a} = V_{a}^{u} + V_{a}^{K}$ 为路段a上的总随机交通流量； $V_{a} \equiv (V_{a}^{u}, V_{a}^{1}, \dots, V_{a}^{k}, \dots)$ 为路段a上的随机流量向量， $v_{a} \equiv (v_{a}^{u}, v_{a}^{1}, \dots, v_{a}^{k}, \dots)$ 为对应路段a上的随机流量期望向量； $V^{u} \equiv (V_{1}^{u}, \dots, V_{^{| A |}}^{u})$ 为UE用户u的路段随机流量向量( $| A |$ 为网络中有向路段数)； $V^{k} \equiv (V_{1}^{k}, \dots, V_{^{| A |}}^{k})$ 为CN用户k的路段随机流量向量， $V^{K} \equiv (\dots, V^{k - 1}, V^{k}, V^{k + 1}, \dots)$ ； $V \equiv (V_{1}, V_{2}, \dots, V_{| A |})$ 为路段随机流量向量， $v \equiv (v_{1}, v_{2}, \dots, v_{| A |})$ 为路段随机流量期望向量； $F_{i}^{w, u}$ 为UE用户u在路径 $i \in I_{w}$ ， $w \in W^{u}$ 上的随机交通流量， $f_{i}^{w, u} = E (F_{i}^{w, u})$ ； $F_{i}^{w, k}$ 为CN用户k在路径 $i \in I_{w}$ ， $w \in W^{k}$ 上的随机交通流量， $f_{i}^{w, k} = E (F_{i}^{w, k})$ ；若路段 $a \in A$ 在路径 $i \in I_{w}$ 上，则 $δ_{i, a}^{w} = 1$ ，否则 $δ_{i, a}^{w} = 0$ 。

根据流量守恒条件，可得如下UE用户和CN用户 $k \in K$ 的路段随机流量可行域 $Ω_{V}^{u}$ ， $Ω_{V}^{k}$ ：

$Ω_{V}^{u} = {V^{u} | V^{u} 满足约束条件 (2.1) ~ (2.3)}$ ：

$D_{w}^{u} = \sum_{i \in I_{w}} F_{i}^{w, u}, \forall w \in W^{u}$ (2.1)

$V_{a}^{u} = \sum_{w \in W^{u}} \sum_{i \in I_{w}} F_{i}^{w, u} δ_{i, a}^{w}, \forall a \in A$ (2.2)

$F_{i}^{w, u} \geq 0, i \in I_{w}, w \in W^{u}$ (2.3)

$Ω_{V}^{k} = {V^{k} | V^{k} 满足约束条件 (2.4) ~ (2.6)}$ ：

$D_{w}^{k} = \sum_{i \in I_{w}} F_{i}^{w, k}, \forall w \in W^{k}, k \in K$ (2.4)

$V_{a}^{k} = \sum_{w \in W^{k}} \sum_{i \in I_{w}} F_{i}^{w, k} δ_{i, a}^{w}, \forall a \in A$ (2.5)

$F_{i}^{w, k} \geq 0, i \in I_{w}, w \in W^{k}, k \in K$ (2.6)

定义 $Ω_{V} = Ω_{V}^{u} \times \prod_{k \in K} Ω_{V}^{k}$ 。

2.2. 构建模型

假设路段出行成本函数 $t_{a} (V_{a})$ 是可分离的连续可微单调递增凸函数。给定一个收费机制 $τ$ ， $τ_{a}$ $(τ_{a} = η_{a} {\bar{V}}_{a} {t^{'}}_{a} ({\bar{V}}_{a}), 0 \leq η_{a} \leq 1)$ 为路段a上的收费，则收费机制 $τ$ 下UE用户u和CN用户k在路段a上的理解出行成本分别为 $c_{a}^{u} (V) = t_{a} (V_{a}) + τ_{a}$ ， $c_{a}^{k} (V) = t_{a} (V_{a}) + V_{a}^{k} {t^{'}}_{a} (V_{a}) + τ_{a}$ 。则可得收费机制 $τ$ 下随机需求UE-CN混合交通均衡分配模型：

引理2.1 基于收费机制 $τ$ 下随机需求UE-CN混合交通网络，向量 $\bar{V} = ({\bar{V}}^{u}, {\bar{V}}^{K}) \in Ω_{V}$ 为该条件下混合交通均衡分配解的充要条件是对任意 $V \in Ω_{V}$ ，以下变分不等式成立：

$\sum_{a \in A} (v_{a}^{u} - {\bar{v}}_{a}^{u}) E [t_{a} ({\bar{V}}_{a}) + τ_{a}] + \sum_{a \in A} \sum_{k \in K} (v_{a}^{k} - {\bar{v}}_{a}^{k}) E [t_{a} ({\bar{V}}_{a}) + {\bar{V}}_{a}^{k} {t^{'}}_{a} ({\bar{V}}_{a}) + τ_{a}] \geq 0$ (2.7)

其中 $v_{a}^{u} = E (V_{a}^{u})$ ， $v_{a}^{k} = E (V_{a}^{k})$ ， ${\bar{v}}_{a}^{u} = E ({\bar{V}}_{a}^{u})$ ， ${\bar{v}}_{a}^{k} = E ({\bar{V}}_{a}^{k})$ 。

在收费机制 $τ$ 下随机需求UE-CN混合交通网络中，为得到系统最优解 $\hat{V} \in Ω_{V}$ ，则求解如下最优化问题：

$\min_{V \in Ω_{V}} E [\sum_{a \in A} V_{a} t_{a} (V_{a})]$ (2.8)

设 $\bar{V}$ 为(2.7)式混合均衡解， $\hat{V}$ 为(2.8)式系统最优解，则定义如下效率损失

$ρ = \frac{E [\sum_{a \in A} t_{a} ({\bar{V}}_{a}) {\bar{V}}_{a}]}{E [\sum_{a \in A} t_{a} ({\hat{V}}_{a}) {\hat{V}}_{a}]}$ (2.9)

显然， $ρ \geq 1$ 。

3. 收费机制下随机需求UE-CN混合交通均衡分配的效率损失

为探讨路段出行成本为单项式函数 $t_{a} (V_{a}) = V_{a}^{n}$ ， $n = 0, 1, 2, \dots, p$ ； $p \in N$ 下的效率损失。先给出如下假设：

假设3.1 [9] 对任意路段出行成本函数 $t_{a} (\cdot)$ ，均存在递增函数 ${\underline{s}}_{a} (\cdot)$ ， ${\bar{s}}_{a} (\cdot)$ ， ${\underline{t}}_{a} (\cdot)$ ， ${\bar{t}}_{a} (\cdot)$ ： $R^{+} \to R^{+}$ ，满足 ${\underline{s}}_{a} (0) = {\bar{s}}_{a} (0) = 0$ ， ${\underline{t}}_{a} (0) = {\bar{t}}_{a} (0) = 0$ ，且对任意随机路段流量 $V_{a}$ ，有

$0 < {\underline{s}}_{a} (v_{a}) \leq E [t_{a} (V_{a}) V_{a}] \leq {\bar{s}}_{a} ( v a )$

$0 < {\underline{t}}_{a} (v_{a}) \leq E [t_{a} (V_{a})] \leq {\bar{t}}_{a} ( v a )$

$0 < v_{a}^{k} {\underline{r}}_{a} (v_{a}) \leq E [V_{a}^{k} {t^{'}}_{a} (V_{a})] \leq v_{a}^{k} {\bar{r}}_{a} ( v a )$

其中 $v_{a} = E (V_{a})$ ， $v_{a}^{k} = E (V_{a}^{k})$ 。

假设3.2 [7] 对任意随机需求变量 $D_{w}$ 都存在直到 $p + 1$ 阶的有限矩，即 $0 < E (D_{w}^{p + 1}) < + \infty$ ，则存在常数 $l_{n}$ 和 $h_{n}$ ( $n = 0, 1, 2, \dots, p + 1$ )，满足 $0 < l_{n + 1} \leq l_{n} \leq h_{n} \leq h_{n + 1}$ ，使得

$0 < l_{n} v_{a}^{n} \leq E (V_{a}^{n}) \leq h_{n} v_{a}^{n}, \forall a \in A$ (3.1)

若 $n = 0$ 或1时， $E (V_{a}^{n}) = v_{a}^{n}$ ，则有 $l_{0} = h_{0} = l_{1} = h_{1} = 1$ 。

由假设3.1和假设3.2可知，当路段出行成本函数均为 $t_{a} (V_{a}) = V_{a}^{n}$ 时，可以得到

$\begin{array}{l} {\underline{t}}_{a} (v_{a}) = l_{n} v_{a}^{n}, {\bar{t}}_{a} (v_{a}) = h_{n} v_{a}^{n}, {\underline{s}}_{a} (v_{a}) = l_{n + 1} v_{a}^{n + 1}, \\ {\bar{s}}_{a} (v_{a}) = h_{n + 1} v_{a}^{n + 1}, {\underline{r}}_{a} (v_{a}) = n l_{n - 1} v_{a}^{n - 1}, {\bar{r}}_{a} (v_{a}) = n h_{n - 1} v_{a}^{n - 1} \end{array}$ (3.2)

下面，令 $\bar{V}$ 和 $\bar{v}$ 分别为(2.7)式的解和对应的期望， $V$ 和 $v$ 为任意的随机流量向量和对应的期望。根据变分不等式(2.7)式，可得

$\begin{array}{l} \sum_{a \in A} {\bar{v}}_{a} E [t_{a} (\bar{V_{a}})] \leq \sum_{a \in A} v_{a} E [t_{a} (\bar{V_{a}})] + \sum_{a \in A} \sum_{k \in K} (v_{a}^{k} - {\bar{v}}_{a}^{k}) E [{\bar{V_{a}}}^{k} {t^{'}}_{a} ({\bar{V}}_{a})] + \sum_{a \in A} (v_{a} - {\bar{v}}_{a}) E (τ_{a}) \\ = \sum_{a \in A} v_{a} E [t_{a} (V_{a})] + \sum_{a \in A} v_{a} {E [t_{a} (\bar{V_{a}})] - E [t_{a} (V_{a})]} + \sum_{a \in A} \sum_{k \in K} (v_{a}^{k} - {\bar{v}}_{a}^{k}) E [{\bar{V_{a}}}^{k} {t^{'}}_{a} ({\bar{V}}_{a})] + \sum_{a \in A} (v_{a} - {\bar{v}}_{a}) E ( τ a ) \end{array}$

不等式左右两边同时除以 $\sum_{a \in A} {\bar{v}}_{a} E [t_{a} ({\bar{V}}_{a})]$ ，结合 $τ_{a} = η_{a} {\bar{V}}_{a} {t^{'}}_{a} ({\bar{V}}_{a})$ 整理得

$\begin{array}{l} \frac{\sum_{a \in A} {\bar{v}}_{a} E [t_{a} ({\bar{V}}_{a})]}{\sum_{a \in A} v_{a} E [t_{a} (V_{a})]} \\ \leq {1 - \max_{v_{a} \geq 0} {\frac{v_{a} {E [t_{a} (\bar{V_{a}})] - E [t_{a} (V_{a})]} + \sum_{k \in K} (v_{a}^{k} - {\bar{v}}_{a}^{k}) E [{\bar{V_{a}}}^{k} {t^{'}}_{a} ({\bar{V}}_{a})] + (v_{a} - {\bar{v}}_{a}) E [η_{a} \bar{V} {t^{'}}_{a} ({\bar{V}}_{a})]}{{\bar{v}}_{a} E [t_{a} ({\bar{V}}_{a})]}}}^{- 1} \end{array}$ (3.3)

根据假设3.1及3.2，可将(3.3)式化简为

$\begin{array}{l} \frac{\sum_{a \in A} {\bar{v}}_{a} E [t_{a} ({\bar{V}}_{a})]}{\sum_{a \in A} v_{a} E [t_{a} (V_{a})]} \\ \leq {1 - \max_{v_{a} \geq 0} {\frac{v_{a} [h_{n} {({\bar{v}}_{a})}^{n} - l_{n} {(v_{a})}^{n}] + n {({\bar{v}}_{a})}^{n - 1} \sum_{k \in K} {\bar{v}}_{a}^{k} (h_{n - 1} v_{a}^{k} - l_{n - 1} {\bar{v}}_{a}^{k}) + η_{a} n [v_{a} h_{n - 1} {({\bar{v}}_{a})}^{n} - l_{n - 1} {({\bar{v}}_{a})}^{n + 1}]}{h_{n} {({\bar{v}}_{a})}^{n + 1}}}}^{- 1} \end{array}$ (3.4)

由于上式括号中右侧第二项的分母是定值，我们来讨论如下最优化问题：

令

$M (v_{a}) = v_{a} [h_{n} {({\bar{v}}_{a})}^{n} - l_{n} {(v_{a})}^{n}] + n {({\bar{v}}_{a})}^{n - 1} \sum_{k \in K} {\bar{v}}_{a}^{k} (h_{n - 1} v_{a}^{k} - l_{n - 1} {\bar{v}}_{a}^{k}) + η_{a} n [v_{a} h_{n - 1} {({\bar{v}}_{a})}^{n} - l_{n - 1} {({\bar{v}}_{a})}^{n + 1}]$ (3.5)

由于函数 $M (v_{a})$ 的Hessian矩阵为半负定矩阵，故函数 $M (v_{a})$ 在 $n \geq 0$ 的条件下是变量 $v_{a}^{u} \geq 0$ ， $v_{a}^{k} \geq 0$ 的凹函数，从而 $M (v_{a})$ 有全局最大值。令 $λ_{a}^{u}, λ_{a}^{k}, a \in A$ 为 $v_{a}^{u}, v_{a}^{k}, k \in K$ 的拉格朗日乘子，则(3.5)式的一阶最优条件如下：

$h_{n} {({\bar{v}}_{a})}^{n} - (n + 1) l_{n} {(v_{a})}^{n} + η_{a} n h_{n - 1} {({\bar{v}}_{a})}^{n} + λ_{a}^{u} = 0, \forall a \in A$ (3.6)

$λ_{a}^{u} \geq 0, v_{a}^{u} \geq 0, λ_{a}^{u} v_{a}^{u} = 0, \forall a \in A$ (3.7)

$h_{n} {({\bar{v}}_{a})}^{n} - (n + 1) l_{n} {(v_{a})}^{n} + n h_{n - 1} {({\bar{v}}_{a})}^{n - 1} {\bar{v}}_{a}^{k} + η_{a} n h_{n - 1} {({\bar{v}}_{a})}^{n} + λ_{a}^{k} = 0, \forall a \in A, k \in K$ (3.8)

$λ_{a}^{k} \geq 0, v_{a}^{k} \geq 0, λ_{a}^{k} v_{a}^{k} = 0, \forall a \in A, k \in K$ (3.9)

结合(3.6)式和(3.7)式，可得 $v_{a} \geq {[\frac{h_{n} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} {\bar{v}}_{a}$ 。因此在任意给定路段 $a \in A$ ，当且仅当满足以下两个条件之一时，(3.5)式可取得最大值，即：

$v_{a} = {[\frac{h_{n} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} {\bar{v}}_{a}$ (3.10)

$v_{a} > {[\frac{h_{n} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} {\bar{v}}_{a}$ (3.11)

若(3.10)式成立，由(3.6)式和(3.7)式可知 $λ_{a}^{u} = 0$ ， $v_{a}^{u} \geq 0$ 。将(3.10)式代入(3.8)式，有

$n h_{n - 1} {({\bar{v}}_{a})}^{n - 1} {\bar{v}}_{a}^{k} + λ_{a}^{k} = 0, \forall a \in A, k \in K$ (3.12)

由于(3.12)式中的参数非负，此时 $λ_{a}^{k} = 0$ ， ${\bar{v}}_{a}$ 、 ${\bar{v}}_{a}^{k}$ 和n中至少有一个为0。若 ${\bar{v}}_{a}$ 或n为0，则(3.5)式为0；因此当 ${\bar{v}}_{a}^{k} = 0, λ_{a}^{k} = 0$ ，(3.5)式变为

$\begin{array}{l} \max_{v_{a} \geq 0} {v_{a} [h_{n} {({\bar{v}}_{a})}^{n} - l_{n} {(v_{a})}^{n}] + n {({\bar{v}}_{a})}^{n - 1} \sum_{k \in K} {\bar{v}}_{a}^{k} (h_{n - 1} v_{a}^{k} - l_{n - 1} {\bar{v}}_{a}^{k}) + η_{a} n [v_{a} h_{n - 1} {({\bar{v}}_{a})}^{n} - l_{n - 1} {({\bar{v}}_{a})}^{n + 1}]} \\ = \max_{v_{a} \geq 0} {v_{a} [h_{n} {({\bar{v}}_{a})}^{n} - l_{n} {(v_{a})}^{n}] + η_{a} n [v_{a} h_{n - 1} {({\bar{v}}_{a})}^{n} - l_{n - 1} {({\bar{v}}_{a})}^{n + 1}]} \\ = {[\frac{h_{n} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} {({\bar{v}}_{a})}^{n + 1} (h_{n} - \frac{h_{n} + η_{a} n h_{n - 1}}{n + 1}) + η_{a} n {({\bar{v}}_{a})}^{n + 1} {{[\frac{h_{n} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} h_{n - 1} - l_{n - 1}} \\ = ψ_{a} {({\bar{v}}_{a})}^{n + 1} \end{array}$ (3.13)

其中 $ψ_{a} = {[\frac{h_{n} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} \frac{n}{n + 1} (h_{n} - η_{a} h_{n - 1}) + η_{a} n {{[\frac{h_{n} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} h_{n - 1} - l_{n - 1}}$ 。

若(3.11)式成立，由(3.6)式和(3.7)式可知 $λ_{a}^{u} > 0, v_{a}^{u} = 0$ 。此时分两种情形讨论(3.5)式的最大值，令 $| K |$ 表示交通网络中CN用户的数目。

1) $| K | = 1$

显然 $v_{a} = v_{a}^{K}$ ，设 $\frac{{\bar{v}}_{a}^{K}}{{\bar{v}}_{a}} = φ_{a}$ ， $0 \leq φ_{a} \leq 1$ ，将 ${\bar{v}}_{a}^{K} = φ_{a} {\bar{v}}_{a}$ 代入(3.8)式有

$v_{a} = v_{a}^{K} = {[\frac{h_{n} + n h_{n - 1} φ_{a} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} {\bar{v}}_{a}$ (3.14)

由(3.5)式，可得

其中

$\begin{matrix} θ_{a} = {[\frac{h_{n} + n h_{n - 1} φ_{a} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} \frac{n}{n + 1} (h_{n} - h_{n - 1} φ_{a} - η_{a} h_{n - 1}) \\ + n φ_{a} {h_{n - 1} {[\frac{h_{n} + n h_{n - 1} φ_{a} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} - l_{n - 1} φ_{a}} \\ + η_{a} n {{[\frac{h_{n} + n h_{n - 1} φ_{a} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} h_{n - 1} - l_{n - 1}} \end{matrix}$

2) $| K | \geq 2$

由(3.8)式知，若 ${\bar{v}}_{a}^{k_{1}} > {\bar{v}}_{a}^{k_{2}}$ ，则有 $0 \leq λ_{a}^{k_{1}} < λ_{a}^{k_{2}}$ ，进而由(3.9)式得 $v_{a}^{k_{1}} \geq v_{a}^{k_{2}} = 0$ ，令

${\bar{v}}_{a}^{k_{\max}} = \max_{k \in K} {\bar{v}}_{a}^{k}, ι_{a} = \frac{{\bar{v}}_{a}^{u}}{{\bar{v}}_{a}}, χ_{a} = \frac{{\bar{v}}_{a}^{k_{\max}}}{{\bar{v}}_{a}}$

其中 $0 \leq ι_{a} \leq 1$ ， $0 \leq χ_{a} \leq 1$ ， $0 \leq χ_{a} + ι_{a} \leq 1$ ，已知 $v_{a}^{u} = 0$ ， $v_{a} = v_{a}^{u} + v_{a}^{k_{\max}} + \sum_{k \in K, k \neq k_{\max}} v_{a}^{k}$ ，由(3.8)和(3.9)式，得 $v_{a}^{k_{\max}} > 0$ ， $v_{a}^{k} = 0$ ， $k \neq k_{\max}$ 。根据 $v_{a}^{u} = 0$ ， $v_{a} = \sum_{k \in K} v_{a}^{k} = v_{a}^{k_{\max}}$ ，则

$v_{a} = v_{a}^{k_{\max}} = {[\frac{h_{n} + n h_{n - 1} χ_{a} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} {\bar{v}}_{a}, \forall a \in A$ (3.16)

由(3.5)式，可得

$\begin{array}{l} \max_{v_{a} \geq 0} {v_{a} [h_{n} {({\bar{v}}_{a})}^{n} - l_{n} {(v_{a})}^{n}] + n {({\bar{v}}_{a})}^{n - 1} \sum_{k \in K} {\bar{v}}_{a}^{k} (h_{n - 1} v_{a}^{k} - l_{n - 1} {\bar{v}}_{a}^{k}) + η_{a} n [v_{a} h_{n - 1} {({\bar{v}}_{a})}^{n} - l_{n - 1} {({\bar{v}}_{a})}^{n + 1}]} \\ = (h_{n} - h_{n - 1} χ_{a} - η_{a} h_{n - 1}) \frac{n}{n + 1} {[\frac{h_{n} + n h_{n - 1} χ_{a} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} {({\bar{v}}_{a})}^{n + 1} \\ + η_{a} n {{[\frac{h_{n} + n h_{n - 1} χ_{a} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} h_{n - 1} - l_{n - 1}} {({\bar{v}}_{a})}^{n + 1} \\ + n χ_{a} {h_{n - 1} {[\frac{h_{n} + n h_{n - 1} χ_{a} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} - l_{n - 1} χ_{a}} {({\bar{v}}_{a})}^{n + 1} - n l_{n - 1} {({\bar{v}}_{a})}^{n - 1} \sum_{k \in K, k \neq k_{\max}} {({\bar{v}}_{a}^{k})}^{2} \\ \leq ς_{a} {({\bar{v}}_{a})}^{n + 1} \end{array}$ (3.17)

上述(3.17)式的不等式成立的原因是 $\sum_{k \in K, k \neq k_{\max}} {({\bar{v}}_{a}^{k})}^{2} \geq \frac{1}{| K | - 1} {(\sum_{k \in K, k \neq k_{\max}} {\bar{v}}_{a}^{k})}^{2} = \frac{{(1 - ι_{a} - χ_{a})}^{2}}{| K | - 1} {({\bar{v}}_{a})}^{2}$ 成立，且

$\begin{matrix} ς_{a} = (h_{n} - h_{n - 1} χ_{a} - η_{a} h_{n - 1}) \frac{n}{n + 1} {[\frac{h_{n} + n h_{n - 1} χ_{a} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} \\ + η_{a} n {{[\frac{h_{n} + n h_{n - 1} χ_{a} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} h_{n - 1} - l_{n - 1}} \\ + n χ_{a} {h_{n - 1} {[\frac{h_{n} + n h_{n - 1} χ_{a} + η_{a} n h_{n - 1}}{(n + 1) l_{n}}]}^{\frac{1}{n}} - l_{n - 1} χ_{a}} \\ - n l_{n - 1} \frac{{(1 - ι_{a} - χ_{a})}^{2}}{| K | - 1} \end{matrix}$

考虑交通网络中同时存在UE和CN两类用户。若 $| K | = 1$ ，为使(3.5)式取值最大，(3.13)式或(3.15)式中必有一个成立，令

$β_{a} = \max {\frac{ψ_{a}}{h_{n}}, \frac{θ_{a}}{h_{n}}}, β = \max_{a \in A} β_{a}$

若 $| K | \geq 2$ ，则(3.5)式取到最大值时，(3.13)式或(3.17)式中必有一个成立，令

$γ_{a} = \max {\frac{ψ_{a}}{h_{n}}, \frac{ς_{a}}{h_{n}}}, γ = \max_{a \in A} γ_{a}$

根据定义

$\frac{E [\sum_{a \in A} t_{a} ({\bar{V}}_{a}) {\bar{V}}_{a}]}{E [\sum_{a \in A} t_{a} (V_{a}) V_{a}]} = \frac{\sum_{a \in A} {\bar{v}}_{a} E [t_{a} ({\bar{V}}_{a})]}{\sum_{a \in A} v_{a} E [t_{a} (V_{a})]} \cdot \frac{\sum_{a \in A} E [{\bar{V}}_{a} t_{a} ({\bar{V}}_{a})]}{\sum_{a \in A} {\bar{v}}_{a} E [t_{a} ({\bar{V}}_{a})]} \cdot \frac{\sum_{a \in A} v_{a} E [t_{a} (V_{a})]}{\sum_{a \in A} E [V_{a} t_{a} (V_{a})]}$ (3.18)

结合上述假设，此时(3.18)式右边第二项和第三项分别满足

$\frac{\sum_{a \in A} E [{\bar{V}}_{a} t_{a} ({\bar{V}}_{a})]}{\sum_{a \in A} {\bar{v}}_{a} E [t_{a} ({\bar{V}}_{a})]} \leq {[\frac{\sum_{a \in A} {\bar{v}}_{a} {\underline{t}}_{a} ({\bar{v}}_{a})}{\sum_{a \in A} {\bar{s}}_{a} ({\bar{v}}_{a})}]}^{- 1} \leq {(\min_{0 \leq n \leq p} \frac{l_{n}}{h_{n + 1}})}^{- 1}$ (3.19)

$\frac{\sum_{a \in A} v_{a} E [t_{a} (V_{a})]}{\sum_{a \in A} E [V_{a} t_{a} (V_{a})]} \leq \frac{\sum_{a \in A} v_{a} {\bar{t}}_{a} (v_{a})}{\sum_{a \in A} {\underline{s}}_{a} (v_{a})} \leq \max_{0 \leq n \leq p} \frac{h_{n}}{l_{n + 1}}$ (3.20)

因此可得如下定理。

定理3.1假设随机需求UE-CN交通网络中的路段出行成本为单项式函数 $t_{a} (V_{a}) = V_{a}^{n}$ 。设 $\bar{V}$ 和 $\hat{V}$ 分别为VI问题(2.7)式和(2.8)式的解，若假设3.1和假设3.2成立，则收费机制 $τ$ 下随机需求UE-CN混合交通均衡分配的效率损失存在上界，即

$ρ \leq {\begin{array}{l} \frac{1}{1 - β} \max_{0 \leq n \leq p} \frac{h_{n}}{l_{n + 1}} {(\min_{0 \leq n \leq p} \frac{l_{n}}{h_{n + 1}})}^{- 1}, & | K | = 1 \\ \frac{1}{1 - γ} \max_{0 \leq n \leq p} \frac{h_{n}}{l_{n + 1}} {(\min_{0 \leq n \leq p} \frac{l_{n}}{h_{n + 1}})}^{- 1}, & | K | \geq 2 \end{array}$ (3.21)

其中 $| K |$ 为CN用户的数目，参数 $β, γ, l_{n}, l_{n + 1}, h_{n}, h_{n + 1}$ 的定义如上。

下面，我们探讨解析推导法下的效率损失问题。由于不等式 $\sum_{k \in K} {\bar{v}}_{a}^{k} (v_{a}^{k} - {\bar{v}}_{a}^{k}) \leq \frac{1}{4} {(v_{a})}^{2}$ 成立，假设3.1和假设3.2，可将(3.3)式化简为

$\begin{array}{l} \frac{\sum_{a \in A} {\bar{v}}_{a} E [t_{a} ({\bar{V}}_{a})]}{\sum_{a \in A} v_{a} E [t_{a} (V_{a})]} \\ \leq {1 - \max_{v_{a} \geq 0} {\frac{v_{a} [h_{n} {({\bar{v}}_{a})}^{n} - l_{n} {(v_{a})}^{n}] + \frac{1}{4} {(v_{a})}^{2} n h_{n - 1} {({\bar{v}}_{a})}^{n - 1} + n {({\bar{v}}_{a})}^{n + 1} (h_{n - 1} - l_{n - 1}) + η_{a} n {({\bar{v}}_{a})}^{n} (v_{a} h_{n - 1} - {\bar{v}}_{a} l_{n - 1})}{h_{n} {({\bar{v}}_{a})}^{n + 1}}}}^{- 1} \end{array}$ (3.22)

并结合(3.18)~(3.20)式，此时

$\begin{array}{l} \frac{E [\sum_{a \in A} t_{a} ({\bar{V}}_{a}) {\bar{V}}_{a}]}{E [\sum_{a \in A} t_{a} (V_{a}) V_{a}]} \\ \leq {1 - \max_{v_{a} \geq 0} {\frac{v_{a} [h_{n} {({\bar{v}}_{a})}^{n} - l_{n} {(v_{a})}^{n}] + \frac{1}{4} {(v_{a})}^{2} n h_{n - 1} {({\bar{v}}_{a})}^{n - 1} + n {({\bar{v}}_{a})}^{n + 1} (h_{n - 1} - l_{n - 1}) + η_{a} n {({\bar{v}}_{a})}^{n} (v_{a} h_{n - 1} - {\bar{v}}_{a} l_{n - 1})}{h_{n} {({\bar{v}}_{a})}^{n + 1}}}}^{- 1} \\ \cdot \frac{\max_{0 \leq n \leq p} \frac{h_{n}}{l_{n + 1}}}{\max_{0 \leq n \leq p} \frac{l_{n}}{h_{n + 1}}} \\ = {1 - \max_{ω \geq 0} [- \frac{l_{n}}{h_{n}} {(ω)}^{n + 1} + \frac{n h_{n - 1}}{4 h_{n}} {(ω)}^{2} + (1 + \frac{η_{a} n h_{n - 1}}{h_{n}}) ω + \frac{n (h_{n - 1} - l_{n - 1} - η_{a} l_{n - 1})}{h_{n}}]}^{- 1} \cdot \frac{\max_{0 \leq n \leq p} \frac{h_{n}}{l_{n + 1}}}{\min_{0 \leq n \leq p} \frac{l_{n}}{h_{n + 1}}} \end{array}$

式中 $ω = \frac{v_{a}}{{\bar{v}}_{a}}$ 。则有如下定理。

定理3.2假设随机需求UE-CN交通网络中的路段出行成本为单项式函数 $t_{a} (V_{a}) = V_{a}^{n}$ 。设 $\bar{V}$ 和 $\hat{V}$ 分别为VI问题(2.7)式和(2.8)式的解，若假设3.1和假设3.2成立，则收费机制 $τ$ 下随机需求UE-CN混合交通均衡分配的效率损失存在上界，即

$ρ \leq {1 - \max_{ω \geq 0} {- \frac{l_{n}}{h_{n}} {(ω)}^{n + 1} + \frac{n h_{n - 1}}{4 h_{n}} {(ω)}^{2} + (1 + \frac{η_{a} n h_{n - 1}}{h_{n}}) ω + \frac{n (h_{n - 1} - l_{n - 1} - η_{a} l_{n - 1})}{h_{n}}}}^{- 1} \cdot \frac{\max_{0 \leq n \leq p} \frac{h_{n}}{l_{n + 1}}}{\min_{0 \leq n \leq p} \frac{l_{n}}{h_{n + 1}}}$

由于 $ρ \geq 1$ ，若

$\max_{ω \geq 0} {- \frac{l_{n}}{h_{n}} {(ω)}^{n + 1} + \frac{n h_{n - 1}}{4 h_{n}} {(ω)}^{2} + (1 + \frac{η_{a} n h_{n - 1}}{h_{n}}) ω + \frac{n (h_{n - 1} - l_{n - 1} - η_{a} l_{n - 1})}{h_{n}}} \geq 1$

则定义

$\frac{1}{1 - \max_{ω \geq 0} [- \frac{l_{n}}{h_{n}} {(ω)}^{n + 1} + \frac{n h_{n - 1}}{4 h_{n}} {(ω)}^{2} + (1 + \frac{η_{a} n h_{n - 1}}{h_{n}}) ω + \frac{n (h_{n - 1} - l_{n - 1} - η_{a} l_{n - 1})}{h_{n}}]} = + \infty$ 。

4. 结论

本文在现有文献的基础上，探讨UE和CN两类用户组成的混合随机交通网络在收费机制下的效率损失问题。分别运用非线性规划法和解析推导法得到单项式成本函数下的效率损失上界表达式。研究结果表明，解析推导法下的效率损失上界与路段出行成本函数次幂、路段收费有关，而非线性规划法得到的效率损失上界不仅与路段出行成本函数次幂、路段收费有关，还与CN用户的数目相关。

基金项目

贵州省研究生教育创新计划/Innovative Project of Graduate Education of Guizhou Province (YJSCXJH2020126)。

文章引用

毛君竹,顾重秀,王才正,尚美欣. 收费机制下随机需求UE-CN混合交通均衡分配的效率损失
Efficiency Loss of UE-CN Mixed Traffic Equilibrium Assignment with Stochastic Demand under Charging Mechanism[J]. 应用数学进展, 2022, 11(04): 1683-1692. https://doi.org/10.12677/AAM.2022.114183

参考文献

1. Wardrop, J.G. (1952) Some Theoretical Aspects of Road Traffic Research. Proceedings of the Institute of Civil Engineers Part II, 1, 325-362. https://doi.org/10.1680/ipeds.1952.11259

2. Koutsoupias, E. and Papadimitriou, C. (1999) Worst-Case Equilibria. Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, Vol. 1563, Springer, Berlin, 404-413. https://doi.org/10.1007/3-540-49116-3_38

3. Roughgarden, T. and Tardos, E. (2002) How Bad Is Selfish Routing?. Journal of the ACM, 49, 236-259. https://doi.org/10.1145/506147.506153

4. Karakostas, G. and Kolliopoulos, S.G. (2004) The Efficiency of Optimal Taxes. Proceedings of the First International Conference on Combinatorial and Algorithmic Aspects of Networking, Banff, August 2004, 3-12. https://doi.org/10.1007/11527954_2

5. Roberto Cominetti, J. (2009) The Impact of Oligopolistic Competition in Networks. Operations Research, 57, 1421-1437. https://doi.org/10.1287/opre.1080.0653

6. Sumalee, A. and Wei, X. (2011) First-Best Marginal Cost Toll for a Traffic Network with Stochastic Demand. Transportation Research Part B Methodological, 45, 41-59. https://doi.org/10.1016/j.trb.2010.04.007

7. Wang, C., Doan, X.V. and Chen, B. (2014) Price of Anarchy for Non-Atomic Congestion Games with Stochastic Demands. Transportation Research Part B, 70, 90-111. https://doi.org/10.1016/j.trb.2014.08.009

8. Cominetti, R., Scarsini, M., Schroder, M., et al. (2019) Price of Anarchy in Stochastic Atomic Congestion Games with Affine Costs. Proceedings of the 2019 ACM Conference on Economics and Computation, Phoenix, AZ, June 2019, 579-580. https://doi.org/10.1145/3328526.3329579

9. 冯增哲. 基于随机需求的交通网络效率损失研究[D]: [博士学位论文]. 北京: 北京交通大学, 2018.

10. Wang A.B. and Szeto, W.Y. (2018) Reliability-Based User Equilibrium in a Transport Network under the Effects of Speed Limits and Supply Uncertainty. Applied Mathematical Modelling, 56, 186-201. https://doi.org/10.1016/j.apm.2017.11.019

11. Han, D. and Hai, Y. (2008) The Multi-Class, Multi-Criterion Traffic Equilibrium and the Efficiency of Congestion Pricing. Transportation Research Part E Logistics & Transportation Review, 44, 753-773. https://doi.org/10.1016/j.tre.2007.07.011

12. 张俊婷, 周晶, 陈星光, 等. ATIS和道路收费下的混合随机用户均衡的效率损失[J]. 运筹与管理, 2017, 26(5): 137-141.

13. 余孝军, 罗玲玲. 弹性需求下UE-CN混合交通均衡分配的效率损失[J]. 系统科学与数学, 2020, 40(9): 1597-1613.

NOTES

^*第一作者。

期刊菜单