The Algorithms for MEM Stochastic User Equilibrium Model

Baolong Liu^1*, Zhonghui Xue², Yazheng Dang¹, Junxiang Li¹

¹Management School, University of Shanghai for Science and Technology, Shanghai, China.
²Basic Teaching Department, Shanghai Publishing and Printing College, Shanghai, China.

DOI: 10.4236/oalib.1105800                

Abstract

MEM stochastic user equilibrium model is proposed by foreign scholars in recent years. It is flexible due to the joint distribution of the stochastic errors and this property shows a promising application in realistic traffic assignment. However, there is little research on the algorithms for MEM model. This paper adopts MSA, MSWA and SRA to solve the new MEM stochastic user equilibrium model. The performances are verified through an experiment with fixed demand in Nguyen & Dupuis network, and the expected results show that MEM model is applicable in practice. Finally, considering the shortcomings of the experiment, we point out a direction of further research.

Keywords

Stochastic User Equilibrium Model, MEM Model, MSA, Traffic Assignment

1. 引言

交通分配是城市交通规划过程中的重要问题，1952年，Wardrop [1] 提出了著名的用户均衡(User Equilibrium, UE)原则，该原则指出出行者总是选择最短的路线，当不存在某一个出行者可以通过单一地改变自己的路径选择而减少行程时间的时候，就达到了用户均衡状态。均衡状态下，所有被出行者选择的路径具有相等或者最少的行程时间，未被使用的路径则具有相等或者更多的行程时间。然而，UE原则假设所有的出行者都是完全理性且相同的，并且完全了解所有路径的道路情况和行程时间，这种假设在现实情况下是不现实的。实际路网中，出行者通常只掌握路网的部分信息，并且他们选择自己的路线的过程总是随机的。1977年，Daganzo和Sheffi [2] 提出了随机用户均衡(Stochastic User Equilibrium, SUE)原则，放宽了Wardrop用户均衡中关于用户完全了解路径的完美假设，更符合实际的路网情况，因此SUE模型成为了人们研究的热点。

SUE原则既考虑了路径流量对行程时间的影响，也考虑了出行者的感知误差。它允许路径的实际阻抗与出行者的感知阻抗之间存在随机误差，这在实际交通分配问题中更为合理。在SUE解点，出行者单方面改变路径不能降低自己的路径感知阻抗，即达到SUE条件：系统中不再存在司机认为他能通过单边改变路径来降低其阻抗的机会 [3] 。SUE模型路径阻抗随机误差项的分布决定了所使用离散选择模型的不同。目前常用的SUE模型主要是Logit型SUE模型(随机误差项服从Gumbel分布)。

Logit型SUE模型简单直观，并且具有较强的可解释性，因此，在交通分配过程中使用较为广泛。然而，Logit型SUE模型的基本假设是随机误差项是独立的或相同分布的，这就使得它在实际应用过程中具有以下缺点：1) 无法解释路径之间的重叠或相关性；2) 无法考虑不同长度路径的感知差异。近年来，国外学者Natarajan等首次提出了一种MDM模型 [4] ，它并没有假定随机误差项是独立的或相同分布的，而是假设其基于联合分布，涵盖了误差项边缘分布的相关知识，因此能够尽可能地提高出行者的期望效用值，同时又使得MDM模型具有很强的灵活性。在这之后，Ahipasaoglu等人 [5] 将MDM模型和SUE模型联系起来，提出了MDM-SUE模型，并给出了相应的数学规划形式，从而为MDM-SUE模型的求解提供了可能。Mishra [6] 等通过研究表明广义极值选择概率可以运用指数分布获得，这种情况下产生的MDM模型的一种特例即为MEM模型。本文主要研究这种MEM随机用户模型及其求解算法。

在求解SUE模型的过程中，学者们提出了很多算法，如全由全无分配法、增量分配法、Dial算法、粒子群算法 [7] 、蚁群算法 [8] 、人工鱼群算法 [9] 等。其中，经典的MSA算法计算简单，应用广泛，接近平衡分配，是一种最常用的方法，本文主要应用MSA算法以及基于MSA算法的MSWA和SRA这几种算法对MEM-SUE模型进行求解。

2. MEM随机用户均衡模型

2.1. 符号及变量定义

