（计算机应用技术专业论文）基于蚁群算法的交通地理最佳路径的研究.pdf

摘要 交通地理信息系统( g i s t ，g e o g r a p h i c i n f o r m a t i o n s y s t e m f o r t r a n s p o r t a t i o n ) ，是一个以地理信息系统( 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 ) 为 技术支撑，以城市交通为依托，以城市交通查询、规划和决策为目的的信息处 理系统。它涉及到交通领域的许多方面，最优路径的选择就是其重要应用之一， 是一类典型的组合优化问题，在车辆导航系统以及各种城市应急系统中有着广 泛的应用。传统的最优路径算法以d i j k s t r a 算法为代表。这些算法均属于贪心算 法，存在典型的局部最小问题，是一种静态的局部最优算法。当前的实际交通 网络数据规模庞大，算法需要提前将整个交通数据导入才能进行路径的选择。 这样显然不能反映出交通中不断变化的道路实际情况对交通路径选择的影响。 蚁群算法是一种新兴的模拟仿生算法，算法具有模拟生物界群体觅食的能力， 并且能够在实际的路径搜索过程中对外界的影响做出动态的响应，因而在交通 最优路径选择中具有极大的可行性与适应性。 论文首先介绍了交通地理信息系统的国内外研究现状、关键技术、主要功 能和具体应用，然后讨论研究了传统的最短路径选择算法，其中有d i j k s t r a 算法、 f l o y d 算法以及其他几种基于智能计算的最短路径算法。在以上几种经典的最短 路径算法的基础上，结合蚂蚁觅食行为引入蚁群算法，并研究了基本蚁群算法 的原理、模型、实现步骤和流程，分析了重要参数的设置，总结了蚁群算法的 优缺点，介绍了几种经典的改进蚁群算法，由于传统的改进蚁群算法模型只提 高了算法全局寻优的能力或者算法的收敛速度，为求在收敛速度和全局寻优能 力之间取得一种平衡，本文提出了基于自适应信息素更新的双种群蚁群算法， 根据信息量的分布情况进行信息量的更新，以动态地调整各路径上的信息量分 布，使之不至于过分集中或者分散，以在加速收敛的同时避免早熟。使用自适 应的信息素更新策略，增强了算法的全局寻优能力，同时，通过使用双种群策 略进一步提高了算法的收敛速度。通过实验结果分析，验证了改进后的蚁群算 法在稳定性和寻优能力两方面都取得了良好的效果。最后应用改进后的蚁群算 法，建立一个在不同交通条件下搜索g i s t 的最短路径问题的模型。 关键字：交通地理信息系统，蚁群算法，最短路径 a b s t r a c t 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 - tf o rs h o r t ，w h i c hi sa n i n f o r m a t i o np r o c e s s i n gs y s t e mb a s e do nt h eg i st e c h n o l o g y , r e l y so nu r b a nt r a f f i c a n dw i t ht h ep u r p o s eo ft r a f f i c i n q u i r y , p l a n n i n ga n dd e c i s i o n - m a k i n g i ti n v o l v e s m a n ya s p e c t so ft r a n s p o r t a t i o n ，e s p e c i a l l y , t h eo p t i m a lp a t hs e l e c t i o nw h i c hi so n eo f t h em o s ti m p o r t a n ta p p l i c a t i o n s ，i sat y p i c a lc 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 ma n d i th a sb e e nw i d e l ya p p l i e dt ot h ev a r i o u sv e h i c l en a v i g a t i o ns y s t e m sa n du r b a n e m e r g e n c ys y s t e m s 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 sa r er e p r e s e n t e db yd i j k s t r a a l g o r i t h m t h e s ea r ea l lg r e e d yw h i c ha r es t a t i cl o c a lo p t i m a la l g o r i t h m sa n dh a v e t y p i c a ll o c a lo 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 fr 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 el o a d e di 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 l e c tt h ea 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 nt h ep a t h c 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 cs i m u l a t i o na l g o r i t h m i th a st h e c a p a 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 gas h o r t e s tp a t hf r o mn e s tt o f 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 er o u t i n gs e a r c h p r o c e s s s oi t h 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 nf o r t r a f f i c f i r s t l y , t h et h e s i sp r e s e n t e dt h er e s e a r c h i n gs t a t u so fg i s th o m ea n da b o a r d ，t h e k e yt e c h n o l o g y , t h ei m p o r t a n tf u n c t i o n sa n da p p l i c a t i o n s ，s e c o n d l y , i td i s c u s s e da n d r e s e a r c h e ds e v e r a lt r a d i t i o n a la l g o r i t h m so fo 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 d d 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 do t h e ra l g o r i t h m s b a s e do ni n t e l l i g e n t c o m p u t i n g t h i r d l y , c o m b i n i n gt h e s et 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 sw i t ha n t f o r a g i n gb e h a v i o r , a n tc o l o n ya l g o r i t h m ( a c a ) w a si n t r o d u c e d ，a n dt h et h e s i sa l s o r e s e a r c h e dt h et h e o r y , m o d e l ，i m p l e m e n t i n gs t e p sa n dp r o c e s s e so ft h ea l g o r i t h m ， a n a l y z e dt h es e t t i n go ft h ei m p o r t a n tp a r a m e t e r s ，s u m m a r i z e dt h ea d v a n t a g e sa n dt h e d i s a d v a n t a g e s ，a n di n t r o d u c e ds o m ec l a s s i c a li m p r o v e da n tc o l o n ya l g o r i t h m s a st h e t r a d i t i o n a li m p r o v e da l g o r i t h m se i t h e ri m p r o v e dt h ea b i l i t yo fg l o b a lo p t i m i z a t i o no r t h ec o n v e r g e n c er a t e ，f o rt h es a k eo ft h eb a l a n c eb e t w e e nt h eb o t h ，t h et h e s i s i n t r o d u c e dt h ed u a l p o p u l a t i o no fa n tc o l o n ya l g o r i t h m b a s e do n a d a p t i v e u p h e r o m o n eu p d a t i n g u p d a t i n gt h ep h e r o m o n eb yt h ed i s t r i b u t i o na n da d j u s t i n g d y n a m i c a l l yt h ep h e r o m o n ed i s t r i b u t i o no ft h ep a t h s ，s ot h a tt h ep h e r o m o n ew o n tb e c o n c e n t r a t e do rd i s p e r s i v e ，t oa v o i dp r e m a t u r i t yw i t ha c c e l e r a t e d c o n v e r g e n c e t h r o u g ht h es t r a t e g yo fa d a p t i v ep h e r o m o n eu p d a t i n g , i ti m p r o v e dt h ea b i l i t yo f g l o b a lo p t i m i z a t i o n ，m e a n w h i l ea sw e l la st h ec o n v e r g e n c er a t et h r o u g ht h es t r a t e g y o ft h ed u a lp o p u l a t i o n t h ee x p e r i m e n ts h o w e dt h a tt h ei m p r o v e da l g o r i t h mo b t a i n e d g o o de f f e c t so nb o t ht h es t a b i l i t ya n dt h eo p t i m i z a t i o n f i n a l l yt h et h e s i sa p p l i e dt h e i m p r o v e da l g o r i t h mt ot h es o l u t i o no fo p t i m a lp a t hc h o s e nf o rg i s - ti nd i f f e r e n t t r a f f i cc o n d i t i o n s k e y w o r d s ：g i s - t , a n tc o l o n ya l g o r i t h m ，o p t i m a lp a t h i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：玉兰日期：盟：墨：! 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时 授权经武汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 期： 武汉理一i ：大学硕十学位论文 第1 章绪论 智能计算，也有人称之为“软计算 【1 1 ，虽然至今没有一个统一的定义，但 我们可以这样来概括它。智能计算就是借用自然界( 生物界) 规律的启迪，根据其 原理，模仿设计求解问题的算法。目前这方面的内容很多，如：人工神经网络 技术、遗传算法、进化规划、模拟退火技术和群集智能技术等。 群居昆虫以集体的力量，进行觅食、御敌、筑巢的能力。这种群体所表现 出来的“智能 ，就称之为群体智能。如蜜蜂采蜜、筑巢、蚂蚁觅食、筑巢等。 从群居昆虫互相合作进行工作中，得到启迪，研究其中的原理，以此原理来设 计新的求解问题的算法，即群智能算法【2 1 。 蚁群算法( a c a , a n tc o l o n ya l g o r i t h m ) 1 3 l 是一种具有代表性的群智能算法。 它最初由意大利学者d o r i g om 于1 9 9 1 年首次提出，其本质上是一个复杂的智能 系统，具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法结合等优 点。如今这一新兴的仿生优化算法已经成为人工智能领域的一个研究热点。目 前对其研究已渗透到多个应用领域，并由解决一维静态优化问题发展到解决多 维动态组合优化问题，由离散域范围内的研究逐渐拓展到了连续域范围内的研 究，而且在蚁群算法的硬件实现上也取得了很多突破性的研究进展，从而使这 种新兴的仿生优化算法展现出勃勃生机和广阔的发展前景。 交通地理信息系统1 4 j 是以地理信息技术为手段，将人、车和道路三者紧密协 调，能最大地动态、高效地对交通进行管理的具有空间分析功能的地理信息系 统。g i s t 的基本功能包括编辑、制图、显示及测量图层等功能，主要用于对空 间和属性数据的输入、存储、编辑，以及制图和空间分析等。g i s t 的其他功能 包括迭加、动态分段、地形分析、栅格显示和路径优化等。在g i s t 的上述功 能中，空间分析功能是地理信息系统软件的核心，而最短路径优化分析在空间 分析中占有非常重要的地位。 最短路径分析是地理信息系统中网络分析的一项重要功能，等价于图论中的 节点问求解最短路径问题。经典的求解最短路径的d i j k s t r a 算法存在计算时i 日j 较 长的问题，而智能优化算法，如遗传算法，禁忌搜索，蚁群最优化等，这些方 法在多项式时问内获得一个近似解，而不是以高昂的时间丌销来获取一个精确 武汉理工大学硕士学位论文 解。其中蚁群算法作为一种新兴的智能计算方法，具有良好的全局优化能力、 本质上的并行性、求解时间短、易于计算机实现等优点，本文在研究基本蚁群 算法的原理、模型、重要参数取值等基础上，针对传统蚁群算法改进的不足， 提出基于自适应信息素更新的双种群蚁群算法，并通过实验对改进算法的性能 进行了比较和分析，然后加入交通状态参数，建立了g i s t 最短路径模型来模 仿在不同交通条件下的g i s t 路径优化问题。最后总结了本文的研究工作和内 容，并对以后的工作提出了更多展望。 1 1 课题研究背景和意义 随着目前城市道路基础设施建设发展日益迅猛，道路建设的速度仍然赶不 上机动车和交通量的增加速度，从而确保城市交通的高效、畅通、安全和环保 的管理任务也日益繁重。因此采用现代化的技术手段管理城市交通，提高交通 的机动性和灵活性，提高交通设施的利用率，提高交通的安全性，尽量发挥现 有交通系统的运行效率，来缓解城市交通的拥挤状况，也势在必行。地理信息 系统【5 l 是计算机技术发展的产物，是以地球科学为基础，运用计算机技术获取、 存取、编辑、处理、分析、显示和输出地理数据的系统。城市交通的空间地理 特征非常适合采用地理信息系统技术，将地理对象的属性特征和空间信息融为 一体，集成现有交通检测系统，实时动态地反映交通态势的变化情况。以交通 地理信息系统为平台的智能交通管理系统是城市交通管理发展的必然方向。 g i s t 是一个以g i s 为技术支撑，以城市交通为依托，以城市交通查询、规划和 决策为目的的信息处理系统。它将城市交通与g i s 技术有机地结合为一体，主 要利用g i s 技术强大的空间分析功能及属性库管理能力来管理交通资源。各大 中等城市( 例如武汉市) 已经建立了自己的g i s t 。 为从根本上解决交通问题，吸取西方发达国家在交通管理规划方面的经验 教训，增强规划决策和管理的科学性、合理性，逐步展开g i s t 技术在交通规 划与管理中的推广和应用，进行g i s t 的理论和应用研究，具有重要的理论意 义和现实价值1 6 j 。 ( 1 ) 路网信息：将路网的实体数据和属性数据以分路段的方式将其与地理坐 标联系起来，每一路段不仅具有空间位置，而且还有属性数据的信息，如道路( 航 道) 名称、道路( 航道) 等级、道路( 航道) 宽度、长度、车道数、隔离带类型、出 2 武汉理丁大学硕十学位论文 入口控制类型、路面材料等。 ( 2 ) 设施管理：将地理、运输、土壤、湿地、航道深度等信息集成为一体， 可以进行交通基础设施质量的管理和维修管理，对桥梁以及信号控制装置的维 护进行管理。 ( 3 ) 事故定位及分析：将计算机辅助绘图软件和交通事故数据文件与g i s t 集成为一个整体，开发出事故定位系统。形象直观地报告事故地点、性质和起 因，找出事故多发地段，分析可能引起事故的道路条件的缺陷，结合现有道路 条件，进行事故发生情况的预测，有些研究还利用g i s t 再现事故，为事故鉴 定提供有效的手段。 ( 4 ) 运输规划：运输规划需要大量的信息，而g i s t 则是提供所需信息的最 好手段，同时g i s t 能够提供多种直观形象的规划方案供选择比较，既快速又 直观，可大大地缩短规划设计周期，从而降低成本，并更能保证设计质量。 ( 5 ) 运输网络和运输需求分析：g i s t 能够进行运输网络的迭加和获得基于 网络路段线性参数信息( 动态分段) 。可以将g i s t 应用于应急状态下的路径计 划、各种道路设施的规划和应急反应时间的确定等。g i s t 还可以将运输需求模 型融人其中，进行运输需求的预测和分析。 ( 6 ) 车辆行驶引导系统：将g i s t 中有关道路地图和停车设施、道路属性及 购物、游览的信息直观的呈现在驾驶员的面前，并提示车辆当前的位置，帮助 驾驶员搜索到达目的地的最佳路径。随着智能运输系统( i t s ，i n t e l l i g e n t t r a n s p o r t a t i o ns y s t e m s ) 的发展，i t s 可为驾驶员提供实时的交通信息，g i s t 可 利用这些实时信息直观的为驾驶员提供汽车行驶的最佳路线。 当前交通拥挤和交通事故正越来越严重的困扰着世界各国的大城市，但目 前缺乏高效的路径诱导系统，在路径选择算法方面还不完善，缺乏实时性高、 有效性强的路径选择算法，使得交通最优路径选择问题一直称为各国投资研究 的重点问题。根据统计资料显示，西方发达国家由于公路堵塞而造成的直接或 间接经济损失十分惊人，而我国每年因交通事故和拥挤所引起的损失至少一千 七百亿元人民币，这种趋势还在加剧1 7 i 。 最优路径选择是智能交通系统的重要研究课题，它能够根据存储在电子地 图中的道路网的拓扑关系，实时准确地规划出最优路径。最优路径规划的目的 是帮助车辆驾驶人员或调度人员在车辆出发地和目的地之l 日j 按照某种策略选定 一条最优路径。本课题既是智能交通系统的重要研究课题，同时也是车辆导航 3 武汉理：r 大学硕士学位论文 系统中的关键技术，因此，本课题具有较重要的研究和应用价值。最优路径问 题是交通网络分析中的一个重要问题，也是g i s t 的一个研究热点。它是资源 分配、路线设计及分析等优化问题的基础1 8 j 。 国内外大量专家学者对此问题进行过深入研究。最优路径问题可分为单源 最优路径问题及全源最优路径问题两种【引。其中单源最优路径问题更具有普遍意 义，且可为全源最优路径问题提供良好的借鉴方案。单源最优路径问题的算法 有很多种，从早期的基于限制条件的深度优先搜索算法、基于有向无环图的动 态规划法、基于邻接矩阵的d i j k s t r a 算法、到最大相关边法、最大相关点法、基 于邻接表的d i j k s t r a 算法、a 算法等。针对不同的网络特征、应用需求及具体的 软硬件环境，各种算法在空间复杂度、时间复杂度、易实现性等方面各具特色。 其中，采用贪心启发策略的d i j k s t r a 算法是目前己知的理论上最完善的算法，它 以极强的抗差性而得到广泛的普及和应用。这些算法均属于贪心算法，存在典 型的局部最小问题，是一种静态的局部最优算法。当前的实际交通网络数据规 模庞大，算法需要提前将整个交通数据导入才能进行路径的选择。这样显然不 能反映出交通中不断变化的道路实际情况对交通路径选择的影响。蚁群算法是 一种新兴的模拟仿生算法，算法具有模拟生物界群体觅食的能力，并且能够在 实际的路径搜索过程中对外界的影响做出动态的响应，因而在交通最优路径选 择中具有极大的可行性与适应性。 1 2 国内外研究现状和进展 1 2 1 国外研究现状 美国是较早利用计算机技术进行交通运输和规划数据库的国家之一i l 叭。目 前，几乎所有州的交通和公路部门都在使用g i s t 。美国联邦公路署( f h w a ) 从 8 0 年代中期开始了综合公路数据库( n h p n ) 丌发，并于1 9 8 8 年建立了实用的 g i s t ；1 9 9 5 年美国联邦公路署建立了公路数据库，该数据库是适用于交通运输 网络规划、分析建模的综合数据库，包含由4 5 0 0 0 条道路组成的全国公路网， 总长度为3 7 0 0 0 0 英罩，与每条道路空间位置相关的属性信息有公路等级、归属、 编号、长度、路幅形式、中央分隔带及交叉口的类型、车道数、路面的铺筑类 型、桥梁、州际交通量、州界等。n h p n 这一适用于公路养护管理的综合数据库 4 武汉理工人学硕+ 学位论文 是迄今为止世晃上最大的公路数据库；美国印第安那州交通部采用g i s t 管理 全州的9 2 万英里长的公路，上千座桥梁，铁路、航道及民航机场等。 在美国公路署的倡导下，各州运输局相继展开一系列的g i s t 的研究，包 括适合于g i s t 的交通运输建模问题、g i s - t 的数据存储方式、数据格式转换、 g i s t 应用范围、软件平台选择、g i s t 项目可行性研究等。其中w i s c o n s i n 运 输局是g i s t 的开发与数据集成的先驱，开发了基于g i s 的路面管理系统、桥 梁管理和维护g i s 、基于g i s 的交通事故分析等系统。同时，美国各州级公路署 还与测绘部门紧密合作，将g p s 技术引入数据采集中并建立了进行空间信息采 集和集成的参考框架和标准。美国还成立了g i s t 工作组，从事g i s t 与i t s 的数据模型、线性参考系设计、数据质量控制、线性参考系中的误差传播等研 究。 加拿大是路面管理系统开发应用较为成熟的国家之一【1 1 l ，目前基于g i s 的 路面管理系统己经广泛应用。加拿大应用g i s t 成功地完成了在温哥华岛的一 条1 2 7 k i n 、四车道的公路通道选择和初步设计，很好地解决了项目涉及的环境 分析( 包括野生动物、森林、水、土壤、植被和土地利用等问题) 、公路选址等 问题；加拿大的艾伯塔省也建立了公路维护地理信息系统，用来定期检测路面 的平整度和损坏程度等。 日本近年来加大交通信息化、智能化建设的投入，1 9 9 9 年成立了全国交通 信息中心，全面整合交通信息资源，建立了综合数据库系统，并在此基础上实 现了全国路网的监控管理1 1 2 l 。日本东京研制了基于g i s t 的车载导航系统，由 c d r o m 数据库和实时通信系统组成。系统采用k i w i 导航数据标准，将数据 记录在c d 、d v d 或h d d 上，满足嵌入式应用快速、高效的要求，实时为社会 各行业提供较全面的咨询服务( 如出行计划、民用导航等) 。 韩国紧跟美国、日本之后，其管理体制和方式与同本完全相同。目前全国 高速路网的监控系统己建成，并制定了三阶段智能交通发展计划，其目标是在 2 0 1 0 年初步完成全智能交通体系建设。德国是较早将g i s t 用于公路选线实际 工作中的国家之一。通过g i s t 技术，进行o r a n i e n b u r g 市绕城公路的环境协调 性研究及路线方案的规划。 到目前为止，在发达国家g i s t 几乎已经渗透于交通的各个领域。在交通 规划中主要用于交通需求分析与预测、路网方案评估、项目选择及优化、交通 工程设施规划、危险品运输路径规划、紧急情况下的疏散规划、公交线路规划、 5 武汉理- f ：大学硕+ 学位论文 公共汽车站站址选择等；在道路设计中主要用于道路走廊选择、路权取得、道 路线形仿真等；在交通管理与服务中主要用于日程养护管理、路面管理系统、 桥梁管理系统、辅助决策系统、交通控制、交通事故分析、交通动态模拟、汽 车运输调度、交通灾害防治、超限卡车路径选择、车辆导航系统等：在港口方 面主要用于港口基础设施管理、船舶自动识别技术、装卸管理等；在航道中主 要用于航道疏浚、航标管理等。这些应用的技术手段都是以g i s t 为中心，集 成了全球定位系统、遥感、网络和多媒体等技术。 1 2 2 国内研究现状 g i s t 在我国交通部门的应用起步较晚，但发展迅速，目前g i s t 已在我国 得到了广泛应用，具体情况如下1 1 3 j ： ( 1 ) 北京市1 9 9 4 年就实施了交通部行业联合科技攻关计划，其依靠北京市 测绘部门提供的1 ：2 5 万电子地图进行北京市公路管理地理信息系统的研究( 单 机版) 与开发：2 0 0 3 年北京市公安局和公安交通管理局科研所又联合开发了北京 市交通地理信息系统，在北京市交通管理中发挥了重要作用。 ( 2 ) 上海市城市综合交通规划研究所以a r c l n f o 软件为平台，整合了空间信 息、遥感信息和各种交通调查资料，进行了综合交通规划基础地理信息系统的 研究与开发，其目的是为上海市综合交通规划与决策部门提供宏观决策的信息 支持，为专业福建师范大学何兴燕硕士学位论文设计人员提供可视化工具，以 提高规划水平；9 9 年上海市公路管理处利用静态g p s 和动态g p s 差分技术相结 合的方式完成了1 ：2 0 0 0 的公路电子地图的制作( 公路、桥梁以外的背景图层由 测绘部门提供) ，并以此为依托，开发了部分公路g i s 应用，目前整个项目仍处 于开发阶段。其选用的g i s 软件平台、数据库及开发工具主要有：a r c i n f o 、 m a p o b j e c t 、o r a c l e 。 ( 3 ) 1 9 9 9 年起，江苏省交通厅从宏观管理需求出发，组织完成了基于l ：2 5 力电子地图基础之上的交通地理信息系统开发，实现了空间数据和属性数据的 挂接，主要包含公路、水运等空问和属性信息；2 0 0 0 年，江苏省交通科学研究 院与江苏省测绘局合作，在1 ：2 5 力- 电子地图的基础上开发了w e b g i s 的“江苏 省国省道地理信息系统 。 ( 4 ) 1 9 9 9 年，四川、黑龙江等省在l ：2 5 力的基础地理信息系统上建立了全 省的公路数据库。1 9 9 9 2 0 0 0 年，广东、安徽、浙江、山东等省公路管理部门建 6 武汉理t 大学硕士学位论文 立了全省公路数据库，并利用l ：2 5 电子地图相继开发了部分应用，如中国一加 拿大政府合作完成“广东省综合交通规划管理系统 ，为省级、国家级开展综合 运输规划研究奠定基础。 ( 5 ) 交通部1 9 9 1 年决定建立全国公路数据库系统，并将公路数据库二、 三级( 省、市级) 的试点工作下达给陕西省交通厅等，陕西省交通厅与中科院遥 应用研究所合作等对公路空间数据和属性数据进行了较为完整的设计，并利用 电子地图初步开发出了具有动态分段等功能地市级公路数据库t r a n s g i s 的研制 开发。2 0 0 1 年交通部建立全国公路数据库系统h d b s ，该系统是至今为止规 模最大的交通数据库系统，用户涉及全国3 2 个省4 0 0 多个地市4 0 0 0 多个区县。 2 0 0 4 年在现有全国公路数据库系统基础上交通部又开发完成了中国国家 公路地理信息系统，整合完成了路网空间数据库、搭建全国路网综合信息平台、 实现公路数据的可视化管理；为公路主管部门提供及时、准确、全面的有关公 路线路、里程及路况的信息，实现高效的数据资源管理和深层次的开发利用； 为决策者提供可靠的决策依据；为全国路网实时监控系统和公众出行服 务系统提供基础平台。 可见，近年来我国对g i s t 的研究有了长足的发展，虽然最初的g i s t 应 用只局限于建立一些交通网络数据库。“十五”期间，国内g i s - t 的研究和应用 开始向纵向发展，越来越多的交通部门开始采用地理信息技术来管理交通数据 库，针对g i s t 技术理论和方法的研究也越来越多。2 0 0 2 年立项的国家“十五 科技攻关重大项目“智能交通关键技术开发和示范工程”的1 6 个课题中有5 个 课题与g i s t 关键技术密切相关。g i s t 对于交通行业，不仅是作为电子地图和 数据库集成继续发挥作用，同时在路网数据智能管理、空间分析和信息服务方 面展现出更多的技术魅力，成为交通规划、交通工程、交通管理和出行服务等 方面不可或缺的技术支撑。目前，浙江、上海、广东、北京、黑龙江、山东、 江苏、河南等省均建有运用比较成功的g i s t 系统。据 2 0 0 4 年全国交通信息 化建设调研报告显示，全国很多省厅已丌始明确g i s t 在交通建设、管理、 运营和服务中的重要地位，均结合其已有公路、航道等基础资源数据库建立了 不同程度的g i s t 系统，如基于g i s 的公路信息系统、桥梁管理信息系统、公 路管理信息系统等，注重通过政府网站为公众提供可视化的出行服务。 1 3 本文研究内容及章节安排 1 3 1 本文的研究内容 7 武汉理：1 ：人学硕十学位论文 论文首先对交通地理信息系统和蚁群算法进行了系统的分析，提出了将蚁 群算法应用于交通地理信息系统的思路。在此基础上，对基本蚁群算法进行了 改进，并通过实验比较和分析了算法的性能。 论文的主要研究内容包括t ( 1 ) 介绍了交通地理信息系统的基本框架、主要功能和关键技术； ( 2 ) 介绍了几种传统的最短路径算法，研究了基本蚁群算法的原理、模型、 算法流程、参数设置、优缺点及其改进方法； ( 3 ) 深入研究蚁群算法理论，针对传统改进蚁群算法的不足，提出了基于自 适应信息素更新的双种群蚁群算法，并对其原理、算法描述、流程等进行了详 细的研究和实验分析，并将改进算法应用于交通地理信息系统中最短路径的优 化，建立一个在不同交通条件下搜索g i s t 最短路径的模型。 1 3 2 本文的章节安排 本论文分为五章，其组织结构如下： 第一章，绪论。论述了本课题的研究背景和意义，并回顾了国内外交通地 理信息系统的研究现状和进展。 第二章，交通地理信息系统的研究。介绍了交通地理信息系统的概念、主 要功能、关键技术、基本框架和具体应用。 第三章，基于改进蚁群算法模型的研究。介绍了传统的最短路径算法，系 统阐述了基本蚁群算法的理论基础，通过旅行商问题( t s p , t r a v e l l i n gs a l e s m a n p r o b l e m ) 给出了基本蚁群算法的数学模型和实现步骤。此外还分析了影响算法性 能的各种因素，对参数口、卢、p 进行了重点分析，总结了蚁群算法的优缺点， 介绍了几种经典的蚁群算法模型，最后根据传统改进算法的不足，提出了一种 基于自适应信息素更新的双种群蚁群算法，为求在收敛速度和全局寻优能力之 间取得一种平衡，并通过实验结果证明取得良好效果。 第四章，基于蚁群算法模型的g i s t 最佳路径的研究。在上一章的基础上， 将改进后的蚁群算法模型应用到g i s t 在不同交通条件下求解相应最短路径问 题。 第五章，总结与展望。总结了本文的工作，并对进一步工作进行了展望。 8 武汉理工人学硕士学位论文 第2 章交通地理信息系统的关键技术与应用 2 1 交通地理信息系统的概念 交通地理信息系统是地理信息系统的一个分支；是收集、存储、管理、综 合分析和处理空间信息和交通信息的计算机软硬件系统；它是在传统g i s 基础 上，加入几何空间网络概念及线的叠置和动态分段等技术，并配以专门的交通 建模手段而组成的专业信息系统；是g i s 与多种交通信息分析和处理技术的集 成。随着目前智能交通系统的蓬勃发展，作为辅助城市交通管理与规划的有效 技术手段，g i s t 在i t s 中占有举足轻重的地位，已成为g i s 应用的一个发展热 点。 2 1 1 内涵 交通地理信息系统的实质是以现代计算机科学、地理学、信息科学、管理 科学和测绘科学为基础，与传统的交通信息分析和处理技术紧密结合，采用数 据库、计算机图形学、多媒体等最新技术，对交通地理信息进行数据处理，能 够真实准确地采集、修改和更新地理空间数据和属性信息，为决策者提供可视 化的支持【1 4 1 。它是g i s 和交通的有机集成系统，如图所示： g i s t ：g 薹s + 交通ct m n 甲。矗d l j d n ) 图2 - 1 交通地理信息系统 9 公踌变通 铁路交通 航空 水运爻遇 管道芟遁 武汉理丁大学硕十学位论文 由此可见，g i s t 系统覆盖整个交通运输体系，包括公路、铁路、航运、水 运、管道等。它是g i s 在交通领域的延伸，是专门化的g i s ，是g i s 与多种交 通信息分析和处理技术的集成。 2 1 2 特点 g i s t 的研究对象是具有线性分布和网络分布的交通信息，以及交通信息的 影响与被影响区域。由于交通信息的线性性、动态性、复杂性，使得g i s 在交 通领域的应用与其他领域有很大的差异性，即g i s t 系统有其独特的特征。主 要表现在以下几个方面： ( 1 ) 数据类型：g i s t 系统要求的数据类型多、分布广、不易采集。g i s t 的数据类型包括基础地理信息、交通专题信息和社会经济信息三类基本信息。 基础地理信息包括自然地理要素( 如地貌、水系、植被) 和地表人工设施( 如道路、 房屋、地名、境界等) 数据，一般可通过地图数字化获得；交通专题信息可分为 静态信息和动态信息两类，是附着在交通网络和设施上的各种交通属性信息， 一般可通过土地管理部门、测绘部门、建设部门获取；社会经济数据是关于区 域内的社会、经济、环境、交通运输状况等数据，综合反映区域内社会经济状 况，主要通过调查访问获取。 ( 2 ) 数据组织：有其独特的技术特征。如线性参照系统，它是用一维空间来 表达地理现象的位置，通过地理现象沿路径到该路径起点的距离进行定位；动 态分段技术是在不改变原有数据结构的基础上，实现对多重属性信息关系的表 达；几何网络拓扑关系，由节点、连通性、路段、路径系统、里程等基本要素 组成，只有在以上要素建立的几何空间网络拓扑关系上，才能胜任交通网络的 分析和交通建模的需要。 ( 3 ) 系统功能：具有复杂的空间分析能力，包括线性特征的叠加分析、不同 参照系下线性数据转换、最短和最佳路径分析、资源分配分析、相邻和最邻近 分析、车辆路由选择能力分析、网络负载模型分析等。 总之，g i s t 是将g i s 技术、通讯技术、计算机技术等，有效地集成并运用 于整个交通系统，从而建立起一种在大范围、全方位发挥作用的、实时准确的、 高效的综合运输管理系统，实现运输工具在交通网络上的运行管理。 1 0 武汉理：l = 人学硕+ 学位论文 2 2 交通地理信息系统的主要功能和关键技术 2 2 1 主要功能 交通地理信息系统的主要功能有：基本功能、叠加功能、动态分段、地形 分析、栅格显示功能和路径优化功能。 ( 1 ) 对电子地图的基本操作。对电子地图的基本操作主要包括创建、修改、 显示和查询。创建功能包括在原地图上创建新地图元素或者创建一张新地图。 查询功能包括空间数据查询、非空间数据查询、通过空间数据查询非空间数据 以及通过非空间数据查询空间分布，此外还可选定两点搜寻最短路径。显示功 能包括一般显示、地图元素显示、地图放大和缩小等。修改功能包括对地图元 素空间和非空间数据的修改以及删除等。 ( 2 ) 图层叠加功能。图层叠加功能允许两幅或更多图层在空间上比较地图 要素和属性，分为合成叠加和统计叠加。合成叠加得到一个新图层，它将显示 原图层的全部特征，交叉的特征区域仅显示共同特征；统计叠加的目的是统计 一种要素在另一种要素中的分布特征。 ( 3 ) 动态分段功能。动态分段功能将地图网络中的连线根据其属性将特征 相近的连线分段。分段是动态进行的，因为它与当前连线的属性相对应，如果 属性改变了，动态分段将创建一组新的分段。动态分段被引入g i s t 的软件是 为了分析以线为基础的交通系统的属性，如路面管理中，路网将以路面铺装采 用沥青或混凝土来“自动分段 ，以便每种类型的路面含在同一个组中。如果因 为需要采用路面类型和车道数这两种属性进行分段，那么每类路面中车道数相 同的又自动形成一组。 ( 4 ) 地形分析功能。地形分析功能主要通过数字地形模型( d t m ) ，以离散分 布的平面点来模拟连续分布的地形，为道路设计创建一个三维地表模型，这在 道路设计中是十分需要的。实际的道路设计采用另一软件在导入g i s 的三维地 模后进行，然后设计的结果再导出到g i s 中，以供将来的分析。这在道路选线 和施工设计中是十分需要的。 ( 5 ) 栅格显示功能。栅格显示功能允许g i s 包含图片和其它影像，并可对这 些图片对应的属性数据进行叠加分析，从而对图层进行更新。如可以通过添加 新特征建筑像桥梁和交叉口以及更f 线型等，对原有的道路图层进行更新。对 武汉理：i ：人学硕十学位论文 带状( 沿线一定宽度) 或多边形( 周围一定范围) 图层进行叠加，可以标出沿线或 周边土地的用途和其他交通属性。 ( 6 ) 网络分析功能。主要指路径优化分析，即最短路径分析( 或者是最佳路 径选择分析) ，此外，还有相邻和最邻边分析，网络负载分析，车辆路由选择分 析，资源分配分析等能力。 综上所述，空间分析是交通g i s 的核心。网络分析、叠加分析和地形分析 等功能为交通g i s 进行空间分析提供了强有力的工具和广阔的应用空间。 2 2 2 关键技术 ( 1 ) 数据库管理系统。长期以来，交通部门要使用和维护大量的信息，在很 多情况下都是多个交通信息系统共存于同一个部门中，而且每一个交通信息系 统只能处理某一类数据信息( 如高速公路规划网、公路管理系统以及事故信息 等) 。g i s t 的数据管理系统的关键技术在于通过建立数据模型和数据交换的框 架，把上述不同的数据存储于一个统一的数据管理系统中，任何部门都能访问 到该系统中符合本部门要求的数据，同时能对这些数据进行分析和建模，然后 进行管理和决策。 ( 2 ) 数据协同。交通数据一般都是由多个机构提供并维护，数据类型、数据 标准难以统一。每个数据源可能都有自己的数据模型。数据模型的不同和使用 方法的多样性给数据管理分析造成了很大问题。由于数据位雹、拓扑结构、分 类、命名和属性、线性测量的误差，导致不同来源数据的统一过程比较复杂， 结果存在很大的不确定性。要使g i s 技术在交通领域取得进展，必须借助数据 协同技术，从地图的匹配算法、交通数据的错误模型和错误传播( 尤其是一维数 据模型) 、数据质量标准和数据