（交通信息工程及控制专业论文）基于蚁群算法的动态交通分配及路径诱导研究.pdf

摘要 动态交通分配和路径诱导为智能交通系统研究的两个核心内容，如何有效的 把交通动态分配到路径上以及实现路径诱导的优化，一直以来就是交通研究的重 要课题。随着路网的扩张以及交通工具的进一步增加，交通日趋饱和，拥堵现象 日益严重，对交通流的分配、引导在整个交通控制系统中起着越来越重要的作用。 目前学术界在研究这两个关键问题的时候，都遇到了复杂的优化问题，如何高效 率的解决这些优化问题成为研究的热点。 以往的交通分配和路径诱导模型多半以静态模型为主，而且没有考虑实时变 化的交通信息因素对交通的影响，导致模型不能对实时地路况信息做出反映，本 文力图将实时交通信息加入动态交通分配与路径诱导模型，通过实时交通信息对 驾驶员的出行路线做出影响，来让模型达到更好的交通分配与路径诱导效果。 论文主要工作和研究成果如下： ( 1 ) 改进了基本蚁群算法，提出了基于路径均值的蚁群算法。主要改变了信 息素的更新方式，将路径因素纳入了信息素更新的考虑范围之内，有效地提高了 算法搜索速度。 ( 2 ) 将实时交通信息应用于动态交通分配模型的建模当中，并用本文提出的 基于路径均值的蚁群算法进行求解运算，在实时动态交通信息的引导下，对交通 进行分配，发挥了蚁群算法本身的优势，取得了较好的效果。 ( 3 ) 将实时交通信息应用于路径诱导算法当中，并用基于路径均值的蚁群算 法进行搜索，较好的改进了经典算法，取得了路径诱导过程里寻找最优路径的效 果。 论文最后对长沙市的主要干道进行了仿真试验，结果表明，基于蚁群算法的 动态交通分配模型和路径诱导算法能对实时交通信息做出反应，动态调整道路信 息素浓度，较好的改进了经典动态交通分配及路径诱导模型，同时有效的提高了 模型求解速度。 关键词：交通分配；路径诱导；优化；仿真；蚁群算法；路径均值 a b s t r a c t d y n a m i ct r a f f i ca s s i g n m e n ta n dr o u t eg u i d e i st h et w oc o r ec o n t e n to f i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ，h o wt oa s s i g n i n gt h e 位l m ct or o u t ea n do p t i m i z e t h er o u t eg u i d i n gs y s t e me f f e c t i v e l yi sa ni m p o r t a n tp r o j e c ti nt r a n s p o r t a t i o nr e s e a r c h w i t ht h es p r e a d i n go fr o u t en e ta n dt h ei n c r e a s i n gt r a f 矗cv e h i c l e ，t r a n s p o r t a t i o n b e c a m em l ，a tt h es a m et i m e , t h et r a f f i ci a mb e c a m es e r i o u s l y a s s i g n i n ga n d g u i d i n gt h et r a 伍cb e c a m em o l ea n dm o l ei m p o r t a n ti nt r a t f i ec o n t r o ls y s t e m a l m o s t a c a d e m i cc i r c l e sm e e tt h ec o m p l e xp r o b l e mo fo p t i m i z i n go nr e s e a r c h i n g ，h o wt o s o l v i n gt h e s eo p t i m i z i n gp r o b l e mw i t he f f i c i e n c yb e c o m et h ek e yt a r g e t u s e dt ot r a f l ：i ca s s i g n m e n tm o d u l ea l m o s tb e l o n gt os t a t i ct r a f f i cm o d u l et h a t d i d n tc o n s i d e rt h ei m p a c to ft h ec h a n g i n gt r a f f i ci n f o r r n a t i o n , t h a tl e a dt ot h em o d u l e c a n tr e f l e c tw i t ht h er o a di n f o r m a t i o n t i l i sa r t i c l ei n t e n d st oa d dt h el i a 伍c i n f o r m a t i o nt ot h ed y n a m i ct r a f f i ca s s i g n m e n ta n dr o u t eg u i d em o d u l e a n de x p e c t t h r o u g hu s i n gt h ei n f o r m a t i o nt oi n f l u e n c et h ed r i v e r r o u t ec h o i c et og a i nab e t t e r e t f e c t i v e t l l i sa r t i c l e sm a i nw o r ka n dr e s e a r c hr e s u l tl i s tb e l o w ： ( 1 ) i m p r o v e dt h eb a s i ca n tc o l o n ya l g o r i t h ma n da d v a n c e dt h ea n tc o l o n y a l g o r i t h mt h a tb a s e do nt h ea v e r a l z eo fr o u t e t h a ti sm a i n l yc h a n g et h ew a y o fi n f o r m a t i o ni na d a p t a t i o n ，i m p r o v i n gs p e e do fs e a r c h i n gt i m e ( 2 ) a , p p z y i n gt h ed e v e l o p e da l g o r i t h mt ot h ed y n a m i c 锄ca s s i g n m e n tm o d e l 诵t hr e a l - t i m ei n f o r m a t i o na n do b t a i na o dr e s u l t ( 3 ) a p p l y i n gt h er e a l - t i m ei n f o r m a t i o nt ot h er o u t eg u i d es y s t e m ，a n ds e a r c h i n g b e s ts o l u t i o nw i t ht h ea n tc o l o n ya l g o r i t h mt h a tb a s e do i lt h ea v e r a g eo f r o u t e a n do b t a i n e dag o o dr e s u l ti ns e a r c h i n gt h er o u t e a tt h ee n d , t h i sa r t i c l ei m i t a t e dt h ep r i m a r yr o u t eo fe h a n g s h ac i t y , 1 1 圮 s i m u l a t i o np r o v e dt h a tt h i sa l g o r i t h mc a l lr e a c tw i t ht h er e a l t i m et r a f f i ci n f o r m a t i o n , d y n a m i ca d a p t i n gt h er o u t ei n f o r m a t i o n , a n di m p r o v e dt h ec l a s s i cd y n a m i ct r a f f i c a s s i g n m e n tm o d e la n dt h er o u t eg u i d ea l g o r i t h m ，a n dp r o m o t e dt h es p e e do ff i n d i n g t h em o d e l ss o l u t i o n k e yw o r d s ：t r a t t i ea s s i l l 皿m e n t ；r o u t eg u i d e ；o p t i m i z e ；i m i t a t e ；a n tc o l o n y a l g o r i t h m ；a v e r a g eo fr o u t e i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：李乡 日期矽夕薄厂月莎日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“ ) 作者签名： 导师签名： 帮专 岱午 日期：劳厂月 日期：为癣r 月谚日 1 1 引言 第一章绪论 随着全球经济的腾飞，对交通运输的需求越来越迫切。交通运输业的发展水 平是国家兴旺发达的重要标志之一。交通运输业的高速发展，一方面促进了物质 交流和人们的往来，大大缩短了出行时间，提高了工作效率；另一方面也带来了 许多弊病，特别是地面汽车运输，不论是在发达国家还是在发展中国家，都存在 着不同程度的交通问题。随着城市交通诱导技术的发展，人们对解决交通拥挤的 办法从单纯提高路网的通行能力发展到通过土地使用方法来对城市居民的出行 进行优化，通过减少城市车辆绝对出行数量来缓解城市交通压力。这种提高路网 的通行能力与优化土地使用方法相结合的方法产生了非常积极的效果。但事实 上，无论是哪个国家的大城市，可供修建道路的空间都是非常有的，同时，对道 路以及土地使用的建设资金筹措也比较困难。在这种背景下，系统地解决道路交 通问题的思想成为未来交通管理与控制的发展方向。 随着全球科学技术的飞速发展，计算机技术、网络技术和通讯技术已逐步渗 入到城市交通管理中。利用现代化科学技术管理城市交通，合理地和科学地引导 和控制交通流，有效地提高现有交通网络的运行效率，这是城市交通管理发展的 必然。智能运输系统，简称i t s ( i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ) ，正是 在这种情况下提出来的。i t s 是应用信息技术、通信技术、定位技术以及控制技 术未改善道路交通的效率、安全和环境因素的这场全球性的技术变革。它是目前 国际公认的解决城市以及高速公路交通拥挤和提高行车安全的最佳措施，也是全 世界交通运输领域研究的前沿问题。 动态交通流分配( d y n a m i ct r a f f i ca s s i g n m e n t ，简称d t a ) 与路径诱导系统 r g s ( r o u t eg u i d a n c es y s t e m ) 是i t s 里的两个重要组成部分，是解决城市交通问 题的关键。目前学术界在研究这两个关键问题的时候，都遇到了复杂的优化问题， 如何高效率的解决这些优化问题成为学术界研究的热点n 】。 1 2 智能交通系统概论 智能交通系统简称i t s ，i t s 是将先进的信息技术( 包括数据通信、计算机 等) 、传感器技术、自动控制理论、运筹学、人工智能等有效地综合运用于交通 的运输、服务控制和车辆制造等方面，加强车辆、道路、管理者三者之间的联系， 从而形成的一种实时、准确、高效的综合运输系统，最终使交通运输服务和管理 智能化，使路网上的交通流运行处于最佳状态，改善交通拥挤和阻塞，最大限度 地提高路网的通行能力，提高整个公路运输的机动性、安全性和生产效率。 1 2 1 智能交通系统研究的历史和现状 早在2 0 世纪6 0 年代，美国就开始进行i t s 的先驱性研究，即电子路径诱导系 统的研究，这可以说是i t s 的最早起源。在i t s 研究的早期工作中，美国主要开展 了车路系统的智能化研究。并将其称为智能车辆道路系统；1 9 9 0 年，美国运输部 成立了i v s h ( i n t e l l i g e n tv e h i c l e h i g h w a ys y s t e m ) 组织，1 9 9 4 年，i v s h 组织 更名为i t sa m e r i c a ( i n t e l l i g e n tt r a n s p o t a t i o ns y s t e mo fa m e r i c a ) 组织。 根据i t sa m e r i c a 发布的消息，1 9 9 8 年1 2 月开始的美国国家i t s 发展战略计划已经 完成，该计划是美国运输部与i t sa m e r i c a 合作的成果，代表了美国更新其i t s 发展战略的第一步。目前美国已经在i t s 的整体组织及规划，以及研究、开发、 运作实验方面进行了大量的部署、投资，在电子收费、商业车辆运营等一些i t s 的实际应用方面处于国际领先地位。 欧洲从1 9 8 6 年开始涉及i t s 的研究。由欧洲主要汽车公司发起的欧洲高效安 全道路交通计划( p r o g r a m m ef o ra ne u r o p e a nt r a f f i cw i t hh i g h e s te f f i c i e n c y a n du n p r e c e d e n t ds a f t y ，简称p u t h e u s ) 旨在以汽车为主体，利用先进的信息、 通信与自动化技术等来改善运输系统，解决交通问题；由欧洲社团委员会发起的 欧洲汽车安全专用道路设施计划主要涉及公路和交通控制技术的研究。在19 9 1 年末成立的欧洲道路运输通信信息实施协调组织作为民办的公共组织，负责监 督和协调欧洲的i t s 研究、发展和实施。欧洲i t s 的研究特点是：在广泛和协调 欧洲的i t s 领域都进行着研究与开发；e c 发起组织的i t s 研究着重技术的部署与 评价，具有高度的研究连贯性，但是与实际的应用和部署尚存在差距；欧洲在 公路上广泛部署了车辆专用电台，可以向用户提供声音或编码信息；将公共交 通视为重要研究内容，公交优先和公交乘客信息系统已经投入使用；无论哪个 国家或企业提出的交通信息系统方案都可以在不同的1 2 个国家分别进行现场实 验。因此，必然具有可使用各种环境的技术及发展新技术的可能性。 i t s 是目前世界上所有国家正在大力发展和应用的现代化交通运输运作和管 理系，在我国的发展也经历了一个较长的理解和接受过程，并且现在已经进入了 具体的研究和实施阶段。国家科学技术部已于1 9 9 9 年1 1 月在北京举办了首届i t s 研讨会：国家建设部与欧洲的i t s 推进组织e r t i c o 联合建立了e u - c h i n a 计划；国 家计划委员会在1 9 9 9 年4 月的科技立项会议中将i t s 歹d 为i 0 0 个重点科研领域之 ：一，并指出“i t s 近期的产业化重点事加快发展先进的交通管理系统、道路交通 信息服务、高速公路通信监控系统及紧急事件处理和救援系统、不停车收费系统。 2 对上述各系统，形成系统设计，设备制造，项目建设、系统运行管理的总体能力 以成套设备的规模化生产能力一 1 2 2 智能交通系统组成 国际上公认的智能运输系统的服务领域主要有以下7 个方面： ( 1 ) 先进的交通信息服务系统( a t i s ) 先进的交通信息服务系统是建立在完善的信息网络基础上的，交通参与者通。 过装备在道路上、车上、换乘站上、停车场上以及气象中心的传感器和传输设备， 可以向交通信息中心提供各处的交通信息：该系统得到这些信息并通过处理后， 实时向交通参与者提供道路交通信息、公共交通信息、换乘信息、交通气象信息、 停车场信息以及与出行相关的其他信息：出行者根据这些信息确定自己的出行方 式、选择路线。更进一步，当车上装备了自动定位和导航系统时，该系统可以帮 助驾驶员自动选择行使路线。 ( 2 ) 先进的交通管理系统( a t m s ) 这个系统有一部分与a t i s 共用信息采集、处理和传输系统，但是a t m s 主要是 给交通管理者使用的，它将对道路系统中的交通状况、交通事故、气象状况和交 通环境进行实时的监视，根据收集到的信息，对交通进行控制，如：信号灯、发 布诱导信息、道路管制、事故处理与救援等。 ( 3 ) 先进的公共交通系统( a p ，i - s ) 这个系统的主要目的是改善公共交通的效率( 包括：公共汽车、地铁、轻轨交 通、城郊铁路和城市间的公共汽车) ，提供便捷、经济的、运量大的公交系统。 ( 4 ) 先进的车辆控制系统( a v c s ) a v c s 目前还处于研究试验阶段，从当前的发展看，可以分为两个层次： 一是车辆辅助安全驾驶系统，该系统有以下几个部分：车载传感器( 微波雷 达、激光雷达、摄像机、其他形式的传感器等) 、车载计算机和控制执行机构等， 行驶中的车辆通过车载的传感器测定出与前车、周围车辆以及与道路设施的距离 和其他情况，车载计算机进行处理，对驾驶员提出警告，在紧急情况下，强制车 辆制动。 二是自动驾驶系统，装备了这种系统的汽车也称为智能汽车，它在行使中可 以做到自动导向，自动检测和回避障碍物，在智能公路上，能够在较高的速度下 动保持与前车的距离。智能汽车在智能公路上使用才能发挥出全部功能，如果在 普通公路上使用，它仅仅是一辆装备了辅助安全驾驶系统的汽车。 ( 5 ) 货运管理系统( c v o ) 这里的货运管理系统是指以高速道路网和信息管理系统为基础，利用物流理 论进行管理的智能化的物流管理系统。综合利用卫星定位、地理信息系统、物流 信息及网络技术有效组织货物运输，提高货运效率。 ( 6 ) 电子收费系统( e t c ) 公路收取通行费，是公路建设资金回收的重要渠道之一，但是是随着交通量 的增加，收费站开始成为道路上新的瓶颈。电子收费系统就是为解决这个问题而 开发的，使用者可以在高速公路公司或银行预交一笔通行费，领到一张内部装有 电子线路的通行卡，将其安装在自己汽车的指定位置，这样当汽车通过收费站的 不停车收费车道时，该车道上安装的读取设备与车上的卡进行相互通信，自动在 预交帐户上将本次通行费扣除。在现有的车道上安装电子不停车收费系统，可以 使车道的通行能力提高3 5 倍。 ( 7 ) 紧急救援系统( e m s ) 紧急救援系统是一个特殊的系统，它的基础是a t i s ，a t m s 和有关的救援机构 和设施，通过a t i s 和a t m s 将交通监控中心与职业的救援机构联成有机的整体，为 道路使用这提供车辆故障现场紧急处置、拖车、现场救护、排除事故车辆等服务。 1 3 动态交通分配与路径诱导研究现状与意义 1 3 1 动态交通分配研究现状 城市动态交通分配理论历经2 0 余年的发展，世界各国的学者进行了多方面的 理论与应用研究。从对出行者路径选择行为的假定看，d t a 模型又可以分为两类： 反应型和预测型，或瞬时( i n s t a n t a n e o u s ) 的d t a 模型让出行者根据当时交通状 况选择当时成本最低的路径，这也是实际生活中出行者的真实行为体现。由于城 市交通状况有很强的时变特性，这类模型可能让相同o d 对、相同时间出发的出行 者在不同的时刻到达目的地。w i e ( 1 9 9 0 ) 乜1 、b o y c e ( 1 9 9 5 ) 3 3 、l a m h l 和h u a n g ( 1 9 9 2 ) i s 、r a n ( 1 9 9 3 ) 抽3 、k u w a h a r a 口3 和a k a m a t s u ( 1 9 9 7 ) 随1 中提出的模型都属于这类。 预测型分配模型或理想的d t a 模型让出行者根据一段时间的交通状况来决定最佳 行驶路径，即最佳路径是在体验到的实际行驶成本上决定的，b e r n s t e i n ( 1 9 9 3 ) 9 3 、f r i e s z ( 1 9 9 3 ) n 们、k u w a h a r a ( 1 9 9 6 ) 口1 中提出的模型可以归于这一类。目前 交通理论界遇到的难题是，无论哪种模型，都是非线性、非凸、超大规模且具有 强时变特征的，很难找到有效的求解算法，况且这些模型还不能完全揭示实际环 境中的交通行为。所以，已经开发出来的商业软件中，都是使用模拟近似技术。 对于实用的d t a 系统，计算效率极为关键。并行分布仿真应是一种选择，如 p a r a m i c s 、t r a n s i m s 就可在并行机上运行。有的学者目前正在开展基于网络技 术的交通信息处理系统的研发，都是很好的实用思路。 从动态网络交通流模型的研究方法上看，该类模型又可以分为五类：( 1 ) 计 4 算机模拟方法；( 2 ) 数学规划( m a t h e m a t i c a lp r o g r a m m i n g ，简称m p ) 建模方法； ( 3 ) 最优控制( o p t i m a lc o n t r o l ，简称o c ) 理论建模方法；( 4 ) 变分不待式 ( v a r i a t i o n a l i n e q u a l i t y ，简称v i ) 与非线性互补( n o n l i n e a r c o m p l e m e n t a r i t y ，简称n c p ) 理论建模方法；( 5 ) 不动点( f i x e dp o i n t ，简称 f p ) 理论建模方法等。 y a g a r ( 1 9 7 1 ) 提出了第一个基于计算机模拟的动态网络交通流分配模型。 该模型满足w a r d r o p 用户最优原则，考虑了随时间变化的需求以用排队的形成。 y a g a r ( 1 9 7 0 ) 也提出了一个具有启发性的动态系统最优( d y n a m i cs y s t e m o p t i m a l ，简称d s o ) 模型的算法，该算法被v a na e r d e 和y a g a r ( 1 9 8 8 ) 进行了 改进。b r a s t o w ( 1 9 7 3 ) 提出了另一个d u o 问题的计算机模拟模型。在他的模型中， 随时间段为常值的需求函数通过流量密度关系转换为随距离分段为常值的函 数。此外，m a h a m a s s a n i 和p e e t a ( 1 9 9 3 ) 、m a h a m a s s a n i ( 1 9 9 2 ) 的模型也是基于 计算机模拟的模型。 由于不动点理论与变分不等式、非线性互补理论之间的关系密不可分，因此 就有学者研究基于不动点理论的动态网络交通流分配模型。k a u f m a n ( 1 9 9 8 ) 研究 了动态分配中用户均衡性质，指出动态路径均衡条件是一个不动点问题，给出了 不同均衡条件下不动点问题存在的充分条件，并给出了求解这个不动点问题的一 些建议。l a m ( 2 0 0 2 ) 在研究弹性公交发车频率下的公交分配时，给出了一个基于 不动点理论的随机均衡模型，证明了不动点模型的存在性，并设计了有效的求解 算法。 如上所述：从研究问题的角度看，d t a 模型的研究工作主要沿着两类方法展 开：道路交通流模型和网络交通流模型。道路交通流模型的模拟方法主要以研究 微观或宏观的交通流特性为侧重点，这些模型可以模拟出一些交通管理策略下的 可能结果，但不能确定应该采用什么样的管理策略。另外，这些模型一般也缺乏 明确的解析性质，并且不能确定其解是否为最优解。而从解析的角度构造的动态 网络交通流模型( r a n 和b o y c e ，1 9 9 6 ；s m i t h ，1 9 9 3 ) 虽然具有良好而明确的性 质，比如最优条件、遵守动态的w a r d r o p ( 1 9 5 2 ) 原则，但它的难点在于，如何将 真实的交通动态条件添加到已有的复杂公式中去。如何建立交通仿真模型也很重 要，应在仿真的精确性和计算的有效性之间取得合理的折衷，比如中观模型既利 用了宏观流体模型的思路，也吸收了微观交通模型的一些优点，值得考虑。为此， 一些研究学者尝试将宏观仿真模型引入到动态网络交通分配理论中。m e r c h a n t 和n e m h a u s e r ( 1 9 7 8 a ) 将宏观仿真模型应用到其系统最优的分配模型中。最近， w o n g ( 2 0 0 1 ) 所l o 和c h e n ( 2 0 0 0 ) 的基于路径阻抗的静态交通分配模型与t r a n s y t 交通模型进行结合，其中路径阻抗是由路径上每条路段的延迟时间与行驶时间相 5 加而得出。d a g a n z o ( 1 9 9 4 ，1 9 9 5 a ) 利用有限差分设计了一种新的近似方法一元 胞传输模型( c e l lt r a n s m i s s i o nm o d e l ，简称c t m ) ，它模拟的车流符合实际情 况，并且收敛速度很快，解法简单，并且能够扩展用于一般的情形。 1 3 2 路径诱导现状 i t s 将先进的计算机处理技术信息技术、数据通信技术以及电子自动控制技 术等有效地综合运用于整个交通管理体系，可将人、路、车有机地结合起来以达 到最佳的和谐统一，从而在大范围内建立起一种全方位发挥作用的实时、准确、 高效的交通运输综合管理系统。 a t i s ( 先进的出行者信息系统) 是i t s 的一个研究领域。它运用各种先进的通 信信息技术向旅行者提供到达日的地所需要的各种信息。其中很多信息是在车中 获得，也有许多旅行计划所需的信息可以于旅行前在家中、办公室等地获得，甚 至还可随时地利用便携式计算机、掌上电脑得到。a t i s 除提供传统意义的旅行者 信息功能外，它的主要功能子系统还有路径导航系统( 也称路径诱导系统) 、停车 场可利用性诱导系统和数字地图数据库。 其中车载路径导航是a t i s 的最重要的功能之一。车载路径导航系统就是利用 计算机和通信等技术通过向驾驶员提供基于交通信息的最佳行驶路线来达到诱 导出行行为、减少车辆在路上的逗留时间进而实现改善交通和避免交通拥挤、阻 塞的目的。利用它能避免因盲目行驶或凭经验行驶造成的交通阻塞，达到了使路 网畅通、高效运行的目的。它能帮助驾驶员避开拥挤和事故，避免因不熟悉城市 交通环境而迷路，也有利于保障安全。动态交通导航系统包括交通信息的采集处 理与传输、交通状态预测、最优路径选择三个方面。车辆路径导航系统同交通管 理与控制系统融合，不仅可以在大范围内进行交通流疏导，从而缓解道路交通拥 挤状况：此外，还可以向火警车辆、救护车辆与紧急救援车辆提供最优路径引导 服务。最优路径的计算方式分为集中式与自主式两类，前者由中心计算机集中计 算最优路径井将信息发送给车辆，后者由车载计算机根据从通讯网络接受到的实 时交通信息计算出最优路径。路径导航按服务对象类型分为多车导航和单车导 航，前者向众多请求线路引导服务的车辆服务，后者为单个车辆服务。 我国对路径一导航系统的研究起步较晚，目前处于对定位系统、电子地图、 通信系统等问题的研究阶段，投入使用的基本上都是以无线广播为主的初级导航 手段。基于g p s 集群通信和可变标志牌的导航系统正处于研究和实验阶段，而对 比较全面的动态路径导航系统的研究还处于起步阶段。 目前国内针对道路交通的路径优化以及相关的研究很多，就现状而言大体可 以分为两类。一类是基于静态、简单约束交通条件下的路径优化：目前多数的研 究和实际应用都属于此类。国内现有的路径导航系统一般是静态路径导航，一般 6 仅是利用数字地图数据库的信息实现为车辆提供定位信息和静态地理信息等静 态路径导航功能。另一类是基于动态交通条件下的路径优化。与静态路径诱导系 统相比，动态路径诱导系统不同之处在于利用了实时交通信息( 如经过某一路段 所需的时问) ，能够实现更有效的诱导。由于这类研究史接近于真实环境，具有 更大的应用价值和更广阔的研究发展空间，因此动态路径诱导系统是路径诱导系 统发展的必然趋势。 1 3 3 动态交通分配模型的意义与特征 所谓交通流分配就是将已经预测出来的起讫点( o r i g i n - d e s t i n a t i o n ，简称 o d ) 需求按照一定的规则符合实际的分配到网络中的各条道路上，并且求出各条 道路的交通流量。但由于实际网络的复杂性( 一般由很多组0 d 且各组o d 之间的路 径也互相重叠) ，进行交通流分配一直是一项难度很大的工作。 静态交通流分配模型都是以这样的假定为前提条件的，即o d 间的交通需求都 是稳定不变的，交通流分布形态是固定的，路段上分配的交通需求量也是不变的， 这种模型主要针对长期稳态的交通系统，一般只能用于较长时间的交通计划。如 果o d 交通需求是随时间变动的，网络便达不到模型假设的那种均衡。而实际交通 网络上的交通需求具有动态性质，这使得交通网络上的交通流具有动态特性。动 态交通分配模型要考虑时变得0 d 需求，时变得交通条件下的交通行为，这样的模 型显然是极其复杂的，但由于其对i t s 中的动态路径诱导的关键性作用，因此相 关研究具有非常重要的理论与实际意义。 交通流的时变性主要包括： 旅行者出发时间的时变性。旅行者在分析了道路拥挤状况后，会调整出 发的时间或提前或拖后，通过避开高峰期，以减少路上消耗的时间，但要为此付 出代价。 旅行者到达工作地时间( 或目的) 的变性，为提高或延后到达的时间也 要同样付出一定的代价。事实上以上两种决策，都是一个在路上消耗时间与代价 的价值交换。 高峰期间交通流不会是均匀的，静态模型中将交通流视为均匀分布于研 究阶段，会低估旅行时间和拥挤程度。 在0 d 对之间的最短路径应是时变的。这是实时i v i t s 的理论基础。 拥挤发生在不同的时间和地点。这一点在静态模型中体现不出来。最直 观的现象是，上班和下班高峰期间发生的拥挤，在正常期间可能不会出现。 拥挤像一个运动的“瓶颈 ，不是固定的，而是随时空变化的。 用一个简单的例子说明上述问题，参见图( 1 1 ) ，路段3 上的拥挤程度完全 取决于节点1 、2 和3 上运量的进入时刻和相应的路段行驶时间。 7 如果运量在路段1 a 2 f l 勺行驶时间是( f ，一f 1 ) ，在路段2 上的行驶时间就是 ( ，一f ：) ，则高达3 0 0 的运量在，同时刻到达路段3 ，最拥挤，另一方面，假若在 路段1 和2 上行驶时间不等于( r 3 一f 1 ) 和( t 3 - t 2 ) ，则每一个节点上进入网络的 运量1 0 0 不会在同一时刻到达路段3 ，拥挤程度就减小了。若路段上的行驶时间又 是运量的函数，这个问题就极其复杂了，只有动态交通分配模型才有希望解决。 1 0 0 ，l 1 0 0 f 2 1 0 0 ，3 图1 1 交通示意图 对动态交通流模型来讲首先有必要从时间和空间上对非定常交通流做出描 叙。因此，有必要将交通网络划分成更小的空间。另外，时间间隔要取得很短， 时间和空间的划分方法取决于所研究问题的精度要求。但不管怎么说，和静态交 通流相比，计算容量和计算时间都将变得非常大。 1 3 4 动态交通分配与路径诱导之间的关系 动态路径诱导的理论研究是i t s 理论研究的最重要领域之一，其核心内容是 实时动态交通分配理论。动态交通分配是指以随时间变动交通需求为对象的交通 量分配。实时动态交通分配则是基于路网中的一个活动着的交通流预测其短期 内的交通需求进行交通量的分配，在动态路径诱导系统中依据哪种交通信息进行 路径规划，即把什么样的信息提供给用户才能达到避免拥挤、提高路网使用效率 的目的如何在短时间内得到这些信息，以及如何根据这些信息快速确定出最佳 出行路径等都是动态交通分配所要研究的问题。其理论模型与算法的优劣直接影 响动态路径诱导系统进而影响整个智能运输系统的造价与功能。 1 5 本文主要内容 1 5 1 本文主要研究内容 在整个交通规划过程中，路网交通分配具有重要地位。通过动态交通分配可 以将现有出行交通量分配到路网上，了解路网负荷能力，对路网的各种改善方案 8 进行评估，确定道路系统设计流和服务水平，同时可以实时预测路网的交通流量， 引导车辆避开拥堵或即将成为拥堵的地段，为车辆诱导提供依据。传统的动态交 通分配和路径诱导模型及算法随着路网的增加、车流量的增长导致算法的复杂度 和计算时间呈几何级增长，主要问题体现在如下两个方面： 1 ) 加入了实时交通信息后的动态交通分配与路径诱导模型不再是简单的将 预测( 采集) 的数据带入固定模型计算，在模型建立的本身就含有大量的参数计 算，如动态路径阻抗、实时速度预测等，导致模型的建立本身比较复杂。 2 ) 随着模型的复杂性增加，模型的变量增加、维数变大、约束条件变多， 这一系列条件的约束使得对模型的求解变得困难。 从蚂蚁觅食演化而来的蚁群算法由于其具有分布式计算能力、全局优化、易 于与其它算法结合、鲁棒性强等优点，在解决t s p 、q p a 问题方面都有了出色的应 用，同时在动态环境下也蚁群也表现出高度的灵活性和健壮性，尤其是在组合优 化问题方面表现出了较强的搜索解能力，本文将蚁群算法应用于动态交通分配和 路径诱导的模型建立和模型求解，以期利能用蚁群算法本身的优点较好的改进动 态交通分配和路径诱导模型和算法。 1 5 2 论文组织结构 本文分为五章，各章内容按如下方式组织： 第一章介绍智能交通系统的组成与研究状况、动态交通分配与路径诱导的简 介和研究状况，以及本文研究的内容与意义。 第二章具体介绍了传统的蚁群算法以及传统蚁群算法本身存在的问题，在传 统蚁群算法的基础上介绍了改进的蚁群算法基于路径均值的蚁群算法，提出了 路径在信息素更新中的重要性，并且对新提出的算法进行了仿真试验。 第三章对动态交通分配模型的现状以及存在的问题进行了分析，针对经典模 型存在的问题，提出了将改进蚁群算法应用于动态交通分配模型，将实时动态交 通信息加入模型，并用蚁群算法进行模型求解，将蚁群算法的信息素更新方式进 行了改进，加入了实时交通信息。 第四章分析了经典路径诱导算法中的不足，将改进的蚁群算法应用于动态路 径诱导中，并提出了一种新的信息素更新方式，同时考虑t g p s 和g i s 等先进技术 在诱导过程中的应用。 第五章对动态交通分配和路径诱导算法进行了仿真，基于长沙市的交通情 况，对长沙市主要交通干道进行了交通分配，同时仿真了各种条件下的路径诱导 并与经典算法进行了比较，通过实例验证了模型以及算法在实际应用中的改进作 用。 最后对本文的研究工作进行了总结和展望。 9 第一章绪论 上 第二章 蚁群算法及其改进 i ii 卜品配 第四章 路径诱导 il i 长沙市羔要干道动萎妻翥分配及诱导仿真 上 第六章总结 图1 3 文章结构图 1 0 第二章蚁群算法及其改进 2 1 蚁群算法简介 蚁群算法是一种源于生物世界新的仿生类算法n 羽。人们从仿生学的机理中受 到启发，提出了许多用于解决复杂优化问题的新方法，如遗传算法、进化策略、 模拟退火、禁忌搜索算法等，并成功地运用于实际问题。蚁群算法是近年来提出 来的一种新型的模拟进化算法，通过人工模拟蚂蚁搜索食物的过程中个体的信息 交流与相互协作，最终找到从蚁群到食物源的最短路径原理，并成功地应用于解 决t s p 问题，取得了很好的结果。 2 1 1 蚁群算法思想 据昆虫学家的观察和研究发现，生物世界中的蚂蚁有能力在没有任何可见提 示下找出从其窝巢至食物源的最短路径，并能随环境的变化而变化，适应性地搜 索新的路径，产生新的选择。作为昆虫的蚂蚁在寻找食物源时，能在其走过的路 径上释放一种蚂蚁特有的分泌物信息素，使得一定范围内的其他蚂蚁能够察觉 到并由此影响它们以后的行为。当一些径上通过蚂蚁越来越多时，其留下的信息 素轨迹也越来越多，以致信息素强度增大( 当然随时问的推移会逐渐减弱) ，后 来蚂蚁选择该路径的概率也越高，从而增加了该路径的信息素强度，这种选择过 程被称之为蚂蚁的自催化行为。由于其原理是一种正反馈机制，因此也可将蚂蚁 王国理解成所谓的增强型学习系统。这种优化过程的本质在于：( 1 ) 选择机制。 分泌物越多的路径，被选择的概率越大。( 2 ) 更新机制n 羽。路径上的分泌物会随 蚂蚁的经过而增长，而且同时也随时间的推移逐渐挥发消失。( 3 ) 协调机制。蚂 蚁之间实际上通过分泌物来互相通信、协同工作的。蚁群算法正是充分利用了这 样的优化机制，即通过个体之间的信息交流与相互协作找到最优解，使它具有很 强的发现最优解的能力。 。 2 1 2 蚁群算法原理 下面引用d o r i g om 的例子来说明蚂蚁算法的实现原理，如图1 2 所示。蚂蚁要 从巢穴a 去食物源e 。沿途中，h c 为障碍物( 见图1 2 一( a ) ) ，使得蚂蚁在b 点必 选择经由h 到达d ，从而到达e ，或者经由c n 达d 再n e ( 见图1 2 一( b ) ) ，蚂蚁 依据其到达b 之前其他蚂蚁在这两条路径上遗留的信息素的迹的大小选择路径。 假定距离d b h = d d h = i ，d b c = d d c = 0 5 。假设每一个时间间隔里有3 0 只新蚂蚁从a 到b ，同时有3 0 只新蚂蚁从e 至t j d ，每只蚂蚁释放的信息素的迹为1 ，信息素在一 个时间间隔里会全部挥发掉。t = 0 时，各条路径上信息素的迹均为0 ，3 0 只蚂蚁在 点b ，3 0 只蚂蚁在点d ，选择哪条路径完全随机。从统计学的角度可以认为选择 b c 、b h 、d c 、d h 的蚂蚁数均为1 5 ，t = l 时，3 0 只新蚂蚁从a 出发到达b ，而此 时b h 上面的信息素的浓度为1 5 ，b c 上的浓度为3 0 ( 有1 5 只蚂蚁经由c n 达b ，并 且有1 5 只蚂蚁经由c n 达了d ) 。这样，这3 0 只新蚂蚁中就有2 0 只选择路径b c d ， 而只有1 0 只选择b h d 。从e 出发到达d 点的3 0 只蚂蚁中选择d c 和d h 的分别为2 0 只和1 0 只。随着时间的推移，蚂蚁会以越来越大的概率选择这条最短路径b c d ， 而废弃其他较长的路径n 朝。 。 d h d ( a ) 点间距离 0 5 ch o 5 ch ( b ) t = 0 时刻( b ) t = 1 时刻 图1 2 蚁群系统示意图 c 蚂蚁算法中的人工蚂蚁它具备真实蚂蚁所不具备的特征：记忆性能够记忆其过去的 行为信息；非盲目性选择路径时按照一定规律寻找最短路径；离散性存在于离散的 环境中，从一个离散状态转移到另一个离散状态。 2 2 蚁群算法一般模型 蚂蚁系统是最早的蚁群优化算法，是大量蚁群算法的原型，为了说明蚂蚁系 统模型，我们首先引入经典优化问题旅行商问题( t s p ) 。旅行商问题的实质是： 已知1 1 个城市和两两城市之间距离，旅行商出发访问其中的每座城市，要求总行 程最短。其图论描述为：给定图g = ( v ，a ) ，其中v 为顶点集，a 为各顶点相互连 线组成的边集，已知各顶点之间的连接距离，要求确定一条长度最短的h a m i l t o n 的回路，即遍历所有顶点当且仅当一次的最短回路。具体来讲，问题是指对于给 定的n 个城市集合( 1 ，2 ，n ) ，找到一条经过每一个城市一次且回到起点的最小花 费的封闭环路。问题的目标函数是n 引： 一条经过每一个城市一次且回到起点的最小花费的封闭环路。问题的目标函 1 2 数是： n - i m i n d = d ( i ，f + 1 ) + d ( 甩，1 ) ( 2 1 ) i - i 其中n 代表n 个待遍历的城市，d ( i ，f + 1 ) ( i = 1 ，2 ，n ) 表示城市i 和城市i + l 之间的距离，d ( n ，1 ) 表示从第个城市回到起点城市地距离。现给定一个n 城市的 t s p 问题，蚁群中蚂蚁的数量为m ，以此来建立蚁群算法的模型n 引。 为了描叙方便，引入如下的符号和概念： 以( i ，j = 1 ，2 ，n ) 为城市和城市之间的距离； 6 。( f ) 为t 时刻位于城市的蚂蚁个数，即所= b 。( f ) ( 江1 ，2 ，一，力) ； l = l ( t ) 为t 时刻边( i ，j ) 上的信息素浓度 巩为边( i ，j ) 的能见度( v i s i b i l i t y ) 或理解为由城市i 转移到城市j 的启发信息， 该启发信息由要解决的问题给出，在t s p 问题中一般取砜= l d ，。 口为信息启发式因子，反映蚂蚁在运动过程中所积累的信息量在指导蚁群