给定一个强连通交通网络G(N，A)，N是节点集，A为有向路段集。令：P为所有路径集合；R为起讫点集合，r为其中的元素；a为一条路段， $a\in A$ ；k为一条路径， $k\in P$ ； $P_r$ 为OD对r间所有路径集合； $f_r^k$ 为OD对r间第k条路径上的流量； $q_r$ 为OD对r间的交通需求； $C_r^k$ 为OD对r间第k条路径上的感知阻抗； $c_r^k$ 为OD对r间第k条路径上的实际阻抗； ${\xi }_r^k$ 为OD对r间第k条路径上的误差阻抗； $v_a$ 为路段a上的流量； ${\delta }_r^{ak}$ 为0~1变量，对r中的第k条路径经过路段a时取1，否则取0； $P_r^k$ 为OD对r间第k条路径被选择的概率。

2.2. MEM随机用户均衡模型

MEM模型中随机效用的累积分布函数如下：

$F_r^k\left({\zeta }_r^k\right)=1-\exp \left(\frac{{\alpha }_r^k-{\zeta }_r^k}{{\phi }_r^k}\right),\forall {\zeta }_r^k\ge {\alpha }_r^k$ (1)

其中， ${\alpha }_r^k$ 是位置参数， ${\phi }_r^k$ 是和感知误差有关的尺度参数， ${\phi }_r^k$ 越大，出行者对路径的感知误差越大，MEM模型路径选择概率公式如下：

$p_r^k=\text{exp}\left(\frac{{\alpha }_r^k-{\lambda }_r-c_r^k}{{\phi }_r^k}\right)$ (2)

${\lambda }_r$ 满足：

${\displaystyle {\sum }_{k\in P_r}\exp \left(\frac{{\alpha }_r^k-{\lambda }_r-c_r^k}{{\phi }_r^k}\right)}=1$ (3)

假定 ${\phi }_r^k=\phi$ ，由公式(3)可得：

${\lambda }_r={\phi }_r^k\ln \left[{\displaystyle {\sum }_{i\in P_r}\exp \left(\frac{{\alpha }_r^k-c_r^k}{{\phi }_r^k}\right)}\right]$ (4)

假设对于每条路径，位置参数 ${\alpha }_r^k=\alpha$ ，即都是相等的，则根据公式(2)和(4)，MEM模型的路径选择概率为：

$p_r^k=\frac{\text{exp}\left[{\phi }^{-1}\left(\alpha -c_r^k\right)\right]}{{\displaystyle {\sum }_{i\in P_r}\text{exp}\left[{\phi }^{-1}\left(\alpha -c_r^i\right)\right]}}$ (5)

MEM模型中的路径流量为：

$f_r^k=q_r\frac{\text{exp}\left[{\phi }^{-1}\left(\alpha -c_r^k\right)\right]}{{\displaystyle {\sum }_{i\in P_r}\text{exp}\left[{\phi }^{-1}\left(\alpha -c_r^i\right)\right]}}$ (6)

综上，基于MEM模型的SUE数学规划模型(MEM-SUE)为：

$\begin{array}{c}\min Z_{MEM}\left(f\right)={\displaystyle {\sum }_{a\in A}{\displaystyle {\int }_0^{v_a}{t}_a\left(w\right)\text{d}w}}+\frac{1}{\theta }{\displaystyle {\sum }_{r\in R}{\displaystyle {\sum }_{k\in P_r}{f}_r^k\ln f_r^k}}\\ -\alpha {\displaystyle {\sum }_{r\in R}{q}_r}-\frac{1}{\theta }{\displaystyle {\sum }_{r\in R}{q}_r\left(\ln q_r+1\right)}\end{array}$ (7)

约束条件为：

${\displaystyle {\sum }_{k\in P_r}{f}_r^k}=q_r,r\in R$

$f_r^k\ge 0,r\in R,k\in P_r$

$v_a={\displaystyle {\sum }_{r\in R}{\displaystyle {\sum }_{k\in P_r}{f}_r^k{\delta }_r^k}},a\in A$

3. 算法和算例

3.1. 算法

