（计算机应用技术专业论文）交通系统中最优路径选择算法的研究.pdf

首都师范大学硕士学位论文交通系统中最优路径选择算法的研究 摘要 近年来，智能交通系统( 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 i j k s t r a 算法为代表。这些算法均属于贪心算法，存在典型的局部最小问题，是 一种静态的局部最优算法。当前的实际交通网络数据规模庞大，算法需要提前将整个交通 数据导入才能进行路径的选择。这样显然不能反映出交通中不断变化的道路实际情况对交 通路径选择的影响。蚁群算法是一种新兴的模拟仿生算法，算法具有模拟生物界群体觅食 的能力，并且能够在实际的路径搜索过程中对外界的影响做出动态的响应，因而在交通最 优路径选择中具有极大的可行性与适应性。 论文综合分析了当前道路交通中在路径选择方面存在的问题，介绍了道路交通数据的 计算机表示方式与存储结构；讨论研究了当前路径选择的几种经典的算法，分别研究了 d i j k s t r a 算法、f l o y d 算法、a 算法。从算法的基本思想、算法过程、具体实现以及算法 分析等方面探讨了算法的优缺点。在以上几种经典最优路径算法的基础上结合蚂蚁觅食行 为引入新的算法一蚁群算法( a n t c o l o n y a l g o r i t h m ，a c a ) 。并进一步研究了蚁群算法 的基本原理和在交通最优路径选择中的应用与实现过程。通过实验确定最佳的蚁群算法参 数组合，并与经典的最优路径算法进行了数据仿真对比。 论文研究、确定在交通数据量较大、道路交通复杂的情况下，采用蚁群算法进行最优 路径选择能极大地发挥仿生算法的全局搜索优势，提高路径选择的效率，降低路径选择所 带来的时问耗费，并且能够有利于实现动态的最优路径选择过程。 关键词：智能交通系统，交通路网，最优路径，有向赋权图，蚁群算法 首都师范大学硕士学位论文交通系统中最优路径选择算法的研究 a b s t r a c t i nr e c e n ty e a r 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 ) h a sb e e np a i dm o r ea n dm o r e a t t e n t i o n i tw a sg i v e nb i r t ht oi nt h eb a c k g r o u n do f c o n t e m p o r a r ys c i e n c ea n dt e c h n o l o g yf u l l y d e v e l o p e dw h i c hs e e k st oi n t r o d u c ea d v a n c e dc o m p m 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 a li n t e l l i g e n c et ot r a n s p o t a t i o ns o a st os o l v et h et r a f f i c c o n g e s t i o n , e 帕l s u r et h et h es a f e t ya n di m p r o v et h eu s i n g r a t eo ft r a f f i cn e t w o r k i t si n v o l v e s m a n ya s p e c t so f t r a f f i cf i e l d a n di nt h e s ea s p e c t s ，o n ei m p o r t a n ta p p l i c a t i o ni st h ec h o o s i n go f t h eo p t i m a lp a t h b e f o r es t a r t i n go f f , t h eu s e i sa l ei n t e r e s t e di nh o wt of i n da no p t i m a lp a t hf r o mt h es t a r t p o i n tt oe n dp o i n t t h et r a d i t i o n a lo p t i m a la l g o r i t h m sw e r er e p r e s e n t e db yd i j k s t r aa l g o r i t h i n t h e s ea r ea l l g r e e d yw h i c ha r es t a t i c l o c a l o p t i m a la l g o r i t h ma n dh a v et y p i c a ll o c a l o p t i m i z a t i o np r o b l e m a tp r e s e n t ，t h es c a l eo f r e a lt r a f f i cd a t ai sh u g e a n di ts h o u l db e l o a d e d i na d v a n c eo fa l g o r i t h mc a r r i e do u ti n t ot h ep a t hc h o s e n o b v i o u s l y , t h i sc a n n o tr e f i e c tt h e a c t u a lc o n t i n u o u ss i t u a t i o no ft r a f f i co np a t hc h o s e n a n tc o l o n ya l g o r i t h mi san e wb i o n i c s i m u l a t i o na l g o r i t h m i th a st h ec a p i b i l i t yi ns i m u l a t i n gc o l o n yc o o p e r a t i o na n df i n d i n ga s h o r t e s tp a t hf r o mn e s tt of o o d ，w h i c hc o u l dr e s p o n dd y n a m i c a l l yt oe x t e r n a la f f e c t i o ni nt h e r o u t i n gs e a r c hp r o c e s s s oi th a si n f i n i t ef e a s i b i l i t ya n df l e x i b i l i t yi nt h eo p t i m a lp a t hc h o s e no f t r a f f i c t h i sp a p e ra n a l y s i s e dt h ec u r r e n tp r o b l e mi nt r a f f i cp a t hc h o s e ng e n e r a l l y , p r e s e n t e dt h e e x p r e s s i o na n ds t o r g es t r u e t a l ei nc o m p u t e ro ft r a f f i cd a t a , d i s e n s s e da n dr e s e a r c h e dt h e t r a d i t i o n a la l g o r i t h mo f c u r r e n to p t i m a lp a t hc h o s e n , w h i c hc o n t a i n e dd i j k s t r aa l g o r i t h m ，f l o y d a l g o r i t h ma n da + a l g o r i t h m a n dt h ea l g o r i t h m sa d v a n t a g ea n dd i s a d v a n t a g ew a sd i s c u s s e d f r o mb a s i ci d e a , a l g o r i t h mp r o c e s s ，i d i o g r a p h i ci m p l e m e n ta n da l g o r i t h ma n a l y s e c o m b i n e d t h e s es e v e r a lt r a d i t i o n a lo p t i m a lp a t ha l g o r i t h m sa n da n tf o r a g i n gb e h a v i o r , an e wa l g o r i t h m w a si n t r o d u c e d ，t h a tw a sa n tc o l o n ya l g o r i t h m ( a c a ) a n dt h e nf u r t h e rr e s e a r c h e dt h ea c a s b a s i cp r i n c i p l e sa n dt h ea p p l i c a t i o na n di m p l e m e n t a t i o np r o c e s so f t r a f f i co p t i m a lp a t hc h o s e n t h r o u g hl a r g en u m b e r so fd i f f e r e n te x p e r i e n c e , t h eb e s te x p e r i m e n t a lp a r a m e t e r s c o m b i n a t i o n o f a c aw a sm a d ec e r t a i n a tl a s t , c a r r i e do u td a t as i m u l a t i o na n dc o m p a r e dt h e mw i t hc l a s s i c t 首都师范大学硕士学位论文 交通系统中最优路径选择算法的研究 o p t i m a lp a t hc h o s e na l g o r i t h m sr e s u l t t h r o u g ht h i sp a p e r sr e s e a r c h ，w ec o n f i r m e dt h a tu s i n ga c a a st h eo p t i m a lp a t hc h o s e n a l g o r i t h mc o u l de x e r tt h es i m u l a t e da l g o r i t h m sp r e d o m i n a n c eo fg l o b a ls e a r c h , i m p r o v et h e r a t eo fp a t hc h o s e n , r e d u c et h et i m e1 1 8 0i np a t hs e l e c t i o ni nt h es i t u a t i o no fb i gq u a n t i t yo f t r a f f i cd a t aa n dc o m p l i c a t e dt r a f f i cs t a t u s a n dt h i sa l g o r i t h mw i l lb eh e l p f u li na c h i e v i n gt h e d y n a m i co p t i m a lp a t hs e l e c t i o np r o c e s s 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 ，t r a f f i cn e t w o r k , o p t i m a lp a t h , d i r e c t e d g r a p hw i t hw e i g h t ，a n tc o l o n y a l g o r i t h m u 首都师范大学硕士学位论文交通系统中最优路径选择算法的研究 英文缩略词 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 智能交通系统 a c a ：a n tc o l o n y a l g o r i t h m 蚁群算法 g i s ：g e o g r a p h i ci n f o r m a t i o ns y s t e m 地理信息系统 g p s ：g l o b a lp o s i t i o n a ls y s t e m 全球定位系统 c a c s ：c o m p r e h e n s i v e a 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 ：r a d i of r e q e n e y 射频 r g s ：r o u t eg u i d e n c es y s t e m 路径诱导系统 a t i s ：a d v a n c e dt r a f f i ci n f o r m a t i o ns y s t e m 先进的交通信息服务系统 t r a v t e k ：t r a v e lt e c h n o l o g y 旅行技术 a d v a n c e ：a d v a n c ed r i v e ra n dv e h i c l ea d v i s o r yn a v i g a t i o nc o n c e p t 先进的驾驶员咨询与车 辆导航概念 s t o r m ：s t u t t g a r tt e r r i t o r i a lt r a f f i co p e r a t i o na n dm a n a g e m e n t 斯图加特区域性交通运营 管理 首都师范大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所 取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表 或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 皮幻 日期：) 叼年明习e l 首都师范大学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规定，学校有权保留学位论 文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论文用于非 赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文的内容编入有 关数据库进行检索。有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后 适用本规定。 学位论文储签名：是丑沁 日期：肼t - 月岛e l 首都师范大学硕士学位论文交通系统中最优路径选择算法的研究 第一章绪论 1 1 我国城市道路交通中存在的典型问题 1 交通拥堵现象日益严重 随着国民经济的高速发展和城市化进程的加快，我国机动车拥有量及道路交通量急剧 增加。尤其是在大城市，由交通拥堵导致的交通事故、环境污染的加剧，是我国城市面i 临 的极其严重的“城市病”之一，已经成为国民经济进一步发展的瓶颈问题。以北京市为例， 高峰小时交通流量超过1 0 0 0 0 辆的交叉路口数已经从1 9 9 4 年的2 9 个增加到1 9 9 9 年的5 2 个，高峰小时交通流量超过4 0 0 0 辆的交叉路口数已达到9 8 个；2 0 0 2 年3 月二环路平均 全天交通流量达到1 3 2 0 0 0 多辆，三环路平均全天交通流量达到9 7 0 0 0 多辆；二环、三环 主要干道的负荷度在9 0 左右【”。在北京市公安交通管理局2 0 0 3 年1 1 月5 日公布的8 4 处最拥堵路段中【2 】：东城区7 处、西城区7 处、崇文区4 处、宣武区4 处：朝阳区2 7 处、 海淀区1 7 处、丰台区1 2 处、石景山区l 处、昌平区l 处、大兴区4 处。这说明北京城区 交通拥堵是全城整体性的问题，影响了城市功能的正常发挥和城市可持续发展。而且，随 着汽车保有量的增加，交通拥堵现象将日益严重。 2 交通污染造成城市环境的日益恶化 交通污染已成为城市环境质量恶化的主要污染源。尽管我国汽车拥有量还不是很大， 但汽车尾气对大气的污染程度己相当严重。如北京市机动车产生的污染物排放量占总排放 量的比例分别为c o ：6 0 ，n o x ：5 4 7 ，h c ：8 6 8 。随着机动车拥有量的增加， 汽车尾气对大气污染程度还在加剧。并且道路交通产生的噪声污染在城市污染中所占比例 也相当高，一般占总噪声强度的5 0 ，多数大城市的主要道路交通噪声均超过了6 5 d b ， 有些城市的道路噪声超标率达9 0 以上1 3 】【4 】【卯。 3 能源消耗严重 交通运输消耗大量的能源。在当前的能源结构中，石油占有重要地位。据最新的b p 世界能源统计指出【6 】：以目前的开采速度计算，全球石油储量可供生产4 0 年。石油资源 短缺将成为全球共同面临的问题。而在整个石油的消耗中，交通过程中消耗的石油几乎占 整个石油消耗量的一半。 4 混合交通流相互干扰，交通事故频发 首都师范大学硕士学位论文交通系统中最优路径选择算法的研究 我国城市经济水平还相对较低，交通工具种类繁多，居民根据自身情况选用不同的交 通出行工具，导致不同性能和不同功能的交通流在同一水平面上混合行驶，相互干扰，特 别是机动车受到非机动车( 尤其是自行车) 的干扰，使得机动车交通流的速度降低，城市 道路利用率降低，交通效率下降。随着道路容量的降低，城市交通更加拥挤，矛盾更为恶 化。这也是产生交通事故的重要因素之一。 5 城市交通发展政策不合理、道路路面优先通行权不明确导致交通结构不合理 目前我国城市道路增长慢，城市交通管理的技术设备落后，无论是城市路网的发展还 是城市交通管理的改善，均不适应城市交通量的增长。目前我国的特大城市如北京、上海、 广州、沈阳等城市道路拥堵现象十分严重，城市行车难日益成为我国交通运输的普遍问题。 城市交通不畅通，不仅严重影响全国交通运输网的运输效率，而且直接影响到市民的日常 工作和生活。 根据对国内1 0 个大城市居民出行调查资料分析【3 】国内客运交通结构极不合理。在 全部出行方式中，公共交通方式出行仅占5 - 一1 0 ，而自行车交通却占了5 0 ，6 0 ，其 他非公交机动车交通占1 0 左右，步行占3 0 左右。在各出行方式中，不同方式对道路 空间的要求又是不样的，公交出行方式的道路利用率最高，人均出行占路面积仅为l m 2 ， 非公交机动车人均占路面积为l o - q 5 m 2 ，自行车出行为3 4 m 2 k 。道路利用率最高的公 交系统没有得到充分发挥，而利用较低的自行车出行成了出行方式的主体，从而造成城市 交通系统运输效率低下，造成交通拥挤。目前，全国3 2 个百万人1 2 1 以上的大城市中，有 2 7 个城市的人均道路面积已经低于全国平均水平。9 0 年代中后期，上海等城市中心区5 0 的车道上高峰小时饱和度已达到9 5 ，全天饱和度超过7 0 ，平均车速下降到1 0 k m h1 7 1 。 交通系统中存在如上的问题，已经越来越严重的影响到城市的综合发展。为此在当代 科学技术充分发展的背景下，智能交通系统应运而生。它将先进的计算机技术、通信技术、 数据库技术、人工智能技术等运用于交通运输中，解决交通拥挤、保证交通安全、提高交 通网络使用效率等问题。在智能交通系统的研究中，交通最优路径选择是其中的一个重要 研究方向，也是各国都着重解决的问题。 1 2 交通最优路径选择算法研究的背景和意义 当前交通拥挤和交通事故正越来越严重的困扰着世界各国的大城市，但目的缺乏高 效的路径诱导系统，在路径选择算法方面还不完善，缺乏实时性高、有效性强的路径选择 算法，使得交通最优路径选择问题一直称为各国投资研究的重点问题。根据统计资料显示， 2 首都师范大学硕士学位论文交通系统中最优路径选择算法的研究 西方发达国家由于公路堵塞而造成的直接或间接经济损失十分惊人。随着我国交通运输事 业的迅速发展，如何研究一套适合我国国情，并集现代通信技术、电子技术、计算机技术、 g i s 和g p s 于一体的路径诱导系统与应用在这些系统中的实时高效路径选择算法，使之 能够为路网上的出行者提供必要的交通信息，为其指出当前的最佳行驶路线，从而避免盲 目出行造成的交通阻塞，达到路网畅通已成为全社会的共识，并且对我国的国民经济建设 有重要的现实意义和经济价值。 本课题即是针对实际交通过程中出现的交通拥堵、路径选择不合理等情况对交通路径 进行研究，分析路径选择及路径诱导策略，研究了在路径诱导中采用的各种不同路径选择 算法，并进行数据验证对比，找到一种贴合实际需要、满足要求的、并能够有效实施的路 径选择算法而提出的。 ， 课题利用蚁群算法中的分布式计算机制、个体相互协作寻找最优路径的群体性行为特 性对纷繁复杂的交通数据进行处理，针对交通过程中不同的耗费代价标准及时作出代价最 小的决策，选择最优路径。同时也与其他以d i j k s t r a 算法为代表的一些最短路径算法进行 对比，获得交通路径诱导系统中最有效的、满足实时要求的最优路径选择算法策略。 在公路交通系统中，进行最优路径算法的分析与研究，能够有效地发挥各种算法在处 理各种动态组合优化问题方面的作用，并能拓广各种智能优化算法的应用范围。同时引入 新的仿生算法，能够结合实际交通流的特点进行仿真模拟，具有较强的理论研究价值。在 实际交通网络中，针对现有道路交通状况进行最优路径算法方面的研究，结合智能化思想， 将局部搜索与全局搜索想结合，利用算法发现最优解的能力，指导市民出行，在最大程度 上缓解交通拥堵，并进一步能够为交通管理部门制定合理的管理政策和服务手段，促进北 京的市政化和数字化建设。为北京经济的进一步发展和2 0 0 8 年北京奥运会的顺利开展奠 定良好的环境和坚实畅通的道路基础。 1 3 交通最优路径选择的国内外研究现状 最优路径的选择，最后都要归结到交通网络的最短路径问题。以最短路径为主的最优 路径问题一直是计算机科学、运筹学、交通工程学、地理信息科学等学科的一个研究热点。 通过最短路径的选择，可以将无序的交通出行变得有序，优化客流分布，减少出行的盲目 性，提高城市道路网的运行效率。 但是，两点间的“最短路径”可能需要考虑的并非仅仅是“空间距离”的最短，还有 “时问最短”和“经济上的最省”等等【8 】o 1 首都师范大学硕士学位论文交通系统中最优路径选择算法的研究 1 3 1 国外研究现状 目前国际上的i t s 研究形成了日本、美国和欧洲三大阵营，对交通路径诱导系统和路 径选择算法方面的研究也是如此，下面分别介绍日本、美国和欧洲的研究情况。 日本的车载路径诱导系统处于世界领先地位。1 9 7 3 年一个称为c a c s ( c o m p r e h e n s i v e a 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 的行程时间的结 论 9 1 。从1 9 9 0 年开始的r g s ( r o u t eg u i d e n c es y s t e m ，路径诱导系统) 项目在日本建立 了世界上提供无偿服务的、第一个进行交通信息服务的通信系统，1 9 9 6 年4 月r g s 正式 开始。信息服务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 l n ，全球定位系统) 和f m 调频 副载波接收功能，可以进行车辆导航和路径诱导。和r g s 的免费信息服务形成对照的是 东京的a t i s ( a d v a n c e d t r a f f i ci n f o r m a t i o ns y s t e m ，先进的交通信息服务系统) 的有偿信 息服务。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 每5 m i n 从各种信息源获得交通信息，重组整理后将其传给a t i s 终端， 终端以一电子地图显示交通拥挤程度并推荐一条最快路径。 美国的t r a v t e k ( t r a v e lt e c h n o l o g y ，旅行技术) 和a d v a n c e ( a d v a l i c ed r i v e ra n dv e h i c l e a d v i s o r y n a v i g a t i o nc o n c e p t ，先进的驾驶员咨询与车辆导航概念) 是两个典型的自治型路 径诱导系统项目 1 0 1 。t r a v t e k 是由美国联邦公路委员会、佛罗里达交通部及奥兰多市等政 府部门和通用汽车、美国汽车委员会等私人合作者联合开发的路线引导系统。历时两年， 于1 9 9 2 年1 月在奥兰多市开始运行。t r a v t e k 向用户提供车辆当前位置、动态交通信息、 路线选择和引导等丰富的信息服务，帮助驾驶员安全、快速地穿过拥挤地区【l l 】。 t r a v t e k 系统由三大部分组成( 如图1 1 所示) ：( 1 ) t r a v t e k 信息和服务中心( t r a v t e k i n f o r m a t i o n & s e r v i c ec e n t e r ，t i s c ) ，由美国汽车委员会负责建立和管理。( 2 ) 交通管理 中心( t r a f f i cm a n a g e m e n tc e n t e r ，t m c ) ，由政府部门负责建立和管理。( 3 ) 装备有计算 机及通讯设施的车辆( 称为t r a v t e k 车辆) ，包括车内系统所有硬件、软件及通讯设备均 由通用汽车公司提供。这三部分利用电话线路、8 0 0 m h z 的调频广播和自动蜂窝电话等多 种数字通讯方式相联系。 4 首都师范大学硕士学位论文交通系统中最优路径选择算法的研究 t r a v t e k 车辆 窝电话通讯 图1 1 t 伯v 1 e k 系统组成 a d v a n c e 是一个a t i s 示范工程，车辆利用差分g p s 导航及定时计算、地图匹配来引 导它们的路径。而这些车辆作为一种探测器，将动态运行信息传至交通信息中心，然后中 心将这些信息传送给其他车辆帮助它们进行动态路径选择。 欧洲对路径诱导系统的研究开始是基于红外信标通信展开的，德国和英国分别在8 0 年代 末期开发出了用于示范的l i s b 系统和a u t o g u i d e 系统，而后英国推出了世界上第一个商 用车载路径诱导系统t r a m cm a s t e r 。进入9 0 年代，德国西门子公司基于l i s b 开发的 a l b s c o u t 系统具有一定的国际影响，它不但安装于德国柏林等欧洲城市，亦应用到了美 国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 ( s t u t t g a r tt e r r i t o r i a lt r a f f i co p e r a t i o na n dm a n a g e m e n t ，斯 图加特区域性交通运营管理) 项目致力于开发双模式路径诱导系统：即在安装红外信标的 区域开发基于红外信标的中心决定式路径诱导，同时在广域网内开发基于r d s t m c 交通 广播的路径诱导。 1 3 2 我国研究现状 我国对路径诱导系统的研究起步较晚，2 0 世纪9 0 年代初，一些高校和交通研究机构 开始了城市交通诱导系统技术的研究和尝试。在“九五”期间，交通部提出加强智能公路 运输系统的研究和发展与目标规划，目的在于结合我国国情，分阶段地开展交通控制系统、 驾驶员信息系统、车辆调度与导航系统、车辆安全系统及道路收费管理系统等5 个领域的 5 首都师范大学硕士学位论文交通系统中最优路径选择算法的研究 研究开发，并在此基础上加速科技成果商业化的进程。目前处于定位系统、电子地图、通 信系统等问题的研究阶段，投入使用的基本上都是以无线广播为主的初级诱导手段。基于 g p s 、集群通信和可变标志牌的诱导系统正处于研究和试验阶段，而对比较全面的动态路 径诱导系统的研究还处于起步阶段【1 2 1 。 上海交警总队和同济大学于1 9 9 5 年6 月完成的多段接力式动态标志路线引导系统通 过可变标志牌和广播实现交通流诱导。由于可变标志牌仅显示单一路段交通信息，只适合 诱导路段比较单纯的高速公路网，而在行驶路径较为复杂的城市路网中，则会因为诱导路 径过短而产生误导现象。哈尔滨工业大学运用g p s 和集群通讯系统设计的试验性指挥调 度系统，适合于公安、消防、电力等特殊交通集团做分组调度使用。由清华大学、北京人 民广播电台和中科院遥感所共同研制的车辆定位导航系统利用调频广播副载波传送差分 g p s 信号，由车载g p s 接受信号并修正自己的位置，但此系统目前只能提供车辆定位信 息和静态地理信息。 上述提到的诱导系统基本上都是以无线广播和可变显示屏为主的初级路径诱导系统。 其路径诱导形式还处于群体诱导，并没有实现单车实时动态路径的诱导。因此，上述成果 只解决了交通诱导路径系统的部分技术问题，但对于更复杂的诱导方式和交通系统，其研 究的涉及范围和深度有限，尚有许多关键问题有待于研究和开发。并且伴随着交通状况、 交通车辆、出行方式等的多样化，选择一种合理的交通路径诱导算法进行最优路径选择也 迫在眉睫。本文正是在这样的发展现状与背景下进行的。 1 4 论文的研究内容与组织 最优路径算法研究的主要是以最短路径算法为代表的各种算法。主要研究根据实际的 城市道路路网，通过分类的方法处理不同要求下的路权问题，根据各因素在最短路径中的 重要性修改算法的适用范围，综合上述两方面的研究来修改最优路径算法的实现步骤。算 法的研究包括传统的路径选择算法和当前兴起的新的模拟仿生算法等。本文主要研究的是 适合大型道路交通网络的最优路径算法，所以对于用户端是如何定位和通讯的等问题不做 深入的研究。 本篇论文的主要工作可以分为下面三部分： 研究路径诱导系统中路网的设计与存储方案。分析道路路网的表达、路径的权重、 存储结构等。 研究各类传统的最短路径算法，分析各种最短路径算法在公路交通路径选择中的 6 首都师范大学硕士学位论文 交通系统中最优路径选择算法的研究 适用性、有效性，确定算法的应用条件和应用范围。 深入研究蚁群算法理论，对蚁群算法的特点、应用方式、算法的数学支持进行详 细的讨论。将其作为一种最优路径选择算法与各类路径选择算法进行对比。确立 大型交通网络中的最优路径选择算法。 本论文分为五个章节。其组织如下： 第一章，绪论。分析了我国城市道路中存在的典型问题，论述了最优路径选择算法课 题研究的背景与意义，介绍了国内外有关最优路径选择算法研究的现状。 第二章，交通路网的表达方式与存储结构。从路网的表达方法、路网的存储结构以及 路网属性数据库的设计与实现等方面介绍了各种交通网络的表达方式，从而确立交通数据 在计算机中的存储结构与表达方式。 第三章，经典的最优路径算法及其应用。讨论了最优路径的基本问题和数学表示，介 绍了最优路径选择算法的基本术语。研究了当前实际应用中的几种经典的最优路径算法， 包括d i j k s t r a 算法，启发式算法等，并对算法的特点、适应性等进行分析。并进一步讨论 其分别在路径选择中的应用和存在的问题。 第四章，基于蚁群算法的最优路径选择。介绍了蚁群算法的发展过程，基本算法原理； 讨论了蚁群算法解决交通路径问题的可行性，以及实现交通最优路径选择的蚁群算法模 型：研究了基于蚁群算法的最优路径选择问题，并对蚁群算法进行最优路径选择进行了实 现，通过实验进行参数选择，确立最优的参数组合。最后与其他经典的最优路径算法进行 了仿真比较。 第五章，总结与展望。对全文进行了总结，并指出了当前存在的一些问题，以及指出 了今后应努力的方向。 1 5 本章小结 本章从我国城市道路中存在的典型问题，分析了交通最优路径选择课题的研究背景与 开展意义，并介绍了该课题在国内外发展的现状，最后列出了论文的研究内容与各章节的 组织结构。 7 酋都师范大学硕士学位论文交通系统中最优路径选择算法的研究 第二章交通路网的表达方式与存储结构 交通路网( 以下简称路网) 是计算最优路径与路径诱导的基础和对象。路网的表达方 法与存储结构直接决定了路径优化算法的种类以及算法的难易程度。路网数据库所存储的 信息，如结点信息、路段信息等交通管制信息，也直接影响到最优路径的计算。由于要实 现最优路径的选择，所以实际的路网必须以合理的表达方式和数据结构组织、存储起来， 成为计算机和算法能够识别的符号或信息。这样才能选择出最优路径。 本章研究的主要内容是采用何种方式表达和存储路网，既能满足路径选择计算的需 要，又要存储量小。所谓满足路径选择计算的需要是指路网的各种属性，如路段的属性、 交叉口的属性等要满足最优路径的需要，特别是有关单行线、交叉口转向限制等交通管制 信息，如何在路网中表达，需要很好地研究。所谓的存储量小是指路网在计算机中所占的 存储空间要小。因为路网是一个庞大的网络，路网有很多方面的属性，因此不可能存储全 部的属性信息，也是没有必要的。另外具体的路网表达方法与储存结构是密切联系的。 2 1 路网的表达方式 从路网的直观结构考虑，很自然地会想到用图来表示路网，交叉口对应结点，两交叉 口之间的路段对应边或弧，路段的某种量化属性作为权值，这样用一个赋权图就可以初步 地描述路网；又由于同一路段的不同方向其属性一般而言不尽相同，故应采用有向图描述 路网。而且用图来表示路网也符合最优路径的计算和选择的需要。本章较多地涉及到图的 有关知识，首先介绍论文中与图相关的基本定义和术语。 2 1 1 图的基本定义和术语 图的定义 图( g r a p h ) 是由非空的顶点集合和一个描述顶点之间关系的边或者弧的集合组成 1 4 d 5 1 0 在图论中，用有序三元组g = ( 矿( g ) ，e ( g ) ，q ，g ) 来表示一个图。其中： ( 1 ) v ( g 1 称为结点集，是图g 中顶点的集合； ( 2 ) e ( g ) 称为边集，是图g 中边的集合，并且v ( g ) n e ( g ) = 中； 首都师范大学硕士学位论文交通系统中最优路径选择算法的研究 ( 3 ) q o 称为关联函数，是e ( g ) 到矿( g ) 的有序或无序对集合的映射。 v ( g ) 中的元素称为结点，e ( g ) 中的元素称为边或弧，y ( g ) 所含元素的个数即结点 个数称为图的阶，记为i 矿( g ) i 或，l ；以g ) 所含元素的个数称为g 的边数或弧数，记为 i e ( g ) i 或m 。 有向图和无向图 在一个图中，如果任意两个顶点h ，_ 构成的偶对 e 是有序，即顶点_ ， y ，之间的连线是有方向的，则称该图为有向图，此时边e 往往用弧a 来表示；反之，若 偶对 占是无序，则称该图为无向图。 顶点、边、弧、弧头、弧尾 顶点集v ( g ) 中的数据元素u 称为顶点( v e r t e x ) 或者结点( n o d e ) ； 以v j ，0 ) 表示顶点吩，吩之间有一条直接连线。如果是在无向图中，则称这条连线为 边e ；而如果是在有向图中，一般称这条连线为弧爿。边用顶点的无序偶对( u ，_ ) 来表示， 称顶点叶和顶点吩，互为邻接点，边( 叶，0 ) 依附于顶点h 和顶点0 ；弧用项点的有序偶 对 来表示，有序偶对的第一个结点叶被称为始点( 或弧尾) ，在图中就是不带箭 头的一端；有序偶对的第二个结点 ，被称为终点( 或弧头) ，在图中就是带箭头的一端。 稀疏图和稠密图 对于雄个结点的无向图，边数m 的最大允许值为；盯。一1 ) ；对于刀个结点的有向图， 弧数m 的最大允许值为n ( n - 1 ) 。边数或弧数远远小于此值的图( 如m = o ( n ) ，或 m n l o g n ) 称为稀疏图，反之称为稠密图( 如m = o ( n 2 1 ) 。 赋权图 图的边或弧可具有与之相关的数据信息，可以表示从一个结点到另一个结点的距离、 费用等等。这种与图的边或弧相关的数据信息叫做权( w e i g h t ) ，这种边或弧带权的图称 为赋权图或赋权有向图，通常又称为网络。 另外，图的结点也可能带有反映其某种特性的量化信息( 称为结点权重) ，这种带有 结点权重的图称为点赋权图。 9 首都师范大学硕士学位论文交通系统中最优路径选择算法的研究 一般地，将弧 上带的权记为w ，它也称为这条弧的长度。 结点的关联边 在有向图中，弧 称为从结点h 发出，也称为结点u 的前向关联边；类似地， 弧 称为射入结点，也称为结点叶的后向关联边。 结点的出度和入度 结点v 的度( d e g r e e ) 是指和v 相关联的边的数目，记为d ( 力，在有向图中，以结点 ，为终点的所有弧的数目，称为该结点的入度( i n d e g r e e ) ，记为i d ( v ) ；以结点y 为始点 的所有弧的数目，称为该结点的出度( o u t d e g r e e ) ，记为o d ( v ) 。 连通、连通图、单向连通图、强连通图、弱连通图 在无向图g 中，如果从结点u 到结点_ 有路径，则称u 和叶是连通的。如果图中任 意两个结点u ，”，v 都是相互可达的，即畸和都是相互连通的，则称是g 连通图 ( c o n n e c t e dg r a p h ) 。 在有向图g 中，如果在任何顶点偶对中，至少从一个顶点q 到另一个顶点_ 是连通 的，则称图g 是单向连通图；如果在任何两个顶点偶对中，两顶点u 与_ 都是相互连通 的，即对于每一对结点_ ，0 v ，叶，从叶到和从”到畸都存在路径，则称图g 强 连通图；如果把有向图g 作为无向图是连通的，则称图g 是弱连通图。 路径和路径长度 对于无向图，结点叶到结点0 之问的路径( p a t h ) 是指结点序列p v l ，1 2 ，_ ) ，其 中叶矿( 1 - i s ，) ，r ( v ，v j + 1 ) e ( 1 i ，一1 ) ，此时路径的长度m 定义为边的数目， 即： l e t = j 一1 ( 2 1 ) 对于有向图，路径也是有向的，结点v 。到结点v 2 _ f n j 懈( p a t h ) 是指结点序列 尸“，v 2 ，v ) ，其中v i 矿( 1 f ，) ，且 e e ( 1 i j - 1 ) ，此时路径p 的长度“ 定义为边的数目，即： 1 0 首都师范大学硕士学位论文交通系统中最优路径选择算法的研究 l e a = _ ，一l ( 2 - 2 ) 对于赋权有向图，路径p 的长度是其所经过的弧的长度之和，即 三m = w ( 2 3 ) i 叶叶) e p 若路径p 是从结点v ，到结点_ 的所有路径中长度中最短的一条，则称尸是从结点岣 到结点_ 的最短路径，其长度t 。 ，称为从结点v i 到_ 的最短距离。 结点的后继和前驱 对于有向图g = ( l e ) 的一条路径p “，v 2 ，_ ) ，当l s f 0 ，根据情况，其值可以稍微给大一些。 最少费用 根据路况，选择最佳经济路径( 尽可能不走收费道路) 。所以可通过加大收费道路的 权值实现。具体的实现方法同上。 心= 协耋：。，簇淼霉路 协 心2 1 ( + 五+ 五，+ 1 ) 如，如果是收费道路 幢。w 其中无 0 ，根据情况，其值可以稍微给大一些。 2 1 4 路网的拓扑关系 拓扑关系是指如何表达点状实体、线状