（计算机应用技术专业论文）基于蚁群算法的动态路径诱导研究.pdf

西南交通大学硕士研究生学位论文第l 页 摘要 动态路径诱导系统( d y n a m i cr o u t eg u i d e n c es y s t e m ，d r g s ) 是智能交通 系统的一个重要内容。它根据出行的起止点向驾驶员提供最优路径指引和其 他丰富的实时交通信息，通过诱导驾驶员的出行行为来改善路面交通系统， 防止交通阻塞的发生，减少车辆在道路上的逗留时间，并且最终实现交通流 在路网中各个路段上的合理分配。最短路径选择是动态诱导系统的核心内容 和主要目标，随着城市路网规模的不断扩大和交通流量的显著增加，原有的 路径诱导算法已经不能满足动态路网实时性的要求。蚁群算法作为一种新兴 的人工智能算法，具有良好的全局优化能力、本质上的并行性、求解时间短、 易于计算机实现等优点，己被应用于高度复杂的组合优化、通信网络的路由 选择、车辆调度等问题，取得了良好的效果。 本文围绕最短路径选择问题，对在动态路网中求解最短路径的几个关键 问题如：动态路网的模型，路网边的权值行程时间的计算，算法的选择 等进行了扼要的介绍，选择了性能更好的蚁群算法所为最短路径选择算法。 本文重点分析了蚁群算法的原理，模型，以及参数的设置，并针对其存在的 缺点给出了一种改进算法一一基于信息素扩散的双种群蚁群算法 ( p d d p a s ) 。本文选取了三个不同规模的t s p 问题对p d d p a s 算法进行实 验，分别对p d d p a s 算法性能，参数的设置，信息素扩散的策略进行考察， 并得出了相应的设置方案。结果表明，改进的p d d p a s 算法具有寻优能力强， 收敛速度快，参数设置稳定的优点。最后，本文将p d d p a s 算法在路网地图 上进行了简单的实现。 关键词动态路径诱导；行程时间；蚁群算法；p d d p a s 西南交通大学硕士研究生学位论文第l i 页 a b s tra c t d r g si sa ni m p o r t a n ta s p e c to ft h ei t s i to f f e r st h es h o r t e s tr o u t eg u i d i n g a n do t h e ra b u n d a n tr e a l t i m et r a f f i ci n f o r m a t i o nt ot h ed r i v e ra c c o r d i n gt os o u r c e a n dt a r g e tp o i n t i ta c h i e v e st h eg o a l so fi m p r o v i n gt r a f f i cs y s t e m ，p r e v e n t i n g t r a f f i cja m ，r e d u c i n gt h ev e h i c l e s s t a y i n gt i m e ，r e a l i z i n gt h er a t i o n a ld i s t r i b u t i o n o ft r a f f i cf l o wo ne a c hr o a ds e c t i o nb yg u i d i n gt h ed r i v e r st r a v e lb e h a v i o r s h o r t e s tr o a dg u i d e n c ei so fk e yc o n t e n to fd r g s w i t ht h ec o n s t a n te n l a r g e m e n t o fu r b a nr o a dn e t w o r ka n dr e m a r k a b l ei n c r e a s e i n go ft r a f f i cf l o w ，t h ee x i s t i n g t y p i c a la l g o r i t h m si ns h o r t e s tr o u t eg u i d e n c ei su n a b l et om e e tt h er e q u i r e m e n t s o ft h ed y n a m i cr o a dn e t w o r k a sak i n do fn e wd e v e l o p i n ga r t i f i c i a li n t e l l i g e n t a l g o r i t h m ，a n tc o l o n ya l g o r i t h mh a st h ec h a r a c t e r i s t i c so fw e l lg l o b a lo p t i m i z i n g a b i l i t i e s ，p a r a l l e l i s mi ne s s e n c e ，s o l v i n gi ns h o r tt i m e ，r e a l i z i n ge a s i l ye t c i th a s a p p l i e dt oh i g h l yc o m p l i c a t e dc o m b i n a t o r i a lo p t i m i z a t i o n ，r o u t es e l e c t i o n i n c o m m u n i c a t i o nn e t w o r k ，v e h i c l es c h e d u l i n ge t c ，a n dh a so b t a i n e dg o o dr e s u l t s t h i sp a p e rb r i e f l yi n t r o d u c e ss e v e r a lk e yp r o b l e m sa r o u n dt h eq u e s t i o no f s h o r t e s tr o u t eg u i d e n c es u c ha st h e d y n a m i cr o a dn e t w o r km o d e l ，t h er o a d v a l u e ( t h et r a v e lt i m e sc a l c u l a t e ) ，t h ea l g o r i t h mo fr o u t eg u i d e n c e a n df i n a l l y c h o o s e sa n tc o l o n ya l g o r i t h mw h i c hh a sb e t t e rp e r f o r m a n c et ob es h o r t e s tr o u t e g u i d e n c ea l g o r i t h m t h ep a p e rh a sa n a l y s e da n tc o l o n ya l g o r i t h m sp r i n c i p l e ， m o d e l ，a n dt h es e t t i n go ft h ep a r a m e t e re s p e c i a l l y , t h e np r o v i d e dak i n do f i m p r o v e m e n ta l g o r i t h m _ 。d u a lp o p u l a t i o n a n t c o l o n ys y s t e m b a s e do n p h e r o m o n ed i f f u s i o n ( p d d p a s ) t h ep a p e rc h o o s e st h r e et s pq u e s t i o n sw h i c h h a v ed i f f e r e n ts c a l et oe x p e r i m e n t i z e t h ep d d p a s sp e r f o r m a n c e ，p a r a m e t e r s e t t i n g ，a n dp h e r o m o n ed i f f u s i o nm e t h o da r ei n v e s t i g a t e d ，b a s e do nw h i c ha c o r r e s p o n d i n gs e t t i n gh a sd r a w n t h er e s u l ti n d i c a t e st h a tp d d p a sh a sb e t t e r s e a r c ha b i l i t y , f a s tc o n v e r g e n c es p e e d ，a n dh i g h e rs t a b i l i t yi np a r a m e t e r f i n a l l y , t h ep a p e rr e a l i z et h ep d d p a so nar o a dn e t w o r km a p k e y w o r d s d g r s ；d y n a m i c t r a v e lt i m e ；a c o ；p d d p a s 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位 论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保盔声使用本授权书。 ( 请在以上方框内打“) 学位论文作者签名：刮在巷 指导老师签名： e i - 期： n e t 期：萨卵 砷d9 ，7 9 。 i 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作 所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均己在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本文的主要创新点如下： 给出了一种基于信息素扩散策略的双种群蚁群算法p d d p a s 算法。 p d d p a s 使用信息素扩散策略提高了算法的全局寻优能力，使用双种群策略 提高了算法的收敛速度。实验表明，与同类算法相比，改进的p d d p a s 算法 具有寻优能力强，收敛速度快，参数设置稳定的优点。 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 研究的背景及意义 随着我国社会经济的发展和大中城市路网的逐渐成熟，人们对交通运输 的各种需求明显增长。从1 9 9 9 年到2 0 0 5 年，我国公路总长从1 3 0 万公里上 升到1 9 0 万公里，上升幅度小于5 0 。而在同期，我国的注册车辆数由1 5 0 0 万辆上升至3 2 0 0 万辆，上升幅度大于1 0 0 。同时，从2 0 0 5 年到2 0 0 7 年这 短短的两年内，我国的注册车辆数又将近翻了一翻，达到5 3 0 0 万辆。目前， 道路容量的增长难以适应车辆和交通量的增长己成为我国城市交通普遍存在 的问题，由此引发的城市常发性交通拥挤越来越严重，交通高峰期的持续时 间不断延长，高峰期出现交通拥挤的路段不断增加，交通高峰期事故频发等 现象严重降低了道路交通网络的安全性和运行效率，制约了城市的可持续发 展，已经成为我国各大城市亟待解决的重要问题。 实际上，路网并不是在全部时间和空间上都是满负荷运转的，若能够及 时获得路网上的动态交通信息，准确地掌握以及预测路网的交通状态，并以 此进行出行诱导，就可以充分利用交通系统的时空使用效率和安全性来满足 不断增长的运输需求。 动态路径诱导系统( d y n a m i cr o u t eg u i d e n c es y s t e m ，d r g s ) 就是以此为 目的提出的。它根据出行的起止点向驾驶员提供最优路径指引和其他丰富的 实时交通信息，通过诱导驾驶员的出行行为来改善路面交通系统，防止交通 阻塞的发生，减少车辆在道路上的逗留时间，并且最终实现交通流在路网中 各个路段上的合理分配。动态路径诱导系统的研究经历了从静态路径引导 系统到动态路径诱导系统的过程，国内现有的路径诱导系统一般是静态路径 诱导，它利用一个记录着过去交通状况的历史数据库或者干脆是地理信息系 统( 数字地图) 等静态信息进行路线引导。随着人们对交通条件要求的提高 以及计算机硬件技术和通信技术的发展，人们开始了对动态路径诱导的研究， 与静态路径诱导系统相比，其不同之处在于它能够利用实时交通信息( 如经 过某一路段所需的时间) 进行更有效的诱导，动态路径导航系统是路径诱导 系统发展的必然趋势。 西南交通大学硕士研究生学位论文第2 页 1 2 研究现状 动态路径诱导系统包括交通信息的检测处理、交通状态预测、最优路径 选择三个方面。 交通信息的检测 已有的交通信息检测技术包括固定检测技术和移动检测技术两种。 ( 1 ) 固定检测技术目前使用最广泛的是环形线圈检测器，它利用埋设 在车道下的环形线圈对通过或存在于线圈上的车辆所引起的电磁感应变化进 行处理来进行检测，可以提供精度较高的交通流量、路口车速和路段时间占 有率等基本交通信息，但其只能检测路口交通信息，难以检测路段交通信息。 为尽可能减少误差，国内一些学者利用仿真手段研究了检测器的最佳布设位 置，结果表明，检测器的最佳布设位置和路段长度有关，路段长度越长，检 测器最佳布设位置距下游交叉口越远【3 】。 ( 2 ) 移动检测技术主要指基于g p s 的浮动车检测技术，它通过在车辆 上的g p s 接收装置，以一定的采样间隔记录车辆的三维位置坐标和时间数 据，再分析计算出车辆的瞬时车速及其通过特定路段的行程时间和速度指标， 可以提供连续的、路段的甚至整个路网的交通信息，但由于受到浮动车随意 停车，浮动车数量，车辆类型以及驾驶员的驾车习惯、g p s 定位精度等多 方面的影响，检测精度较低【2 j 。 交通状态预测 ( 1 ) 较早期的交通流预测方法主要有自回归滑动平均模型( a r m a ) 、自 回归模型( a r ) 、滑动平均模型( m a ) 和历史平均模型( h a ) 等【l 引。这些基于统 计方法的线性预测模型考虑问题都较为简单，参数一般都用最小二乘法( l s ) 在线估计，具有计算简便、易于实时更新、便于大规模应用的优点。但这些 模型未能反映交通流的不确定性和与非线性，无法克服随机干扰因素对交通 流量的影响，随着预测时间间隔的减少，这些模型的预测精度就会变得很差。 ( 2 ) 随着交通流预测研究的不断深入，一些更复杂，预测精度更高的预 测方法被提出，包括k a l m a n 滤波方法、小波分析、神经网络以及多种方法结 合的复合预测方法。k a l m a n 滤波方法采用递推状态空间模型，既能处理平稳 数据，也能处理非平稳数据：模型具有线性、无偏、最小均方差性；便于在 计算机上实现，且大大减少了计算机的存储量和计算时间，适于在线分析， 预测精度较高【6 】。但k a l m a n 滤波方法也是线性预测模型具有上述所说的缺点。 西南交通大学硕士研究生学位论文第3 页 小波分析是一种非线性预测，其中多尺度方法较之普通的时间序列方法具有 更强的抗干扰能力，因此具有较强的适应性。但对信号进行二进小波分解时， 每次分解都将信号样本减少一半，进行分解后只能依据较少的样本数据进行 阶数和参数的估计，影响了重构模型和预测精度。同时还需要其他时间序列 方法，所以影响了预测精度，而且也没有考虑相邻路段的影响。 最短路径选择 在动态路网中进行路径诱导与传统的静态路网相比有很大的不同，许多 学者进行了大量的研究。代表性的工作有： ( 1 ) c o o k e 和h a l s e y ( 1 9 9 6 ) 基于在离散时间范围内，弧的旅行时间是离 散间隔的整数倍的假设，改进了b e l l m a n 的最短路径算法，基于b e l l m a n 最 优化原理建立了时间依赖的方程，首次提出了时变路网的最优路径算法【i 2 | 。 ( 2 ) k a u f m a n 和s m i t h 给出了d r e y f u s 算法在t d n 路网中是不正确的反 例，k a u f m a n 和s m i t h 研究的核心内容是在一致性约束假设条件下，证明传 统的两大类最短路径算法，标号设置算法和标号修改算法在一致性约束条件 下可以求解一类时变路网是最短路径问题。但k a u f m a n 和s m i t h 以及 g r i e r g c h a b i n i 研究的均是时变路网的特例，不具有普遍应用价值【l 4 | 。 ( 3 ) o r d a 和r o m ( 1 9 9 0 ，1 9 9 6 ) 提出了三种类型的路网模型：不受限制的 等待模型、禁止等待模型和源等待模型。当访问的结点允许等待时，这种方 法可以确定最优等待时间，或者如果在其他结点不允许等待而在源结点可以 等待的最优等待时间【15 , 1 6 】。如果每一结点都不允许等待，则o r d a 和r o m 方 法不能应用到非f i f o 路网，无法找到最优路径。o r d a 的方法在计算机通信 路网中是有效的，但在交通应用中是无效的，因为交通路网结点处等待是没 有意义的，交叉路口是不允许等待的。 蚁群算法的研究 蚁群算法于1 9 9 1 年由d o r i g o 在他的博士论文中提出。d o r i g o 等人利用 t s p 问题与觅食的相似性，运用了正反馈原理和分布式算法，通过模仿蚂蚁 行为成功的解决了t s p 这个具有典型代表的组合优化问题。随后他们又相继 解决了二次指派问题( q u a d r a t i ca s s i g n m e n tp r o b l e m ，q a p ) 、车间调度问题 ( j o bs h o ps c h e d u l i n g ，j s p ) 、网络路由问题( n e t w o r k i n gr o u t i n g ) 等，并作了大 量的实验研究。结果表明，该算法具有明显的优越性。1 9 9 6 年，d o r i g o 等 在( i e e et r a n s a c t i o n so ns y s t e m ，m a n ，a n dc y b e r n e t i c s p a r tb 上发表了“a n t s y s t e m ：o p t i m i z a t i o nb yac o l o n yo fc o o p e r a t i n ga g e n t s ”一文【3 ，在这篇文章中， d o r i g o 等不仅更加系统地阐述了蚁群算法的基本原理和数学模型，还将其与 西南交通大学硕士研究生学位论文第4 页 遗传算法、禁忌搜索算法、模拟退火算法、爬山算法等进行了仿真实验比较， 并对蚁群算法中初始参数对其性能的影响做了初步探讨，这是蚁群算法历史 上具有奠基性文章。随后的几年里，蚁群算法逐渐引起了世界许多国家研究 者的关注，其应用领域也得到了循序拓宽。进入本世纪后国际著名的顶级学 术刊物( ( n a t u r e ) ) 曾多次对蚁群算法的研究成果进行报导，( ( f u t u r eg e n e r a t i o n c o m p u t e rs y s t e m s ) ) 和( ( i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ) ) 分别 于2 0 0 0 年和2 0 0 2 年出版了蚁群算法特刊。如今，蚁群算法已经成为一个备 受关注的研究热点和前沿性课题。 1 3 本文研究内容及章节安排 最短路径选择是动态路径诱导的核心内容和主要目标，本文围绕最短路 径求解问题展开工作，对在动态路网中求解最短路径的几个关键问题如：动 态路网的模型，路网边的权值行程时间的计算，算法的选择等进行了扼 要的介绍，重点分析了蚁群算法的原理，模型，以及参数的设置，针对其存 在的缺点给出了一种改进的蚁群算法基于信息素扩散的双种群蚁群算法 ( p d d p a s ) ，并通过大量实验验证了其性能。最后，将p d d p a s 算法在路网 地图上进行了实现。 本文具体的章节组织如下： 第1 章绪论，概要性地介绍了论文研究的背景和意义，以及动态路径 诱导主要内容，明确了本文研究的目标。 第2 章动态路径诱导的关键问题，主要对动态路网的模型，行程时间 的计算，以及常用的人工智能算法进行了介绍。 第3 章基本蚁群算法，章体具本分析了基本蚁群算法的原理和模型， 对算法的参数设置和其优缺点进行了详细的讨论。 第4 章蚁群算法改进，本章给出了一种基于信息素扩散的双种群蚁群 算法( p d d p a s ) ，并通过大量实验验证了其性能。本章是本文工作的重心。 第5 章p d d p a s 在路网上的实现，本章针对路网特性，对p d d p a s 的 参数进行了具体的设计，并在路网地图上对算法进行了实现。 西南交通大学硕士研究生学位论文第5 页 第2 章动态路径诱导的关键问题 动态路径诱导系统的核心内容就是最短路径选择，依据哪种交通信息进 行路径选择，以及如何根据这些信息快速确定出最佳出行路径等都是最短路 径选择所要解决的问题。本章就最短路径选择的几个关键问题动态路网 模型、路权参数的计算，以及算法的选择等问题进行了分析和介绍，为最短 路径的求解建立了基础。 2 1 动态路径诱导的理论基础 动态路径诱导的基础是动态交通分配理论。动态交通分配源于静态交通 分配。在静态交通分配中，路段特性函数是交通量与出行时间( 费用) 的关系 函数，静态均衡分配要求该特性函数为单增的凸函数。对于行程时间的估计 精度要求不高，甚至不必考虑交通拥挤。但是在实际中，交通需求随时间变 化，这使得交通网络上的交通流具有动态特性，当路网拥挤时，低交通量同 样也能导致低速度和较长的行程时间，这是与静态交通分配的单增的路段特 性函数相矛盾的。 动态交通分配克服了静态分配的缺点，考虑了交通需求随时间变化的特 性，更确切地描述了交通网络上瞬时交通流的分布状态【2 2 ，2 3 1 。d t a 追求动态 的系统最优，定义为：在【o ，t 时段中，系统中各出行者在各瞬时通过所选 择的出行路径所花费的总出行费用为最小，即： 一 7 _ f = ：i 。c 。( x 。) d ( t ) ( 2 1 ) 其中e ( x 。) 是路径a 在时段t 上的交通负荷x 。( f ) 所引起的出行费用，该 函数为非负、递增、可微的凸函数，c 。( x 。) 又称为广义路阻( 出行费用) 函数， 其含义是出行者为了完成从出发点到终点的出行所付出的代价及其为社会带 来的副影响的总和。它包括出行途中占用的时间，支付的能源或票价等货币 量以及产生的车辆磨损、环境污染等非货币量。在d t a 的实际应用中，一个 典型的广义费用函数具有如下形式： e ( t ) = m d 口( f ) + k l 。+ p o ( 2 - 2 ) 西南交通大学硕士研究生学位论文第6 页 其中，c 。( f ) 是随时间变化的路径a 上的广义费用；l a 是路径长度：d 。( f ) 是随时间变化的路径行程时间；只是路径a 的道路质量所表示的路阻；k ，m 是 常数因子；所以，由式( 2 2 ) 知，在一条路径上，k 。+ 只为常数，广义出行 费用可以由路径平均行程时间直接决定。 行程时间作为基本的诱导信息还有其他的优势：( 1 ) 行程时间是所有出 行方式都具有的一个普通的参数，所以不同的出行可依据同样的参数来比较； ( 2 ) 从技术角度，行程时间可通过通信链路发送到各种信息媒体；( 3 ) 行程 时间信息对用户来讲易于理解，驾驶员能够直接通过行程时间找到避免拥挤 且能达到目的地的最短路径。 所以路段行程时间是基于d t a 理论的，它既能够反映路段阻抗或拥挤情 况、又是驾驶员容易接受的交通流参数。 2 2 动态路网的表达 2 2 1 动态网络模型 动态路网的路权值是值随着时间而动态变化的。这一特性被成为“时间 依赖性”，具有这一特性的网络被称为动态网络或时间依赖网络。时间依赖网 络可以用模型t d n = ( 矿，彳，g ) 来表示，其中y 是一个非空有限节点集， a y 矿为有限边集，用( v ，1 ，) 表示从节点1 ，。到v ，的有向边；g = g 玎( f ) ) ， g i ，( f ) 表示t 时刻从节点，出发通过边( v ，1 ，f ) 到达节点v ，的行程时间。 对于离散时间情况，t d n 模型可以表示为t d n = ( y ，彳，g ，s ) ，其中，s 是 离散时间的时间间隔，即s = t o ，t o + ，t o + 2 a t o + 尬) ，其中t 。为初始时 间，为一个很短的时间间隔，路网中通常可以取5 到15 分钟，在这个时间 间隔内路网中边的条件不发生变化。m 是使得t 。到t 。+ m a 成为感兴趣时间 段( 如交通高峰期) 的最大整数。v 木s = ( 1 ，；，t ，) i ，属于y 且t ，属于s ) ， 表示节点的状态空间，有序对( v ，t ，) 表示节点的一个状态，同样一个节 点，在不同的时间具有不同的状态。 在t d n 网络中，令r ( v ，v i ，t ) 表示t 时刻从节点1 ，出发到节点v ，的一条路 径，即r ( v ，1 ，t ) = ( 1 ，f ) ，v 。，t ) ，( y ，t ”) ) ，其中( 1 ，。，t ) 是节点v 的一种状态， 表示在t 时刻到达节点v 。求解动态路网的最短路径，即是求解特定时刻从 源节点出发到达目的节点的最短时间路径。 西南交通大学硕士研究生学位论文第7 页 2 2 2 动态网络的最短路径问题 动态网络与静态网络中的最短路径问题有很大的不同。静态网络的最短 路径常用经典的d i j k s t r a 算法求解，d i j k s t r a 算法可以简单的描述为： 设矿为节点集合，a r c s 嘲 表示边( i ，j ) 上的权值，若( i ，j ) 不存在，则 置a r c s f 】为o o ；d ( v ) 为源点v 。到v 的最短路径，且d ( v 。) ，d ( v 2 ) ，d ( v 女) 已 求得，s = v 。，1 ，”v 。) 为最短路径终点的集合，则下一条最短路径为： d ( v ) = m i n d ( ，) + a r c s ， 【v 】) ；其中1 ，s ，v s 。 从中可以看出，d i j k s t r a 算法的理论基础是：最短路径的子路径仍然是 最短路径。该条件在静态网络中是成立的f 删，但在动态网络中有所不同。 首先引入一个概念：f i f o ( f i r s ti nf i r s to u t ) 网络。 定义2 1 ：对于网络中任意一条边( v ，v ，) ，在任意时刻t 。t 序，如果满 足条件：t + g f ，( f 一) t 口+ g 口( f 占) ，则称边( v ，v ，) 是f i f o 的。也就是说，从节 点v i 出发的早，则一定早到达节点1 ，。 如果网络中所有的边都是f i f o 的，则这个网络被称为f i f o 网络，否则， 如果有一条边不满足f i f o 特性，该网络就是非f i f o 网络。f i f o 网络具有 以下的特性p j ： 定理2 1 ：对于f i f o 网络中的任意节点对( i ，) ，i 为源节点，j 为目标 节点，其最小行程时间函数具有f i f o 特性。 定理2 2 ：若f 是t 。时刻从源节点s 到，的最短路径d 形。) 上的任意一个 节点，则该最短路径d j ( ) 上的任何子路径d ，( f 。) 是从s 到i 的最短路径。 定理2 2 就是d i j k s t r a 算法所要求满足的条件。即当网络是f i f o 网络时， d i j k s t r a 算法成立。静态网络由于其边上的权值是固定不变的，每条边的行走 时间也是不变的，同时也不用考虑节点处的延误，即静态网络是f i f o 网络。 t d n 网络与静态网络相比有很大的不同。当t d n 网络满足f i f o 条件时， 具有以下性质【5 j ： 性质2 1 ：若d j ( 岛) = ( v 0t o ) ，( ，l ，t i ) ，v 2 ，t 2 ) ，( v ，f ，) ) 是从源结点v o 在 t 。时刻出发，在t ，到达结点1 ，的最小时间路径，则对于任意结点1 ，；( i = 1 ， 2 ， 3 ，1 ) ；子路径d 沁o ) = ( v 。，t o ) ，( 1 ，州t ) ，( v 2 ，t 2 ) ，v 川t ) ) 均是从源结点在 在t 。时刻出发，在t ，到达结点v i 的最小时间路径。 即动态f i f o 网络同样具有传统的最短路径的性质，可以使用d i j k s t r a 等算法求解。但t d n 网络并不总是满足f i f o 的。这种情况在交通网络中非 西南交通大学硕士研究生学位论文第8 页 常常见，一个实际的例子如：一辆车先驶过一个路段，在交叉口处遇到红灯 而停止等待，当信号灯由红灯转为绿灯时，另一辆辆车恰好到达交叉路e 1 ， 此时第二辆车将不必等待而能先于第一辆车驶出该路段。该问题可具体表述 为：在非f i f o 的t d n 网络中，如果其中一条边( i ，) 的行程时间函数g l ，( f ) 满足：g u ( f ) a t + g f ( f + f ) ，那么性质1 不成立。考虑下图： 图2 1一个简单的动态非f i f o 网络 在如图网络中计算从节点1 至节点4 的最短路径，使用d i j k s t r a 算法将 得到解( 1 ，3 ，4 ) ，最短行程时间c = g 。，( 0 ) + 9 3 4 ( 1 0 ) = 3 0 ，但实际最短路径 为( 1 ，2 ，3 ，4 ) ，其行程时间为c = 9 1 2 ( 0 ) + 9 2 3 ( 1 0 ) + 9 3 4 ( 2 0 ) = 2 5 。 所以，当动态网络满足f i f o 原则时，所有基于静态网络的最短路径算法 ( 如d i j k s t r a 算法等) 都适用于动态网络，当动态网络不满足f i f o 原则时，那 些基于静态网络的最短路径算法都不适用于动态网络。这时只能选用一些基 于人工智能的算法来求解该问题【，】。 2 3 行程时间的计算 路网的动态性即表现为其行程时间随时间的动态变化。因此，准确的预 测和计算路段上的行程时间就成为路径诱导的关键。 根据研究对象的不同，行程时间预测分为城市道路行程时间预测、快速 路行程时间预测和高速公路行程时间预测。其中城市道路行程时间预测较其 它有一定的特殊性，这主要是由其交通流的特殊性引起的。如在城市道路上， 交通流的流速往往比较低，且经常会在节点处断开。另外城市道路的交通流 组成也很复杂，由此造成的突发事件也较多 4 1 。 根据研究内容的不同，行程时间预测可以分为路段行程时间预测和路径 西南交通大学硕士研究生学位论文第9 页 行程时间预测，前者又分为路段交通流平均行程时间和路段单车行程时间。 路段交通流平均行程时间是某一时段内路段上所有行驶车辆的行程时间平均 值，与交通需求和道路通行能力有关。路段单车行程时间是单个车辆通过某 路段的行程时间，与车辆性能和道路交通状况有关。路径行程时间是起终点 间按一定路径出行所需的时间，与所选择的路径和路径的道路交通状况有关。 本章将主要针对城市路段单车行程时间的预测进行具体的讨论和分析。 2 3 1 行程时间的主要参数 影响行程时间的主要因素包括：路段的等级，长度，车道数，路段上的 交通流量，交通密度，以及机动车自身的性能因素如车速等。其中以交通量、 交通密度、车速等随着时间的变化而动态变化的因素最为重要。 交通流量是单位时间通过某一地点的车辆数，单位为( 辆h ) 。通常其值 是在某一点测到的，例如路段的入口、中间某一点或出口，而不同点的交通 流量读数可能差别很大。传统的路段交通流行程时间预测模型如历史趋势方 法、时间序列模型、卡尔曼滤波、多元回归模型、神经网络法等，大多使用 交通流量作参数，这在静态路径诱导中可以取得很好的效果，但在时变的动 态路网中，交通流量已无法完全描述动态交通特征。 交通负载是在某一时刻路段上存在的车辆数。而单位路段长度上的交通 负载即为交通密度( 辆k m ) 。从交通负载的定义可以看出，交通负载是一个特 定路段上车辆数的空间观测量，且它的移动引起交通密度的变化。 图2 - 1行程时间和交通流量、交通密度的关系 图2 1 显示了行程时间与交通流量和交通密度的关系。行程时间不是关 于交通流量的单调函数，而是关于交通密度的单调函数挎】。交通流量随着进 入路段的车辆数的增大而增大，当车辆数多到发生拥堵时，车流速减缓，车 辆走走停停，交通流量降低，行程时间却变得更大。所以不能通过交通流量 西南交通大学硕士研究生学位论文第1 0 页 的大小直接判断行程时间的长短。而这一过程中，随着路段上车辆数的增大， 交通密度始终是增大的，交通密度与行程时间是正相关的关系，可以直观的 反映出行程时间的大小。 因此，交通负载或者交通密度更能反映路段交通状况随时间的变化特征， 其状态方程为【1 7 1 8 1 ： 了a x o ( t ) ：u a ( f ) 一v 。( f ) ( 2 3 ) 口z 式中( f ) 是t 时刻路段上的交通负载，u a ( f ) 是单位时间内进入路段的车 辆数，匕( f ) 是单位时间内离开路段的车辆数。当_ d x a ( t ) ：o 时，即流入率等于 a l 流出率时，为静态分配。当堕掣0 时，为动态分配，即交通负载是时变的， d f 一个点的交通流量不能对其描述，而需要使用交通密度描述其状态。 车速是计算行程时间的关键参数，研究发现 1 9 】，实际中的车流在城市路 网中的运行速度与交通密度的关系有如图2 2 所示的模式，即速度密度 关系模式分为三种情况：自由车流，正常车流及饱和车流。 v m a x ! e 速 f k m h v r a i n 交通流密度( 辆k m ) 图2 - 2车速一交通流密度关系 根据格林伯( g r e e n b e r g ) 交通流理论，路段上的行驶速度v 与交通流密 度k 有如下的对数车流模型： l nf 生、1 lk j ( 2 4 ) 其中，v 。为最大交通量时的速度；k j 为阻塞密度( 辆k m ) 。这种模型和 交通拥挤时的实测数据很吻合，但是当交通密度很小时，就不太适合。可以 西南交通大学硕士研究生学位论文第11 页 二三v ：1 _ ( 等) ，尼二羹 c2 5 ) 式中，k j 是阻塞密度( 辆k m ) ：k 脚是最优密度( 辆k m ) ，k = k j e ；1 ，。为k 。 时对应的速度( k m h ) v o 为设计车速( k m h ) ，它的值与道路等级和车道数 有关，如表2 1 所示。 表2 - 1 车速与道路等级、车道数的关系 道路等级快速干道主干道次干道支路 设计车速( k m h ) 6 0 8 04 0 6 03 0 4 02 0 3 0 车道数 2 4 2 41 3 l 2 将式( 2 - 5 ) 用离散形式表示，则在动态交通分配中，在时间t 时刻路段 i 上的交通流的行驶速度为： k i k f ( f ) 庀 ( 2 6 ) k ， k i ( f ) 定 式中，k i ( f ) 为t 时刻路段i 上的交通密度。 2 3 2 路段行程时间模型 本文所指的路段是指包含一个有信号灯控制的有交叉口的路段。路段行 程时间是指在某个时间周期内，车辆驶过道路某一路段总的持续时间。在拥 挤的城市交通网络中，尤其在早晚交通高峰期间，交叉口前排队的长度较长。 而且城市道路网络不同于公路交通网络，城市路网交叉口比较密集，路段比 较短，平均在5 0 0 2 0 0 0 m 之间，所以在研究路段阻抗时必须要考虑路段下游 交叉口车辆排队长度这个因素【9 】。 当车辆进入路段后，其行程时间是随交通密度的变化而变化的，由于车 辆在下游出口附近经常要排队等待绿灯，从而使交通流产生间断。为了区别 描述，称有排队的这一区域为下游高密区，相应的，称没有排队的区域为上 游低密区。车辆在下游高密区产生的交通延误时间随着交通流密度的变化而 _、jl 丽 = = u u 西南交通大学硕士研究生学位论文第12 页 有非常敏感的差异。这里对车辆间的影响忽略不计。 根据车辆在路段上行驶的特点，可以将车辆的行驶时间分为三部分：在 上游自由行驶的时间t ，在下游排队等待的时间f 。，和通过交叉口的时间t 。， 如图2 3 所示，车辆通过路段i 的总的行程时间可表示为【1 0 ，1 1 】： t f 2 f ，+ f g + 乞 ( 2 - 7 ) = 二竺兰二二二 口口口 4 口口口一一， 图2 3路段行程时间模型 2 3 3 路段行程时间的预测 由方程( 2 - 7 ) 可以看出，要想预测某路段的实时动态行程时间，就要分别 对f ，f 。，t c 进行预测。但需要注意的是，后面两个部分时间分别是在对第一部 分时间的预测基础上的再预测，即如果车辆在时刻即将进人路段，那么路 段i 的行程预测时间为 8 】： 正( f o ) = 正d ( f o ) + 正9 ( f o + t d ( f o ) ) + 互。( f o + 正d ( f o ) + 正9 ( z o + 正d ( f o ) ) )( 2 8 ) 即： t ，= r 4 ( 气) t 。= 1 9 ( 气+ z “( ) ) t 。= z 。( + z d ( 岛) + z 研( + 互d ( f o ) ) ) 下面分别分析t ，f 。，t 。首先对需要的参数作如下的定义： 厶路段i 的长度：群( f ) 一一f 时刻路段i 上的排队长度；，( f ) f 时刻路段i 上的车辆总数；圪路段f 上的车速，跟交通密度有关；d ， 各种机动车的平均车长；m 路段i 的单向车道数；旯；路段i 下游交叉 口的绿信比；e 一一路段i 下游交叉口的信号周期；路段i 下游交叉口 单位时间单车道的最大通行能力； 西南交通大学硕士研究生学位论文第13 页 ( 1 ) 自由行驶时间t ，的预测 从图2 - 3 可以看出，自由行程时间t ，是指从进入路段f 开始，经过上游 低密度区域到达下游高密度区排队队尾的时间。显然有： 0 = ( l ，一霹( t r ) ) 1 ，t ( 2 - 9 ) 由方程( 2 9 ) 可知下游排队队长为： g = l ，一1 ，t 木t ， ( 2 1 0 ) 我们假设路段i 不吸收车流量，即从上游路口进入路段i 的车辆全部由下 游交叉口流出，则排队队长还可表达为： 群= ( n i ( f ) d 。m ) 一以d ，a i t ， ( 2 一1 1 ) 由方程( 2 10 ) 和方程( 2 - 11 ) 口- i 以求出t ，和l q i ( t ) 分别为： t ，= ( ，咒f 三f n i ( ) d ，) ( m jv i 一f 旯f d ，) ) 珧) = 厶一v t 而m i l i 厕- n i ( t o ) d ， ( 2 1 2 ) ( 2 1 3 ) ( 2 ) 排队时间的预测 车辆的排队等待时间不仅跟队长和下游交叉口的通行能力有关，还跟到 达队尾时的信号灯状态有关。不同的信号灯意味着车辆将花费不同的等待时 间。参考r o u p h a i l 提出的延误模型9 1 ，并假设一个周期的信号灯由红灯和绿 灯组成，那么可以近似分为两种情况： 1 ) 车辆在绿灯开始时刻到达，则等待时间为： t 。= l q ( f ，) c f p ，d ， ( 2 1 4 ) 2 ) 车辆在红灯开始时刻到达，则等待的时间为： t q t = 鬈( f ，) e ( 。d ，) + c f ( 1 一 ) ( 2 1 5 ) 设车辆在绿灯期间到达的概率为p i ，则在红灯期间到达的概率为 ( 1 一p i ) 。因此，车辆在路段f 等待时间的期望为： 西南交通大学硕士研究生学位论文第1 4 页 e ( t g ) = t q p f 州叮( 1 - p f ) = 日( f ，) c ，p 。( i d ，) + ( 1 一p i ) ( r 7 ( t ，) c ；( ，d 。) + c ，( 1 一 ) ) = c ，( l t ( t ，) ( ，d ，) + ( 1 一丑) ( 1 - p ，) ) 车辆排队时间可以用其期望近似表示，即： t g = e ( t q ) ( 2 1 6 ) ( 3 ) 通过交叉口时间的预测 车辆通过交叉口的时间集中在绿灯阶段， 车通过交叉口的时间： t c = c i 九i “i + p 所以可以用下式表示平均每辆 ( 2 1 7 ) 此处c 之, u , 表示车辆通过交通灯的时间；是浮动参数，描述车辆向 不同方向转弯所要花费的不同时间。由于交叉口的行程较短，且交叉口内不 允许停车。所因此t 。一般远小于t ，和t 。，的精度不必要求很高，取某段时 间交叉口在该方向的统计值即可。 由以上分析可知，车辆在路段i 的行程时间的预测结果就是方程( 2 1 2 ) ， ( 2 1 6