MSA 算法是求解交通分配问题的经典算法，其主要思想是对上一次迭代过程中各路段的交通流量与本次迭代过程中所获得的附加流量进行加权平均，进而通过计算得到本次迭代过程中各路段的交通流量。当各路段交通量的均方根误差(RMSE)小于预设值时，则停止迭代，路段上的最终交通量就是最后分配结束后所获得的交通量。MSA算法一般是沿下降方向给定一个确定的步长，标准公式如下：

${\lambda }^{\left(n\right)}=\frac{k_1}{n+k_2}$

式中， $k_1$ 为正常数，决定步长的长度， $k_2$ 是非负常数，代表了对起始步长的补偿值，n为迭代次数。经典的MSA算法一般令 $k_1=1$ ， $k_2=0$ ，即取 ${\lambda }^{\left(n\right)}=\frac{1}{n}$ 。本文同时采用其他两种变步长的MSA算法对MEM随机用户均衡模型进行求解：连续权重平均法(MSWA)以及自动调整平均法(SRA) [10] 。

本文采用算法主要步骤如下：

Step 1：根据各路段初始自由阻抗计算各路径阻抗，进而计算各路径流量 $f_r^{k\left(n\right)}$ ，令迭代次数n = 1；

Step 2：更新路段阻抗和路径阻抗。

Step 3：确定下降方向。执行一次离散模型加载，得到各路段的附加路径流量 $g_r^{k\left(n\right)}$ ，则下降方向为 $g_r^{k\left(n\right)}-f_r^{k\left(n\right)}$ 。

Step 4：更新路径交通量。

$f_r^{k\left(n+1\right)}=f_r^{k\left(n\right)}+{\lambda }^{\left(n\right)}\left(g_r^{k\left(n\right)}-f_r^{k(n)}\right)$

本文采用的三种算法的区别在于迭代步长 ${\lambda }^{\left(n\right)}$ 选取方法的不同。

对于相继平均法：

${\lambda }^{\left(n\right)}=\frac{1}{n}$ ，

对于连续权重平均法：

${\lambda }^{\left(n\right)}=\frac{n^d}{1^d+2^d+3^d+\cdots +n^d}$ ，

其中：d为正的参数。

对于自动调整平均法：

${\lambda }^{\left(n\right)}=\frac{1}{\beta \left(n\right)}$ ，

其中，

