求解MNW随机用户均衡问题的改进人工鱼群算法

刘宝龙

摘 要：MNW随机用户均衡模型解决了Logit模型所有路径感知方差完全相等的假设，因此在交通分配中具有一定的应用前景。针对这一模型，本文采用了一种定向搜索变异的改进人工鱼群算法，该算法在迭代时可以保证鱼群在当前状态下自适应变异的同时还可以向当前的最佳位置移动。随后在固定需求下的Nguyen & Dupuis中对该算法进行验证，取得了预期的结果，说明了MNW模型良好的应用价值。同时，针对实验中存在的不足提出了进一步的研究方向。

关键词：随机用户均衡模型;MNW模型;人工鱼群算法;交通分配文章编号：2095-2163（2019）04-0125-04 中图分类号：U491 文献标志码：A

0 引 言

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

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

然而，Logit型SUE模型假设所有路径感知方差完全相等，这在交通分配的研究应用中存在着一定的局限性。为了放松该假设，Castillo等人[4]提出了服从Weibull分布的 Weibit模型、即MNW模型。该模型与Logit模型的主要区别是：Logit模型的效用函数采用加法形式，而MNW模型的负效用函数是乘法形式。在此之后，Kitthamkesorn等人[5]将MNW模型和SUE模型联系起来，构建了MNW-SUE模型，并给出了相应的数学规划形式，从而为MNW-SUE模型的求解提供了可能。本文主要研究这种MNW随机用户模型及其求解算法。

在求解SUE模型的过程中，学界已陆续推出了很多算法，如全有全无分配法、增量分配法、Dial算法、粒子群算法[6]、蟻群算法[7]、截断拟牛顿型信赖域法[8]等。为了对MNW-SUE模型进行求解，本文采用定向搜索变异的改进人工鱼群算法来展开验证。对此拟做研究论述如下。

1 MNW随机用户均衡模型

1.1 符号及变量定义

1.2 MNW随机用户均衡模型

MNW模型采用的效用函数可表示为：

2 算法和算例

2.1 改进人工鱼群算法

2.2 算例及结果分析

本文基于Nguyen & Dupuis路网利用改进的人工鱼群算法对求解MNW随机用户均衡模型的性能进行验证，如图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。路段的基本属性采用魏秋月[9]设置的路段属性，如路段容量、路段初始阻抗等相关信息。

路段的行驶时间函数采用美国联邦公路局提出的费用-流量（BPR）函数，可将其写作如下数学形式：

从图2可以看出，改进人工鱼群算法具有较快的收敛速度，并且在迭代后期的收敛性趋于稳定。图3给出了分配结束时各条路段上的流量情况，表明该改进人工鱼群算法有能力求解该类型交通分配问题，具有良好的应用价值。同时从图3可以看出，路段15、18的路段流量超出了路段容量，这是由于算法未考虑路段容量限制造成的，这也为后续研究指明了方向。

3 结束语

本文针对近年来新提出的MNW模型采用定向搜索变异的改进人工鱼群算法进行求解，取得了预期的结果，结果表明该算法具有良好的收敛表现和应用价值。同时，由于该算法在应用过程中并未对路段容量进行限制，所以分配结果中有可能会出现流量超出路段容量的情况，这也是下一步的研究重点。

参考文献

[1]WARDROP J G. Some theoretical aspects of road traffic research [J]. Proceeding of the Institute of Civil Engineers， 1956， 1（2）：57-68.

[2] DAGANZO C F， SHEFFI Y. On stochastic models of traffic assignment [J]. Transportation Science， 1977， 11（3）：253-274.

[3] 黄海军. 城市交通网络平衡分析：理论与实践[M]. 北京：人民交通出版社， 1994.

[4] CASTILLO E， MENENDEZ J M， JIMNEZ P， et al. Closed form expressions for choice probabilities in the Weibull case[J]. Transportation Research Part B：Methodological， 2008，42（4）：373-380.

[5] KITTHAMKESORN S， CHEN A. A path-size weibit stochastic user equilibrium model[J]. Transportation Research Part B：Methodological，2013，57：378-397.

[6] 刘炳全， 孙广才. 基于Logit分配的交通网络设计模型的改进粒子群算法[J]. 科学技术与工程， 2008， 8（19）：5446-5450，5456.

[7] 张福龙. 基于最大最小蚁群算法的随机用户交通分配模型研究[D]. 西安：长安大学，2016.

[8] 刘建美， 马帅奇. 关于求解随机用户均衡问题的截断拟牛顿型信赖域法研究[J]. 数学的实践与认识， 2017，47（10）：184-190.

[9] 魏秋月. 基于蚁群优化的随机用户均衡模型研究[D]. 西安：长安大学，2017.

[10]姜山，季业飞. 改进的人工鱼群混合算法在交通分配中的应用[J]. 计算机仿真， 2011， 28（6）：326-329.