（模式识别与智能系统专业论文）交通网络分析中的最优路径算法研究.pdf

中国科学技术大学硕士论文 摘要 最优路径算法是交通网络分析中路径分析的核心。当前对交通网络动态最优 路径问题的研究有两大方向，一是传统静态最优路径算法在交通网络中的应用。 二是通过对道路交通流的建模，运用动态规划、变分理论、随机过程理论等知识 建立影响交通流的各要素间的依赖关系，再求解最优路径。前者基于一种静态的 路段权值假设，即该路径的权值在最优路径算法求解过程中保持不变。而这种假 设在交通网络中是不成立的。交通网络的一大特征正是时变性和不可预知性。若 以道路的通行时间来表示该路的权值，则同样一条道路的权值可能因为一天中的 不同时刻而有很大的差别，从而最优路径可能也不止一条。静态最优路径算法无 法解决这个问题。后者往往由于模型一般比较复杂( 模型越是接近实际的交通流 状况就越复杂) 而难于求解。 本文针对最优路径算法在实际应用( 如导航应用) 中的特点，提出了分时分 段计算动态最优路径的思想，即在对应时段对应路段应用得到的交通信息指导路 径寻优；并依据该思想提出了动态最优路径算法和自适应的动态最优路径算法。 前者依据各路段的权值在一天中对应时段的统计分布状况，根据车辆到达路口的 时间，通过查表的方式计算出一个全局的最优路径，该算法用以解决成批派车的 点到点之阈最优路径问题。后者依据车辆到达路口的时间。实时接收该时刻各路 段的权值分布情况，选出一条最优路径到达下一个路口：在下一个路口继续应用 该策略直到到达目的地，该算法可以解决具有随机出行特征的单车实时选择最优 路径阀题。 关键词：胁算法动态最优路径算法自适应动态最优路径算法矢量地图全球卫 星定位系统地理信息系统智能交通系统 中国科学技术大学硕士论文 a b s t r a c t t h es h o r t e s tp a t ha l g o r i t h m sa r et h eg o r eo fp a t ha n a l y s i so ft r a n s p o r tn e t w o r k a n a l y s i s t h ec u r r e n tr e s e a r c ho ft h ed y n a m i cs h o r t e s tp a t ha l g o r i t h m sh a st w o o r i e n t a t i o n s o n et h ea p p l i c a t i o no ft r a d i t i o n a ls t a t i cs h o r t e s tp a t ha l g o r i t h m sa n dt h e o t h e ri sc o m p u t i n gt h es h o r t e s tp a t hw i t ht h ea p p l i c a t i o no fk i n d so fk n o w l e d g e t h r o u g hm o d e l i n gt h et r a n s p o r t a t i o ne n v i r o n m e n t s t h ef i r s tm e t h o db a s e so nt h e f i x e dw e i 曲h y p o t h e s i so ft h ep a t hw h i c hd o e s n tc o i n c i d et h ef a c tt h a tt h et r a n s p o r t n e t w o r ki sad y n a m i cn e t w o r kw i t hav a r i e da n du n p r e d i c t a b l ew e i g ho fe a c hp a t hi n a l lt i m e t h ed y n a m i cs h o r t e s tp a t h sm a yv a r yw i t hd i f f e r e n tt i m ei nad a y , s os t a t i c s h o r t e s tp a t hc a n n o ts o l v et h i sn e wp r o b l e m t h es e c o n dm e t h o do f t e nc a n n o tg e tt h e a c c n r a t es o l u t i o nf o ri t sc o m p l i c a t e dm o d e l t h i st h e s i s r a i s e san e ws t r a t e g yt oc o m p u t et h ed y n a m i cs h o r t e s tp a mi r i t r a n s p o r tn e t w o r ka c c o r d i n gt ot h ec h a r a c t e r so far e a lt i m ee n v i r o n m e n t t h a ti s s e a r c h i n gt h es h o r t e s tp a t hi nt h el i g h to ft h ep o s i t i o na n d t h ea r r i v a lt i m et h r o u g ht h e a c q u i r e m e n to fr e a lt i m ei n f o r m a t i o no ft r a n s p o r t a t i o n t h et h e s i sa l s og i v e s t w o a l g o r i t h m sw h i c ha d a p tt o d i f f e r e n tc i r c u m s t a n c e s t h ed y n a m i cs h o r t e s tp a t h a l g o r i t h mc o m p u t e st h eg l o b a l s h o r t e s tp a t ht h r o u g hc h e c k i n gt h et a b l ew h i c h m a i n t a i n sa l lp a t h s w e i g hi nt h ec o r r e s p o n d i n gt i m es e g m e n t ，a n dt h i sa l g o r i t h mc a n a f f o r das o l u t i o nf o rab a t c ho fc a r r i e r s t r a v e l t h ea d a p t i v ed y n a m i cs h o r t e s tp a t h a l g o r i t h ma c h i e v e san e ws h o r t e s tp a t hi ne v e r yc r o s s i n gt og u i d et h ec a r r i e rt og ot o t h en e x to n et h r o u g ha c q u i r i n gt h er e a lt i m ei n f o r m a t i o no ft r a n s p o r t a t i o n ，w h i c hc a n s o l v et h er e a lt i m en a v i g a t i o no f i n d i v i d u a lt r a v e l k e yw o r d ：a a l g o r i t h m ，d y n a m i cs h o r t e s tp a t ha l g o r i t h m ，a d a p t i v ed y n a m i c s h o r t e s tp a t ha l g o r i t h m ，v e c t o rm a p s ，g l o b a lp o s i t i o n i n gs y s t e m ( o p s ) ，g e o g r a p h i c i n f o r m a t i o ns y s t e mf o rt r a n s p o r t a t i o n ( g i s - d ，i n t e l l i g e n tt r a n s p o r ts y s t e m ( i t s ) n 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名： d 7 年上月日 f 1 中国科学技术大学硕士论文 绪论 第一章绪论 本章首先简要介绍了智能交通系统( i n t e l l i g e n tt r a n s p o r ts y s t e m ，i t s ) 、全球定位系统 ( g l o b a lp o s i t i o n i n gs y s t e m , g p 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 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 mf o rt r a n s p o r t a t i o n , g i s t ) 的相关内容 然后分别就静态最优路径和动态最优路径的研究现状做出简要概括。最后给出了本文的研究 方向 1 1i t s 简介 i t s 是数字城市的一个重要组成部分，本节就i t s 的发展历史和组成作一简介。 1 1 1i t s 的由来 交通是国民经济发展的两大支柱之一，交通运输是国家的经济命脉，是生产力的重要体 现。交通问题具有明显的地域特征，是地理信息科学的一个主要研究发展。此外，交通技术 的发展与电子技术、通讯技术、计算机技术等高新技术的发展息息相关：这些高新技术也是 实施“数字地球”战略必须着重发展的技术。可以毫不夸张地说，数字交通将是“数字地球” 战略发展的最大受益者之一，同时也是实施“数字地球”战略的一个重要组成部分。 城市交通网络在城市发展中占有至关重要的地位。它不仅是城市的一个重要组成部分， 同时也决定了城市中居民的生活方式长期以来，交通问题已成为困扰城市发展的重要问题。 世界各国都面临这日益严重的城市交通问题如交通拥挤、车辆行驶缓慢、交通事故频繁及 其由于交通堵塞造成的大量空气污染等问题。很多发达国家逐渐认识到，欲有效解决这些问 题，仅仅依靠道路建设，扩大路网规模是远远不够的，交通问题的解决必须依赖现代信息技 术与管理技术的有机结合他们纷纷呼吁对现代交通问题给予新的认识，建立卓有成效的， 对环境危害低的交通系统，更方便地进行客货运输促进经济发展，减少交通事故 为了解决我国城市的交通问题，改善城市交通系统的性能，一方面需要通过改造路网系 统、拓宽路面，增添交通设施以及道路建设等城市交通所必需的“硬件”建设来实现；另一 方面需要通过采用科学的管理手段，把现代高新技术引入到交通管理中来提高现有路网的交 通性能。这样就可以改善整个道路交通的管理效率，提高道路设施的利用率，实现城市交通 管理的科学性和有效性。2 0 世纪9 0 年代初，美国、日本和西欧等竟相投入大量资金和人力， l 中田科学技术大学硕士论文 开始大规模地进行道路交通运输智能化的研究和实验，称之为“智能车辆道路系统” ( i n t e l l i g e n tv e h i c l ea n dh 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 s i t s ) 。 1 1 2i t s 的组成 i t s 是将先进的信息技术，数据通讯传输技术、电子传感技术，电子控制技术以及计算 机处理技术等有效地集成运用于整个地面运输管理体系，而建立起的一种在大范围内，全方 位发挥作用的，实时、准确、高效的综合运输和管理系统“1 i t s 将汽车，司机、道路及其 相关的服务部门相互连接起来，使得汽车在道路上的运行智能化。它的概念模型如图1 所示： 图1 智能变通系统( i t s ) 的概念模型 具体地说，该系统将采集到的各种道路交通及服务信息经交通管理中心集中处理后，传 输别公路运输系统的各个用户( 司机、居民、公安局、停车场，运输公司、医院、救护摊障 等部门) ，出行者可实时选择交通方式和交通路线；交通管理部门可自动进行合理韵交通疏 导、控制和事故处理：运输部门可随时掌握车辆的运行情况，进行合理调度。 i t s 主要由6 个高级交通系统构成，分别为：高级交通管理系统、高级出行信息系统， 高级车辆控制系统、商业车辆运行系统，车辆自动定位系统及车辆自动识别系统“1 。这6 个 高级系统有可细分为2 9 个公共服务系统。i t s 通过这些公共服务系统完成公路与街道的交 通j i 盏控。为出行者提供交通信息，对可能出现的险情及延误预先提出警告，帮助交通管理部 门对车辆进行有效的实施疏导、控制和事故处理，减少交通阻塞和延误。辅助车辆的自动导 2 中国科学技术大学硕士论文 航、进行公麸交通的实时调度和行驶路线的调整，帮助运输部门增加客运宰降低运营成本， 提高商业运输效率等。 1 2 1g p s 简介 1 2g p s 、g i s 简介 世界上第一个实用的卫星导航系统是美国研制的“予午仪”( t r a n s i t ) 它于1 9 6 4 年 正式投入使用子午仪系统能在全球范围内，全天候实现二维( 经度，纬度) 定位，其定位 的精度为o 1 0 3 海里，因而获得了广泛的应用。然而其定位不连续、不实时、不能给出高 度的缺点对航空、航天、测绘等一些用户的应用受到影响1 2 1 为了满足军事应用和民用提出的更高要求，美国于1 9 7 3 年开始研制一种新的卫星导航 系统导航星全球定位系统( n a v s t a rg l o b a lp o s i t i o n i n gs y s t e m ) ，该系统简称为全球定位 系统( g p s ) 或导航星( n a v s t a r ) 系统。n a v s t a r 是n a v i g a t i o ns a t e l l i t et i m i n ga n dg a n g m g 的缩写，其含义为用导航卫星类进行计时和测距。目前，国际上已经公认；将这全球定位 系统简称为g p s g p s 经过漫长的研究、试验、研制和组网阶段，经受来自经费和技术方 面的挫折，于1 9 9 4 年3 月l o 日第2 4 颗工作卫星进入预定轨道，系统全面投入使用。它不 仅能在世界上任何一个地方任何时候同时接收4 颗卫星信号进行高精度的三维位置( 经度、 纬度和高度) 测定，还能实时地对运载体进行三维速度的测定和高精度的授时。它从根本上 解决了定位和导航的问题，可以满足各类不同用户的需要。g p s 已经成功地应用于舰船和 飞机的导航，导弹卫星测控、精密绘制、精密授时、作战训练、石油资源开发、车辆的跟踪 和导航等方面。近几年来，农业、公安和旅游等行业也纳入了g p s 的应用范围 虽然美国原计划研制g p s 主要是为了军事目的，但是，考虑到民用卫星定位的大量需 求；美国政府在进行g p s 系统设计时，计划提供两种服务1 2 l ：标准定位服务( s p s ：s t a n d a r d p o s i t i o n i n g s e r v i c e ) 和精密定位服务( p p s ：p r e c i s e p o s i t i o n i n g s e r v i c e ) 。标准定位服务利用 粗铡捕获码( c a 码；c o a r s e a c q u i s i t i o nc o d e ) 定位预计精度约为4 0 0 m ，以供民问用户 使用。精密定位服务利用精测码( p 码：p r e c i s ec o d e ) 定位预计精度约为i o o m ，供军方和 某些特许用户使用。在g p s 实验卫星应用阶段，多次测试表明：实际定位精度远远高于预 计的精度，利用c a 码定位精度可以达到1 5 m ，利用p 码定位精度可以达到3 m 。对于使用 c a 码的民用用户来说，这样的定位精度太高，影响到荚国的自身利益。于是，美国政府对 中国科学技术大学硕士论文 g p s 应用采取选择可用性s a ( s e l e c t i v e a v a i l a b i l i t y ) 政策。实旃s a 政策就是在卫星上采用 一种技术，人为地将误差引入卫星钟和导航数据以降低g p s 的定位精度，使得非特许用户 不能利用c a 码获得高精度定位p 】。在卫星上采用s a 技术后，使c a 码的水平定位精度限 制到l o o m ，垂直测量耪度为1 5 6 m 。美国国舫部常年对s a 政策进行测量，并根据形势和要 求对部分和全部卫星取消s a 政策s a 政策的引入，在一定程度上限制了g p s 的应用。为 了提高定位精度。人们研究出差分g p s 技术- - d g p s ( d i f f e r e n t i a lg p s ) 。但是。d g p s 系 统需要建立相应的差分基准站和监测站，造价昂贵。随着g p s 应用的不断发展。g p s 广大 用户要求取消s a 政策的呼声越来越高，考虑到庞大的g p s 应用市场，美国政府最终于2 0 0 0 年5 月1 日取消了s a 政策，这大大促进g p s 定位和导航的应用的进一步发展。 2 0 0 0 年以后以波音公司为首，休斯空问和通信公司、计算机科学公司( c s c ) 、洛克西 德马丁管理与数据系统( m & d s ) 和雷声公司开始研究开发新一代的全球定位系统- - g p s 1 1 1 g p si l l 的结构基于现有的卫星导航系统，并将开发出具有创新结构的g p s 系统。我国 也开始研发自己的卫星定位系统北斗导航系统。2 0 0 0 年1 0 月3 1 日。我国自行研制的 第一颗“北斗导航试验卫星”在西昌卫星发射中心发射升空；1 2 月2 1 日，第二颗“北斗导 航试验卫星”发射升空；2 0 0 3 年5 月2 5 日，第三颗“北斗一号”被成功地送入太空，标志 着中国已经拥有自主建立完善的卫星导航系统，也预示着我国导航定位技术将发展到了一个 新的阶段。 1 2 2 g i s 简介 g i s 这一术语是1 9 6 3 年由r o g e rf t o m l i m o n 提出的，2 0 世纪8 0 年代开始走向成熟， 但对g i s 没有统一的定义。文献f 4 】认为：“地理信息系统的定义由两部分组成：一方面，信 息系统是- f l 学科，是描述、存储、分析和输出空问信息的理论和方法的- - f l 新兴的交叉学 科：另一方面，地理信息系统是一个技术系统，是以地理空间数据库为基础。采用地理模型 分析方法，适时提供多种空间地理信息和动态地理信息，为地理研究和地理决策服务的计算 机技术系统。”；文献【5 】给地理信息系统下的定义是：“地理信息系统是一种特定而又十分重 要的空间信息系统，它是以采集、储存、管理、分析和描述整个或部分地球表面( 包括大气 层在内) 与空间和地理分布有关的数据的空间信息系统。1 9 8 7 年英国教育都( d ( ) e ) 下 的定义是：“g i s 是一种获取、储存、检查、操作、分析和显示地球空间数据的计算机系统”。 1 9 8 8 年美国国家地理信息与分析中心( n c g i a ) 下的定义是：“为了获取、储存、检索、分 4 中国科学技术大学顼士论文 析和显示空间定位数据而建立的计算机化的数据库管理系统”关于g i s 国内外有许多定义， 不同的应用领域。不同的专业，对它的理解是不一样的。目前，g i s 还没有一个完全统一的 被普遍接受的定义1 6 1 英国著名地理信息系统和地图学家d r h i n d 说：“如果问1 0 0 个人， 什么是地理信息系统，也许会有9 9 种答案。但是地理信息系统是一种技术”l l 。虽然人们对地理信息系统的理解不完全一致但是地理信息系统一般具有以下三个方面 的特征： 1 具有采集、管理、分析和输出多种地理信息的能力，具有空问性和动态性； 2 由计算机系统支持来进行空间地理数据管理，并由计算机程序模拟常规的或专门的地理 分析方法，作用于空间数据。产生有用的信息，完成人类难以完成的任务； 3 计算机系统的支持是地理信息系统的重要特征，因而使得地理信息系统能以快速、耪确， 综合地对复杂的地理系统进行空问定位和过程动态分析。 g i s 是从2 0 世纪6 0 年代开始逐渐发展起来的新技术。由于地球是人们赖以生存和发展 的基础，所以g i s 是与人类的生存、发展和进步密切关联的一门信息科学技术，受到人们 愈来愈多的重视，其应用已涉及到各行备业。特别是近几年。由于全球信息化的飞速发展、 信息高速公路、“数字地球”、“数字城市”、“虚拟社区”理论的提出，g i s 产业受到了空前 的关注，越来越多的人投身到g i s 的学习浪潮中。 2 0 世纪8 0 年代是g 1 s 普及和推广应用的阶段。由于计算机的发展，推出了图形工作站 和p c 微机等性价比大为提高的新一代计算机计算机和空间信息系统在许多部门得到广泛 应用。随着计算机网络技术的普及应用，使她理信息数据的长距离传输时效得到极大的提高。 g i s 系统软件和应用软件的发展。使得g i s 从解决基础设施的规划( 如道路、输电线) 转向 更复杂的区域开发和规划。例如土地的农业利用、城市化发展、人口规划与布局等，地理因 素成为投资决策中不可缺少的依据。许多国家把g i s 作为有关部门的必备工具投入日常运 转。与卫星遥感技术想结合。g i s 开始用于全球性问题研究。例如全球沙漠化、全球可居住 区的评价、厄尔尼诺现象及酸雨、核扩散及核废料以及全球变化与全球监测。美国军方制作 了全球| ：1 0 0 万空阃数据库d c w ，原苏联制作了全球数字调和模型和数字正摄影像。2 0 世 纪8 0 年代，g i s 软件的研制和开发也取得t j i i 大的成绩，仅1 9 8 9 年市场上有报价的软件就 达7 0 多个，并且涌现出了一些具有代表性的g i s 商用软件，如a r c i n f o 、m a p i n f o ， m i c r o s t a t i o n 、m g ei n t e r g r a p h 等。 我国g i s 的发展虽然较晚，但发展势头迅猛，大体上经历了4 个阶段，即起步( 1 9 7 0 1 9 8 0 年) 、准备( 1 9 8 0 - - 1 9 8 5 年) 发展( 1 9 8 5 1 9 9 5 年) 、产业化( 1 9 9 6 年以后) 阶段。 5 生曼型堂垫查盔兰堕主堡苎 丝鱼 。九五一期间，原国家科委将g i s 作为独立课题列入“重中之重”科技攻关计划。给予充分 的重视和支持，技术发展速度明显加快，g i s 基础软件技术支持得到了全面的加强，出现了 一批有水平的技术成果和产品。先后涌现出一批优秀的国产g i s 平台软件，如g e o s t a r , 、 c i t y s t a r 、m a p g i s 、s u p e r m a p 等g i s 商用软件。它们已在很多部门和领域得到了广泛的应 用，并引起了政府部i 1 的高度重视。从应用方面看，地理信息系统已在资源开发、环境保护、 城市规划建设，土地管理、农作物调壹、交通、能源、地图测量、林业，房地产开发自然 灾害的监测和评估、金融、保险、石油与天然气，军事、犯罪分析、运输与导航、i1 0 报警 系统、公共汽车调度等方面得到了具体应用。 1 2 3g i s t 简介 交通网络具有很强的空间特征。而g i s 能够有效地对地球空间数据进行采集、存储、 检索、建模、分析和输出，它的独特之处就在于能够把地理位置和相关属性信息有机地结合 起来。正是由于g i s 所具备的强大的空间操作，管理与分析功能使之与交通网络分析的结 合成为必然。g i s 技术为交通工程学的发展提供了一种先进的、有效的手段 交通网络分析需要实时地对网络特征进行描述、对弼络要素进行跟踪。g p s 是一种全 天候、全方位的导航系统，用于精密定位、测速和精确授时。借助于g i s 技术，可以得到 车辆在三维空间中的运动轨迹，即所谓四维航迹。g p 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 sf o rt r a n s p o r t a t i o n ，g i s t ) 是地理 信息系统技术在交通领域的推广和应用。作为缓解现代城市交通问题的有效技术手段， g i s - t 不但可以存储，管理和更新城市交通网络的空间数据库，辅助城市交通线路规划、交 通管理，而且更重要的是，通过与g p s 技术、无线通讯技术、互联网络技术、虚拟现实技 术的有机结合，在( 3 1 s 的数据库操作技术及空间分析技术的辅助下，可以建立广泛的实对 数字交通信息用户服务体系，实现全数字化交通信息的实时发布、存储与检索。为城市交通 管理、车辆的人工及智能导航、客货运输调度及居民出行等提供有效的技术支持。这种实时 数字交通信息用户服务体系在被交通问题困扰的大中城市具有十分迫切的市场需求 i t s 所包含的6 个高级交通系统中，有4 个与g i s - t 支持下的交通网络分析直接相关 由此可以看出g i s - t 在i t s 中占举足轻重的地位。交通网络分析的效率直接决定了交通分 6 中国科学技术大学硕士论文 析模型运行的质量。交通网络分析能够实时地根据用户需求对交通网络的空间、时序及属性 特征进行描述，辅助车辆路线选择、区位分配分析等并可对交通网络进行实时优化 目前，g i s - t 技术在国外发达国家发展很快在欧美等发达国家，各地方交通部门纷纷 采用g i s - t 技术建立交通管理系统、出行信息系统、商业车辆运行系统、车辆自动定位系 统及车辆自动识别系统等，并尝试通过i n t e r n e t 实时发布交通信息。在日本以丰田公司为 首的各大汽车公司，与交通部门通力合作，己制定了完善的数字交通信息通讯协议。并在全 球率先建立了全数字化交通信息台，通过广播电台实时发布城市交通信息，与之配套的车载 交通信息系统。可实时接收发布的数字交通信息，反映在计算机屏幕上，并可自动完成顾及 实对交通状况的车辆的自动导航 g i s 在我国已有l o 余年的发展历史，在资源、环境、测绘、城建等领域取得了很大的 进展。但g i s 在交通领域的应用，还只限于公路数据库的建立与管理，在城市交通领域， 也只限于静态的路段查询及检索。近几年，随着g p s 技术的广泛推广与普及，g i s g p s 集 成技术支持下的车辆导航与监控应用已经在我国得到了一定的发展。但其中存在一个很大的 问题，即静态的g i s 数据库不能反映实时变化的城市交通网络的动态特征，这在很大程度 上影响了车辆导航应用的有效性。 1 3 交通网络分析中动态最优路径算法研究意义 最优路径问题是一个很古老的问题，其原型是运筹学中的最短路径问题，目前在互联网 的寻址计算、智能交通系统。地理信息系统等领域有着广泛的应用。现代意义上的最优路径 已不再仅仅是指地理意义上的距离最短，它还可以是指时间最少、费用最省、线路容量最大 等等。但无论采用何种标准。最优路径问题都可归结为在加权网络中寻找最短路径的研究， 即图论中的最短路径问题 在i t s 所包含的6 个高级交通系统中，有4 个与g i s - t 支持下的交通网络分析直接相 关。交通网络分析的一个重要组成部分是路径分析，丽路经分析的核心为最优路径算法。对 最优路径的研究与应用有利子降低能耗，缩短运输时问，提高通行效率。因此，对最优路径 问题的研究不但具有重要的理论价值，而且具有重要的应用价值 传统的对最优路径问题的研究主要基于一种静态的路段权值假设，即该路径的权值在最 优路径算法求解前已知且在算法求解过程中也一直保持不变而这种假设在交通地理信息系 统的应用中是不一定满足的。交通网络是一种动态网络，它的最大特征正是时变性和不可预 7 中国科学技术大学硕士论文 知性。若以道路的通行时间来表示该路的权值，则同样一条路的权值可能因为一天中的不同 时刻而有很大的差别( 尤其上、下班时刻与其他时问) ，这将直接导致选择一条用时最少的 路径可能会有较大差别而静态的最优路径算法无视这种差别必将导致误决策。在这种情 况下就需要开发出新的动态的最优路径算法以解决新的问题 1 4 最优路径算法的研究现状 最优路径算法是智能交通中路径诱导系统的核心内容，从宏观来看，有以下几种主要的 分类方式： 1 ) 按诱导系统的目标可分为系统路径诱导和单车路径诱导系统路径诱导的目标是使得 交通网络给定时同区阔内的车辆的通行量达到最大。单车路径诱导的目标贝b 是使得车辆在起 始点之间的通行时间最短。 2 ) 按诱导路径生成方式可分为分散型诱导系统和中心型诱导系统。分散型诱导系统由车 载系统算生成诱导路径。而中心型诱导系统则由交通管理部门通过计算产生诱导路径，并 将结果通过通信装置传送给车辆。 3 ) 接路径诱导所依据的信息性质可分为静态路径诱导系统和动态路径诱导系统，相应的 是静态最优路径算法和动态最优路径算法。以下分g 就静态最优路径的研究现状和动态最优 路径的研究现状予以阐述。 1 4 1 静态最优路径算法的研究现状 静态最优路径算法的在路径寻优的过程中路径的权值为定值，可将其从以下几个角度进 行分类 从问题求解目标的不同，可将搜索算法分为求解单源点多汇点的最优路径和所有顶点对 之间的最优路径。前者的典型代表如d i j k s t r a 算法，后者的典型代表如f l o y d 算法。 从搜索算法的是否具有智能性的角度，可将其分为两大类，即盲目搜索和启发搜索。前 者如b f s 算法、d f s 算法、i d s 算法等等，其中也包括了d i j k s t r a 算法( 为简便起见，下称 d 算法) 。后者主要是一些人工智能领域的研究成果。包括遗传算法、蚁群算法、a 算法等 等普遍认为启发搜索算法比盲目搜索算法的效率要高。因为启发搜索引入了问题域的相关 信息。从而使得搜索更具针对性，这一点在稠密图搜索中表现得尤其明显 8 中国科学技术大学硕士论文 目前国内矢量地图最优路径问题的研究按照算法分类主要有以下几种： 1 以d 算法为基础对其优化，这是目前国内的研究热点。按其主要思想又可分为两类： 1 )通过减少需要搜索的节点数来提高算法的执行效率。如提取关键顶点的思想1 8 1 确 定最多4 条最优路径。而后选优。通过降低d 算法关联矩阵实现中0 ( 及一) 的冗余来实现 的邻接点算法【i o l 和应用弧与节点的关联的低值扩散算法柳。根据路网的设计原则( 如在没有 障碍的情况下，道路一般沿直线建造等) 确定一个最优路径的搜索区域( 椭圆搜索区域及矩 形搜索区域) 的思想i “l 。以十字链表结构记录顶点和边为基础，采用顶点分区和记录绝对 地址来优化d i j k s t r a 算法的方法i t 2 | 。将矢量地图中的节点分成两类：端点和交叉点。对不 同类别的顶点应用不同的搜索策略的文献。 2 )通过优化d 算法优先级队列的实现来提高算法的执行效率改进传统的优先级队 列的数组实现，如使用二叉堆的实现、使用b u c k e t 数据结构的实现嗍。辅以地址队列 通过对地址队列的排序来实现快速索引最小权值顶点【1 6 1 等还有一种称之为直线优化的d 算法。具体思想是指在应用d 算法的过程中将临时标记结点到源点的最短路径与该结点 到目标结点的直线距离之和作为此临时标记结点的一个属性值，以此属性值作为从临时标记 结点集合中选取永久标记结点的依据。算法总是选取此属性值最小的临时结点作为永久标记 结点 i t , t s l 。然其本质( 包括属性值的选取及算法的执行过程) 却是完全借用了h a r t 、n i l s s o n 和r a p h a e l 在1 9 6 8 年提出的a + 算法的思想 需要说明的是，以上两类的界限并不是十分清楚的，常常一类论文中也含有另一类的思 想。仍然将其分类是为了说明在算法执行的过程中哪类因素占据主导地位。 2 分层网络h i t o p o 。很多分层网络里的搜索算法还是基于d 算法的，但是将其单列， 是因为分层网络相对于平面网络有其自身的特点。一般通过对平面连通图的自定义划分。建 立了一个h i t o p o 图。其显著的优点有二：1 ) 路径的分等级搜索，更加符合交通工具出行的 实际情况。2 ) 单层图中需要搜索的节点数减少，总的算法的效率得到了提高。其显著的缺点 有一：不能确保得到的路径一定是最优的，是一种有损算法，因为局部最优和并不等于全局 最优。但是通过运用了限制搜索区域、比较、双向分层搜索等策略保证了了一个次最优的结 果，这类如文献f 1 ”啦”。还有一种类似分层网络的思想，但却不能不称之为分层网络，而是 一种子图划分的思想。大致是按照定的原则( 如按重要顶点) 将大图划分为小的子图，然 后对予图进行计算。最后将子图的顶点连接起来，形成最优路径。其优缺点大致同前这类 如文献l “。尽管该类算法只是得到一个次最优的结果，但是在实际应用中仍然有其重要的 o 中国科学技术大学硕士论文 实践价值。尤其是当全局最优搜索难以进行或花费的计算资源比较大时( 如一些超大规模的 城市) 。 3 某些智能算法在最优路径搜索中的应用。如遗传算法、蚁群算法、a 算法等。文献矧 采用变长度整数编码的染色体表示路径，设计了适合于最优车辆路径问题求解的遗传算子， 给出了适应度调整函数，求解最优路径。算法的执行效率较离，但用遗传算法解决路径规划 这类问题的难点在于路径编码、遗传算子设计、种群初始化等方面。文献i “l 使用a 算法实 现最优路径搜索，著且为保证一定是最优路径对算法进行如下优化：当使用a 算法找到一 条“最优路径”后。立即从目标点回溯树。在回溯过程中将所找到的最优路径与其他路径进 行比较，且保留较短路径，当回溯到树根时则可保证找到最优路径。 4 其他。如利用矢量地图的拓丰卜信息的方向优先搜索思想1 2 ，利用先验知识构造可能的 查询树。再进行深度优先遍历，确定最优路径的思想1 2 6 1 。此类算法的缺陷在于难以找到一 个通用的规则( 如方向规则的定义) 且依赖的外界条件有可能不成立( 如缺乏先验知识) 1 0 中国科学技术大学硕士论文 1 4 2 动态最优路径算法的研究现状 动态最优路径算法与静态最优路径算法最大的差别就在于算法中必须要考虑时阀的因 素，其路径的权值可以根据交通状况实时变化，以适应动态寻优虽然这更能反应实际的情 况，但对交通环境的智能化要求也较高，即要求能够实时接收交通信息以更新路径的权值。 在国外，动态的最优路径算法研究是一个热点，尤其是在一些发达国家。我国目前国内这方 面的研究不多其中一个重要原因在于我国的交通智能化水平不高。 由于引入了时间的因素，使得动态最优路径算法的研究方法大大增加。目前在国内主要 有以下一些思想。第一类是以传统的静态算法思想为基础，通过引入时间要素，将其应用到 动态的最优路径寻优中来。如动态的d i j k s t a 算法思想，这类文献如 2 7 ，2 8 ，2 9 。动态的a 算法思想，郾以r e k o r f 教授提出的l r t a * ( l e a r n i n gr e a lt i m ea ) 算法为基础，通过 改变估价函数值更新规则与解时间和解质量的相对折中，加快算法收敛速度。这类文章如文 献 3 0 3 1 。第二类是通过对道路交通流的建模，综合考虑各种动态因素对最优路径选取的影 响来选取实时的最优路径。如建立道路交通流的变分不等式模型和随机时间依赖网络模型， 前者如文献 3 2 ，3 3 后者如文献【3 4 ，3 5 】等。第三类是借助g i s 数据库技术，结合d i j k s t r a 算 法来实时寻优，如文献 3 6 。3 7 国外对动态的最优路径算法研究很多。除了上述提到的各种方法，还有如下一些主流思 想：第一类将对动态的最优路径算法按时问离散化为对一个时间序列的静态最优路径算法的 研究，这类文章如文献f 3 8 ，3 9 。第二类是基于交通流状态预测的思想，如文献f 4 0 】。第三类 是一些智能算法如神经弼络算法、遗传算法、退火算法在路径寻优过程中的应用。这类文章 如文献1 4 1 a 2 , 4 3 ，4 4 1 中国科学技术大学硕士论文矢量地图综述 第二章矢量地图综述 g i s 应用离不开电子地图，交通矢量地图作为一种融合了信息科学( 如计算机图形学、 数据库等) 、地理科学( 经纬度、地物分布等) 相关知识的新技术，是各类g i s - t 应用( 如城 市地理信息系统、车辆的导航、监控、定位等等) 的基础。自然它也是最优路径算法实施的 基础。此外矢量地图对于建设数字化地球、数字化城市也具有重要的意义。 本章主要介绍了矢量地图的相关概念，随后重点介绍了g p s 实验的矢量地图的概念模 型和存储组织，因为这是后面实验的基础。 2 1 矢量地图的基本概念 矢量地图是电子地图的一种，它通过一种记录坐标的形式来表达空问对象问的相对位 置，是目前各类g i s 应用的地图基础。 2 i i 电子地图及其分类 髓着计算机的出现和信息论的发展，地图制图逐步由手工绘制过渡到电子化、自动化的 阶段，从数字资料自动制图、图形资料自动制图到航空遥感和航天遥感图像的自动制图，电 子地图的技术发展非常迅速。不久以前，美国还利用卫星扫描生成全球的三维电子地图。电 子地图的应用非常广泛，在海洋、气象，水文、琏质、土地利用、地球物理、宇航、测绘、 勘探等领域都需要电子地图。2 0 世纪6 0 年代，g i s 的兴起和迅猛发展更推动了电子地图制 图的发展。g i s 是一种专门用于管理地理空间分布数据的计算机信息系统所以其中的数字 电子地图是一个必不可少的部分，在很大程度上决定了g i s 的命运。我国对箭图自动化和 g i s 的研究起步较晚，近几年，形成一股关于电子地图的研究热潮。 按照电子地图的数据格式可将其分为矢量电子地图和栅格电子地图。前者通过记录坐标 的方式尽可能精确地表达呈点、线、面分布的空间对象。后者则是以规则的像元阵列来表示 空间对象的分布，其阵列中的每个数据表示该空间对象的属性特征，如类型、等级等属性。 此外根据电子地图在g i s - t 应用场合的不同，可将其划分为车载导航地图、应用于监控跟踪 的电子地图、用于导游目的的手持式电子地图、用于智能交通全局指挥调度的电子地图等。 中国科学技术大学硕士论文 矢量地图综述 2 1 2 矢量地图在g i s 中的应用 矢量数据结构和栅格数据结构都可描述点、线、面这三种基本的空间对象类型。但其侧 重点则不同。矢量方法强调地理现象的离散性，即所有的地理现象都有边界，而实际上这些 边界可能不存在，如块多变形表示成一片居民区栅格方法将地理空间划分成一块一块的 栅格，其中，栅格的大小代表了定义的空间分解力它表示了栅格数据的比例尺；栅格的值 表达了这个位置的状态或属性。矢量数据结构的空间对象与要表达的地理现象具有一定的对 应关系，但栅格数据结构的空间对象则没有。表i 是两种数据模型的特点比较 栅格模型 矢量模型 1 教据结构简单 1 提供更严格的数据结构 2 叠加操作易实现更有效 2 提供有效的拓扑编码，因而对需要拓扑信息的 3 能有效表达空问可变性 操作更有效如网络分析 4 栅格图像便于做图像的有效增强 3 图形输出美观。接近手绘 表2 i 矢量数据模型与栅格数据模型比较i 习 除了以上一些基本特点比较外栅格图像在地理应用领域有着这样的缺陷：首先，栅格 图像文件对图像的每像素点( 不管前景或背景像素) 都要保存，所以其存储较大。其次，不 能对栅格地图上的对象( 曲线、文字或符号) 进行属性编辑如修改、拷贝、移动及删除等图 形操作，更不能进行拓扑求解，只能对某个矩形区域内的所有像索同时进行图像编辑操作。 再次，当图像进行放大或缩小显示时，图像信息会发生失真，如在放大的过程中发生像素堆 积成块的情况。特别是图像目标的边界会发生阶梯效应，而在缩小的过程中路会消失。而矢 量图形则不同。首先，由于矢量地图是通过记录坐标的形式来表达空间对象，所以其数据存 储量较小。例如成都市地图，按照大约1 ：2 0 0 0 0 0 的比例尺转化成2 4 位位图，大小约为1 5 m ， 而我们生成的矢量地图数据库，只有1 3 7 k ，近3 0 0 0 条道路( 矢量边) 的矢量文件大小只有 约6 1 k 。其次，在矢量图形中每个目标均为单个矢量单位( 点、线、面) 或多个矢量单位的结 合体。基于这样的数据结构，可以很方便地在地图上编辑各个地物，将地物归类，以及