$\beta \left(n\right)=\{\begin{array}{l}\beta \left(n-1\right)+{\lambda }_1,{\lambda }_1>1,如果\Vert {\lambda }^{\left(n\right)}-f^{\left(n\right)}\Vert \ge \Vert {\lambda }^{\left(n-1\right)}-f^{\left(n-1\right)}\Vert ;\\ \beta \left(n-1\right)+{\lambda }_2,0<{\lambda }_2<1,如果\Vert {\lambda }^{\left(n\right)}-f^{\left(n\right)}\Vert <\Vert {\lambda }^{\left(n-1\right)}-f^{\left(n-1\right)}\Vert .\end{array}$

Step 5：收敛性检验。若均方根误差RMSE小于规定值，则停止迭代，否则，n = n + 1，返回Step 2继续循环。

其中，

${\text{RMSE}}^{\left(n\right)}=\sqrt{\frac{1}{\left|K\right|}{\displaystyle {\sum }_r{\displaystyle {\sum }_k{\left(g_r^{k\left(n\right)}-f_r^{k\left(n\right)}\right)}^2}}}$ ，

$\left|K\right|$ 为所有OD对间路径的数量。

3.2. 算例及结果分析

本文采用Nguyen & Dupuis路网对三种算法在求解MEM随机用户均衡模型的性能进行比较，如图1所示。

该路网共有4个OD对(分别为：(1, 2)，(1, 3)，(4, 2)，(4, 3))，25条有效路径和19条路段。在该路网中，每个OD对之间具有固定的交通需求，各OD对之间的交通需求为：(1, 2):100；(1, 3):200；(4, 2):150；(4, 3):150。路段的基本属性采用魏秋月 [11] 设置的路段属性，如路段容量、路段初始阻抗等相关信息，具体内容见表1。路段的行驶时间函数采用美国联邦公路局提出的费用?流量(BPR)函数：

Figure 1. Nguyen & Dupuis network

图1. Nguyen & Dupuis路网

Table 1. Link attributes

$t_a\left(v_a\right)=t_a^0\left[1+\beta {\left(\frac{v_a}{C_a}\right)}^n\right]$ ，

式中： $t_a^0$ 是路段a的自由流行驶时间， $C_a$ 是路段a的容量， $t_a\left(v_a\right)$ 是路段a的行驶时间函数， $\beta$ 和n为定值。

对MEM随机用户均衡模型进行求解时，令 $\alpha =0$ ， $\phi =50$ ， $\beta =0.15$ ，n = 4。图2给出了三种算法收敛时的迭代次数对比情况，图3为3种算法分配到各路段上的流量。

从图2可以看出，尽管MSWA和SRA在迭代初期RMSE值较大，但在第3次迭代左右即表现出了明显优于MSA算法的收敛速度。同时SRA算法的收敛速度又优于MSWA算法，是3种算法中收敛速度最快的算法。图3表明：对于MEM随机用户均衡模型，3种算法的路段流量分配结果差别不大，都是在第2、9、17条路段上分配的较多的流量。综合考虑各算法的收敛速度，MSWA和SRA算法相较于经典的MSA算法更为优越，SRA算法的表现最佳，具有较好的应用价值。

Figure 2. Iteration numbers

图2. 迭代次数

Figure 3. Link flow

图3. 路段流量

4. 结论

本文针对近年来新提出的MEM模型采用了MAS、MSWA、SRA算法进行求解，取得了预期的结果，结果表明SRA算法相较于其他两种算法具有更优越的收敛表现和应用价值。同时，这几种算法在应用过程中并未对路段容量进行限制，所以分配结果中有可能会出现流量超出路段容量的情况，这也是下一步的研究方向。

致 谢

本论文得到上海出版印刷高等专科学校高层次引进人才科研启动资金和上海出版印刷高等专科学校高等教研究所课次项目支持，在此一并感谢！

基金项目

国家自然科学基金面上项目(NO. 71572113)。

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Wardrop, J.G. (1952) Some Theoretical Aspects of Road Traffic Research. ICE Proceedings of Engineering Divisions, Thomas Tel-ford, London, 325-362.
[2]	Daganzo, C.F. and Sheffi, Y. (1977) On Stochastic Models of Traffic Assignment. Transportation Sci-ence, 11, 253-274. https://doi.org/10.1287/trsc.11.3.253
[3]	黄海军. 城市交通网络平衡分析: 理论与实践[M]. 北京: 人民交通出版社, 1994.
[4]	Natarajan, K., Song, M. and Teo, C.P. (2009) Persistency Model and Its Applications in Choice Modeling. Management Science, 55, 453-469. https://doi.org/10.1287/mnsc.1080.0951
[5]	Ahipasaoglu, S.D., Ankan, U. and Natarajan, K. (2016) On the Flexibility of Using Marginal Distribution Choice Models in Traffic Equilibrium. Transportation Research Part B: Methodological, 91, 130-158. https://doi.org/10.1016/j.trb.2016.05.002
[6]	Mishra, V.K., Natarajan, K., Padmanabhan, D., Teo, C.-P. and Li, X. (2014) On Theoretical and Empirical Aspects of Marginal Distribution Choice Models. Management Science, 60, 1511-1531. https://doi.org/10.1287/mnsc.2014.1906
[7]	刘炳全, 孙广才. 基于Logit分配的交通网络设计模型的改进粒子群算法[J]. 科学技术与工程, 2008, 8(19): 5446-5450+5456.
[8]	张福龙. 基于最大最小蚁群算法的随机用户交通分配模型研究[D]: [硕士学位论文]. 西安: 长安大学, 2016.
[9]	刘炳全, 度巍. 求解Logit随机用户均衡问题的改进人工鱼群算法[J]. 现代电子技术, 2016(3): 127-130.
[10]	Liu, H.X., He, X. and He, B. (2009) Method of Successive Weighted Averages (MSWA) and Self-Regulated Averaging Schemes for Solving Stochastic User Equilibrium Problem. Networks and Spatial Economics, 9, 485-503. https://doi.org/10.1007/s11067-007-9023-x
[11]	魏秋月. 基于蚁群优化的随机用户均衡模型研究[D]: [硕士学位论文]. 西安: 长安大学, 2017.