路网拥塞控制中的多目标路径决策模型研究

蒋斌　徐骁　杨超　李仁发

摘 要：智能交通系统领域中的路网拥塞控制是解决路网拥塞问题的主要手段之一，针对该问题，利用自底向上的agent建模方式，构建一种多目标路径决策agent移动模型.在该模型中，车辆agent兼顾最短路径和拥塞避免两个优化目标，通过车辆agent行驶距离最短（最短路径）和途经区域的拥塞程度最低（拥塞避免）两个目标优化来动态进行路径决策.基于多目标路径决策移动模型一方面能够实现对交通拥堵路段的分流控制，另一方面能够挖掘网络拓扑结构中易发生拥塞的路口的共同特征，为路网拥塞控制提供帮助.仿真实验结果表明，该模型能较好地改善路网结构中的拥塞路段.针对不同链路密度及链路分布的网络所进行的仿真实验结果进一步表明，路网结构的链路密度对拥塞路段出现在网络中的地理位置影响不同，而路口节点位置影响其拥塞程度；网络结构的链路分布形态对发生拥塞路段的地理位置和拥塞优化结果具有直接影响.

关键词：多目标优化；路网拥塞；agent移动模型

中图分类号：TP399 文献标识码：A

智能交通系统（ITS，Intelligent Transportation Systems）在交通领域的各个方面，例如路径规划、车辆导航及拥塞控制等方面已得到了许多成功应用.拥塞控制作为ITS中的一个关键应用，一直是研究热点＼[1＼].目前，交通拥塞的研究方法大致可以分为3类：1）基于统计物理学的方法，如Liao等人使用熵复杂因果关系平面法分析交通数据，实验结果表明：其方法在评价交通动态状态分级时效果最好，交通数据被分为：拥塞，中级，通畅＼[2＼].Helbing介绍了多种交通流以及自主性多粒子所描述的系统，回顾和比较了交通领域中关于实证数据、行人和车辆通行的主要方法以及微观中观宏观三种模型＼[3＼]. 2）基于数学规划的方法.1985年，Sheffi运用数学动态规划及其建模方法，系统地阐述了交通流量的拥塞问题，并且提出了多种用户均衡状态及交通流建模的解决方案＼[4＼].文孟飞等人利用一种基于增量搜索的多目标优化方法实现了车辆的实时路径诱导＼[5＼].3）基于ABMS（agentBased Modeling and Simulation）的智能交通拥塞控制方法.例如，Narzt等人运用昆虫群集产生的电子信息素，通过对其它车辆信息素的搜集、区分及避开拥塞，采用非集中控制的方式在仿真交通系统中分析汽车多种规避拥塞的不同策略＼[6＼]. 梁满朝、李文勇等人针对城市交通信号控制的动态路径优化问题，综合考虑了路口距离和道路的饱和程度，通过基于蚁群算法和群决策理论的动态路径优化算法模型，并证明了其有效性＼[7＼]. Buscema等人则考虑驾驶员行为偏好对路径选择的影响，指出驾驶员对于路径的选择不仅仅依赖于交通引导系统同时也依赖于驾驶员的主观感觉＼[8＼].此外，文献＼[9＼]提出了一种基于agent的智能驾驶模型，通过结合网络、车辆信息共享更新的基础设备和自适应巡航联合控制的方法，证明了该agent智能驾驶模型的实用性以及如何使用该技术减少拥塞.

湖南大学学报（自然科学版）2015年第4期蒋 斌等：路网拥塞控制中的多目标路径决策模型研究

交通系统涉及个体自主驾驶行为与复杂交通环境之间的实时交互和反馈机制，属于典型的复杂系统研究范畴.本文采用自底向上的ABMS方法，联系微观个体行为与宏观交通涌现现象来研究智能交通系统的拥塞控制问题.现有基于agent的拥塞控制方法主要从车辆个体行为出发来研究改善拥塞的方法，预测驾驶时间或者用户行为，缺乏一定的宏观视角分析整个交通系统拥塞分布的涌现，从多目标优化的角度来实现网络拥塞均衡算法也较少.针对上述问题，本文提出一种基于多目标路网拥塞均衡算法的agent移动模型，同时考虑最短路径和拥塞避免两个目标来动态决定车辆agent的移动目标，依据该优化策略自主地向各自预定目标移动，以实现整个网络拥塞动态均衡的目的.

