基于改进粒子群算法的随机流路网可靠性研究

张 薇

（兰州交通大学 交通运输学院，甘肃 兰州730070）

0 引 言

城市交通路网可靠性是衡量道路交通系统性能的重要指标。目前交通网络的可靠性研究主要集中在以下3个方面：连通可靠性、行程时间可靠性和容量可靠性。目前，路网可靠性的研究主要集中在行程时间、容量可靠性两方面［1－4］。本文针对容量可靠性进行研究。

Chen等提出了容量可靠性概念后，接着又提出了基于灵敏度分析和Monte Carlo技术来求解可靠性的方法。Lo和Tung建立了随机约束线性规划模型、PUE（概率用户平衡）模型来计算路网的可靠性。刘海旭、蒲云构造了双层规划模型来计算路网的可靠性。这些模型都是以线性规划为基础，并且被应用在实际的大规模道路交通网络中时，其计算量大。文献 ［5］从状态空间的角度来考虑路网的容量可靠性问题，为路网可靠性的评价提供了一个新的空间。它选取网络最可能状态来确定路段及路网可靠性的下界和上界以得到可靠性的近似值。不难发现，当状态数量增加时，可靠性的上下界趋于接近，这说明状态数量的选取限制了可靠性的准确度。文献 ［5］中可靠性计算结果只是估计值的原因在于其算法只选取了状态空间中的一部份最有可能状态作为研究基础。本文建立了随机流路网容量可靠性模型，并基于此模型提出了一种交通路网容量可靠性计算方法，计算可靠性时考虑路网的整个状态空间，采用改进的粒子群算法对整个状态空间进行搜索，以获得状态空间的所有下界点来计算路网的容量可靠性。

1 随机流交通路网可靠性模型

1.1 随机流交通路网模型定义

定义G＝ （N，E，F，P）是一个随机流交通路网，其中N是交通路网节点的集合，E＝ ｛ei｜1≤i≤m｝是路段的集合，F＝ （fij）为m×h的容量矩阵，h为路段具有的状态数，fij表示路段ei的第j种状态的容量，其中fi0为路段ei的最大容量，并且fij＞fij＋1，P＝ （Pij）为m×h的概率矩阵，Pij表示路段ei的第j种状态的概率，并且。

根据我国目前大中城市的道路服务水平划分标准 （见表1），路段上的服务水平按照饱和度分为5个级别，由于不同的服务水平下路段的容量也会不同，并且这5个服务水平级别恰好能够反映路段的5种容量状态。因此可将路网中各路段上采集到的交通流量数据对应地划分到5个状态中。方法如下：设vi是第j个路段的第i个流量数据，根据饱和度，可得到对应的服务水平级别，即可知对应容量状态。随机流路网模型的参数计算如下：各状态的容量值fjk取在该状态下的路段容量平均值，设该路段上共有n个采集数据，划分到第k状态的数据个数为nk，k∈［0，4］，则第j个路段的第k状态概率为Pjk＝，并且＝1。

表1 我国大中城市道路服务水平划分采用值

实际的交通网络中路段的容量是不确定的，完全畅通时，容量为最大值；完全阻塞时，容量为0，更多的情况下路段既不处于完全畅通状态，也不处于完全阻塞状态，而是介于两者之间的某种状态，其容量为0到最大值之间的某一个值。因此，路段的容量是随机的，是随着流量的改变而变化的。容量的不确定性使得路网的可靠性计算变得困难。本文建立的交通路网模型将各路段的容量以道路服务水平为依据进行状态划分，使得容量的不确定转化为5种确定状态，以解决路段容量的实测数据很难得到的问题，来研究整个路网的可靠性。

另外，连通可靠性经常被用于如地震等自然灾害发生时的特殊情况下的路网状态评价，而不适用于正常的交通网络中［6－11］。本文的随机流路网模型恰好描述了路网的多种状态及各种状态的概率，使得最终可靠性评价结果能够表征路网连通的程度，从而可以判断路网的确切状态。这样连通可靠性的应用范围能够得到扩展，应用于正常交通网络中可靠性的评价。

1.2 路网可靠性定义

路网容量可靠性反映的是路网能够满足一定交通需求的概率。各路段的若干状态的随机出现构成了路网的巨大的状态空间Ω。令X＝ （x1，x2，…，xi，…xn）为交通路网G＝ （N，E，F，P）的状态空间Ω中的任一状态，同时令交通需求量为d。若某个路网状态X＝ （x1，x2，…，xi，…xn）能够满足需求流量d，并且大于此状态的路网状态都能够满足需求流量d，则该状态称为路网的d－下界点。

