智能交通系统中动态路径诱导算法分析

1DOI：10.13607/j.cnki.gljt.2015.01.026智能交通系统中动态路径诱导算法分析王勇，于文震（南京电子技术研究所，南京210013）摘要：对智能交通中动态路径诱导算法进行较为系统的综述。首先，从微观和宏观角度对动态诱导系统中需要用到的交通参数模型进行分析和比较，并列举几种交通参数模型；然后，对一些经典路网寻优算法进行分析，并引用一些专家学者的研究成果；最后，对动态路径诱导算法的未来发展方向进行探讨。关键词：智能交通系统；动态路径诱导；交通参数模型；路径寻优文章编号：1009-6477（2015）01-0000-00中图分类号：U491.2文献标识码：AAnalysisofDynamicRouteGuidanceAlgorithminIntelligentTrafficSystemWANGYong,YUWenzhenAbstract:Thispapersystematicallysummarizesthedynamicrouteguidancealgorithminintelligenttrafficsystem.Firstthepaperanalyzesandcomparestrafficparametermodelsthoseshouldbeusedindynamicguidancesystemfrommicroandmacroviewpointsandlistsseveraltrafficparametermodels;second,thepaperanalyzessomeclassicroadnetworkoptimizationalgorithmsandreferstoresearchachievementsofsomeexpertsandscholars;andfinallythepaperprobesintothefuturedevelopmentdirectionofthedynamicrouteguidancealgorithm.keywords:intelligenttrafficsystem;dynamicrouteguidance;trafficparametermodel;routoptimizationITS是综合信息技术、数据通信技术、控制技术及网络技术建立的一种大范围、全方位、实时、准确、高效的智能交通运输管理系统。动态路径诱导系统(DRGS)是ITS的一个重要组成部分，该系统利用计算机、通信等现代技术，并根据出行者的起讫点和用户具体要求，向用户提供实时交通信息和最优路径引导指令[1]。通过系统诱导来优化用户的出行决策，合理分配交通路网的交通流[2]，改善交通状况。基金项目：江苏省物联网应用示范工程项目(GRS2010-10)收稿日期：2014-05-06作者简介：王勇（1989-），男，山东省济宁市人，在读研究生.2015-02-1517:32根据交通信息性质，路径诱导系统可分为静态路径引导系统和动态路径诱导系统。前者依据的是静态交通路网信息，后者是在前者基础上，利用现代技术获得实时、动态的路网信息。动态路径诱导系统通常由控制中心、通信系统和车载终端3部分组成，其中信息处理主要在控制中心完成。根据不同的计算方式，动态路径诱导系统可分为中心决定式和分布式2大类，其中分布式动态路径诱导系统通常是将实时计算任务分配给不同的车载单元，从而实现更快捷的动态路径诱导[3]。动态路径诱导算法是交通诱导的核心，基本思想是结合动态、实时的路网信息，得到最优行驶路线，因此，动态路径诱导算法通常需考虑交通状况的多个方面，尤其是交通参数模型和路径寻优算法。本文对动态路径诱导算法中的2大核心部分，即交通参数模型和路径寻优分别进行了分析，并结合部分理论成果提出动态路径算法的未来研究方向和方法。1交通参数模型交通参数模型是动态路径诱导算法的基础，它能提供交通网络的参数变化，从而为动态诱导算法提供必要的基础数据支持。本文将从微观和宏观2个层次介绍交通参数模型。1.1微观方面在动态路径诱导算法中，交通参数模型从微观方面需要解决以下几个问题：各进口道流量、路口平均延误、路口服务水平、路段车辆数、路口饱和度、路段交通饱和度[2]。限于篇幅，本文仅介绍路口的平均延误和路段交通饱和度[2]。1.1.1路口平均延误某一检测时段内，各个方向路段延误加权值。经典的路口平均延误有稳态延误模型、定数延误模型、过度函数延误模型。常见的路口平均延误模型根据路口饱和度的不同状态采用不同的延误模型：低饱和状态下采用稳态模型；过饱和状态下采用定数模型；过度模型是介于二者之间的模型。1）稳态延误模型。只有在饱和度低的情况下，即车辆平均到达率远低于路口通过能力时，才可使用稳态延误模型，该模型得到的结果与实际结果接近。稳定延误模型中路口平均延误包括2部分：均衡相位延误与随机延误。经典稳态延误模型中，路口平均延误模型包括Webster模型[2]、Miller模型[2]和Akcelik模型[2]。Webster模型：𝑑=𝑐(1−𝑔𝑐)22(1−𝑞𝑠)+𝑥22𝑞(1−𝑥)−0.65(𝑐𝑞2)13𝑥2+5𝑔𝑐(1)3式中：𝑑为平均延误；𝑐为周期时长；𝑔为有效绿灯时间；𝑥为饱和度；𝑞为到达率；S为路段饱和率。Miller模型：𝑑=𝑐(1−𝑔𝑐)22(1−𝑞S)[𝑐1−𝑔𝑐+2𝑄0𝑞](2)式中：𝑄0为平均过饱和车辆数。𝑄0=exp⁡[−1.33𝑆𝑔(1−𝑥)𝑥]2(1−𝑥)(3)式中：𝑆𝑔路段的绿灯饱和率。Akcelik模型：𝑑=𝑐(1−𝑔𝑐)22(1−𝑞S)+𝑄0𝑞(4)其中：𝑄0=1.5(𝑥−𝑥0)1−𝑥(𝑥𝑥0)0(𝑥𝑥0)(5)𝑥=0.67+𝑆𝑔600(6)将公式(1)、(2)、(4)进行对比，其结果相差甚微，最多相差1s[2]。2）定数延误模型。定数延误模型必须满足以下3点：（1）在时间段𝑇内，车辆到达率𝑞和通过能力𝑄为一定值，且𝑞大于𝑄；（2）在时间段𝑇的开始点，初始排队长度为零；（3）过饱和排队长度是关于时间t的一个线性函数，当超过时刻𝑇，过饱和排队长度就停止增加。平均延误可用以下公式表示：𝑑=𝐷𝑞𝑡=𝐶𝑟2𝑞+𝑄0𝑞(7)其中：𝑄0=(𝑞−𝐶)𝑡2=(𝑥−1)𝐶𝑡2(8)式中：𝐶为该进口方向通行能力。3）过度函数延误模型。过度函数延误模型包括3个部分：均衡相位延误、随机延误、过饱和延误。𝑑=𝑐(1−𝑔/𝑐)22(1−𝑞/𝑠)+𝑄0𝐶(𝑥1)(𝑐−𝑔)2+𝑄0𝐶(𝑥≥1)(9)其中：𝑄0=𝐶𝑡4[𝑥−1+𝑥−12+4𝑥𝐶𝑡](10)41.1.2路段交通饱和度传统路段交通饱和的概念是：在某一时段内，路段上车辆的实际到达流量，即交通量𝑞和路段通行能力𝐶的比值，即𝑥=𝑞𝐶1(11)实际道路交通中，由于交通路网中瓶颈处的通行能力以及其他路口都会对该路段产生影响，甚至不同时段也对该路段存在影响，所以现行通行能力𝐶1定义为𝐶1=𝑆𝜆1𝑡1+𝑆𝜆2𝑡2+⋯𝑆𝜆𝑛𝑡𝑛，𝑡1+𝑡2+𝑡3…𝑡𝑛=𝑡，其中：𝑆为路段饱和流率；𝜆𝑛为实时绿信比；𝑡𝑛为交叉路口使用的绿信比𝜆𝑛的时间；𝑡为分析周期。1.2宏观方面交通参数模型在宏观上需要解决如路口拥挤程度分级、路段拥挤程度分级方法、拥挤持续时间估计方法、有无交通事件判别算法等方面的问题。限于篇幅，本文只介绍路段拥挤程度分级方法。1.2.1路段拥挤分析方法1）模糊聚类法。聚类分析法是将多种事物之间的性质直接进行比较，将相近、相似事物性质的归为一类，将性质差别较大的事物归为不同类别。聚类分析时，采样样本种类尽量多包含不同的交通状态，样本量要足够大，应采用若干天连续24h的数据进行分析，其中需包括国家节假日（节假日的时长包括3d和7d）、周末、寒暑假等。按聚类方法分级以后，应将实时交通信息变量输入该类方法，将其归为聚类方法中的一个等级。在杨兆升等人[2]的书中提供了2种方案，一种是采用流量（与路段宽度、车道数有关）、占有率、速度等路段拥挤指标参数，通过采集大量数据，形成3×𝑛维的交通状态信息向量，然后经过聚类拥挤程度分为3类，见表1；另外一种是采用流量（与路段宽度、车道数有关）、占有率、速度，广义路段上车辆数（与路段宽度、车道数、路段长度有关）、广义路段饱和度等参数，形成5×𝑛维的交通状态信息向量。表1路段拥挤指标状态向量模糊聚类顺畅阻滞拥堵流量/h34.005.0020.00占有率/%97.03367.3073.5速度/(km·h-1)20.4044.330.1052）改进的McMaster算法[2]（基于模糊聚类）。改进的McMaster算法判断拥挤的依据是道路路段在拥堵时车流速度降低、道路占有率以及存在拥挤车流。改进的McMaster算法判断拥挤的依据是道路路段在拥堵时车流速度降低、道路占有率以及存在拥挤车流。该算法运用要满足以下条件：道路交通拥挤与非拥挤之间快速转变，而流量和占有率却缓慢变化。按照改进的McMaster算法建立流量-占有率模型。3）基于人工神经网络(ANN[2])的单截面算法。ANN算法是快速发展的人工智能技术，其可以模拟人脑信息的记忆和处理功能，擅长从海量数据中提取有用信息。ANN算法流程见图1。图1ANN算法流程2路径寻优算法“最短路径”是数学重要分支图论中的经典问题，Dijkstra算法[3]和Floyd算法[4]为最短路径的求解提供了基础，同时也为动态路径诱导算法奠定了基础。在实际交通路网中求解节点间的最短路径，首先需将交通路网抽象为一个图论中定义的有向图或无向图，并利用图的节点邻接矩阵记录点间的关联信息，然后通过遍历图中的节点并且获取最短路径矩阵，从而获得最佳优化路径。2.1算法分析动态路径诱导系统中，交通网络中支路和节点的权重值是实时不断变化的，此时算法求解会异常复杂，如果满足先进先出条件，则可使用Dijkstra算法解决动态最短路径问题；当不符合先进先输入变量设计输入交通参数数据预处理输入变量值计算输入隐层结点数量确定权值如：误差精度Ɛ和训练次数峰值n训练网络训练误差Ɛ或者训练次数n拥挤识别ANN输出TAANN输出TB阻滞拥堵是是否是否顺畅否6出条件时，则采用时间离散化处理来求解任意点到终点的最短路径。常见KSP算法[4]和A*算法[4]也为动态路径诱导系统提供了算法基础。最短路径问题(KSP)是在有向图中找出起点到终点之间花费代价最小的K条路径组，KSP是最短路径问题一种变形，解决该类问题的算法是KSP算法。该算法定义一个有向图𝐺=𝑉,𝐴，𝑉为图中有限节点构成的集合，𝑉=𝑣1…𝑣𝑖..𝑣𝑛；𝐴为有向图中所有节点对的距离所构成的集合；𝑐表示为A上的非负函数对于一切𝑎∈𝐴，记𝑐𝑎=𝑐𝑖𝑗，称图𝐺=(𝑉,𝐴,𝑐)为容量网络[4]。假定从有向图𝐺中𝑠节点到𝑡节点的路径利用𝑝序列表示，即𝑝=(𝜈1=𝑠,𝜈2…𝜈𝑘=𝑡)，则由𝑠到𝑡的距离𝑐(𝑝)为：𝑐𝑝=𝑐𝑖𝑗𝑖,𝑗𝜖𝑝(12)式中：𝑐𝑖𝑗是(𝑖,𝑗)之间的距离。KSP算法根据路径限制条件分为限定无环KSP算法和一般KSP算法。A*算法是一种静态路网中求解最短路径最有效的算法。该算法从初始点到任意节点n的估价函数可表示为：𝑓𝑛=𝑔𝑛+𝑕(𝑛)(13)式中：𝑓𝑛为有向图中起始节点到节点n之间的估价函数；()gn为状态空间中起点到任意节点𝑛的实际距离；𝑕(𝑛)为有向图中节点𝑛到目标顶点估算距离。当𝑕𝑛=0时，只需求出𝑔𝑛，即求出起点到任意节点𝑛之间的最短路径，其可以转化为单源最