1 ODD协议模型描述

通过ODD协议（Overview， Design concepts，Details）＼[10＼]描述基于多目标路网拥塞均衡算法的agent移动模型的设计与实现.

1.1 目的

本文提出一种基于多目标路径决策移动模型分析路网的拥塞问题.模型同时考虑最短路径和拥塞避免两个目标的优化，确保车辆抵达目的地的过程中整个网络拥塞得到改善.仿真实验验证了模型的有效性，同时针对不同链路密度和链路分布的模型试验，分析了不同网络结构对拥塞涌现和优化结果的影响，为实际路网中拥塞控制提供理论参考.

1.2 实体， 状态变量和尺度

如表1所示，模型包含两类实体：路口节点和车辆.其中，路口节点表示仿真实验预定义的路网结构中的交通路口节点，车辆定义为网络中依据一定移动策略自主移动的agent.

表2给出了模型中的状态变量：1）路口节点状态，包括节点饱和度和当前等待的车辆agent队列，节点饱和度指交通路口的最大通行能力，当车辆agent数目达到上限时将饱和度置1（具体定义及计算见2.4）；2）网络链路状态，表示整个路网不同路口节点间的连接状况（即网络中的边）；3）车辆agent的状态，包括出发地、目的地、当前路径及当前状态（等待或是移动至下一路口）.对于每个路口节点r，我们定义状态变量Ux来描述其在时刻t的拥塞状况为：

Ux=preA（r，t）desiG（r，t）， （1）

其中，preA（r， t）表示节点r在时刻t的前置影响，desiG（r，t）表示节点r在时刻t的节点饱和度，具体计算见1.4.本文中，为了简化计算，我们将preA（r， t）的值设置为1.

表2 状态变量定义及其描述

Tab.2 Status variables definition and description

1.3 过程与调度

仿真过程中，每个agent抵到一个路口节点i，会根据该路口节点i的邻接节点集Si={v1， v2，…，vj，…，vn}进行计算（vj表示与节点i相邻的节点j），通过多目标优化算法计算集合中所有节点的效用值（效用函数定义及计算见2.6），处于移动状态的agent会选择集合Si中效用值最小的节点作为目标节点.若agent移动后到达最终目标路口节点，则将该agent从路网中移除.每一个仿真周期将执行两类实体和整个网络状态的更新.图1是对该仿真过程和调度的伪代码描述.

1.4 设计理念

基本原理. 本模型设计的主要原理来自于Sheffi提出的城市路网车流均衡最优化理论[4].拥塞作为交通复杂系统中最重要的机制之一，直接影响着通行时间，并与该交通节点的车流数目相关.在给定网络结构和平流量数据时，Sheffi将影响交通通行的因子细化为多类，其中最为重要的一点即是链路函数，链路函数反应为该道路关于车辆流量的通行时间函数，通过时间的长短将直接反应出车流拥塞的程度.Sheffi还提出UE（userequilibrium）状态理论，即没有驾驶员能够通过改变路径缩短他们的通行时间，该理想状态在实际情况中很难达到.针对UE状态，他提出了多种解决该类均衡问题的方法，并指出最小路径树（Label connecting algorithm）方法是其中最有效的办法之一.根据Sheffi的理论和建模方法，我们的模型选取避免拥塞和最短路径作为两个考虑的优化目标，并基于其理论来建立我们agent移动模型的相关参数和移动规则.

Sheffi理论大多是建立在宏观车流数学模型之上，通过数学规划等方法为达到某种平衡而进行计算.模型结合其理论，将交通复杂系统通过多agent系统进行模拟仿真，将个体移动策略和全局拥塞分布动态联系起来，是交通领域仿真模拟的新尝试.

涌现. 随着车辆agent在路网中的自主移动，将形成路网中各路口节点不同的拥塞分布，并涌现出某些拥塞特别严重的路口节点.研究agent移动策略与拥塞现象涌现的内在联系，对实现拥塞均衡具有很大的意义.

适应性. 在模型中， 车辆agent会基于最短路径和拥塞避免两个原则决定最终移动目标.车辆agent在移动过程中会基于周边路口节点的拥塞程度改变移动策略.