其中，状态X1＞X2的含义为：不存在x1i＜x2i的情况，即状态X1中的所有路段容量都大于或等于状态X2中的对应的路段容量。

根据可靠性原理，当需求流量为d时，节点i和j之间的可靠性为Rd（i，j）＝Pr｛X｜f（X）≥d｝＝Pr｛X｜X≥Xi，Xi为d－下界点｝，因此，可靠性的计算问题转化为求出路网状态空间中足够d－下界点的问题。

2 基于改进粒子群算法的随机流交通路网可靠性分析

2.1 一种改进的粒子群算法

粒子群优化 （particle swarm optimization，PSO）算法是一种模拟鸟群觅食行为的演化计算算法。粒子群优化算法提出之后引起了全世界学者的广泛关注。由于粒子群优化算法概念简单，收敛速度快，涉及参数少，易于实现，具有很强的全局优化能力，因而迅速得到了认可，在当前的优化应用中受到越来越多的关注。目前粒子群优化算法已广泛应用于函数优化、神经网络训练、模糊系统控制、水利、电力和经济等大规模组合优化问题求解［12－15］。但是在求解问题规模庞大的交通路网问题时基本粒子群算法常常会陷入局部无解状态。本文利用粒子群算法的最优解实质是基于局部极值搜寻的这一特点，提出一种改进的能够搜索出满足要求的多个解的方法，应用这种改进的粒子群算法实现整个状态空间中足够d－下界点的目标搜索，从而进行有效的交通流路网可靠性分析。

基本PSO算法一直适用于寻找一个最优解的问题，其实将多个粒子散布于状态空间中，各个粒子通过自己本身的思考和其它粒子提供的信息作为指导，不断地改变飞行速度，最终是能够在状态空间中找到满足某条件的多个解的。

式中：i＝1，2…，m，d＝1，2，…，D；ω——惯性因子；c1、c2——学习因子；r1、r2—— ［0，1］之间的随机数；α——约束因子；——所有局部无解状态的出发点的重心。粒子既具有认知能力，又具有粒子之间的社会信息共享与相互合作。粒子的速度取决于当前最好位置和无解状态的重心位置，通过学习后会向自己当前最好位置靠近，而远离局部无解状态的位置，从而尽快找到局部最优解。

随机流交通路网随着节点的增加，问题的规模解也越来越多，常规基本粒子群算法往往陷入局部无解状态，使问题无法求解。本文提出一种改进粒子群算法，即在基本粒子群算法中加入一种转移机制。即当某一粒子连续t次更新后仍处于一局部范围，则重新为该粒子找到新的出发点。令xit2为粒子i从位置xit1更新后的位置，则｜xit1－xit2｜为粒子i某一次的移动距离，若｜xit1－xit2｜＜ε（ε为一较小值），表示粒子移动距离较小，如果粒子连续t次都移动较小距离，并且没有找到目标，则认为该粒子近期在一个较小范围内搜索，可能陷入局部范围找不到目标的状况。若判断出粒子已经陷入局部无目标搜索，则重新设置粒子的位置进行搜索。设置方法如下：为当前所有粒子所在位置的重心，粒子i的新位置为xi＝＋α，其中α是一较大值，使得粒子在新的空地重新开始搜索，不会出现拥挤现象，能够保证全局搜索的能力。

2.2 基于改进粒子群算法的d－下界点搜索

各路段的若干状态的随机出现构成了路网的巨大的状态空间Ω。令X＝ （x1，x2，…，xi，…xn）为交通路网G＝ （N，E，F，P）的状态空间Ω中的任一状态，xi表示第i条路段所处的状态号，xi∈ ［0，4］，fixi为该路段在xi状态下的最大容量，并且当j＜j’时，fij＜fij′。在n维的目标搜索空间中，选择m个路网状态组成一个群体，从初始粒子群体开始，每个粒子根据自己的飞行经验和其它粒子的飞行经验来动态调整自己的飞行方向和距离，最终找到满足d流量的下界点。

适应度函数为fitness（X）＝d－f（X），表示当前状态的最大流量与目标流量的距离。其中，f（X）为X路网状态下的最大流量。根据最大流最小割定理，网络的最大流等于最小割的容量。在某一状态X下，最大流f（X）＝min｛c（k）｜k为G的割｝，其中，c（k）为X状态下k的容量。

