（交通信息工程及控制专业论文）城市交通路径诱导算法研究.pdf

摘要 智能交通系统就是将先进的计算机技术、通信技术、数据库技术、人工智能 技术等运用于交通运输中，用以解决交通拥挤，提高交通网络的使用效率。动态 路径诱导作为智能交通系统的关键技术之一，其主要功能是辅助驾驶员为到达目 的地而选择最优路径。本论文根据出行者需求和道路通行能力，研究动态路径优 化问题，即为了获得两点之间的距离最短、时间最短、费用最小的最优路径。相 比于传统静态诱导系统中简单的物理意义上的路径最短或静态时间最短，具有重 要的理论意义和工程应用价值。本文的研究工作和成果如下： 1 、针对动态路网的路径诱导问题，通过分析经典d i j k s t r a 算法、f l o y d 算法 和启发式搜索算法，发现经典算法不满足动态路径诱导的最优路径求解，研究利 用遗传算法解决动态路网的优化方法。 2 、针对标准遗传算法在动态最优路径求解时存在局部极点、全局收敛慢等问 题，研究了适用于动态最优路径求解的改进自适应遗传算法，通过改进算子选择、 自适应遗传率和变异率，解决了局部极小和收敛速度慢的问题，仿真结果验证了 算法的正确性和有效性。 3 、对城市路网模型和车辆路径模型进行建模，把改进的自适应遗传算法应用 到动态交通条件下路径诱导的最优求解，并与标准遗传算法、简单的自适应遗产 算法进行仿真比较，结果验证了改进自适应遗传算法用于动态最优路径计算、效率和 实用性方面的优势。 关键词：智能交通系统，路径诱导，遗传算法，动态最优路径，自适应算法 a b s t r a c t 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 mi sa p p l i c a t i o no fa d v a n c e dc o m p u t e rt e c h n o l o g y , c o m m u n i c a t i o nt e c h n o l o g y , d a t a b a s et e c h n o l o g ya n da r t i f i c i a li n t e l l i g e n c et e c h n o l o g yt o t r a n s p o r t a t i o nt os e t t l et r a f f i cc o n g e s t i o n ，r a i s ee f f i c i e n c yo fu t i l i z a t i o no ft r a f f i cn e t w o r k d y n a m i cr o u t eg u i d a n c ei ni 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 sa so n e o ft h ek e yt e c h n o l o g i e s ， i t sm a i nf u n c t i o nh e l p st h ed r i v e r st os e l e c to p t i m a lr o u t e t h i sp a p e ri n v e s t i g a t e st h e d y n a m i cp a t ho p t i m i z a t i o np r o b l e ma c c o r d i n gt ot r a v e l e rd e m a n da n dr o a dc a p a c i t y t h e r o u t em a yb es h o r t e s tr o u t eo fd i s t a n c e ，s h o r t e s tr o u t eo ft i m e ，s h o r t e s tr o u t eo fe x p e n s e c o m p a r e dw i t ht h et r a d i t i o n a ls t a t i ci n d u c t i o ns y s t e mo nas i m p l ep h y s i c a lm e a n i n go rt i m e s t a t i cs h o r t e s tp a t h ，d y n a m i cp a t ho p t i mi z a t i o nh a si m p o r t a n tt h e o r e t i c a la n de n g i n e e r i n g a p p l i c a t i o nv a l u e i nt h i sp a p e r ，t h er e s e a r c hw o r ka n dr e s u l t sa le a sf o l l o w s ： ( 1 ) b ya n a l y z i n gt h ec l a s s i c a ld i j k s t r aa l g o r i t h m ，f l o y da l g o r i t h ma n d h e u r i s t i cs e a r c h a l g o r i t h m ，i tc a nb ef o u n dt h a tt h ec l a s s i c a la l g o r i t h m sa l en o ts a t i s f i e dw i t hd y n a m i cr o u t e g u i d a n c et os o l v et h eo p t i m a lp a t h i no r d e rt od e a lw i t ht h i sp r o b l e m ，d y n a m i co p t i m i z a t i o n a l g o r i t h mu s i n gg e n e t i ca l g o r i t h mi sp r e s e n t e dt os o l v et h eo p t i m a l r o u t e ( 2 ) s t a n d a r dg e n e t i ca l g o r i t h me x i s t sl o c a le x t r e m ep o i n t s ，s l o wg l o b a lc o n v e r g e n c ei n s t u d y i n gt h ed y n a m i co p t i m a lr o u t i n gp r o b l e m ，a ni m p r o v e do p e r a t o rs e l e c t i o na n da d a p t i v e g e n e t i cv a f i a t i o nr a t e a l ee m p l o y e dt os o l v et h e s ei s s u e s s i m u l a t i o nr e s u l t sv e r i f yt h e c o r r e c t n e s sa n de f f e c t i v e n e s so ft h ei m p r o v e da l g o r i t h m ( 3 ) b a s e do nt h em o d e lo fu r b a nr o a dn e t w o r ka n dt r a f f i cp a t h ，t h ei m p r o v e da d a p t i v e g e n e t i ca l g o r i t h mi sa p p l i e dt os o l v et h ep r o b l e mo fd y n a m i co p t i m a lp a t h c o m p a r i n gw i t h t h es t a n d a r dg e n e t i ca l g o r i t h mo fs i m p l ea d a p t i v eg e n e t i ca l g o r i t h m ，s i m u l a t i o nr e s u l t sv e r i f y t h a tt h ei m p r o v e da d a p t i v eg e n e t i ca l g o r i t h mi se f f i c i e n ta n dp r a c t i c a la d v a n t a g e si n c a l c u l a t i n gt h ed y n a m i co p t i m a lp a t h k e yw o r d 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 ，r o u t eg u i d a n c e ，g e n e t i c a l g o r i t h m ，d y n a m i co p t i m a lp a t h ，a d a p t i v e a l g o r i t h m n 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究工 作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任何 未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：岱碍 洳p 夕年，月棚 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成 果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名： 导师签名： 必b ，年2 - 月多日 ? 卯庳j 月，日 | 长安大学硕士学位论文 第一章绪论 1 1 选题背景 伴随着我国改革开放的不断深化，城乡经济更加繁荣，城市规模也在日渐扩 大，我国机动车拥有量及道路交通量同时也迅速增加。尽管我国各省、自治区和 直辖市的道路建设和交通管理也在不断发展和改善，但也有一些道路设施及交通 管理设备得不到及时更新，交通管理手段相对落后，加上交通参与者的安全意识 淡薄，导致目前城市道路交通普遍存在以下问题： 1 ) 交通拥挤。当今，交通堵塞已经成为世界各大城市的通病。交通堵塞不仅 浪费时间，而且造成燃料浪费，加重大气污染。世界许多城市交通高峰时的车速 从8 0 年代以来一直下降。在我国，差不多所有大城市都存在严重的交通拥挤问题。 2 ) 交通事故。交通事故不但造成巨大的经济损失，而且给受害者带来精神痛 苦。据公安部官方统计，2 0 0 8 年，全国共发生道路交通事故2 6 5 2 0 4 起，造成7 3 4 8 4 人死亡、3 0 4 9 1 9 人受伤，直接财产损失l o 1 亿元。因此，如何减少交通事故己成为 全世界亟待解决的重大社会问题。 3 ) 大气污染。由于交通运输业迅速发展，致使机动车的保有量急剧增加，排 放的废气严重地污染了环境。虽然采取了不少治理措施，但机动车数量不断增加， 至2 0 0 8 年底全国机动车保有量为1 6 9 8 8 7 7 4 4 辆，大气污染状况改善非常困难。 4 ) 消耗能源。交通运输消耗大量的能源。在当前的能源结构中，石油占有重 要地位。据专家预测，石油储量只够使用4 0 - 5 0 年，石油资源短缺将成为全球所共 同面临的问题。而交通运输大约消耗世界石油总产量的一半。 在大城市，以上的问题尤为严重。交通问题现如今已成为影响城市功能正常 发挥和城市可持续发展的一个全局性问题。城市交通系统智能化作为城市交通研 究的一个主要发展方向，可以引导城市的有序发展、促进城市土地资源的合理开 发利用，从而降低城市基础设施建设费用，提高城市相关设施的利用率及经济价 值。城市交通智能化最大的吸引力还在于它已成为解决现代城市所面临的诸多困 扰和环境保护问题的一个有效途径。这不但可以减少能源需求，降低城市机动车 尾气排放和噪音污染，而且因为它有潜力节省大量的土地，所以能促进城市结构 和城市布局的合理性，实现城市环境和城市经济的同步改善。 第一章绪论 1 2 智能交通系统发展简介 交通问题作为全球共同面临的问题，正引起世界各国的重视，如何更好地减 少交通拥挤，以便提高交通效率，降低环境污染，是近年来的一热点问题。在解 决交通问题的过程中，人们逐渐地认识到仅仅依靠多修路已不能满足实际的需要， 而应采用现代化的高新技术来改变落后的交通控制及管理方法，从而最大程度地 提高通行效率，并且提出了“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 是在关键基础理论模型的前提下，把先进的信息技术、数据通信 传输技术、电子控制技术及计算机处理技术等有效地结合运用于整个交通管理体 系，将人、车、路三者有机协调的结合起来，以达到最佳的和谐统一，从而建立 起一种大范围、全方位发挥作用的实时、准确、高效的交通运输管理系统【1 1 。 智能交通系统的发展起步于6 0 7 0 年代，相关的i t s 项目在当时有美国的e r g s ( e l e c t r o n i cr o u t eg u i d a n c es y s t e m ，电子路线引导系统) 、欧洲的c o s t 3 0 ( c o o p e r a t i o ni nt h ef i e l do fs c i e n t i f i ca n dt e c h n i c a lr e s e a r c h ，科学技术领域研究协 会) 、日本的c a c s ( c o m p r e h e n s i v ea u t o m o b i l ec o n t r o ls y s t e m ，汽车综合控制系 统) 等。 2 l 世纪八十年代末以来，日本、美国、欧洲等发达国家为了解决所面临的交 通问题，竟相的发展智能交通系统，投入大量的资金和人力进行道路功能和车辆 智能化的研究，以便在未来的市场上占据有利地位，起初称之为“智能车辆道路 系统( 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 s - - i v h 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 ) 。 1 9 8 6 年，欧洲开始积极实施以欧盟( e u ) 及各相关国政府为主导的智能交通 系统研究项目d r i v e ( d e d i c a t e dr o a di n f r a s t r u c t u r ef o rv e h i c l es a f e t yi ne u r o p e ， 欧洲汽车安全专用道路设施) 和民间为主导的p r o m e t h e u s ( p r o g r a mf o ra e 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 ya n du n p r e c e d e n t e ds a f e t y ，欧洲高效安全道 路交通计划) 。 日本在c a c s 后，从8 0 年代后半期，发展了以建设省为主导的路车间通信系统 r a c s ( r o a da u t o m o b i l ec o m m u n i c a t i o ns y s t e m ：1 9 8 4 1 9 8 9 ) 和以警察厅为主导 的新汽车交通信息通信系统a m t i c s ( a d v a n c e dm o b i l et r a f f i ci n f o r m a t i o na n d 2 长安大学硕士学位论文 c o m m u n i c a t i o ns y s t e m s ：1 9 8 7 1 9 8 8 ) 。9 0 年代，日本参加了以美国为主导的i t s 国际化工作。到1 9 9 6 年，日本已经有相当大数目的大小项目在开展，从理论规划 到实际的实施，从现场试验到形成产业，其发展规模和速度咄咄逼人。目前日本 在i t s 项目上已经形成了官方、民间、学术机构相协调的体制，这对日本i t s 的发 展起到了很大的推动作用。 美、欧、日在i t s 方面的研究各有侧重，研究体系稍有不同，但大体一致。 其中美国的i t s 研究开发体系最为完善，受到国际i t s 研究领域的广泛认可，其 研究分类和各自的研究内容【2 3 “1 如表1 1 所示。 表1 1i t s 的研究分类和各自的研究内容 研究类别主要研究内容 先进的交通管理系统1 ) 市区域的中央化交通信号控制系统 ( a t m s - a d v a n c e dt m f n c2 ) 高速公路管理系统 m e s s a g es y s t e m ) 3 ) 交通事故管理系统 4 ) 电子收费及交通管理系统 1 ) 出行者信息系统 先进的出行者信息系统 2 ) 车载路径诱导系统 ( a t i s a d v a n c e dt r a v e l e r 3 ) 停车场停车引导系统 i n f o r m a t i o n s y s t e m ) 4 ) 电子地图数据库 先进的乡村运输系统 1 ) 出行者的安全与保护 ( a r t s _ a d v a n c e dr u r a l2 ) 紧急情况管理系统 t r a n s p o r t a t i o ns y s t e m ) 3 ) 旅游和出行者信息服务系统 4 ) 基础设施的运营和保养 5 ) 商业车辆运营 6 ) 车队运营与管理系统 7 ) 公共性的出行者服务系统 商业车辆运行1 ) 出行者的安全与保护 ( c v o o m m e r c i a lv e h i c l e s2 ) 紧急情况管理系统 o p e r a t i o n s ) 3 ) 旅游和出行者信息服务系统 第一章绪论 4 ) 基础设施的运营和保养 5 ) 商业车辆运营 6 ) 车队运营与管理系统 7 ) 公共性的出行者服务系统 先进的车辆控制和安全系统1 ) 防碰撞系统 ( a v c s s “d v a n c e dv e h i c l e s2 ) 智能化行车控制系统 c o n t r o ls e c u r i t ys y s t e m s )3 ) 驾驶员视野加强系统 4 ) 车辆防抱死系统a b s 5 ) 驾驶员安全监控系统 6 ) 车辆安全监控系统 7 ) 车载路线诱导系统 8 ) 协作驾驶 自动公路系统a h s 有三种研究理念： ( a h s - - a u t o m a t e dh i g h w a y 1 ) 基于车辆智能化的匿名驾驶系统 s y s t e m s ) 2 ) 基于公路基础设施智能化的公路控 制系统 3 ) 前两者的综合 日本在这方面的研究最为先进内容 有： 1 ) 公路与车辆、车辆与车辆之间的通 信 2 ) 事故检测警告 3 ) 使用视频雷达的车辆 4 ) 最大速度控制 5 ) 自动停车控制 相对而言，我国在i t s 领域的研究起步比较晚。在本世纪7 0 年代建立了电子 信息技术、科技情报信息、自动控制等方面的研究机构。迄今为止已经取得了以 道路桥梁自动化检测、道路桥梁数据库、高速公路监控系统、高速公路收费系统、 交通与气象数据采集自动化系统等为代表的一批成果。尽管如此，由于研究的分 4 长安大学硕士学位论文 散加上研究水平所限，形成的多数研究项目是针对交通运输的某一局部领域而进 行的，缺乏一项综合性的、具有战略意义的研究项目。i t s 项目恰恰是覆盖这些领 域的一项综合性技术，通过i t s 可以将原来一些互不相干的项目有机的联系在一 起，使公路交通系统在规划、建设、管理、运营等方面工作在更高层次上协调发 展，使公路交通发挥出其更大的效益。北京、上海等一些特大型城市，为解决人、 车和路之间日益突出的矛盾，已提出了一系列交通规划，均将智能交通系统列为 重大研究项目。一方面，北京、上海、广州等大城市陆续的从国外引进了一些先 进的城市交通控制、道路监控等系统；另一方面，还加大了自主研发的步伐，如 国家计委、科委组织开发的系统。1 9 9 8 年，交通部正式成立了中国交通委员会， 秘书处就设在交通智能运输系统工程研究中心。代表中国参加相关国际智能交通 系统的标准化活动，现在正着力于中国智能运输系统标准体系框架的研究，在此 之外，我国从2 0 0 3 年起在全国3 6 个城市实施以实现城市交通智能控制为主要内容 的。畅通工程一，并逐步的推广到1 0 0 个城市。 1 - 3 车辆路径诱导系统研究现状 车辆路径导航系统( 也称路径诱导系统) 是a t i s 最重要的功能子系统之一， 车辆路径导航系统是应用全球定位系统技术( g p s ，g l o b a lp o s i t i o n i n gs y s t e m ) 、 电子交通图( e l e c t r o n i cm a po f t r a f f i cn e t w o r k ) 、计算机技术、多媒体技术和通信 技术的一个综合系统。它通过向驾驶员提供基于实时交通信息的高效、实时的路 径选择和路径选择方案来达到诱导出行者出行行为，以减少车辆在道路上的逗留 时间，进而实现整体的改善城市交通和避免交通拥挤和阻塞的目的。车载导航计 算机系统、无线通信设备、车辆定位模块、导航电子地图数据库、人机交互等设 备构成了车辆路径诱导系统的主要硬件设备。典型的车辆路径诱导系统如图1 1 所 示由八个主要功能模块构成。 第一章绪论 图1 1 车辆路径诱导系统框架图 目前国际上的i t s 研究形成了日本、美国和欧洲三大阵营，对车辆路径诱导 系统的研究也是如此。 日本的车载路径诱导系统在世界上处于领先地位。1 9 7 3 年命名为c a c s ( c o m p r e h e n s i v ea u t o m o b i l et r a f f i cc o n t r o ls y s t e m ，全方位汽车运输控制系统) 的项目首先开展了基于r f 射频通信的车载动态路径诱导系统的开发实验，得到了 可以减少1 3 的行程时间的结论。1 9 9 0 年开始的r g s ( r o u t eg u i d a n c es y s t e m ) 项 目在日本建立了全球第一个进行交通信息服务的通信系统，r g s 是一项不以赢利 为目的的项目。r g s 在1 9 9 6 年4 月正式开始使用，信息服务r g s 播发的动态交通 信息包括：主要地点之间的行程时间、交通拥挤、事故、广域的最短路径选择信 息及道路施工、天气情况和停车场信息等。目前，高档的r g s 车载接收机结合了 差分g p s ( g l o b a lp o s i t i o ns y s t e m ，全球定位系统) 和f m 调频载波接收功能，可 以进行车辆导航和路径诱导。和r g s 的免费信息服务形成对照的是东京的a t i s 的有偿信息服务。1 9 9 3 年7 月，东京政府和私人公司凭借建立a t i s 公司来提供优 质服务的动态交通信息。1 9 9 4 年2 月，a t i s 公司利用双向通信开始投入使用的a t i s 系统由a t i s 中心和a t i s 终端组成，a t i s 每5 分钟从各种信息源获得交通信息， 整理后将其传给a t i s 终端，终端用电子地图显示交通拥挤程度并以此推荐一条最 快路径。 6 长安大学硕士学位论文 美国的“旅行技术 t r a v t c k 和“先进的驾驶员咨询与车辆导航概念 a d v a n c e 是两个比较典型的自治型路径诱导的系统项目。t r a v t e k 是由美国联邦公路委员会、 佛罗里达交通部门及奥兰多市等政府部门和通用汽车及美国汽车委员会等私人合 作者联合开发出的路线引导系统。t r a v t e k 给用户提供车辆当前位置、动态交通信 息路线选择等丰富的信息服务，帮助驾驶员安全、快速地穿过车流拥挤地区。 t r a v t e k 系统由三大部分组成，如图1 2 示：( 1 ) t r a v t e k 信息和服务中心( t i s c ) 由美国汽车委员会负责建立和管理。( 2 ) 交通管理中心( t m c ) ，由相关政府部门 负责建立和管理。( 3 ) 装备有计算机通讯设施的车辆( 称为t r a v t e k 车辆) ，包括 车内系统的所有硬件、软件及通讯设备都由通用汽车公司提供。这三部分利用电 话线路8 0 0 m h z 的调频广播和自动蜂窝电话等数字通讯方式相联系。a d v a n c e 是一 个a t i s 示范工程，车辆利用差分g p s 导航以及定时计算、地图匹配来引导路径。 而这些车辆作为一个探测器，将动态通行信息传至交通信息中心，中心将这些信 息传送给其它车辆来帮助它们进行动态路径选择。 各种数据源( 如 传感器) 交通管理中心 事件 地图更新信息 各种服务信息( 旅 馆、饭店等) 唑算p 和服h 地画石i 务中心l l：二二 交通信息( )信息与服务请求( 尸) 务( ) 蜂窝电话通讯 图1 2 t r a v t e k 系统构成 欧洲的路径诱导系统的研究最初是基于红外信标通信展开的，德国和英国分 别在8 0 年代末开发出了用于示范的l i s b 系统及a u t og u i d e 系统，之后英国推出了 全球第一个商用车载路径诱导系统t r a f f i cm a s t e r 。进入九十年代后，德国西门子 公司基于l i s b 开发的a l i s c o u t 系统具有一定的国际影响，它不但安装于德国柏 7 第一章绪论 林等欧洲城市，还应用到美国m i c h i g a n 的o a k l a n dc o u n t r y ，该系统是基于红外信 标通信方式的中心决定式的路径诱导系统。德国斯图加特的s t o r m 项目则致力 于开发双模式路径诱导系统：即在安装红外信标的区域开发基于红外信标的中心 决定式的路径诱导，同时在广域内研究基于r d s t m c 交通广播的路径诱导。 我国对路径诱导系统的研究起步比较晚【4 1 ，目前处于对定位系统、电子地图、 双向通信等系列问题的研究阶段。上海同济大学和上海交警总队1 9 9 5 年合作完成 的多段接力式动态标志路线引导系统，就是通过可变标牌和交通广播电台来实现 路径诱导。该系统采用在相邻交叉口前设置一些显示多路段交通信息的可变标牌， 就好像接力棒那样，通过各个交叉口上的多路段的动态交通信息，把车辆逐段印 导到不拥挤的路段上，到达目的地。哈尔滨工业大学利用g p s 和集群通信系统设 计的实验性的指挥调度系统，适合于公安、消防、电力等作分组调度使用。由通 信中心、手持机用户和车载机用户组成常规的集群通信系统。由清华大学、北京 人民广播电台和中科院遥感所联合研制的广播调频幅载波车辆导航系统，使用调 频广播传送差分g p s 信号来供车载接收机修正自身位置，该系统在目前只能提供 车辆定位功能和静态地理信息。由吉林工业大学牵头开发的城市交通流诱导系统 u t f g s ( u r b a nt r a f f i cf l o wg u i d a n c es y s t e m ) 是我国的第一个动态路径诱导系统 研究项目，u t f g s 根据我国混合交通的特点，以城市交通面控系统资源为依托， 是基于实时交通信息的出行者信息和分布式动态路径诱导系统。这是一种结合我 国实际情况，考虑到长远发展的较全面的系统，是我国“九五”国家自然基金重 点开发项目。目前u t f g s 的研究己经提出了系统框架，但距整个系统的完善和投 入实际应用还需要一定的时间。跟据介绍，“动态非车载导航一是相对于“静态车 载导航”而言，即导航信息不是由车载终端产生，而是来源于远程中心的。其最 大好处就是能根据城市道路实时的拥堵情况给出合理的路线。 总体来看，我国对车辆导航系统的研究和应用大多是以无线电广播为基础的 初级诱导手段，基于g p s 、集群通信、可变标牌的诱导系统现处于研究和试验阶 段，而比较全面的车辆路径诱导系统的研究成果尚未见报道。 路径优化是车辆导航系统中的一项关键技术。目前国内对道路交通的路径优 化以及相关的研究很多，大体的可以分为两类。一类是基于静态、简单交通条件 下的路径优化【5 】：目前多数的研究和实际应用都属于此类【6 7 】。国内现有的路径导 航系统一般是静态路径诱导，一般仅是利用数字地图数据库的信息来实现为车辆 8 长安大学硕士学位论文 提供定位信息和静态地理信息等静态路径导航功能【8 】。另一类是基于动态交通条 件下的路径优化【9 】。与传统静态路径诱导系统相比，动态路径诱导系统的不同之 处在于利用了实时交通信息( 如经过某一路段所需的时间) ，能够实现更有效的诱 导。由于这类研究更加接近于真实环境，具有更大的应用价值及更广阔的研究发 展空间，因此动态路径诱导系统必将路径诱导系统发展的趋势。 发展i t s 的一个关键问题就是提供实时的交通流信息，减少交通拥挤。而减 少车辆的通行时间是减少交通拥挤的一个很重要的前提，驾驶员也希望能得到在 当前交通条件下避开交通拥挤，寻找动态最短路径。然而，在以往的路径研究中， 一个重要的参数一路径运行成本( 时间) 常常被设定为静态的，在路径的制定和 执行过程中不发生变化。但是，在实际车辆的行驶过程中，由于交通管理、交通 流量、交通事故、天气变化等诸多因素的影响，行驶速度总是在不断变化，导致 路网中各个路段上的运行成本( 时间) 也就相应地发生变化。这种动态变化的情 况对动态路径优化问题的研究具有极其重要的意义，而传统静态网络下的路径问 题研究方法显然无法解决。随着计算机通信和信息处理技术的不断进步以及智能 交通系统的日益完善，实时获取和处理交通信息己经成为可能，这为在动态路网 中研究车辆路径问题提供了有利条件。 基于动态交通条件下的路径优化问题，目前产生了一些不同研究方法。 1 ) 数学优化方法。即利用数学优化模型描述路径优化问题，理论上可以保证 解的最优性，在实际应用中有一些困难，因为实际中的许多因素不能完全形式化， 这样得到的最优解与真正的最优解可能存在一些偏差。 2 ) 现代启发式算法。这类算法是模拟自然界中的“优化”现象研究出的一类 较新的优化求解算法，适用于求解组合优化问题和目标函数问题及某些约束条件 不可微的非线性优化问题。它相比而言较接近于人类的思维方式，易于理解，用 这类算法求解组合优化问题得到最优解的同时也可以得到一些次优解，便于规划 人员研究比较。此类算法主要有：模拟退火算法、遗传算法、t a b u 搜索法、蚂蚁 算法等【1 0 】。虽然这些算法是近似方法，但它们的求解速度快，可以满足解决实际 问题的需要，而且有很多通过优化设计，便可以得到最优解，因此对此类算法的 研究目前颇受重视。 遗传算法( g e n e t i c a l g o r i t h m ，简写g a ) 在最优化、特别是组合优化问题中 的应用是近些年来的一个热点课题。遗传算法模拟生物遗传和进化的过程。它把 9 第一章绪论 类似于遗传基因的一些行为，例如交叉重组、变异、选择和淘汰等机制引入到求 解过程。遗传算法在计算过程中同时保留若干个局部最优解，通过两个或多个解 的交叉重组和单个解的变异来寻找整体最优解。 1 4 论文的研究内容 动态路径诱导系统是一个比较复杂和庞大的系统，即便是其中一个子系统的 研究，往往也涉及到大量的内容和研究工作。笔者通过查阅资料，从国内外研究 现状可以看出，即使是目前开发最为成功的诱导系统，同样也存在着各种各样的 不足。因此本论文的研究工作为：针对当前动态路径诱导系统实用性的关键技术 一路线优化为核心介绍了一些经典的路径优化算法，重点研究适于动态路径诱导 的路线优化算法。本论文研究的内容主要有以下几个方面：介绍了d i j k s t r a 、f l o y d 、 a 等经典最优路径算法的计算思想，分析了其局限性。对遗传算法进行了介绍， 针对传统遗传算法往往陷入早熟、局部搜索能力差的问题进行了改进，并通过实 例进行仿真证实了该算法的有效性。对动态路网模型进行了分析，并把改进的遗 传算法应用于动态路网，给出了基于改进遗传算法动态最优路径的算法。 1 - 5 论文的章节安排 车辆动态路径诱导系统的研究是智能交通系统研究领域的重点问题之一，而 路径诱导算法是车辆路径诱导系统的关键问题之一。有效的诱导算法有利于提高 快速路径搜索能力，更好的解决动态实时的交通信息所带来的各种问题。 论文各章内容安排如下： 第一章描述了路径诱导系统的研究背景，然后概述了国内外对此研究现状， 介绍了研究动态路径诱导系统算法的目的与意义，最后对本文的主要研究内容进 行了概括。 第二章介绍了最短路径算法。主要介绍了传统最短路径算法的概念、应用及 其分类，介绍了几种经典的最短路径算法的基本思想。并对传统的最短路径算法 的适用条件进行了分析，指出其局限性。 第三章介绍了本文求取动态最优路径选用的算法：遗传算法，对该算法的原 理、流程、优缺点进行了介绍。并对其存在问题进行了改进，用实例证明了改进 l o 长安大学硕士学位论文 算法的有效性。 第四章分析了动态车辆路网模型，并给出了动态路径中路段通过时间的计算 方法。 第五章基于改进遗传算法进行了车辆动态路径的优化的算例计算和分析。 第六章对全文工作进行了总结，并进一步的研究方向进行了展望。 第二章 路径优化算法简介 2 1 引言 第二章路径优化算法简介 在车辆导航系统中，路线优化子系统是其中的一个核心子系统，它可以帮助 驾驶员在出行前或在出行中确定行驶路线。 在数学上，最短路径问题( s h o r t p a t hp r o b l e m ) 描述如下：若网络中的每条边 都有一个数值( 长度、成本、时间等) ，则找出两节点( 通常是源节点和阱节点之 间总权值最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之 一。 城市路网可以看作一个加权有向图，节点代表路口，边表示街道或道路，权 代表两个路口间街道的运行距离或运行时间。 在对路网进行描述时，我们常用结点( n o d e ) 来代表道路的交叉口，用路段 ( s e g m e n t ) 来表示两结点之间的道路，用出行费用( t r a v e lc o s t ) 来代表车辆在某 个路段上的消耗。在数学上，结点一般被称为节点( v e r t i c e s ) ，路段一般被称为边 ( e d g e ) 或弧( a r c ) ，出行费用则被归纳成边或弧的权重( w e i g h t ) 。在规定了结 点、边弧和边弧的权之后，路网就转化为一个赋权图赋权有向图。确定路网中 最优路线便转化为图论中的最短路问题。 我们用大写的字母0 来描述算法的运行时间，称之为某算法的时间复杂度 ( t i m ec o m p l e x i t y ) 。例如，设某一算法的输入量为n ，用0 ( n ) 表示该算法运行 时间和n 成正比，而0 ( n 2 ) 则表示该算法的运行时间和1 1 2 成正比。 路径优化算法的应用非常的广泛。最优路径问题( 包括最短路径问题) 因其 具有实际的应用背景，尽管考虑的因素和限制的条件比经典最短路径算法复杂很 多。但是，它的核心思想还是源于经典最短路径算法。 2 2 算法分类 由于问题特征、网络特性等的复杂性，最短路径的算法表现出多样性。总体 说来，最短路径算法可按问题类型、网络特征和求解技术进行分类1 。 长安大学硕士学位论文 ( 1 ) 按问题类型进行分类：按照起点、终节点和路径的数目和特征，最短路 径问题可分为5 种类型，分别为单对节点之间的最短路径、所有节点之间的最短 路径、k 最短路径、动态最短路径及指定必经节点的最短路径问题，其中还可衍生 出其它的特殊最短路径问题，如限制环段数目的最短路径、含环的最短路径等。 分类体系如图2 1 所示。 图2 1 基于问题类型的最短路径算法分类 ( 2 ) 按拓扑结构的网络特征进行分类：在研究不同类型的最短路径问题时， 所选用的拓扑结构的网络特征也不同，例如在分析交通道路网的拓扑结构时，一 般的都是分析稀疏网络，而在研究互联网路由器的寻址问题，一般都用带环的稠 密网络。最短路径问题可按照图2 2 所示体系进行分类。 第二章路径优化算法简介 图2 2 基于网络特征的最短路径算法分类 ( 3 ) 按路径问题的实现技术进行分类：按技术分类一般有以下几种，有路径 搜索技术、预处理技术、路径记录及重构技术和更新技术。其中路径搜索技术又 可分为组合技术和代数方法两种。组合技术通常用标号算法( l a b e l i n g a l g o r i t h m s ) 。标号算法也是多数路径寻优问题核心的部分。按照不同标号节点策 略，标号算法又可以分为标号设定( l a b e ls e t t i n g ) 和标号改正( l a b e lc o r r e c t i n g ) 两种体系。代数方法则通过运筹学中的线性规划形式化、定义代数系统中的联立 线性方程集合形式化及矩阵乘法等一系列方法来求解最短路径问题。具体的分类 如图2 3 所示。 1 4 长安大学硕士学位论文 1 1 1 2 3 基于实现方法的最短路径算法分类 2 3 几种常用最短路径算法 这一类算法的研究是最悠久的，当路网中的权值为一个常量时( 固定值、不随时间 变化) ，这样的路网称为静态路网，相应的求解路网中两点之间的最短路径，或者是从 源结点到所有其他结点的最短路径，或者所有结点之间最短路径的算法称之为静态最短 1 5 第二章路径优化算法简介 路径算法，这类算法属传统的最短路径算法，人们对这类问题的研究已经有相当的历史， 美国著名的数学家，动态规划的鼻祖e w d i j k s t r a 在1 9 5 9 年提出了著名的、具有深远 影响的最短路径算法d i j k s t r a 算法。人们继d i j k s t r a 开创性的工作中提出了许多求解最 短路径问题的方法，其理论不断发展，产生了大量的算法。较常用的主要的有d i j k s t r a 算法、f l o y d 算法、a 算法、双向搜索算法等【1 2 】 2 3 1m j k s t r a 算法 迪杰斯特拉( d i j k s t r a ) 算法是由荷兰数学家e w m j k s t m 在1 9 5 9 年提出的一个适 用于非负权网络的单源最短路径算法，是目前求解最短路径问题理论上最完备、应用最 广泛的经典算法，它可以求出从某指定节点到图中所有其他节点之间的最短路径。 d j i k s t m 算法是一种基于贪心策略的最短路径算法，它的主要思想是按照路径长度 逐点增长的方法构造一棵路径树，由此得到从该树的根节点( 即指定起点) 到其他所有 节点的最短路径。具体做法是：设集合s 中存放已经求出的最短路径的终点，在初始状 态时，集合s 中仅有一个源点v 0 。以后每求出一条最短路径( v o ，v k ) ，就将v k 加 到集合s 中，直到全部顶点都加入s 中为止。 在这里我们引入一个辅助向量d ，它的每个分量d i 表示当前所有已找到的从源点v o 到其他顶点v i 的最短路径长度。其初始状态为：若从v o 到v i 有弧，则d i 为弧上的权值， 不然则令d i 为。设第一条最短路径( v 0 ，v k ) ，其中k 满足 d k = m i n i d lj v i v v o ) ( 2 1 ) 则下一条最短路径( 终点v j ) ，或者为( v o ，v j ) ，或者为( v o ，v k ，v i ) 。一般情况 下，假设s 中存放已经求出的最短路径的终点的集合，则下一条最短路径中间节点一定 是s 中的节点，其长度为 d k = m i n t d t l v t v s ) ( 2 2 ) 在每求得一条最短路径之后，其终点v k j j h 入集合s 中，然后对所有的其他v l v s ， 修改其d i d i = m i n d i ，d k + c ( v k ，v i ) ) ( 2 3 ) 式中，c ( v k ，v i ) 是弧v k ，v 1 ) 上的权值。以上的算法将产生从源点出发到达其他各 项点的最短路径。对于单车辆路径规划问题，只需计算从源点出发到终点的一条最短路 径，为此可对算法做一些修改，即当发现最短路径的终点为目标路径的终点时，算法即 1 6 长安大学硕士学位论文 终止。 根据以上算法原理，设带权有向图g _ - ( v ，e ) ，其中v 是包含n 个顶点的顶点集， e 是包含m 条弧的弧集，( v ，w ) 为e 中从v 到w 的弧，c ( v k ，v 1 ) 为弧( v ，w ) 的非 负权值，设s 为v 中元素的顶点，t 为v 中可由s 到达的顶点，于是求解从s 到t 的具 有最小弧权值和的最短路径搜索过程可描述如下。 ( 1 ) 对每一个顶点v 分配三个信息，即k ( v ) 、d ( v ) 、p ( v ) ，其中k c v ) 为布尔型变 量，来表示顶点v 的最短路径是否已经求出；d ( v )