目标. 假设路口节点的最大车辆通行数量为Max，若节点r在仿真时间步t内通过的车辆数目为v，则节点r在时刻t的饱和度desiG定义为

desiG（r，t）=1v≥Max；

v+1Maxv

假设网络由N个节点构成，仿真实验结束时间步为End，则定义模型的目标函数为整个仿真过程中的平均节点饱和度之和nwval，其值越小则整个网络的拥塞分布情况越好.

nwval=∑Endt=0∑Nr=1desiG（r，t）.（3）

随机特性. 模型中车辆agent的出发地、目的地以及加入到网络中的时间都是随机设定的.在每一个仿真时间步，车辆agent基于效用函数的计算决定下一目标路口节点，该效用函数的定义不仅考虑了主要因素的影响，还通过高斯随机函数模拟了车辆移动过程中随机影响.

观察. 为分析不同网络拓扑结构下路口节点拥塞状况的涌现特征，在每个仿真时间步，记录下所有路口节点的节点饱和度desiG和整个模型的目标函数值nwval.

1.5 初始化

初始化阶段，模型随机产生500个具有不同移动策略、出发点和目的地的车辆agent；不同agent类别之间的比例，效用函数中的权值设定，根据实验目的具体设定.

1.6 子模型

我们所定义的agent移动模型理论来自于朗之万方程，假定agent移动是由主导因子和随机因子两部分共同的作用结果.据此我们定义agent的移动效用方程，见式（4），其中Λ（Ux，t，λ）代表了相邻节点x在时间t的效用值.车辆agent i将会选择其相邻节点集合Si={v1，v2，…，vn}中效用值最小的一个作为目标节点.式（4）中的f（Ux，t）表示的是周边路口节点x在时间t对车辆agent移动的外部作用，其值动态反应了该邻接节点x的饱和程度；g（x，t）代表对agent的路径约束， 其值直接反应出agent距离最终目标节点的路径长度，g（x，t）将会约束agent朝着目的地行进.参数λ是这两个目标之间（最短路径和拥塞避免）的权值.此外， 为了保持移动过程中具有一定的随机性， 我们在效用函数中加入高斯随机扰动Gauss，

Λ（Ux，t，λ）=（1-λ）f（Ux，t）+

λg（x，t）+Gauss. （4）

为简化仿真实验，我们进行了如下约束：在每个仿真时间步，每个路口节点只允许单个车辆agent通过，其他车辆按到达该路口节点的次序进入车辆agent队列尾部等待.

2 实验设定及结果

如表3所示，我们执行3组实验来分别1）验证基于多目标的agent移动模型对网络拥塞均衡的有效性，2）分析网络链路密度对拥塞的影响.

对拥塞均衡的影响

网络结构及节点饱和度分析

分析网络链路分布形态对拥塞的影响.仿真实验中定义了两类agent：第一类Floyd agent将沿着最短路径向目的地移动；第二类Autonomous agent将同时考虑最短路径和拥塞避免两个优化目标，根据效用函数公式（4）向目的地自主移动.通过仿真实验采用的网络拓扑结构以及两类agent在不同比例和权值下的网络节点饱和度分布来分析仿真结果.3组实验都分别给出了本组仿真所采用的网络拓扑结构.

特别的，实验2和3中的网络拓扑结构分别按照链路数目、链路分布形态的不同进行对比实验，实验2中用黑色圆圈进行标识的节点表示在仿真过程中出现明显拥塞或异常的节点.3组仿真实验都给出对应其网络拓扑结构的平均节点饱和度分布，3种不同形状的图标（菱形、正方形、三角形）分别表示采用不同比例和权值构成的agent运行得到的仿真实验结果.如表4所示，3组仿真实验中，当网络中只含有Floyd agent时，用菱形图标表示网络节点的饱和度，而当两类agent各占50%，权值为0.85和0.15（实验1）或者0.95和0.2（实验2和3）时，网络节点饱和度分别采用正方形和三角形表示.表5给出了实验的参数设定.500个车辆agent将在前50个时间步随机加入到预定义的网络结构中，为保证所有agent都能够达到目的地，设定仿真时间步长