根据本文求解问题的特点，对算法参数作以下设置：研究表明较大的惯性权重ω有利于跳出局部极小点，较小的ω有利于算法收敛。随着迭代进行，ω按式 （3）由最大ωmax线性减小到最小ωmin，即

式中：itermax——最大进化代数，ωmax＝0.9，ωmin＝0.4［13］；群体规模m的选择与解的个数有关，m值过小，会遗漏可行解，m值过大，则对搜索时间和空间造成浪费，一般取m值能够满足解的数量即可；本问题中粒子本身的思考和其它粒子提供的信息对粒子的飞行速度都有很好指导意义，可设置加速常数c1＝c2＝2；为不使粒子飞过好位置，且目标是局部最优，所以Vmax可取值相对较小，Vmax＝2。

粒子执行完更新操作后，需对粒子作适当调整才能保证粒子的有效性。调整如下

2.3 改进粒子群算法求解随机流交通路网可靠性流程

本文提出的改进粒子群算法求解随机流路网可靠性算法流程如下：

步骤1 设定各参数的值，包括群体规模m，惯性权重w，加速常数c，最大速度Vmax，最大迭代次数Gmax；

步骤2 初始化m个粒子，包括随机位置和速度，记录粒子的初始位置；

步骤3 计算每个粒子的适应度函数值；

步骤4 对每个粒子Xi，将其适应值与其经历的最好位置Pi的适应值作比较，如果较好，则将Xi作为当前的最好位置Pi；

步骤5 判断粒子是否满足流量d的要求，若满足，记为d－下界点；

步骤6 对非d－下界点，根据转移机制判断粒子是否陷入局部无解状态，若是，重新设置粒子位置；

步骤7 根据式 （1）和式 （2）更新粒子的速度和位置，控制粒子的更新速度在Vmax内；

步骤8 根据式 （4）调整粒子，使得粒子是有效状态；

步骤9 转步骤3，直到各粒子都找到d－下界点为止；

步骤10 计算可靠性Rd（i，j）＝Pr｛X｜X≥Xi，Xi为d－下界点｝。

3 实例验证分析

图1为某城市某一路段抽象出来的交通网络拓扑结构图，其中包括6个节点和7条路段，这里以节点 （2→5）为OD对进行可靠性分析。假设在一天中的车流高峰期8：00－20：00之间连续对7个路段的车流量数据进行采集，每一小时为一个时间段，在12个时间段上共采集到12组数据，连续采集7天，求出平均值作为各路段一天中车流高峰期间的车流数据。

图1 网络结构

本试验随机产生7个路段的12组车流量数据作为基础数据，路段上的各状态对应的容量均为 ｛300，250，200，150，100｝，对该路网建立随机流路网模型，经计算得到表2所示的路网各路段容量及其概率数据。

表2 随机流路网容量及概率数据

应用本文提出的改进粒子群算法搜索得到不同需求量下OD对 （2→5）的d－下界点如表3所示。

为了验证本文提出的改进粒子群算法对交通流路网可靠性分析的正确性，首先应用本文提出的方法计算不同需求量下OD对 （2→5）的可靠性，然后采用传统蒙特卡罗方法进行计算，将两种不同方法计算结果进行比较，见图2，从图2可见清楚地看出本文提出的改进粒子群算法的计算结果与传统蒙特卡罗方法计算基本一致，从而说明了本文提出的改进算法是准确有效的。

表3 不同需求量下的d－下界点

图2 算法结果比较

4 结束语

根据城市交通路网容量的随机性特征，本文建立了随机流交通路网可靠性模型；提出的路网可靠性的算法以整个状态空间为背景搜索出所有的下界点状态，避免状态数量的限制影响到可靠性计算的准确度；搜索过程提出的改进粒子群算法能够寻找到多个可行解，并且在算法中引入转移机制的搜索方案，避免了粒子出现局部无解现象，能够在整个状态空间中找到足够的d－下界点。本文提出的算法为城市交通路网的可靠性评价提供了一个新的途径，可以帮助路网管理者对路网能力进行判断，并对路网的规划有一定指导意义。

［1］Armando M，Leite da Silva，Reinaldo A G，et al.Generating capacity reliability evaluation based on Monte Carlo simulation and cross－entropy methods ［J］.IEEE Transactions on Power Systems，2010，25 （1）：129－136.

