（交通信息工程及控制专业论文）蚁群算法在TSP中的应用研究.pdf

摘要 随着经济的快速发展和车辆数量的不断增加，日益严重的交通问题已经成为制约城 市发展的重要瓶颈。智能运输系统( i n t e l l i g e mt r a n s p o i r t a t i o ns y s t e m ，i t s ) 是解决社会交 通需求与供给之间矛盾的重要途径之一。近几年来，智能运输系统越来越受到人们的重 视，它是以科学技术为支撑，将计算机技术、通信技术、数据库技术、人工智能技术等 运用于交通领域，以达到缓解交通拥挤、保证交通安全、提高交通网络使用效率等目的。 最优路径的选择，作为智能运输系统中的一个研究热点，是一类典型的组合优化问题， 适合采用蚁群算法( a c o ) 求解。 蚁群算法通过其内在的搜索机制和正反馈特性，在解决一系列组合优化问题中取得 了成效，这已经是被大量研究成果证明了的。但是蚁群算法也存在着一些缺陷，如在蚂 蚁的移动过程中，路径选择虽然受到信息素和启发信息的指导，但仍具有随机性，特别 是当问题规模较大时，路径的选择通常需要较长的搜索时间。此外，由于个别路径上的 信息素可能被过于强化，容易使算法陷入局部最优解。 本文首先分析了基本蚁群算法的优缺点，通过仿真实验研究了参数对算法性能的影 响，确定了参数的合理取值范围，然后，针对信息素的优化策略进行了改进，有效地抑 制了收敛过程中的早熟停滞现象。最后，结合t s p 问题实例，对改进后的蚁群算法有效 性进行了验证，结果表明该算法具有较快的收敛速度，能够在较短的时间内搜索到全局 最优解。 关键词：最优路径；蚁群优化算法；旅行商问题；信息素；交通仿真 a b s t r a c t w i t har a p i dd e v e l o p m e mo fe c o n o m ya i l dq u a n t i t ) ro fv e l l i c l e ，t h ei n c r e a s i n 9 1 ys e r i o u s t r a m cp r o b l e mh a sb e c o m eac r i t i c a lb o t t l e n e c kt or e s t r i c tc i t yd e v e l o p m e n t i n t e l l i g e n t t i a n s p o r t a t i o ns y s t e mi so n eo ft l l e m o s ti m p o r r c a n ts o l u t i o l l st od e a l 而t ht l l ec o 1 i c to f d e m a n d 锄ds u p p l yi ns o c i a l 舰m c i nr e c e n ty e a r s ，晰t ht h es u p p o r to fs c i e n c ea n d t e c h n o l o g y ，i t sh a sb e e nm o r e a i l dm o r er e g a r d e db yp e o p l ef o ri t a p p l i e sc o m p u t e r t e c h n o l o g y ， c o m m 疵c a t i o nt e c l u l 0 1 0 鼢d a 协a s et e c | l o l o g ya n da n i f i c i a li n t e l l i g e n c e t e c h n o l o g yt o 仃a m ca r e at os o l v et r a m cj a i i l ，e n s u r et r a m cs a f e t ) ，a i l di m p r o v et l l ee f f i c i e n c y o ft r a 币cn e t w o r k a sah o tr e s e a r c hp o i n to fi t s ，t l l eo p t i m u mp a t h ss e l e c t i o n ，w h i c hi sa c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m ，c a nb e 、v e us o l v e db ya c o i th a sb e e np r o v e db yag r e a td e a lo fr e s e a r c ha c h i e v e m e n t s ，a c oi sg o o da ts o l v i n g c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sb yi t si i m e rs e a r c h i n gm e c h 耐s ma i l dp o s i t i v ef e e d b a c k t r a i t h o w e v e r ，a c oa l s oh a ss o m ed e f e c t s f o re x 锄p l e ，d u r i n gt h em o v e m e n to fa n t s ，r o u t e s e l e c t i o ni n s t m c t e db yp h e r o m o n ea n di n s p i r a t i o na l s oh a sr a i l d o m i c i 够s p e c i a l l y ，w h e nm e s c a l eo fp r o b l e mi sl a 玛e r ，r o u t es e l e c t i o nu s u a l l yc o s tm o r es e a r c m n gt i m e h 1a d d i t i o n ， b e c a u s ep h e r o m o n em a yb es 仃e n 酉h e n e di na ni n d i v i d u a lr o u t e ，t h ea l g o r i t hw i ue a s i l yg e t i m ol o c a lo p t i m a ls o l u t i o n f i r s t l y ，恤t h e s i sa i l a l y z e dt h ea d v 撇g e sa n dd i s a d v a i l t a g e so f b 撕ca c o ，s t u d i e dt h e i n f l u e n c eo fp a r a m e t e r so na l g o r i t 胁p e r f o m l a n c e ，a i l dd e t e r m i n e dr a t i o n a lv a l u ed o m a i no f t h e s ep a r a m e t e r s t h e n ，m eo p t i m i z a t i o ns t r a t e g ya tp h e r o m o r l ew a si m p r o v e d ，s ot h a ti tc o u l d r e s t r a i ne a r l ys t a 印a t i o nd w i n gc o n v e 唱e n c ep r o c e s se n 宅c t i v e l y f i n a l l y ，c o m b i l l i n g 晰t ht h e p r a c t i c a le x a i l l p l e so ft s pp r o b l e m ，t h ee 日e c t i v e n e s so f t 1 1 ei m p r 0 v e da 1 9 0 r i t l l i i lw a sv e r i f i e d t h er e s u l t ss h o w e dm a tt h i sa l g o r i t h mh a sf 瓠t e rc o n v e 玛e n c ea i l dc a nf i n d9 1 0 b a l l yo p t i m 眦 s o l u t i o n si nas h o r t e rt i n l e k e y w o r d s ：o p t i m u mp a t l l s ；a n tc o l o n yo p t i m i z a t i o n ；1 r a v e l i n gs a l e s m a np m b l e m ； p h e r o m o n e ：t r a m cs i m u l a t i o n 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行 研究工作所取得的成果。除论文中已经注明引用的内容外，对论文的 研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本论 文中不包含任何未加明确注明的其他个人或集体已经公开发表的成 果。 本声明的法律责任由本人承担。 敝作者虢1 j 庄忠彳 1 年，肿日 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请 专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的 学术论文或成果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名： 7 7 茬忠! 辛 导师签名： 弘矸 长安大学硕士学位论文 第一章绪论 随着经济的快速发展和车辆数量的日益增加，越来越严重的交通矛盾已经成为制约 城市发展的重要瓶颈。智能运输系统( i n t e 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 ) 是解 决社会交通需求与供给之间矛盾的重要途径之一。近几年来，智能运输系统越来越受到 人们的重视，i t s 是以科学技术为支撑，将计算机、通信、数据库、人工智能等技术运 用到交通领域，以达到缓解道路拥挤、保证出行安全、提高道路网络使用效率等目的。 1 1 论文研究目的及意义 1 1 1 论文研究目的 交通道路和车辆之间的供需矛盾越来越严重的影响着世界各国城市的经济发展，单 纯依靠修建道路来解决供需矛盾已经不太现实。而是需要建立一套完备的路径诱导系 统，目前我们在这方面还不完善的主要原因是在路径选择算法方面比较落后，没有实时、 动态、有效性强的路径选择算法，使得道路最优选择算法一直成为本学科研究的重点问 题之一。 本文通过对几种传统最优路径算法的研究比较，引入一种更适合组合优化问题的求 解算法一蚁群算法。并针对基本蚁群算法在求解实际问题方面的不足进行改进，最后将 改进的蚁群算法同基本蚁群算法进行比较，结合旅行商问题( t r a v e l i n gs a l e s m a n p r o b l e m ，t s p ) 来验证改进算法的可行性和有效性。 1 1 2 论文研究意义 伴随着经济的快速发展，车辆的数量不断增加，道路负荷日益加重，交通拥挤、交 通事故频繁发生的情况，建设一套适合动态路径诱导的系统显得尤为重要，对于提高路 网的利用率，有效的减少交通拥挤，减少环境污染，保障出行安全、提高经济效益具有 重要的意义；最优路径选择算法是解决动态路径诱导问题的核心，如何研究出一种实时 高效的路径选择算法，是交通最优路径选择的首要问题。 t s p 问题是个典型的组合优化问题，也是一个n p 完全难题，是众多领域内出现的优 化问题的集中概括和简化形式，是各种启发式算法的间接比较标准，如果一个算法能在 t s p 上取得良好的性能，则往往在其他组合优化问题上也能取得良好的性能。论文通过 t s p 问题来验证改进的算法是具有非常大的实际意义的。 1 第一章绪论 1 2 论文的研究背景 1 2 1 最优路径选择的提出 社会经济的不断发展，车辆数量的持续增长，造成交通拥挤和阻塞现象日益严重， 交通污染与交通事故已引起社会的普遍关注，仅依靠修建和拓宽道路、扩大规模已无法 解决日益增长的交通需求，也是不太现实的。而越来越多的利用科学技术来提高道路的 利用率、安全程度和舒适性，已成为未来交通运输的发展方向【1 。2 1 。智能运输系统的未 来发展方向主要表现在：车辆控制系统、交通信息服务系统、交通管理系统、交通运输 需求系统、货运管理系统、公共交通系统、电子收费( 收税) 系统、停车场动态管理系 统、火灾预警管理系统、紧急援救系统【3 】。其中i t s 所提供的服务主要包括：提供可靠 的交通信息、提供高效的快速应急服务、大幅度减少交通阻塞，提供高质量低成本的快 货运输、方便快捷的支付手段等【4 】。而本文所研究的路径选择亦是i t s 中的一个主要研 究方向，它为出行者提供可靠的交通信息，高效的快速应急服务，并能减少交通拥塞。 道路的建设速度和车辆的增长速度已经严重失调，这种矛盾在未来还将进一步加 剧，这个供需的不平衡，已经严重影响到交通的畅通。随着交通需求的持续增长和交通 基础设施供给能力的降低，如果没有更有效的交通管理措施出现，交通状况将会更加恶 化。因此，如何获得实时交通信息帮助驾驶员找到一条或多条从出发点到目的地的最优 路径；帮助驾驶员避开拥挤和事故，避免因不熟悉城市交通环境而“迷路 ，减少车辆 在道路上的逗留时间，进而实现改善交通和避免交通拥挤阻塞的目的和使路网畅通、高 效运行，以缓解失衡的交通供需体系，成为亟待解决的问题。 1 2 2 旅行商问题的提出 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 问题也称t s p 问题，是组合优化 中最著名的问题之一，它的特点是问题容易描述而难于求解。自1 9 3 2 年，k m e n g e r 提 出t s p 问题以来，已经引起了许多数学家的兴趣，但至今尚未找到最有效的求解方法。 t s p 问题是一个典型的组合优化问题，也是一个n p 完全难题，它是众多领域中出现的 优化问题的集中概括和简化形式，是各种启发式算法的间接比较标准。如果一个算法能 在t s p 上取得很好的性能，那么在其他组合优化问题上也能取得很好的性能。因此，解 决t s p 问题有着重要的理论价值和应用价值。 众多领域的优化问题都可以归结为t s p 问题，如交通线路规划问题、超大规模集成 2 长安大学硕士学位论文 电路制造问题、车辆调度问题、网络路由问题等等。总之，凡是可以抽象成为遍历所有 城市( 或节点) 一次而且仅一次，要求代价最小的问题，都可以当作t s p 问题来解决【6 1 。 t s p 问题的的理论意义也非常重大。事实上t s p 问题是作为所有组合优化问题的范 例而存在的，已经成为测试新算法或者算法之间比较的标准问题。这是因为，t s p 问题 展示了组合优化的所有方面优点：t s p 问题从基本概念上来讲是非常简单的，但是他求 解的难度相当大的。如果提出的某种算法针对t s p 问题能够取得良好的性能，那么只要 对其进行简单的修改，就可以应用于其它类型的组合优化问题并能够取得良好的效果。 因此，t s p 问题吸引了全世界许多不同领域的学者进行相关的研究，现在t s p 问题已成 为当前研究的热点问题之一。 1 3 蚁群算法及旅行商问题的研究现状 1 3 1 蚁群算法的研究现状 二：一 1 9 9 1 年意大利学者d o r i g om 等人【7 吲在首届欧洲人工生命会议上发表了“吱s t r i b u t e d o p t i m i z a t i o nb y a n tc o l o n i e s 文章，就是在这篇文中提出了蚁群算法。但是当时并没有 在引起学术界广泛的关注。直到五年以后，1 9 9 6 年，d o r i g om 等人又在i e e et r a i l s a c t i o n s o ns y s t e m ，m a n ，a i l dc y b e m e t i c s p 叭b 刊物上发表了“a n ts y s t e m ：o p t i m i z a t i o nb ya c o l o n yo f c o o p e r a t i n ga g e n t s ”一文【9 1 ，在这篇文章中，不仅详细的阐述了蚁群算法的基 本原理和数学模型，还将其与遗传算法、禁忌搜索算法、模拟退火算法、爬山法等进行 了详细的方法比较，把解决单一的对称旅行商问题( s y l i u l l e 仃i ct r a v e l i n gs a l e s m a n p r o b l e m ，s t s p ) 拓展到解决非对称旅行商问题( a s y n u i l e t r i ct r a v e l i n gs a l e s m a l lp r o b l e m ， a t s p ) 、指派问题( q 吼d r a t i c a s s i g m e n tp r o b l e m ，q a p ) 以及车间作业调度问题( j o b s h o p s c h e d u l i n gp r o b l e m ，j s p ) 中来，并且对蚁群算法中参数初始化对其性能的影响做了初步 探讨，这也是蚁群算法史上的一篇奠基性文章。自1 9 9 6 年之后的五年中，蚁群算法逐 渐引起了国际学术界许多研究学者的关注，使蚁群算法的应用领域得到了迅速的拓宽。 1 9 9 8 年1 0 月，蚁群算法创始人d o r i g om 在比利时布鲁塞尔负责组织召开了第一 届蚁群算法国际研讨会( a n t s 9 8 ) 。2 0 0 0 年，d o r i g om 和b o n a b e a ue 等人在国际顶 级学术刊物n a t u r e 上发表了蚁群算法的研究综述，从而把这一领域的研究推向了国 际数学的最前沿。 最近的几年中，n a 胝刊物曾经多次对蚁群算法的研究成果进行了报道【l o 1 2 1 ，2 0 0 0 3 第一章绪论 年f u t u r e g e n e r a t i o nc o m p u t e rs y s t e m ( v 0 1 16 n o 8 ) 和2 0 0 2 年i e e et r a i l s a c t i o n so n e v o l u t i o n a 叮( v o l ，6 ，n o 4 ) 分别于和出版了蚁群算法特刊。现如今，蚁群算法已经成为 备受关注的研究热点和前沿性课题。 1 9 9 1 年g u t j a l l rwj 撰写的报告“ag e n e m l i z e dc o n v e r g e n c er e s u l tf o rt h e g r a p h - b a s e da ms y s t e m 以及在2 0 0 0 年发表的学术论文“ag r a p h - b a s e da n ts y s t e m a 1 1 di t sc o n v e 赡e n c e 【1 4 】，首次对蚁群算法的收敛性进行了证明，这对蚁群算法的发展有 着重大的意义。 随着对蚁群算法研究的不断深入，人们开始关注蚁群算法的硬件实现这一新的研究 方向。i s a a c s 等人【1 5 】将蚁群算法和遗传算法相结合，提出了嵌入式硬件随机数据发生器 设计的新思路，他们只是对其做了离线仿真，没有在硬件上实现。s c h e u e 册a i l l l 等人【1 6 l 深入分析了将蚁群算法映射到f p g a 难点，并在此基础上，提出了一种基于群体蚁 群优化( p o p u l a t i o n b a s e d a n tc 0 1 0 n yo p t i m i z a t i o n ，p a c o ) 算法的仿生硬件实现方案， 并详细给出了该算法在f p g a 硬件结构中相关重要模块的实现步骤。 我国在蚁群算法领域的研究比较晚，从公开的论文发表来看，1 9 9 7 年1 0 月东北大 学控制仿真研究中心张纪会博士与徐心和教授发表的“一种新的进化算法蚁群算法” 一文时国内最早对蚁群算法的研究【1 7 】。在国内蚁群算法的众多研究学者中，值得一提的 是当时年仅1 7 岁的高二学生陈烨于2 0 0 1 年在计算机工程( v 0 1 2 7 ，n o 1 2 ) 上发表了 带杂交算子的蚁群算法一文【1 8 】，并基于s u a lb a s i c 环境开发了一个功能齐全、界 面友好的“蚁群算法实验室”，引起了国内学术界蚁群算法爱好者的极大关注。 回顾蚁群算法1 7 年以来的发展历程，学者对蚁群算法的研究已经由当时单一的 t s p 领域渗透到了多个领域，从解决一维静态优化问题发展到解决多维动态组合优化问 题，由离散域范围内研究逐渐拓展到了连续域范围内研究，而且在蚁群算法的硬件实现 上也取得了突破性的进展，同时在蚁群算法的模型改进及与其他仿生优化算法的相结合 方面也取得了相当丰富的研究成果，从而使蚁群算法展现出前所未有的研究热潮，并已 经成发展为一种完全可以与遗传算法相媲美的优化算法。 1 3 2 旅行商问题的研究现状 旅行商问题作为一个经典的组合优化问题历史悠久，最早的描述【l9 】是欧拉研究的骑 士周游问题，也就是对于国际象棋棋盘中的6 4 个方格，走访6 4 个方格一次且仅一次， 并且最终返回到起始点。早期的研究者使用经典算法求解该问题，但是，随着问题规模 4 长安大学硕士学位论文 的增大，经典算法将变得不可能实现，因为该算法求解所花的时间太长。因此，在后来 的研究中，学者重点使用近似算法或启发式算法对t s p 问题进行研究。 t s p 问题的求解方法有很多，大致可以归纳为以下三种：( 1 ) 使用各种纯数学的方 法构造时间复杂度为多项式的近似算法进行求解。( 2 ) 使用启发式算法或迭代算法进行 求解。( 3 ) 使用遗传算法、蚁群算法、模拟退火算法、等仿生算法进行求解。由于遗传 算法、蚁群算法等具有很强的群体搜索能力，但同时又可能陷入搜索局部最优解的问题， 因此学者通常将局部搜索算法和这些算法相融合构造出更高效的混合算法，采用多种方 法相结合的混合算法来求解t s p 问题。 t s p 问题具有广泛的实际应用价值，在未来相当长的时间内，t s p 问题仍将是算法 研究领域的一个热点问题。 1 4 本论文研究的主要内容 本文主要研究的主要内容是根据基本蚁群算法在解决最优路径问题方面的一些不 足，分析基本蚁群算法的改进机制，根据相关的改进策略对基本算法进行改进，使算法 具有更好的收敛性和实用性。最后将改进的算法结合经典的t s p 问题来仿真，同基本的 算法进行比较，进一步说明改进的算法的可行性和优劣性，并将实际的问题抽象为t s p 问题，运用改进的算法求解。 5 第二章图论与路网结构 第二章图论与路网结构 图论是一门应用数学，他的概念和结果来源非常广泛，既有来自生产实践的问题， 也有来自理论研究的问题。历史上参与研究图论问题的人，既有许多天才的数学家，也 有不少业余爱好者。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数 学家各自独立地建立过。 2 1 图论概述 近年来图论受计算机科学蓬勃发展的刺激，发展极其迅速，应用范围不断扩大，已 渗入诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学、交通运输学等众多 领域。在智能交通中的应用主要表现在以下几个方面【2 0 之1 】： 1 ) 图论在交通监控器安置问题中的应用：考虑到城市交通问题影响着广大人民群 众的切身利益，交管部门只靠交警站岗还不足以控制全局，还必须从整体上进行监控和 调度，有效的方法就是在道路交叉路口或适当的地方安装交通监视器。但如果在每一个 路口或路段都设一个监视器必然造成一定的资金和人力的浪费。事实上，只需在某些路 口或一些恰当的地点安装监视器，便能既完成交通监控任务，又能节省资金。那么，合 理选取这些地点就是问题的关键，借用图论的知识能解决这个问题。 2 ) 图论在路面改建决策中的应用：道路使用若干年后，路面需要改建，由于各个 时期路面的损坏程度不同，需要采用不同的处理方法，因此各个时期的路面建设费用也 不同。可供选择的改建方案也很多，如何设计路面改建方案才能使公路在使用期内路面 改建的总费用最小是个关键问题。借用图论的知识也能解决这个问题。 3 ) 图论在最短路径算法中的应用：寻找一条最短的行车路径是图论研究中的一个 经典算法问题。 2 1 1 图论的发展 关于图论的文字记载最早出现在欧拉1 7 3 6 年的论着中，他所考虑的原始问题有很强 的实际背景。 1 ) 早在1 8 世纪，伟大的瑞士数学家列昂哈德欧拉引进了图论的基本思想，他利 用图解决了有名的柯尼斯堡七桥问题。 2 ) 著名的“四色定理，1 8 4 0 年德国天文学家、数学家默比乌斯，他用数学方法 6 长安大学硕士学位论文 推理证明，辛苦一生没有成功，1 8 5 0 年英国人格思里试图证明一直也没有成效。1 8 9 0 年 英国数学家，海胡特证明了“五色定理 。这是很大的贡献，但“四色定理却无进展， 直到1 9 7 6 年美国科学家利用计算机证明了这一定理。由此，计算机科学为图论的发展开 辟了新的途径。 3 ) 图论中问题的运算与判断可以用线性代数中的矩阵知识，用数学分析中的积分 知识，用概率论知识，用计算机程序的方法来帮助解决。这样致使图论的知识、方法更 加丰富，使图论在社会中的应用更加广泛【2 0 1 。 2 1 2 图论的基本概念 图论( g r a p ht h e o r y ) 是数学的一个分支，它以图为研究对象，是研究城市( 边) 组成的图形的数学理论和方法。图论中的图是由若干给定的点及连接两点的边所构成的 图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两 点的边表示相应两个事物间具有某种关系。 二元数组( 矿( g ) ，彳( g ) ) 称为图( 铲印h ) 。其中y ( g ) 是一个非空的城市( 或叫顶点) 集 合，其成员称为城市或顶点( n o d eo rv e r t i c e s ) 。彳( g ) 是边( 或叫弧) 的集合，其成员称 为边或弧( e d g e so ra r c s ) ，常用g = ( 矿，彳) 表示图，或g = y ，彳，y ，l i ，表示点与边之间的关 系【2 1 。2 4 】。 1 ) 有向图和无向图 假设一个图中任意两个顶点1 ，v 构成的偶对 e 是有序的，也就是顶点 1 ，1 ，之间的连线是有方向的，就称该图为有向图，此时边e 往往用弧4 来表示；相反， 若偶对 e 是无序的，就称该图为无向图。 2 ) 顶点、边、弧、弧头、弧尾 顶点集y ( g ) 中的数据元素b 称为顶点( v e r t e x ) 或者结点( n o d e ) ；尸( 1 ，) 表示顶点 v 。，v ，之间有一条直接连线。如果是无向图，则称这条连线为边e ；而在有向图中，一 般称这条连线为弧彳。边用顶点的无序偶对( 哆，) 来表示，称顶点1 ，。，和顶点0 互为邻 接点，边( 坼，) 依附于顶点，和顶点v ；弧用顶点的有序偶对 来表示，有序偶 7 第二章图论与路网结构 对的第一个结点1 ，被称为始点( 或弧尾) ，在图中就是不带箭头的一端；有序偶对的第二 个结点v j 被称为终点( 或弧头) ，在图中就是带箭头的一端。 3 ) 赋权图 一个图的边或弧上是可以具有与之相关的数据信息，可以表示为从一个结点到另一 个结点的距离、费用或时间等等。这种与图的边或弧相关的数据信息叫做权( w e i g h t ) ， 我们把这种边或弧上具有权的图称为赋权图或着赋权有向图，通常也称为网络。另外， 图的结点处也可能带有某种反映其特性的数据信息( 称为结点权重) ，我们把这种带有结 点权重的图称为点赋权图。一般地，将弧 上的权记为w ，也称为这条 弧的长度。给定某个图g = ( 矿，爿) ，如没有特别说明，就认为矿= h ，v 2 ，b ，心 ， 彳= q ，口2 ，口3 ， ，即城市数l 叫= 疗，l 爿| _ 所2 1 2 2 1 。 4 ) h 锄i l t o n 图 我们称一个图g 为e u l e r 图，如果可以从任一顶点出发，遍历每边恰一次，并最终 回到远出发点，称g 为h 锄i l t o n 图，及汉密尔顿回路。所谓赋权汉密尔顿回路最小化 问题是指，给定 个点及船个点两两之间的距离( 或权数) ，求一条回路，使之经过所有 的点，且经过每个点仅一次，而整条回路( 也称路径或边界) 的总距离( 或总权数) 最小。 汉密尔顿回路问题即经典的t s p 问题。 2 2 路网的表示 2 2 1 路网基本要素及权重 路网的基本表达要素有两类实体：结点( 交叉口或者路的端点) 和弧( 路段本身) 。下 面分别就这两种实体在路网中所代表的对象分别做以介绍，并分析其形成的基本原则。 ( 1 ) 结点 通常我们会认为路网中的结点就是道路交叉口或者是路的端点，但对于车辆路径诱 导系统，这样定义是不够准确的。道路的结点还应该包括以下几种类型的点：路段特性 发生变化的点和可能在此发生转向行为的点。路段特性发生变化的点虽然不是物理实体 上的交叉口，但是在该点处路段的某种属性发生了变化，而且该属性的变化有可能直接 导致该路段权值的变化。例如：某一路段的中间某处车道由由三车道变成两车道，这样 使得道路的通行能力发生了明显的变化，将会直接直接导致后面车辆的行程时间，在这 r 长安大学硕士学位论文 种情况下，就应该把该点作为一个结点。后者不是指交叉口，而是指在一条连续的路段 中间有可能在该点处进行转向行为的点，例如将道路的某处隔离带打开以提供车辆在此 进行掉头的点。在道路上这些都可以认为是结点。 ( 2 ) 路段 路网中路段的情况同结点相比就显得简单一些。路段的表示规则为：将道路的所有 车道合在一起，在相邻的两个结点( 前文描述的结点) 之间的部分作为一个路段。由于路 段的两个方向的属性一般不是相同的，因此可以把路段看作是弧。根据道路的各种优化 目标，可以把该路段的时间、行驶里程以及通行该路段所产生的费用等等作为该路段得 权值。 ( 3 ) 路网权重的确定 路网中路段的权值的确定方法，将会直接影响到最终的计算结果。所以我们首先从 道路优化目标的不同选取原则出发，充分分析各种制约因素来讨论道路权重的设定。根 据不同的道路优化目标，可以确定相应的道路权重，联系到图上，也就是每条弧或边的 权。对于道路优化目标的选取，通常有下列方法： 1 ) 将行驶距离最短作为系统优化目标，则该路段长度就是道路的权重。 2 ) 将行驶时间最短作为系统优化目标，则车辆通过该路段所消耗的时间就为道路 的权重。 3 ) 将行驶最小费用作为系统优化目标，则车辆在该路段所使用的费用就为道路的 权重。 4 ) 如果考虑到某些特殊的要求，如将行驶复杂度最小、规避收费道路等要求作为 选择行驶路线的依据。关于出行复杂度，可以根据转向方向( 左转或右转) 来确定；也可 以简单的用转向次数来度量；对于避免收费道路则可以考虑增加收费道路权值来度量。 2 2 2 道路路网 用图论解决交通网络的问题，是图论在交通系统运用中的基本问题和难点问题。为 了研究出行者路径选择问题，常把道路网简化成赋权图，路网结构简化成赋权图如图2 1 所示。 路网结构可以用有向图表示，通常将有向图记为：g ：( 矿，彳) ，矿代表城市的集合：彳 代表路段的集合。图2 1 中矿= h ，吃，屹，v 4 ，v 5 ，v 6 ) ，彳= q ，呸，口3 ，口4 ，呜，咏，口7 ，啄，口9 ，q 。) 。若某路 9 第二章图论与路网结构 段( 弧) 吼从点v ，指向v j ，则记为：吼= ( v ，v ) 称v ，为吼的起点，v 为吼的终点。 如果将有向图g 去掉箭头，得到一个无向图，称为基础图。一般来讲，点表示道路 的交叉口，点与点之间的连线( 弧) 表示路段，在实际问题中有时不仅要表示路段，还 要知道路段的长度、交通流量、通过时间等等数量指标，因此这种与弧有关的数量指标， 根据实际问题需要，可以赋予不同的含义，称之为权。图g ：( 矿，彳) ，对于g 中的每一条 弧( v l ，v ，) ，相应的有权呢= ，则g 连同其权值称为赋权图。交通网络就是典型的赋权 图【2 7 】。 矿矗 2 3 本章小结 图2 1 路网结构简化赋权图 本章首先介绍了图论发展，基本概念及在i t s 中的应用；接着介绍图论对城市路网 表达的基本要素，路网权重的确定以及权值的计算，最后通过图论的相关知识给出了路 网的赋权图。 1 0 长安大学硕士学位论文 第三章传统最优路径算法及应用 最优路径选择问题具有非常悠久的发展历史，其归根结底就是在图论中求最短距离 的问题。在图论理论的不断发展中，最优路径问题已经从当初建立在图论上抽象网络模 型的算法研究，逐步向现实中