（运筹学与控制论专业论文）智能交通中动态多路径选择的几类智能算法的研究.pdf

摘要动态路径诱导系统( d r g s ) 是智能交通系统0 t s ) 研究的一个重要内容，动态路径诱导算法( d r g a ) 通过向驾驶员提供基于实时交通信息的最佳行驶路径来诱导出行行为，从而达到减少车辆在道路上的逗留时间、避免交通拥塞的目的。本文首先建立了一个包含实时路网信息，对时间进行离散化处理的动态多路径的基本模型，通过优化信号灯配时进一步得到动态多路径的双层优化模型。然后提出了求解该模型的两种智能算法，获得动态路径诱导系统中的“多准最优路径 ：一是结合基本遗传算法和经典f o r d 算法的优点，通过改进遗传算子，提出了求解动态多路径双层优化模型的混合演化算法；二是为了弥补混合演化算法在实时路网信息更新方面存在的不足，进一步通过优化基本蚁群算法的状态转移策略和信息素更新原则，增加路权实时更新信息，借鉴交叉、变异算子的优点，提出了求解动态多路径双层优化模型的改进蚁群算法；最后，通过数值算例表明了混合演化算法和改进蚁群算法的可行性和有效性。关键词：动态路径混合演化算法改进蚁群算法多准最优路径a b s t r a c td y n a m i cr o u t eg u i d a n c es y s t e m ( d r g s ) i si m p o r t a n ti nt h ef i e l do fi n t e l l i g e n tt r a f f i cs y s t e m ( i t s ) t h et r a v e l e r sf i n do p t i m a lr o u t eb a s e do nr e a l - t i m et r a f f i ci n f o r m a t i o nb yu s i n gd y n a m i cr o u t eg u i d a n c ea l g o r i t h m ( d r g a ) t h et r a v e lt i m ei ss h o r t e s ta n dt h et r a f f i cc o n g e s t i o ni sa v o i d e d0 1 1t h e s eo p t i m a lr o u t e s i nt h i sp a p e r , f l r s t l y ，t h er o a dn e t w o r km o d e li so b t a i n e d 、 ，i t l lt h er e a l - t i m en e t w o r ki n f o r m a t i o na n dd i s c r e t et i m e b a s e do nt h ei m p r o v e m e n to fs i g n a ll a m ps e t t i n g ，ab i - l e v e lo p t i m i z a t i o nm o d e li se s t a b l i s h e d t h e n , t w oi n t e l l i g e n ta l g o r i t h m sa r ep r o p o s e dt of i n dt h em u l t i - s t r i pq u a s i - o p t i m a lm u t e s o n ei st h eh y b r i de v o l u t i o n a r ya l g o r i t h m , w h i c hc o m b i n e sw i t l lf o r dm e t h o da n di m p r o v e sg e n e t i co p e r a t o r s t om a k eu pt h el a k eo ft h er o a dn e t w o r kw e i g h tu p d a t i n gi nh y b r i de v o l u t i o n a r ya l g o r i t h m ，t h eo t h e ri st h ei m p r o v e da n tc o l o n ys y s t e ma l g o r i t h m , w h i c hi m p r o v e st h eu p d a t i n gs t r a t e g i e so fi n f o r m a t i o nt r a c ka n dt h es t a t et r a n s i t i o nr u l e sa n da d d st h er e a l - t i m ei n f o r m a t i o n so fr o a dn e t w o r kw e i g h t t h en u m e r i c a le x a m p l e si l l u s t r a t et h ef e a s i b i l i t ya n de f f e c t i v e n e s so ft h eo b t a i n e da l g o r i t h m s k e y w o r d s ：d y n a m i cr o u t eh y b r i de v o l u t i o n a r ya l g o r i t h mi m p r o v e da n tc o l o n ys y s t e ma l g o r i t h mm u l t i - s t r i pq u a s i - o p t i m a lr o u t e s西安电子科技大学学位论文创新性声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。本人签名：独型芝西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。( 保密的论文在解密后遵守此规定)本学位论文属于保密，在一年解密后适用本授权书。本人签名：毯盘导师签名：日期2 1 里：! ：12第一章绪论第一章绪论1 1 问题的提出背景随着我国社会经济的发展和大中城市路网的逐渐成熟，人们对交通运输的各种需求明显增长1 1 j 。近三十年来，我国对交通运输建设投入了大量的人力、物力、财力，铁路、公路、水路、航运和管道运输所构成的现代化综合运输体系已经基本建成。交通运输业的高速发展一方面促进了物资交流和人们的往来，大大缩短了司机的出行时间，提高了工作效率，另一方面也带来了许多弊病【2 】：据2 0 0 8 年4月1 7 日中国江苏网的消息，截至2 0 0 8 年3 月，全国机动车保有量为1 6 2 7 3 5 2 3 2 辆，其中汽车5 9 0 4 4 6 2 6 辆、摩托车8 7 7 5 4 8 5 3 辆、挂车9 0 3 1 8 4 辆、上道路行驶的拖拉机1 5 0 1 2 0 8 4 辆、其他机动车2 0 4 8 5 辆；全国机动车驾驶人为1 6 7 1 6 5 4 2 9 人，其中汽车驾驶人高达1 1 0 3 8 0 3 8 8 人，大量的车辆涌入街头，公路负荷迅速增加，交通日益恶化，导致道路阻塞和交通事故频繁发生。由于交通需求的增长速度远远大于基础设施的建设速度等原因，城市交通的供需矛盾日益突出，各级交通环境的改善己迫在眉睫。改善城市交通系统的途径主要有两个1 3 j ：( 1 ) 加快公路交通基础设旌的建设；( 2 )加强普通公路交通管理系统的建设。针对我国城市人多、车多、路少的现实交通情况，解决车辆快增长与道路慢增长矛盾的最为有效的措施是科学合理地使用道路，因此采用集高科技于一体的智能交通系统 4 1 是必然选择。所以我国更有必要快速发展智能交通系统，利用现有的道路设施，运用先进的科技手段提高道路的运营效率。随着现代电子科技日新月异的发展，尤其是通信、导航、遥感、实时控制、计算机和数据库等技术日趋成熟并广泛应用，出现了一个跨学科的新兴领域：智能交通系统i t s ( i n t e l l i g e n tt r a f | i cs y s t e m s ) ，它为解决交通问题带来了新的思路，并且受到越来越人们的关注【5 】。智能交通系统1 4 1 ( i t s ) 是国际上2 0 世纪9 0 年代初提出的一种全新的交通模式，它是在关键基础理论模型研究的前提下，把先进的信息技术、数据通信传输技术、电子控制技术及计算机处理技术等有效地综合运用于整个交通管理体系，将人、车、路有机结合起来，以达到最佳的和谐统一，从而建立起一种大范围、全方位发挥作用的实时、准确、高效的交通运输管理系统【3 】【4 j 。由于该系统可以使汽车与道路的功能智能化，是目前国际公认的解决城市以及高速公路交通拥挤、改善行车安全、提高行车效率、减少空气污染等的最佳途径，2智能交通中动态多路径选择的几类智能算法的研究也是全世界交通运输领域研究的前沿问题。i t s 指出了未来世纪的交通发展方向，是新时代下科技和社会发展、信息革命推动下的产物。它的全面研究涉及到交通工程学、智能控制科学、计算机科学、计算机视觉和图像处理、模式识别、通信科学、汽车技术等学科。目前国际上的i t s 研究形成了美国、日本和欧洲的三大阵营，它们的研究体系稍有不同，但大体一致。其中，美国的i t s 研究开发体系最为完善，已受到国际i t s 研究领域的广泛认可。我国的i t s 研究刚刚起步，限于经济实力、科研水平、基础设施等原因，现阶段我国智能交通系统的研究尚处于初始阶段。幸运的是国家政府部门和交通运输界已经认识到开展智能交通系统研究的重要性并制定了一系列规划方案。交通部在“九五 期间已经建立了“智能公路运输系统工程研究中心一，分阶段地开展交通控制系统、驾驶员信息系统、车辆调度系统和导航系统、车辆安全系统以及收费系统5 个领域的研究和开发、工程化和系统集成 6 1 。1 2 国内外研究现状1 2 1 动态路径诱导系统d r g s路径诱导系统( r o u t eg u i d a n c es y s t e m ) 是i t s 的一个研究领域，是先进的出行者系统( a t i s ) 的一个核心部分，也是i t s f l 邑够实施的关键技术。路径诱导系统由车载单元和交通控制中心这两大系统和与之相互通信的无线通信网络构成，研究对象是由路网、车流和具有能动行为的出行者组成的复杂系统。它是应用车辆自主定位技术、地理信息系统与数据库技术、计算机技术、多媒体技术和现代通信技术，实时为驾驶员指明最优路线，并引导驾驶员行驶，合理分配整个交通网络上的交通流，从而快速有效地输送驾驶员到达目的地，最终减少整个系统总的交通时耗的高科技综合系统【3 j 。动态路径诱导系统( d y n a m i cr o u t eg u i d a n c es y s t e m s ，简称d r g s ) 是利用计算机和通信等技术，通过向驾驶员提供基于实时交通信息的最佳行驶路线来达到诱导出行行为1 7 1 ，减少车辆在路上的逗留时间，进而实现改善交通和避免交通拥挤阻塞的目的。同时它还能避免因盲目行驶或凭经验行驶造成的交通阻塞达到了使路网畅通、高效运行的目的【3 】【4 j ，并且最终实现交通流在路网中各个路段上的合理分配。而且由于驾驶顺利也稳定了驾驶员的心理，在一定程度上降低事故发生率，提高交通安全。动态路径诱导系统的关键技术【8 】【9 】包括：导航用电子地图第一章绪论导航用电子地图是路径诱导系统中各种功能的基础。导航前的路线规划、路径引导、以及地图匹配功能都依赖于导航电子地图对应的道路网数据库。由于现实世界的变化，导航软件所使用的地图数据总是和现实世界存在差异，通过数据的动态更新就可以保持地图数据的现时性。在动态路径规划的过程中，交通信息处于不断的变化之中，通过导航软件所提供的相应接口，系统可以动态的更新地图数据库中的数据。这要求技术上从数据结构就开始支持数据的动态更新，把数据的动态更新作为数据库设计的基本功能来实现。实时交通信息实时交通信息主要指发生在道路网络上的交通事件、交通实时状态、交通设施及状态等信息。扎实时交通信息的采集，处理和发布。b 道路交通状况的预测。由于交通信息是时刻无规律变化的，所以只有实时的交通信息有时并不能满足出行者的信息需求，迫切需要一个可以根据历史数据结合当前交通状况实时预测道路将来某段时间内的交通状况的系统。路径规划算法在交通网络中，最优路径选择就其本质而言，就是选择合适的路阻函数，将路网合理地优化，再选择合适的算法计算出满足一定条件的最优路径。所以路径规划算法涉及2 个方面的问题：丸道路权重的标定在动态路径规划中，用从外界接收的实时交通信息，主要指路段行程时间( 或平均行驶速度) 、交通事件和交通预测信息等来标定每条路段的动态权值，根据起讫点找出一条最省时的路线是其最终目标。然而，由于目前实时交通信息的局部覆盖，信息内容的单一，不完整，伪动态和交通网络流量预测模型的不合理，无法实现真正的动态路径规划。目前的解决方案是给路段要素增加一个加权系数属性，并将路段长度与加权系数的乘积作为路段的加权长度。b 最优路算法。最优路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。它们在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色。在动态最优路径问题中，弧段权值、节点耗费等均为时间的函数，既可以是连续的，也可以是离散的。本文主要研究动态路径诱导系统的最优路径选择的智能算法。1 2 2 动态路径诱导算法i ) r g a动态路径诱导算法( d y n a m i cr o u t eg u i d a n c ea l g o r i t h m ，简称d r g a ) i 拘研究是d r g s 的核心部分，般应具有通过考虑交通网络的变化来提供最小出行时间路径4智能交通中动态多路径选择的几类智能算法的研究的功能。限于技术条件考虑，动态路径诱导系统中我们所能做的就是动态路径诱导算法的研究，本文的核心内容也是动态路径诱导算法，因此下面对它的研究进展作了详细的介绍。由于动态路径网络中的各路径权值均在动态变化，此时理论上的动态路径诱导算法变得异常复杂【l o l 。如果先进先出( f i f o ) 条件满足，可以推广d i j k s t r a 算法来解决动态最短路径问题【l l 】。在不满足f i f o 条件时，c h a b i n i 1 2 】提出将时间离散化处理来求解任意点到某终止点的最短路径；f u 等人1 1 3 】将路段行驶时间看成连续随机过程，估计在某一时刻特定路径的出行期望时间；l a m 等人【1 4 1 提出一种结合历史数据和当前交通状况的诱导方式，在当前交通流与历史数据没有明显变化时，可按预先计算的离线结果进行诱导，只有在发现当前状况跟历史数据有很大变化时才进行调整；s u n g 等a t l 5 j 提出一种采用g p s 实时数据的路径诱导方法，它基于历史数据和实测数据，采用时间序列的自回归积分滑动平均模型( a u t o r e g r e s s i v ei n t e g r a t e dm o v i n ga v e r a g e ，a r i m a ) 来预测各路段下一时段的通行时间，并采用修正的f l o y d w a u s h a l l 算法来计算最短路径；g a e t a r f i 等人【1 6 1 将交叉口各时间段的绿信比当成控制变量来控制通过从该交叉口出发的路段的诱导车辆比例，从而达到优化每一辆进入交叉口的车辆的总行驶时间的目的，通过对单个交叉口的最优控制来解决全局路网的优化；k o b a y a s h i 等) l t l 7 j 根据下游交叉1 2 1 是否发生拥挤以及是否采用信号灯控制和信号灯的控制参数来估计各路段的平均行使时间，然后采用d i j k s t r a - 算法计算最小的平均行使时间路径；苏永云等人【ls 】研究了路径权值在优化过程中跨时段动态变化的问题，给出了改进的矩阵算法和改进的a 算法来求解k路最短问题；f u 1 9 】将交通网络的最短通行时间归结为一种闭环自适应最短路问题( c a s p r p ) ，将路段的通行时间看成时变的随机变量，并且可以在车辆进人该路段时做出准确的预测，其优化的目标函数定义为下一个可供选择的路段，而不是全部路径。这种方法可以让车辆能及时地接受实时信息，并做出适当的行驶路径变化，因此诱导效率高于在出行开始时就决定全部行驶路径的开环自适应诱导。当考虑路径权值动态变化时，路径诱导算法的实时性问题将变得更加困难；z i l i a s k o p o u l o s l 2 0 】在将路段通行时间看成时变函数时提出一种求平均最短路径的顺序算法，并在此基础上提出一种对算法复杂度改进的大规模并行算法。由于城市交通网络中交通流的高度复杂性和难以预测性，基于精密交通流数学模型的路径诱导算法的实施十分困难，有些研究者开始注意一些对模型要求较低的智能解决方法p o l 。杨兆升等人1 8 1 1 2 l 】提出一种将交通流比拟成自然流体的神经网络诱导模式，并用遗传算法来优化流体神经网络的参数。这种诱导模式基于以下假设：从出行点出发，径流量最大的通道到达目的点的路径就是对应于交通网络的最短路径。计算表明，这种方法较传统k 路最短算法优越，并且成功率较高。贺国光等人l 2 2 j 提出一第一章绪论种具有评测和自学习能力的诱导模式。由于该系统采用知识库模型来代替数学模型描述交通状况与诱导策略之间的复杂关系，使诱导系统不断地学习改进自己的诱导策略，从而能更好地描述它们的不确定性关系。还有人提出蚁群算法、遗传算法等，其中将遗传算法应用于动态路径诱导较为成功，但由于其采用序号编码方式，在遗传操作时会产生大量无效路径，导致算法收敛速度慢，搜索效率低下。本文的主要内容是研究动态路径诱导智能算法。1 3 本文的主要研究内容传统上，动态路径诱导系统( d r g s ) 向司机提供的“最优 路径是一条唯一的路径，一般均是以行驶距离最短或行驶时间最短为目标的。然而，实际的交通网络是动态和随机的，所以用传统的最短路径算法求出的路径并没有考虑到这一特点。鉴于此，国内外有学者对这个问题进行了大量的研究，指出由系统推荐若干条路径给司机，而由司机最后决定选择哪一条是一个相对实际和较好的策略。本文首先建立一个包含实时路网信息，且可以针对时间分段进行离散化处理的动态多路径的基本模型，并通过改进信号灯配时对模型中的相关参数进行了优化处理，构建了动态多路径双层优化模型。然后分别提出混合演化算法和改进的蚁群算法来求解该模型，获得向司机推荐的一组“多准最优路径”。这组“多准最优路径 具有在行驶时间方面相差不大，而在行驶路径方面又具有自己独特的属性。由于司机根据自身的出行习惯选择路径的主观性，也在一定程度上避免了都走同一路径而可能导致的路段堵塞，使得司机在预计的时间内到达目的地。在交通运输领域中，i t s 是一场革命，动态路径诱导算法的研究，将成为i t s产业的重要组成部分，其应用前景十分广阔。理论上，该问题的研究可以促进组合优化与智能算法的发展，同时对科学交叉有着积极的推动作用。该研究具有重要的理论意义与应用价值。本文分四个章节，每个章节主要内容安排如下：第一章概述了动态多路径选择算法的提出背景，分别对动态路径诱导系统( d r g s ) 、动态路径诱导算法( d r g a ) 及国内外研究现状做了简要的阐述。第二章建立一个包含实时路网信息，且可以针对时间进行离散化处理的动态多路径的基本模型，然后通过优化信号灯配时方案进一步得到了双层优化模型。最后以西安市某交叉口为例来说明信号灯配时优化的合理性。第三章提出了混合演化算法。针对第二章提出的动态多路径基本模型和双层优化模型，结合求解路径选择问题的基本遗传算法和经典f o r d 算法的优点，通过6智能交通中动态多路径选择的几类智能算法的研究设计遗传算子，提出了混合演化算法。最后通过数值算例来验证了该算法的有效性。第四章提出了改进的蚁群算法。通过对基本蚁群算法的状态转移策略和信息素更新原则进行改进，引入路权实时更新转换机制，借鉴交叉、变异算子的优点，提出了求解动态多路径基本模型和双层优化模型的改进蚁群算法。最后，给出了相应的数值算例，并通过与混合演化算法的简要比较说明该算法的可行性和高效性。第二章路径诱导系统的动态多路径模型7第二章路径诱导系统的动态多路径模型2 1 动态多路径的基本模型动态路径诱导系统( d r g s ) 是基于电子、计算机、网络和通信等现代技术，利用全球定位系统( g l o b a lp o s i t i o n i n gs y s t e m 简称g p s ) 、电子交通图( e l e c t r o n i cm a po ft r a f f i cn e t w o r k ) 、计算机和先进的通信技术，通过获得的实时交通信息帮助驾驶员找到一条从出发点到目的地的最佳路径，以减少车辆在道路上的滞留时间，这样就可以缓解城市交通的压力，减少城市交通阻塞，并且最终实现交通流在路网中各个路段上的合理分配 3 1 1 4 1 1 7 1 1 2 1 1 。其特点是把人、车、路综合起来考虑。动态的路径诱导模型是实现动态路径诱导系统的核心部分。由于路段上交通状态是动态变化的，路段行程时间也是动态变化的，但是受交通参数检测技术和预测分析技术的限制，难以得到准确的、可用的行程时间随时间变化的关系式，所以如何设计一个可靠、正确的确定权值的方法及路径诱导模型是相当困难的。李威武【l o 】等人指出：由于路径诱导是一个对实时性要求相当强的系统，过分追求模型的精确和复杂并没有多大帮助。我们首先对时间进行离散化处理，划分为空闲时段和繁忙时段，然后将路网系统对应地划分为空闲状态( ，) 和繁忙状态( 刀) 两种情况【2 3 j 。假设在相同路网状态下路段权值是基本固定的，不同路网状态下的路段权值不相同。因此，得到如下的动态路径的基本模型：m m( 2 - 1 )豇勺= ：) ，跋嬲p 2 ，删= 船篙燃p 3 ，其中：s ，d 分别为出行的起点和终点；r ( s ，d ) 为出行的起点s 到终点d 的路径集合；f g 表示司机从起点s 到终点d 所花的时间：( f ) 表示t 时刻司机从交叉口i行驶到交叉口歹的广义时间费用，可以表示为：乞。部d!：2=名智能交通中动态多路径选择的几类智能算法的研究( f ) = t ( i ，歹) + d ( f ，j ) ( 2 - 4 )t ( i , j ) 表示车辆在路段g ) 上的行驶时间，可由路阻函数求得；d ( i ，) 表示在交叉口f 与交叉口j 相邻进口道上的车辆等待延误，可根据修正的韦伯斯特( w e b s t e r )公式求得。满足模型( 2 - l _ 弋2 - 4 ) 的解，即为从起点s 到终点d 的一组“多准最优路径 。2 1 1 车辆行驶时间的确定车辆行驶时间，( f ，j ) 的表达式如下( 2 - 5 ) -删) 2 而( 2 - 5 )式中，u ( i ，j ) 表示路段( f ，j ) 车辆行驶速度，单位：千米小时。用公式( 2 6 ) 来计算：喇) - 1 帆u o ( 1 - o 4 9 删4 v _ f q ，n 疑嚣三p 6 ，其中，u o 表示交通量为零时的车辆行驶速度，单位：千米，j 、时。用公式( 2 7 )来计算【4 1 ：= ，岛j 。( 2 - 7 )岛、岛、q 和屹分别表示交叉口f 与交叉口j 之间的距离、交叉口影响系数、路段的最高限制车速，( 单位：千米小时) 以及路段上的当前车辆行驶速度，( 单位：千米小时) ；，表示自行车影响折减系数；j l l 表示车道宽影响系数；k 表示路段设计车速：1 ) 自行车影响折减系数，的确定：交通路网上自行车已经不是主要交通工具了，因此对机动车道机动车的影响，可以视有无隔离带( 桩) 而分两种情况考虑：( 1 ) 机动车道与非机动车道之间有隔离带( 桩) 。当机动车道与非机动车道之间设有隔离带时，路段上的自行车对机动车几乎没有影响，可不考虑折减，此时取，- = 1 。( 2 ) 机动车道与非机动车道之间无隔离带( 桩) 。当交通量比较小时，自行车对机动车的影响亦可不予考虑；但如果交通量比较大时，自行车可能将侵占部分机动车道而影响机动车的正常运行，使机动车的车速、通行能力降低，此时影响系数取，= 0 8 。第二章路径诱导系统的动态多路径模型92 ) 车道宽影响系数j l l 的确定：车道宽度对行车速度有很大的影响，在城市道路设计中，取标准车道宽度为3 5 米。当车道宽度大于该值时，有利于车辆行驶，车速略有提高；当车道宽度小于该值时，车辆行驶的自由度受到影响，车速降低。车道宽与车速之间呈下陡上缓的曲线关系，其车道宽度影响系数p 可由下式确定：p = 5 。一1 5 ) x l o - 2 ( - 5 4 + 1 8 8 w o 3 - 1 6 9 r o ：3 ) x l o - 2 , 笼三三 c 2 8 ，“一、i 二。o -。i2 3 5、7式中，瞩为一条机动车道宽度，米。当车道宽为标准宽度3 5 h i 时，t = 1 0 0 。车道宽度与影响系数之间的变化关系如下表2 1 所示：，米2 533 544 555 561 0 - 25 07 51 0 0l l l1 2 01 2 61 2 91 3 03 ) 路段设计车速k 的确定：路段设计车速与道路等级有关。根据城市道路交通规划设计规范的建议值【l 】，路段设计车速与道路等级、车道数的关系如下表2 2 所示：表2 2 路段设计车速与道路等级关系表单位：i o n h道路等级快速干道主干道次干道支路设计车速6 0 8 04 0 - - - , 6 03 0 - - - - 4 02 0 3 04 ) 交叉口影响系数瓯的确定：交叉口影响系数，主要取决于交叉口控制方式及交叉口间距。根据前苏联的研究，交叉e l 间距从2 0 0 米增大至u s o o 米时，其车速及通行能力可提高8 0 9 6 左右，并基本上呈线性关系。因此，交叉1 3 影响系数可采用下式计算：岛档盎嗍3 “们3 ，乏裟p 9 ，式中，厶、a ( f ，) 分别表示交叉口i 与交叉口j 2 间的距离，( 单位：米) 和进口道信号灯绿信比。如果由上式计算的瓯 1 ，则取最= 1 。1 0智能交通中动态多路径选择的几类智能算法的研究2 1 2 车辆等待延误分析交叉口处车辆等待延误d ( f ，j f ) 可以表示为：当进口饱和度较小时，各进口道上车辆等待延误可根据修正的韦伯斯特( w 曲s t e r ) 公式计算【9 1 1 2 3 2 7 】：d c ，= d c 丁c 厶，a c l ，= 。9 三篇+ 瓣x 9 2 c 2 - - 。，式中，d ( i ，_ ) 、t ( i ，j f ) 、z ( i ，歹) 、q ：l c ：f 和分别表示在交叉口i 与交叉口j 相邻迸1 3 道上的车辆等待延误、信号灯周期长度( 单位：秒) 、信号灯的绿信比、交通流量( 单位：辆d , 时) 、路段的最高限制车速，( 单位：千米小时) 以及车辆饱和度，= q ( z ( i ，j f ) q ) 。当进口饱和度较大时，韦伯斯特公式的计算结果偏大，美国道路通行能力手册建议用下式计算进口道延误【9 】【2 3 之7 】：d ( f ，_ ，) = 4 ( i ，歹) + 畋( f ，)( 2 - 1 1 )其中：4 0 , 舻鼍鬻筹( 2 - 1 2 )为均匀延误5d 2 ( i ，_ ，) = 1 7 3 x ，2 【( 一1 ) + ( 一1 ) 2 + 1 6 x 毛】( 2 - 1 3 )为过饱和延误，即：随机到达的增量延误以及由于周期失效引起的附加延误。式中：丁( f ，) ，a ( f ，) ，& 的确定均同前。一般认为，韦伯斯特公式的适用范围为饱和度置，= 0 0 6 6 ；美国道路通行能力手册建议公式的适用范围为饱和度置，= 0 1 2 0 。2 2 动态多路径双层优化模型的建立2 2 1 信号灯配时双层优化模型动态多路径选择的基本模型中，司机在某路段的广义时间费用由行驶时间和交叉口车辆等待延误决定。行驶时间由一些不可变因素决定，如道路情况、车型等，因而要改变行驶时间不切合实际，因此想要减少各路段上的广义费用只有从减少交叉口车辆等待延误出发。传统的交叉口处信号控制一般采用定时控制方案，第二章路径诱导系统的动态多路径模型这种方案最主要的缺点在于，当车流量变化较大时，时常会因为放行不合理导致交通阻塞1 2 6 。为此根据实时交通信息控制交通灯周期和绿信比是很有意义的。通过调整控制，可以提高交叉口的通行能力，缓解车辆通过交叉口的受阻滞程度。d ( i ，)是交叉口车辆等待延误，只要存在一个合适的信号周期和绿信比就能保证车辆顺利通行，但是所得到的交叉口延误并不一定是最小的延误。同时信号周期和绿信比是控制交叉口延误时间的重要参数。适当的周期长度和绿信比对疏散交叉口的交通流，减少车辆等待延误时间有非常重要的意义。因此，本节研究配置一个比较适合其交通流量的信号周期t ( i ，) 及绿信比z ( i ，) ，使得车辆在交叉口的延误最小。本节考虑在模型( 2 1 ) ( 2 _ 4 ) 中增加约束条件( 2 1 4 ) ，即设置交叉口的信号周期t ( i ，j f ) 及绿信比z ( i ，) ，使延误d ( i ，_ ，) 最小。m i l ld ( i ，j f ) = d ( t ( i ，) ，a ( f ，歹) )( 2 1 4 )这单，媳力=懒弩一】o 蒜 q 6q 智+ 1 谣喙5 ，o 幅 。s t e p 2 对应于么中的每一个元素，给出绿信比a ( f ，歹) 的集合：b = 九一乇，九一0 0 2 ，乃一0 0 1 ，九，九+ o 0 1 ，九+ o 0 2 ，凡+ ) 。1 2智能交通中动态多路径选择的几类智能算法的研究s t e p 3 将t ( i ，) 和九( f ，) 的所有组合得到的数据依次代入( 2 - 1 4 ) 式，得到一组d ( r ( i ，) ，z ( i ，_ ，) ) 值。s t e p 4 通过比较可以得到一个最小值d ( r ( i ，) ，a ( f ，埘和所对应的t ( i ，j f ) 和z ( i ，) 值，从而给出了使车辆等待延误最小的信号灯优化设置。，m ，乇，m o 取数值实验的经验值。为了验证信号灯配时优化的可行性，我们以西安市某交叉路口为例，将采集到的分时段( 空闲时段和繁忙时段) 交通流量、信号灯设置数据( 单位：秒) 代入( 2 1 0 ) 、( 2 1 1 ) 、( 2 1 2 ) 和( 2 - 1 3 ) ，得到各个时段的车辆等待实际延误，结果如下表2 3 。表2 3 某交叉路口的信号灯、车流量及车辆等待实际延误素信号灯设置( 秒)工作日周末红绿左转周车流量车辆等待车流量车辆等待交通状态灯灯绿灯期( 辆时)延误( 秒)( 辆时)延误( 秒)空东西向1 2 55 53 51 8 06 3 91 5 9 25 2 19 3 9闲南北向9 09 03 51 8 01 0 7 11 4 2 29 2 49 5 9繁东西向1 2 55 53 51 8 07 5 02 4 2 77 3 22 2 7 6忙南北向9 09 03 51 8 01 3 9 52 2 5 01 3 3 82 2 5 0对表2 3 中的车辆等待延误求平均值，记为车辆等待平均延误a p e d 得到：a v e d = 1 7 6 5 秒。观察发现，左转车辆在1 5 秒内可以全部通过交叉路口，左转绿灯时间可由3 5 秒减少至l j l 5 秒。进一步利用本节的信号灯配时优化算法，给出了使车辆等待延误最小的信号灯优化设置。经过多次数值计算取，= 3 0 ，m = 2 0 ，t o = o 1 5 ，m o = o 1 5 。结果如下表2 4所示：表2 4 某交叉路口的车流量、信号灯优化设置及车辆等待延误最小值= 滚：车流量红绿左转车辆等周期日期、交通状态( 辆时)灯灯绿灯待延误东西向6 3 99 04 51 51 5 09 5 7工空闲南北向1 0 7 16 07 51 51 5 08 6 6作东西向7 5 01 1 04 51 51 7 02 1 6 8日繁忙南北向1 3 9 56 09 51 51 7 01 2 7 0周空闲东西向5 2 17 54 01 51 3 03 7第二章路径诱导系统的动态多路径模型末南北向9 2 45 56 01 51 3 07 2 0东西向7 3 21 1 04 51 51 7 02 0 3 2繁忙南北向1 3 3 86 09 51 51 7 01 1 7 3由表2 4 可知，优化后的信号灯设置方案使得各时段的车辆等待延误都减少了，a v e d = 1 1 5 3 秒，与车辆等待实际平均延误相比减少了3 4 6 7 。大大降低了车辆的等待延误时间，从而提高交通系统的通行能力。2 3 本章小结本章主要是建立了路径诱导系统的动态多路径的基本模型及双层优化模型。通过分析交通网络的特征和已有的信息采集手段，将交通路网的路段长度、车道宽度、设计车速、车辆的最高限速等基本数据与实时的路网信息( 交通流量、交叉口信号灯周期以及绿信比) 结合起来，建立了可以针对时间分段进行离散化处理的动态路径的基本模型。进一步，改进城市信号灯配时系统，通过分析和优化模型中的车辆等待延误参数，给出了动态多路径的双层优化模型。最后，以西安市某交叉路口为例，以数值算例的形式验证了信号灯配时优化的可行性和有效性。第三章动态多路径双层优化模型的混合演化算法1 5第三章动态多路径双层优化模型的混合演化算法3 1 1 遗传算法原理3 1 遗传算法遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 的基本思想是基于d a r w i n 进化论和m e n d e l 的遗传学说的，是一类以达尔文的自然进化论与遗传变异理论为基础的求解复杂全局优化问题的仿生型算法。它借鉴生物界自然选择和自然遗传机制，以概率论为基础在解空间中进行随机化搜索，最终找到问题的最优解。遗传算法的兴起是在8 0 年代末9 0 年代初期，但是它的历史可以追溯n 6 0 年代。遗传算法的特点【2 弼o 】：智能性与本质并行性。遗传算法的智能性包括自组织、自适应和自学习等，应用遗传算法求解问题时，在确定了编码方案、适应值函数及遗传算子后，算法将应用演化过程中获得的信息进行自组织搜索，适者生存的选择策略赋予了遗传算法自适应的能力，同时也赋予了它根据环境的变化自动发现环境的特征和规律的能力；遗传算法的本质并行性表现在两个方面：一是遗传算法的内在并行性，即其本身非常适合大规模并行，二是遗传算法的内含并行性，即它可以同时搜索解空间内的多个区域，并且相互之间进行信息交流，这种搜索方式使得遗传算法可以以较少的计算获得较大的收益。这些特点使得遗传算法广泛应用于控制、规划、设计、组合优化、图像处理、信号处理、机器人、人工生命等多个领域。遗传算法通过进化和遗传机理( 染色体之间的交叉和染色体的变异) ，从给出的原始种群中，通过所谓的遗传算子( g e n e t i co p e r a t o r s ) 作用于群体p ( 0 中，进行遗传操作，从而得到新一代群p ”1 ) ，不断进化产生新的解，最后求出最优解1 2 9 川】。1 染色体编码方法。编码是应用遗传算法时要解决的首要问题，它除了决定了个体的染色体排列形式之外，它还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法，还影响到交叉算子，变异算子等遗传算子的运算方法。染色体编码方式一般有以下几种：二进制编码，浮点编码，符号编码。1 6智能交通中动态多路径选择的几类智能算法的研究2 个体适应度评价。个体适应度评价是个体对环境的适应程度的评价，通常用适应度函数( f i t n e s sf u n c t i o n ) 来实现。遗传算法按某种概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为准确计算这个概率，这里要求所有个体的适应度必须为正或零。并且必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理。评价个体适应度的一般过程是：( 1 ) 对个体编码串进行解码处理后，可得到个体的表现型；( 2 ) 对个体的表现型可计算出对应个体的目标函数值；( 3 ) 根据优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度值。3 遗传算子。( 1 ) 选择算子。选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的是为了避免基因缺失，提高全局收敛性和计算效率。( 2 ) 交叉算子。遗传算法中的交叉运算，是指对两个互相配对的染色体安装某种方式互相交换其部分基因，从而形成两个新的个体。遗传算法中，在交叉运算之前先对群体中的个体进行配对，最常用的配对策略是随机配对。( 3 ) 变异算子。所谓变异运算，指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的辅助方法，但是它是必不可少的一个运算步骤，决定了遗传算法的局部搜索能力。使用变异算子主要有以下两个目的：1 ) 改善遗传算法的局部搜索能力；2 ) 维持群体的多样性，防止出现早熟现象。4 遗传算法的运行参数。遗传算法中需要选择的运行参数主要有种群大小m ，交叉概率( 一般取00 40 9 9 ) ，变异概率已( 一般取0 0 0 0 1 o 1 ) ，终止进化代数脚疗等。3 1 2 双层优化模型的遗传算法下面给出了求解动态多路径模型的基本遗传算法步骤：s t e p l 个体编码。采用符号编码。交通路网上的每个结点用自然数编号，使得路网上的节点与第三章动态多路径双层优化模型的混合演化算法1 7自然数一一对应起来 1 ，2 ，3 ，4 ，5 ，6 ，n - 1 ，n ) ，得到路网的邻接矩阵形，矿中的元素为形，( 1 歹加。s t e p 2 优化d ( i ，j ) ，得到信号灯配时改进后的路网的邻接矩阵形。( 1 ) 给定丁( f ，) 的集合：a = 乃一z ，乃一2 ，乃- 1 ，乃，乃+ 1 ，乃+ 2 ，7 ：+ 脚) 。( 2 ) 对应于彳中的每一个元素，给出绿信比a ( j ，j ) 的集合：b = 九一厶，如一0 0 2 ，九一0 0 1 ，九，九+ o 0 1 ，九+ o 0 2 ，如+ ) 。( 3 ) 将r o ，歹) 和a ( f ，) 的所有组合得到的数据依次代入( 2 - 1 4 ) 式，得到一组d ( t ( i ，) ，z ( i ，歹) ) 值。( 4 ) 通过比较可以得到一个最小值d ( t ( i ，_ ，) ，z ( i ，”和所对应的r ( f ，歹) 和a ( f ，歹)值，从而给出了使车辆等待延误最小的信号灯优化设置。s t e p 3 种群初始化。初始种群中各个个体的基因可用均匀分布的随机数来生成。s t e p 4 适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前群体中各个个体遗传到下一代的机会的多少。为了正确评估这个概率，要求所有个体的适应度必须为非负数。s t e p 5 遗传算子。( 1 ) 选择运算：使用比例选择算子。比例选择因子是利用比例于各个个体适应度的概率决定其子孙的遗留可能性。若设种群数为m ，个体f 的适应度为z ，则个体f 被选取的，概率是只= 百，l ，当个体选择的概率给定后，产生【0 ，1 】之间的均匀随机数来石k = l决定那个个体参加交配。若个体的选择概率大，则能被多次选中，它的遗传基因就会在种群中扩大；若个体的选择概率小，则被淘汰。( 2 ) 交叉运算：交叉运算使用单点交叉算子。只有一个交叉点位置，任意挑选经过选择操作后种群中两个个体作为交叉对象，随机产生一个交叉点位置，两个个体在交叉点位置互换部分基因码，形成两个子个体。( 3 ) 变异运算：使用基本位变异算子或均匀变异算子。为了避免问题过早收敛，对于二进制基因码组成的个体种群，实现基因码的小概率翻转，即0 变l ，1 交0 。1 8智能交通中动态多路径选择的几类智能算法的研究s t e p 6 迭代终止条件。如果迭代次数未到达进化代数m a x g e n ，返i 醣u s t e p 4 。否则算法终止。在上述基本遗传算法步骤中，s t e p l 、s t 印3 到s t e p 6 用来求解动态路径选择的基本模型( 2 1 ) ( 2 4 ) ，s t 印l 到s t 印6 用来求解基于信号灯配时的动态路径选择的双层优化模型( 2 - 1 ) - ( 2 - 1 5 ) 。3 2 混合演化算法在上述基本遗传算法的分析过程中，我们发现：种群的初始化结果是影响遗传算法收敛速度的主要因素。在求解最短路的众多算法中，荷兰计算机科学家e w d i j k s t r a 于1 9 5 9 年提出的d i j k s t r a 算法是目前公认的较为有效地算法之一，该算法适用于所有弧的权均为非负和无回路的最短路算法【3 2 】，它是建立在抽象的网络模型上，把路线抽象为网络中的边，以边的权值来表示道路相关的参数，算法确定了赋权网络中从某点到所有其它结点的具有最小权的路，它可给出从某指定顶点到图中其它所有顶点的最短路。但是，对于一般的不含负回路的网络，d i j k s t r a算法是失效的，下面介绍的f o r d 算法在d i j k s t r a 算法的基础上，克服其不足之处，可以求出不含负回路的网络中的最短路。设网络d = ( v ，a ，w ) 不含负回路，v = m ，吃9e o - 9 v n ，并且对一切的( ，) 仨a ，令： o 墨- - ，f o r d 算法的思想是逐次逼近，每次逼近是求d 中从顶点hl 啊习，石l - ，到其余各顶点的带限制的最短路。该算法的复杂性为o ( n 3 ) ，步骤如下：s t e p l 令，( h ) = 0 ，( v