［2］Loustau Pierre，Morency Catherine，Trépanier Martin，et al.Travel time reliability on a highway network：Estimations using floating car data ［J］.Transportation Letters，2010，2 （1）：27－37.

［3］Sumalee A，Kurauchi F.Network capacity reliability analysis considering traffic regulation after a major disaster ［J］.Networks and Spatial Economics，2006，6 （3）：205－219.

［4］ Hesham Rakha，Ihab El－Shawarby， Mazen Arafeh.Trip travel－time reliability：Issues and proposed solutions ［J］.Journal of Intelligent Transportation Systems，2010，14 （4）：232－250.

［5］KUANG Aiwu，HUANG Zhongxiang.On the service reliability in stochastic supply and demand ［J］.Systems Engineering，2007，25 （6）：25－29 （in Chinese）. ［况爱武，黄中祥.随机供求下的道路服务水平可靠性 ［J］.系统工程，2007，25（6）：25－29.］

［6］David Watling.Modelling and evaluation of reliability impacts in road networks：Concepts and methods for traffic assignment models ［C］.Leiden，Netherlands：European Transport and Conference，2008.

［7］LENG Junqiang，ZHANG Yaping，ZHAO Yingping，et al.Assessment of road network capacity reliability based on the constraints of link LOS ［J］.Journal of Transportation Systems Engineering and Information，2009，9 （5）：148－152 （in Chinese）.［冷军强，张亚平，赵莹萍，等.基于路段服务水平约束的路网容量可靠性分析 ［J］.交通运输系统工程与信息，2009，9 （5）：148－152.］

［8］WANG Yingjie，TAO Shining，CHENG Lin.Research on the estimating connectivity reliability of transport networks ［J］.Journal of Transportation Engineering and Information，2008，6 （2）：102－106 （in Chinese）.［王英杰，陶世宁，程琳.交通网络连通可靠性评价方法研究 ［J］.交通运输工程与信息学报，2008，6 （2）：102－106.］

［9］GUO Shuxia，YU Lei，CHEN Xumei，et al.A review of assessment measures on road network reliability ［J］.Urban Transport of China，2008，6 （5）：64－68 （in Chinese）.［郭淑霞，于雷，陈旭梅，等.路网可靠性评价指标研究综述 ［J］.城市交通，2008，6 （5）：64－68.］

［10］GUO Jifu，GAO Yong，WEN Huimin.Assessment methodo－logy of connect reliability based on substituted route ［J］.Journal of Highway and Transportation Research and Development，2007，24（7）：91－94 （in Chinese）.［郭继孚，高永，温慧敏.基于替代路径的路网连通可靠性评价方法研究 ［J］.公路交通科技，2007，24 （7）：91－94.］

［11］ZHAI Jing，LENG Junqiang，WANG Tianyi，et al.Reliability analysis of road network system based on substituted route ［J］.Journal of Kunming University of Science and Technology （Science and Technology），2010，35 （4）：57－60（in Chinese）.［翟京，冷军强，王天逸，等.基于替代路径的道路系统连通可靠性分析 ［J］.昆明理工大学学报 （理工版），2010，35 （4）：57－60.］

［12］HUANG Shaorong.Survey of particle swarm optimization algorithm ［J］.Computer Engineering and Design，2009，30 （8）：1977－1980 （in Chinese）. ［黄少荣.粒子群优化算法综述 ［J］.计算机工程与设计，2009，30 （8）：1977－1980.］

［13］SUN Yong，ZHANG Weiguo，ZHANG Meng，et al.Optimization of flight controller parameters based on chaotic PSO algorithm of adaptive parameter strategy ［J］.Journal of System Simulation，2010，22 （5）：1222－1225 （in Chinese）.［孙勇，章卫国，章萌，等.基于改进粒子群算法的飞行控制器参 数 寻 优 ［J］. 系 统 仿 真 学 报，2010，22 （5）：1222－1225.］

［14］REN Xiaobo，YANG Zhongxiu.Improvement of particle swarm optimization algorithm ［J］.Computer Engineering，2010，36 （7）：205－207 （in Chinese）.［任小波，杨忠秀.粒子群优化算法的改进 ［J］.计算机工程，2010，36 （7）：205－207.］

［15］DAI Jun，LI Guo，XU Chen.Enhanced particle swarm optimization algorithm ［J］.Journal of Computer Applications，2010，30 （5）：1293－1296 （in Chinese）. ［代军，李国，徐晨.一种增强型的粒子群优化算法 ［J］.计算机应用，2010，30 （5）：1293－1296.］