（采矿工程专业论文）城市交通动态路径诱导算法研究及系统设计.pdf

昆明理工大学硕士学位论文 _ - _ _ _ - _ _ - _ - _ _ _ _ _ _ - 一 摘要 智能运输系统( 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 s ) 是在当代科学 技术充分发展进步的背景下产生的，通过将先进的计算机技术、通信技术、现 代控制技术运用于交通运输中，协助人们做出最佳的抉择，控制最佳的路网交 通。路径诱导系统是智能交通系统的核心部分之一，其重要功能之一是为行驶 在道路网中的车辆提供从当前所处位置到目的地的有效、高性能价格比的行车 路线，即对交通网络进行路径规划，为行驶车辆提供最佳路径搜索服务。而实 现路径引导系统，关键就是解决最短路径搜索问题。 本文针对城市道路网的特点，对基于城市通路网的最短路径分析的关键 技术进行了研究。首先系统的介绍了网络分析、图论、地理网络的建模问题等 相关理论，接着论述了交通道路网络在电子地图中的表示。在此基础上论文以 图论作为网络分析的主要方法，对城市电子地图的道路网进行网络分析，将最 佳路径搜索问题转化为图论中的最短路径搜索问题。 最短路径搜索是图论的经典问题。论文对重点介绍了d i j k s t r a 算法， f l o y d 算法和启发式搜索算法等几种经典的最短路径搜索算法，对它们之间时 间复杂度进行了简单的比较，并针对传统算法的表达方式、存储结构等方面的 缺点讨论了最短路径搜索算法的优化方法。以启发式搜索算法为基础，考虑搜 索总代价，论文提出了一种寻找最短路径的行之有效的实用算法，使在搜索过 程中既不用搜索大量无效节点，又能快速准确地找到两点之间的最短路径。在 此基础一h 提出动态诱导系统的实现方法，并对该系统进行了设计，运用m a p x 平 台开发了一套动态路径诱导的地理信息系统软件，该系统具有直观，人机接口 好，能基本满足城市交通诱导的功能。 关键词：地理信息系统、最短路径、d i j k s t r a 算法、启发式搜索算法 昆明理工大学硕士学位论文 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 m s ( i t s ) i s t h e a p p l i c a t i o n o f c o m p u t e r ， c o m m u n i c a t i o n ，a n dc o n t r o lt e c h n o l o g i e st oh e l pd r i v e r sa n do p e r a t o r sm a k i n gs m a r t d e c i s i o n sw h i l ed r i v i n gs m a r tv e h i c l e so rc o n t r o l l i n gt r a f f i co ns m a r tr o a d n e t w o r k s i tb a s e so nt h em o d e r na d v a n c e ds c i e n c ea n dt e c h n o l o g y r o u t eg u i d a n c e s y s t e mi so n e o ft h ec o r eo fi 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 t h em o s ti m p o r t a n t t a s ko fr o u t eg u i d a n c es y s t e mi so f f e r i n ge f f e c t i v ea n dh i g hp e r f o r m a n c e p r i c ed r i v e r o u t ef r o mc u r r e n tl o c a t i o nt od e s t i n a t i o nf o rt h o s ev e h i c l e sw h i c hd r i v i n gi nt h e r o a dn e t w o r k t h a ti sp a t hp l a n n i n gt ot r a f f i cn e t w o r ka n dp r o v i d et h es e r v i n go f s e a r c h i n gt h eb e s tp a t hf o rt h ed r i v i n gv e h i c l e s t h ek e yt oc o m p l e t e t h er o u t e g u i d a n c es y s t e mi ss o l v i n gt h ep r o b l e mo fs e a r c h i n g t h eb e s tp a t h t h i sp a p e rs t u d i e sa n dt e s t st h ek e yt e c h n i q t i e so ft h es h o r t e s tp a t ha n a l y s i s a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fc i t yr o a dn e t w o r k t h ep a p e rf i r s ti n t r o d u c e d s o m et h e o r i e sa b o u tn e t w o r ka n a l y s i s ，g r a p ht h e o r ya n dg e o g r a p h i cn e t w o r k m o d e l i n g ；t h e nt h i sp a p e rd i s c u s s e dt h ep r o b l e mt h a th o wt oe x p r e s st h er o a d n e t w o r ki n d i g i t a lm a p ；b a s eo nt h et h e o r y ，t h i sp a p e rt a k eg r a p ht h e o r ya st h e p r i n c i p a lw a yt oa n a l y z et h er o d en e t w o r ki nd i g i t a lm a p ，a n dt r a n s f o r mt h ep r o b l e m o fs e a r c h i n gt h es h o r t e s tp a t hi nr o a dn e t w o r kt os e a r c h i n gt h es h o r t e s tp a t hi ng r a p h s e a r c h i n gt h es h o r t e s tp a t hi s ac l a s s i c a lp r o b l e mi ng r a p ht h e o r y 。t h i sp a p e r i n t r o d u c e ds o m ec l a s s i f i e da r i t h m e t i c i a n sf o re x a m p l ed i j k s t r aa r i t h m e t i c ，f l o y d a r i t h m e t i ca n dh e u r i s t i cs e a r c ha r i t h m e t i ce m p h a t i c a l l y s o m ec o m p a r ew e r es h o w e d a m o n gt h e s ea r i t h m e t i c i a n sw i t h t h et i m ec o m p l e x i t yi nt h ep a p e r ，a n ds o m e o p t i m i z ew a y sw e r ed i s c u s s e da i ma tt h ed e f e c to fe x p r e s s i o nm o d ea n dm e m o r y s t r u c t u r eo ft r a d i t i o n a la r i t h m e t i c i a n s b a s e du p o nh e u r i s t i cs e a r c ha r i t h m e t i c ，t h e p a p e ra l s op r e s e n t sa l le f f e c t i v ea r i t h m e t i co f t h es h o r t e s tp a t hs e a r c h ，w h i c hc a nf i n d t h es h o r t e s tp a t hb e t w e e nt w on o d e sw i t hh i g hs p e e da n dg r e a ta c c u r a c yw i t h o u t h a v i n gt os e a r c ht h ei n v a l i d a t en o d e s a tl a s tas o r to fs o f t w a r ea b o u ts e a r c h i n g b e s tp a t hw a sp r o g r a m m e dw i t hr e f o r m e da r i t h m e t i c k e yw o r d s ：g e o g r a p h i c a li n f o r m a t i o ns y s t e m ( g i s ) ，t h e s h o r t e s tp a t h ，d i j k s t r a a r i t h m e t i c ，h e u r i s t i cs e a r c ha r i t h m e t i c h 昆明理工大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，由我个人 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任 、 何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡 献的个人和集体，均已在论文中作了明确的说明并表示了谢意。本声明的法 律结果由本人承担。 学位论文作者签名：疹1 多痧 日期：夕僻年月2 6 日 1 关于论文使用授权的说明 本人完全了解昆明理工大学有关保留、使用学位论文的规定，即：学校 有权保留、送交论文的复印件，允许论文被查阅，学校可以公布论文的全部 或部分内容，可以采用影印或其他复制手段保存论文。 ( 保密论文在解密后应遵守) 导师签名 一，垦翌望三_ 丈鲎堕主兰堡堡壅 。1 弓| 言 第一章绪论 随着全球经济的腾飞，对交通运输的需求越来越迫切。交通运输业的发展水 平是同家兴旺发达的重要标志之一。交通运输业的简速发展，一方面促进了物质 交漉耪久程戆往来，太大绫短了窭孬辩阉，提毫了王馋效率；弱一方覆遣豢皋了 许多弊病，特别是地面汽车运输，不论是在发达国家还是在发展中国家，都存在 麓不同程度的交通问题。随着城市交通诱导技术的发展，人们对解决交通拥挤 熬办法簌擎缝撬毫终网豹遴嚣麓力发袋至l 透过主滤便赁方渡慕对瑗素屠瑟翁毽 行进行优化，通过减少城市车辆绝对出行数量来缓解城市交通压力。这种提高路 网的通行能力与优化土地使用方法相绺合的方法产生了非常积极的效果。但事实 上，无论是爨令国家弱大城枣，可攥修建道路熬窆瓣郡是l # 露蠢跟熬，月瓣，对 邋路以及土地使用的建设资金筹措也眈较困难。在这种背景下，系统地解狡道路 交通问题的思想成为未来交通管理与控制的发展方向。 缝蓑全球秘学技拳魏飞速发展，毒 + 箕规技术、嬲络按术昶遇键技术已逐步渗 入到城市交通管理中。利用现代化科学技术管理城市交通，合理地和辩学地弓 导 和控制交通流，有效地提商现有交通网络的运行效率，这是城市交通管理敷展的 必然。智能运输系统，简称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 是应露信惑技术、通信技术、定位技术以及撩制技 术未改善道路交通的效率、安全和环境因素的这场仝球性的技术变革。它怒目前 慰际公认的群决城市以及麓速公路交懑拥挤和提离行车安全的蠛佳措施，也是全 馓舞交通运输领竣磺究鹃静潘阔题。 城市交遇流诱导系统，简称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 ) ， 鼹多 也称道路引导系统，简称r g s ( r o u t eg u i d a n c es y s t e m ) ，是i t s 的熬臻组 成部分，是鳞决城市交逶淘蘧匏关穗。鹜蘸全蘧在磷究诱导系统时，餐存在实麓 行程时间预测和行车路线优化等问题。因此，本论文课题来自云南省自然科学基 众项目：城市动态交通流诱导系统智能分配模型及算法研究，编号： 2 0 0 3 e 0 0 8 6 m 。葵有较强豹学零馥菹帮瑷实意义。 1 2 城市交通流诱导系统概述 无论是毙逡豹交逶餐疆系统，还楚先逶匏霉黢爨信惠系绞，赘提窭了慰行鼗 昆明理工大学硕士学位论文 车辆的实时诱导。因此可以说，u t f g s 是i t s 的重要组成部分，也是i t s 能够实 施的关键技术。u t f g s 利用全球定位系统( g l o b a lp o s i t i o ns y s t e m 、g p s ) 、电 子交通图( d i g i t a lm a p ) 、计算机和先进的通信技术，在车载计算机上自动显示 当前车辆所处的位置、道路网络图和道路交通状况，实时为驾驶员的出行指明最 优路线，并引导驾驶员行驶。根据诱导信息作用的范围，u t f g s 可以分为车内诱 导系统和车外诱导系统两大类。车内诱导系统是在车辆上安装定位装置、信息接 收装置和路线优化装置，对单个车辆实时进行诱导；车外诱导系统主要是根据路 边可变动态画面进行整体车流诱导。两系统在u t f g s 的实施中，均得到了应用。 根据诱导信息的决定方式，u t f g s 分为中心式诱导和分布式诱导。中心式诱导由 诱导信息中心按照车辆的请求，根据动态交通分配理论确定车辆的行驶路线，下 传到车辆，分布式诱导由诱导信息中心下传实时的交通信息数据，车载机根据实 时的交通信息确定诱导行驶路线。中心式诱导对通信系统要求很高，目前，还难 以实施。”“1 根据我国的实际，本文归纳了我国交通流诱导的理论框架，其基本结构为： 一、交通流信息采集与处理子系统 交通流信息的采集主要是在交通控制中心完成的。所以，城市安装自适应式 的交通信号系统是实现交通流诱导的前提条件。这个子系统涉及四个关键问题： 交通信号控制系统应该是自适应式的； 接口技术的研究。把从交通控制中心获得的网络交通流信息传送到交通流 诱导主机； 滚动式预测网络中各路段的交通流量和运行时间； 建立能够综合反映多种因素的路阻函数确定各路段的出行费用，为诱导提 供依据。 二、车辆定位子系统 车辆定位予系统的功能是确定车辆在路网中的确切位鹭，其主要研究内容 有： 建立一套差分的理论模型和应用技术，即讨论如何根据基准台所测出的测 差来修正车载机的误差，从而达到提高定位精度的目的； i r t f 系统的通信网络其中包括信号的编码、发射和接收以及信号的调制 和调解等问题； 研究系统的电子地幽制作方法以及实现技术； 建立一套故障自诊断系统，以保证在系统发生故障或信号在传输中出现较 2 昆明理工大举硕士学位论文 大误差时，也能准确地确定车辆的位鬣。 三、交通信息服务子系统 交逶售惠鞭务予系绞楚交逯滚诱零蓉统戆主要缒袋罄分。宅爵竣怒主糗遁箕 出来的动态交道信息通过各种传播媒介及时地传邀给公众。这照媒介包括有线电 视、联网的计算机、收音机、电话亭、路边的可变标牌和车载的接收装置簿，使 浅学者在家中、在路上都露以褥爨交遗诱导信患。 飚、行车路线优化子系统 行车路线优化子系统是交通流诱导系统的重耍组成部分。它的作用是依据车 辆定位系统所确定静车辆褒网络中静位置帮出行菇狳入豹强的地，结合交遥僚惠 采集与处理予系统传输的路阏交遥信融，为出行者掇供能够避免绷挤、减少嫩误、 快速到达终点的行车路线，在车载计算机的屏幕上强示出车辆行驶前方的交通状 况，并以箭线( 或剐的方式) 标示所建议的最佳抒驶路线。 1 3 国内外研究现状 。3 国夕| 、研究现状 i t s 最早在荑、日、欧等国家和地区发展起来。荧国i t s 的前身是智能车辆道 路系统( 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 mi v h s ) ，起初幽单个州、单个城 毒疆究i v h s ，1 9 9 0 年藏立芝篷爨衣学术舞鞋及致瓣害员组成豹i v h sa m e r i c a 耱 会。1 9 9 4 年i v h s 更名为i t s ，其实施战略是通过实施面向2 i 世纪的“公路交通智 能化”，从根本上解决和减轻事故、低效率和能源浪费等交通中的各种问题。“1 。 基本子1 9 7 3 零哥始动森鼹径诱导鬃绞靛试验，1 9 9 0 年开始磷究开发了路享阂 通信系统( r a c s ) 超智能车辆系统、安全车辆系统簿路径诱导系统。1 9 9 5 年成立 了v i c s ( 道路交通信息系统) 中心。1 9 9 6 年正式启动v i e s 后首先在东京等地鼷施， 1 9 9 8 年牙始在全国推进。翻本的v i c s 楚i t s 实用化的第一步，嚣予世界领先水平。 欧洲的i t s 发展始于7 0 年代的a l 乙王程，8 0 年代i t s 的试验计划开始在欧潮大 规模实施起来。欧洲i t s 的发展计划包括面向汽车的智能化技术的p r o m e t h e u s 计 划，面向道鼹与交通控制糖能化技术的d r i v e 计划。1 9 9 1 年成立_ 欧洲道路交通 邋信合作委员会( e r t i c o ) 泉推动i t s 在敬淄鹃发霞。 美国在智能交通系统的研究和开发方面较日本和欧洲起步稍晚一些，但凭借 冀先进的技术优势，已经后来屠上。翻前在i t s 的试验研究和实践应用上都处于 溺际领先戆佼。美国菲露熬褫i t s 系统帮将澎袋懿焱大枣凌，对箕迸霉了广泛漳 一 曼塑里三查鲎堡圭鲎焦丝奎 入盼礤究。1 9 9 1 年奖闺国会透过了综合逡霞运输效率法黎，萁蘸的赣在于要发展 缀济上有效、环境一 ：完善的围家级综合地面运输系统，以便能够高效率地运送人 员帮货物。1 9 9 2 年，由美国交通部、联邦顾黼委员会耱荧国智熊交通协会联会制 定了翟能交逶系统发震藏鼹诗粼。1 9 9 5 霉3 秀，美滏交遁部正式出敝发毒了强家 智能交通系统项目规划。1 9 9 6 年美国皿特兰大市交邋局邋用已有的智能交通系统 的技术戏系开发了0 1 y m p i c 交遥控翻管滤系统，受2 6 矮爽逶会鼹供了蠢效酶激努。 国努对餐髓霉麓导魏系统瓣谚变恣逐步深讫、缡诧，实时动态车辆导靛已戒 为研究的主流。作为智能车辆导航系统煎要内容之一的路径规划问题，国内外的 学誊对葵最俄纯方法、实髑性避行了大爨鹣萋舅究，y i - h w a w u 等久“。”3 黯藏露交 通动态潮终阻塞攘型、网终浚翘题以及车辆鹣运动方向秽交叉黪溜戆信号静影噙 进行深入的研究，建立模型并讨论了撼于动态交通流量预测的行程时间和最小成 本路径熬闻怒，对意羚稠络毽塞豹影髓敛出浮旗。善。n + l a m “”姆历史熬翻警藏 的交逶摸型弓| 入到车辆导魅系统中去。与此同时，疑镘踌径的算法也大量涌现， 从经典的d i j k s t r a 算法等发展到启发式搜索、分屎搜索等等。 1 3 2 国内磷究现状 我国对于i t s 的研究工作开展较晚，目前尚处于起步阶段。1 9 8 6 1 9 9 5 年间圈 家齐鼹了一系列壤关懿秘学磅究器工程实麓，残为我凰i t s 臻爨翻秀发豹綦疆。 葵阗在城市交通管理、高速公路监控系统、收费系统、安全保障系统等领域墩褥 了多项科研成浆，制定了一些标准和溉范。近几年来，i t s 韭融成为我国交通领 域躯一个研究热点，著吸弓l 了交通、计算执、信息、电子、通信、控制、测绘等 各个幅关业界的人士投身蕻中。1 9 9 9 年阉家投入巨大的a 力、财力，组织建立了 三个国家级智能运输系统工程技术研究中心。2 0 0 0 年2 舅，国家成立了全阖餐麓 运蝓系统协调搬导小组及办公室来具体负责i t s 项目开发应用的组织协调工作 州。 我国对餐能车辆导航系统瓣研究磁西开始，由予耀关交逶基礁设整敕不完蕃 等阁素的限制，翻前主要还处程静态导航阶段，但是实时动态导航墩已成为车辆 导航的研究羹点，如陈壁峰”3 、苏永云。鲫等人黠车辆韵态导髋酌模型及雾法进 行芗深入酶繇究，李寨答入7 2 “黠车辆嚣簸系统中驾驶爨懿反疲露为、搂黧，及 其对车辆导航、路径规划的影响进行了探讨。国内的其他学者对最健路径搜索的 舞法稻鼗据鲭鞫等遣进行了大羹静改避帮磷究，翔涂椿英。“、藩哥。2 1 等大黠动 态车舔号簸系绞帮最短黪经羧索算法热敬遴豹d i 捧s t r 鑫算法、窟发泼搜索、双向 4 昆明理工大学硕士学位论文 搜索等搜索算法进行了深入研究。 1 4 论文的弱的和意义 近年来随着经济的发展，交通事业也正以前所未有的速度j 琏猛发展着。新建 通路和其它各种交通设施越来越多，这对于出行者来说，一方丽为他们提供了更 大麴密行路线逸择寨这，煮劲于缍祷黪疆魏粝逶：稳弱辩毫增大了其塞雩亍煞笺杂 性。另外，尽管道路设施的增加速度较快，却也始终无法跟上机动车数量的增长 速度，造成路网的交通容量始终无法满足不断加速增长的交通需求。据美国联邦 公鼹蔗进行的一王委瞬究淡疆菲离矮车辆全罄出行距离豹约7 以及全部褥敷薅 闯1 2 以上由于缺乏良好的导航和路线引导而被浪赞掉了，这魑无效出彳亍的爨用 每年达4 5 0 亿美元，同时加剧了交通堵塞和交通事故。针对这然形势，出行者在 出 亍时迫切需黉一个能够使其避免掇揍，避免违溉驾驶，安全、便剩、抉撼蟪至l 达目的地的出行服务。而对于交通管瑗喾来说，也希望交通流麓够尽量合理地分 配在整个路刚上。在这样的形势下，一睡行之有效的车辆导航技术无疑成为渤态 路径诱导系统的关键。 最短路径分析是车辆露航技术的曩簧瘫容，对予交通管瑾瑟来说，希囊交道 流能够尽量合理地分配在糙个路网上。对于运输企业来说，通达速度的加快可以 提赢车辆的周转利用率，从丽促进经济效益豹提高。丽对于山行孝来说可以根据 滋行者懿不同鬻求，受冀褥供不圈意义下懿聂饶路线，蘩出露辩阗最短、爨嚣疆 离最短、出行费用最省等，同时在出行时避免拥堵，安全、便利、快捷地到达目 的地。 综上嚣透，其各了整好豹车赣导靛羧零，动态鼹径诱导系统藏哥夔成梵减少 交通拥挤的一个高效而可行的方式，不仅可带来匦大的经济效髓，还可减少环境 污染。基于实f i 寸车辆导航技术的动态路径诱导系统将成为一种崭新的交通模式。 凌凌潼尽块秀矮享辆导簸系统戆骚究鸯差菲零重要瓣意义。 1 5 论文的生要研究内容 路径弓| 罨露绞是警髭交逮系统戆蘩簧缝残部分，与餐憨交逶系统一捞，它涉 及到不同学科的很多方面，本文的研究难以涵盖其全部，而悬麓点就下列方面进 行研究： 燕二章费缓了錾论、漶淫嘲缮戆穰关毂念及瓣络熬楚羚处理。重点探讨了交 通网络的平砸化处理，辆扑结梅及拓扑结构的生成，为后面的璐短路径分析奠定 昆明理工大学硕士学位论文 了基础。 第三章对经典的静态最短路径如d i j k s t r a 算法、f l o y d 算法、启发式搜索 算法、双向搜索算法、分层搜索算法及动态最短路径搜索策略等进行了介绍，对 启发函数与a + 算法的关系进行了研究，并在此基础上对算法的道路网表达方式、 网络的存储结构、搜索策略等方面的优化进行了探讨，提出了一种新的动态最短 路径搜索方法。 第四章简要介绍了地理信息系统、地理信息系统的二次开发及组件技术和 m a p x 组件，总结前两章的内容，通过系统分析对系统进行了功能模块和工作流 程进行了设计和编程。 第五章主要是实施路径引导模型建立以及对改进算法进行了实验检验。 最后，第六章对全文进行了总结，并展望了未来应进一步研究的方向。 1 6 小结 图1 - 1 文章结构图 零章麓要魏夯终了城枣交通诱导惹绞及冀题内辨发疑现状，并对交通诱导系 统中的最短路径研究的一“榉进行了概述，最后提出了本文的主要研究工作。 6 垦望堡三查堂璧主堂堡堡苎 第二章网络分析相关技术 2 1 网络分析与图论 网络分析是牵间分析的内容之一，空间分析是基于地理对象的位置和形态特 征的空间数据分析技术，其目的在于提取和传输空问信息，它通过电子地图的空 闻关系来获取信息和新的知识，用以回答有关空闻关系的应用分析。网络分析主 要指对地理刚络进行分析，包括对地理网络模型、存储结构和算法的研究。网络 分析的一般要完成以下的三个任务：1 ) 把实际的问题转化为一个网络流问题；2 ) 选择一种解决该问题的有效算法；3 ) 根据算池，编制一套有效的程序。本论文中 首先介绍进行网络分析的方法蚍及建立所要解决的地理网络模型，再介缨建立有 效的算法，讨论算法的优化方法和算法的应用并编制一套程序。 图论是进彳_ j = 网络分析的主要方法。图论是研究事物及其之问关系的科学，任 何一个能用二元关系描述的系统，都可以用图的方式提供数学模型。世界上许多 事物以及它们之问的联系都可以用图形直观的表示。这时人们往往用节点表示事 物，用边来表示它们之问的联系。这种由节点和边构成的图彤就是图论所研究的 对象。比如，城市交通道路系统，可以用节点表示交叉路口，用边来表示道路和 街道，从而建立道路交通网。 图的数学表达为：二元组( v ( g ) ，e ( g ) ) 称为图其中v ( g ) 是非空集合，称为节 点集，e ( g ) 是v ( g ) 诸节点之间边( 或弧) 的集合，常用g = ( v ，e ) 表示图。 下面介绍一些图论中的基本概念： 在图g ( v e ) 中，若有边( 或弧) 序列p = ( e ，e 。，e 。) ，其中e - = ( v ，v j ) 。 在图g 中，表示一个线性特征的定义了属性的有序弧段集合称为路径，通常由一 些段组成，而段是条弧或弧的某一部分。如果g 的任意两节点之间都存在道路， 就称g 为连通图，即g 具有连通性。在给定图图g = ( v ，e ) 后，对g 的每条边( v 。，v ) ， 相应的有一个实数w 。，则称这样的图g 为网络或赋权图，w 。称为边( v 。，v ，) 的权。 图论中的许多基本概念，如路径、连通性等都是进行刚络分析的基础。对本论文 要讨论的交通网络，都是连通网络。将图论中网络的概念引入到地理空间中来描 述和表达基于网络的地理目标，即产生了地理网络。 图论的实际应用大量的是网络问题，存图论中我们特称赋有权值的圈为网 络。关于网络的表示，这是一个研究较多的一个问题，在图论中，网络通常利用 矩阵来表示国由于研究问题的出发点不同，图的矩阵表示也有多种形式，其中 最基本的是关联矩阵和邻接矩阵。例如关联矩阵示意图如图2 一l 所示： 最基本的是关联矩阵和邻接矩阵。例如关联矩阵示意图如图2 一l 所示： 昆明理工大学硕士学位论文 第二章网络分析相关技术 2 1 网络分析与图论 秘络分聿斤是空蠢分褫懿雨餐之一，空阉分耩是基予蘧瑾辩蒙懿位置霸形态特 征的空间数据分析技术，其目的在于提取和传输空间信息，它通过电子地图的空 溺关系采获取藩惑窝耨麓知识，用 三l 圈答有关空闺关系耱应溺分辑。瓣络分辑主 要指对地理网络进行分析，包括对地理网络模型、存储结构和算法的研究。阏络 分拳斤的一般要宠袋鞋下熬三个任务：1 ) 毙实际静阉瑟转亿为一个蕊终漉舞熬：2 ) 选择一种解决该问题的肖效算法；3 ) 根据算法，编制一套有效的程序。本论文中 曾先奔缓避行两络分事厅f 冬方法懿及建立掰要麟决静圭| 骜灌网络模圣，嚣分缓建立有 效的算法，讨论算法的优化方法和算法的应用并编制套程序。 鹜论蹩遘嚣瓣络分褥静主癸方法。疆论燕磷究事物及其之闼关系的科学，经 何一个能用二元关系描述的系统，都可以用图的方式提供数学模型。世界上许多 事秘酸及它们之游镌袋祭都可戳雳鹜形蠢餮懿表示。遮藏大锅往往蘼繁熹表示事 物，用边米表示它们之间的联系。这种由节点和边构成的图形就是图论所研究的 对象。魄鲡，赣市交遥邋路系统，可鼓鹈节点袭示交叉路疆，霜边采表示遂貉帮 街道，从而建立道路交道网。 图静数学表达秀：二元缍( v ( g ) ，e ( g ) ) 稼为鹜。冀中v ( g ) 建菲空集合，称为节 点集，e ( g ) 是v ( g ) 诸节点之间边( 或弧) 的集合，常用g = ( v ，e ) 表示图a 下瑟介绍一嫠图论中静基本概念： 在图g ( v ，e ) 中，若脊边( 或弧) 序n p = ( e ，e 。，e 。) ，其中e * = ( v 。v 。) 。 崧圈g 中，表示一个线性特征豹定义了藩往静存事孤瑷集台称为臻较，遥露出一一 然段组成，而段是一条弧或弧的某一部分。如果g 的任意两节点之间都存在道路， 就称g 为连通图，繇g 具有连通髋。在绘定图圈g = ( v ，e ) 后，对g 的每条边( v l ，v ，) ， 相应的有个实数w i j ，则称这样的图g 为网络或赋权阁，w 。称为边( v 、，v ，) 的权。 圈论中的许多摹本概念，如路经、连遥性等都是进行溺络分孝斤翡鏊礁。鼹本论文 要讨论的交通网络，都是连通网络。将图论中网络的概念引入到地理空间中来描 述和表达基于丽络的麓瑾鑫标，郎产生了魄瑾霹络。 图论的实际应用大量的是网络问题，在图论中我们特称赋有权值的图为网 络。关予网络的表示，这是一个研究较多静一个溺瑟，在国论中，黼络逶黎葶| l 蔼 矩阵来表示图由于研究问题的出发点不同，圈的矩阵表示也有多种形式，其中 鼹基本的是关联矩阵帮邻接矩阵。镧辩关联簸箨示意图弼蘩2 1 掰示： ol1l l l011 i a = | ll0 0 l ll0 0 1 0 111 嘲2 一l 网络蹦 f ig 2 1n e t w o r kc h a r t 然而用矩阵形式表示图也有许多不足之处最明擞的是，当图的顶点和边不 断增加时，存储矩阵的容量也随之增加。实际上，一个地理网络比如交通网络往 茬都怒基数予个簇至更多瓣节点嚣逮缓裁。另癸，在短辫攘鍪中诗舞最嚣路径簿 所需赞用都是基于网络边的，而在现实生活中，资源邋过网络节点时也需要一定 的费用，如拐角的阻值，这种信息在矩阵模型中就难以实现。因此，如何管理地 理阚终以及如何对地理孵络进行分褥裁或了一个重要豹问题：一方嚣，是要磅究 如何将现实世界中的地理网络抽象成易予转换的概念模型，即地瑗黼络模型化的 问题；另一方面，是要研究地理网络的具体存储结构和网络分析的簿法，以适应 大容燧地理网络的离效存储署疆怏速面有效的分析。 2 2 地理网络的概念模型 按照几何形态，空闻实体被接象成点、线、面等网栋，从本质上说，地理刚 络震予线狡西标，燕在弧段蘩磴上生成戆。弧段在褐建潮终之蘸不蒸有完整豹滤 理意义，通过结构化的组织生成目标意义的网络体系。由弧段构建网络的过程裘 现为分解和合并两个方面，弧段的一部分作为边参与网络的生成，戚者多条弧段 合并藏一条边参与灏络弱垒戏。为魏挺爨段与路径豹猿念。路径楚缝建网终中具 有较完整地理意义的特征子类，它可以与各种事件直接关联，路裰也是地理刚络 分析结果的存储和显示方式。通过段的概念，路径与地理网络的基本存储单元弧 段联系。这样，剽麓路径系统酾动态分段模登敷可缴受好地表达帮分辑现实瞧爨 的地理网络”“。 构成一个地理网络的元索可以分为地理网络边、地理网络节点、站、中心、 搦受麓，遗理耀终在憩搏上豳线状丑标及箕驸属的点状蜀括组成，簿种耳标又有 自己的属性。 地理网络边是现实世界中各种线路的抽象，是网络中资源流动的路线、街道、 河流、输电线、输水管等。网络边掏成了网络模型的撼架，它可以用各种线状特 征( 弧段、爨径) 寒表示，蠢不仅仅蔗隈予强莰。露终逑骞霞髟绩惑移藩淫蕊患， g 星爨璞：大学硬学璺浚文 网络边的属性信息有两种：一种嫩网络边的强度，如资源流动时间、速度等；另 一秘是网终约资源需求量，妻蔓水流爨等。 丽络边与网络边之闯豹连接点就是网络节点，它位于网络边韵两鲻。节点可 以表示道路的交叉口。多条网络链通过网络节点建立联系。由于网络边不仅仅是 弧段，因丽网络的节点与弧段的节点可以一致，也可以= = i l i 一致。 在“个篷理瘸络中，线，凌蒋鬣稳藏了霆终豹纂磴疆絮。线注籍垂多数是霉“弧 段一节点”模型来模拟的本论文中主要讨论的是最佳路径选择问题，网络分析 中没有涉及到与该问题关系不大的站、中心、拐角等元索，在此不予过多讨论。 邃蘧舔络搏为一耪复杂匏选溅嚣标，狳翼蠢一般网络的逐、节点瓣瓣撞象兹 拓扑意义之外，还具有空间定位上的地理意义和目标复合上的层次意义。与一般 的地理目标一样，地理网络中的线状设施和点状设施除具有空间位置外，还具有 丰富的蟪璎属性，葵l 滋路的路匿状况、通行熊力、交叉路i ：1 的通行能力嚣，都是 进行遗蠼网络分析的纛要因素。 路径诱导是依据网络拓扑关系，通过考察网络元素的空间数据和属性数据， 对网络的性链特征进行多方面的分析计算，找到最适合的路径。路径诱导是车辆 导航系绫中最基本鹣功麓之一，爨帮助驾驶爨在旅行兹窝羧萼亍中寻找行驶臻线静 过程，魁车辆导航的一个基本问题，也是实现导航功能的前提条件，其核心是对 最佳路径的求解。最能路径是指在道路网络中满足某些优化条件的一祭路，如距 离最短、运输费臻最甄、嚣驶辩澎最短等，懑遥路径诱导筏塞最谴路缎，吴套巨 大的经济效益。从嗣络模型的角度稽，最佳路径求解就是在指定网络中两节点闻 找一条阻碍强度最小的路径。 本文所阐述的隧络分辩重点爨对遣聪嘲络孛交通丽终进行路径诱簿，即娶磷 究交通道路网络的最佳路径搜索的算法。 2 。3 网络掇扑处理算法的设计与实现 一般情况下，用户绘谳的道路交通瓣络遮圈廷包含缀横交培的公路和衡迄 等，势不构成完整妁魁络，即不镪会由节点和弧槐成的糍扑关系，甚至谯道路驰 交叉路口处晌两条道路成立体交叉，即该图为一个非平磷图( 如圈2 2 ( a ) ) 。 零课题联讨论蟾路径诱导舞法建基于踺终裁路径诱导算法，顼以必须褥蠲 户撼供的原始交通图陌络化，即程道路交汇处建立节点，并建立节点与道路的邻 接关系。安辩应震r 豹交邋潮络蒸零上爨予平嚣霜，鄯缀少出现立髂交叉熬逶路 ( 对出现立交的情况可以进行特殊处理) ，因此要对在用户绘制的地图中出现立 体交叉豹道鼹进行分割处理，郅在立体交叉的甄祭道路的交叉点上将甄条道路分 9 星塑翌三查兰璧主兰堡垒兰 割为闼条道路，使该交叉点可阱成为一个网络节点( 如图2 2 ( b ) ) 。 ( a ) 立体交叉的道路( b ) 平面拓扑化后的道路嘲 阁2 - 2 交通网络平面拓扑处理示意圈 f i g 。2 - 2t r a f f i cn e t w o r kp l a n et o p o l o g i z e dd i s p o s a lc h a r t 由上面的介绍可以看出，本课题中的网络拓扑处聪算法模块应该有两部分组 成一网络平面化处理算法和拓扑关系生成算法。但湖于课题的黧点不是拓扑处 理，所以本课题豹交逶霹络黧鄂认麦已避行了嬲终乎嚣他处理，戏为交通网终平 面图。下面将对逸两个算法介绍，交通网络平面化处遴算法简要介绍，拓扑缡构 生成算法重点介绍。 2 。3 。 交逶霜络平瑟他处理算法 地理信息系统只能为系统提供地理对象的显示以及地理信息的编辑、保存等 功熊，它 三l 线型域辑线型表示公路，但不能智能的对公路的交叉节点进行判断， 即不越形成交遥阏络，就不黯应用隧络一h 沟豢短路径嚣法对路径遴行诱导，系绫 需飘对这样的交通公路图进行交叉节点生成，即将交叉的两条公路进行分割处 理，在公路交叉处生成可以终结并转向的交叉节点如图2 - 2 。 具体处理滚程如下： 将整个地图按照定的尺寸分割成若干个部分( 以加快处理速度) ； 猩每个部分的公路对象中查找交叉的公路； 将交叉嚣嚣祭公路在交叉蒂点分割域燃拿路段； 麓复、操作直到找不到交叉的公路； 修改相应的原始交通网络阁。 2 。3 ，2 拓扑结梭生成算法 网络图中，拓扑结构建立在路段及站点两个基本缮素的基础之1 5 1 ，按照爱 素缡号的清单来枣糖。对于爨径寻找及选线分手厅来说，可以产生每个节点的邻按 路段清单及每个潞段的起始和终止节点清单。 1 0 昆明理工大学硕士学位论文 经过上面处理的交通地图由于有可能出现有些公路虽然交叉但并不存在交 叉节点的情况，所以没有直接生成交叉节点和路段的对应关系，给用户修改第一 阶段预处理结果的余地，所以要进行再次处理以建立交叉节点与路段的对应关系 如图2 2 。交通网络图的各个路段的地理信息如果不做任何处理将会给数据的调 入带来很大的不便，因此需要将数据( 比如道路的长度) 预先计算，并保存在数 据文件中，以便程序直接引用。 网络拓扑处理为平面图中的每个弧和节点都生成个数据结构以存储该对 象的拓扑信息，弧段对象的数据结构如下： 表2 一l 弧段的数据结构 t a b 2 1g r cd a t as t r u c t u r o i 路段号l 路段长度i 路段名称i 路段起始节点号l 路段终止节点号l 节点对象的数据结构如下： 表2 - 2 节点的数据结构 t a b 2 2n o d e d a t as t r u c t u r e 1 节点号l 节点x 坐标l 节点y 坐标 建立交叉节点与路段的对应关系的具体处理方法如下： 在每个路段的端点坐标处附近查找已经生成的交叉节点，如果没有划生成一 个，并建立该路段与该交叉节点的邻接关系； 重复操作直到所有路段都有与之对应的端点( 交叉节点) ： 修改相应路段图，以保存路段与节点的对应关系。 2 3 3 网络拓扑结构实现 网络拓扑处理操作的结果生成网络的节点和路段文件并建立节点数组和路 段数组的邻接关系。用户应用系统可以将拓扑化的结果保存起来。本课题中，路 径诱导地理信息系统接收到用户的拓扑结构生成指令后调用拓扑结构生成模块 进行拓扑处理，然后创建节点，并可将结果保存到路段图中。 2 4 本章小结 本章主要介绍了图论、地理网络和拓扑”z - ，一x u 一- “一n ” ”l l 。刚络拓扑处理 过程是路径诱导系统的预处理过程，是进行网络最佳路径分析的基础，建立网络 拓扑结构的数据结构和算法。 昆明理工大学硕士学位论文 第三章最佳路径搜索算法 最短路径问题是交通网络分析中的一个重要问题，也是g i s 中的一个研究热 点。它是资源分配、路线设计及分析等优化问题的基础。交通网络分析中的其它 问题，如最可靠路径问题、最大容量路径问题、各种各样的路径导航问题都可以 归并到最短路径问题类型中。 最短路径问题是图论中的经典问题，也是交通网络分析的核心问题之一。最 短路径问题在图论中研究得最为彻底，求解算法有几十种。国内外大量专家学者 对此问题进行了深入研究。经典的图论与不断发展完善的计算机数据结构及算法 的有效结合使得新的最短路径算法不断涌现。它们在空间复杂度、时间复杂度、 易实现性及应用范围等方面各具特色，下面介绍几种经典的最短路径搜索算法， 现有的最短路径搜索算法基本上都是从这几种经典算法中变化来的。按照问题特 征中的起终点特性，最短路径问题可分为两种：单源最短路径问题及所有节点间 最短路径问题。其中单源最短路径问题更具有普遍意义，且可为所有节点间最短 路径问题提供良好的借鉴方案。 3 1 经典的静态最短路径搜索算法 3 1 1 dj k s t r a 算法 在图论中路径和最短路径的定义如下： 在带权图d 中，弧( v 。v ，) 上带的权w ( v ，v ，) 称为这条弧的长度。一条 路径的长度是这条路径所经过的弧的长度和。即若p 是d 中的一条路径，则p 的长度l 。为： f p = e w ( u ，v ) ( “v e 口 在带权图d 中，若p 是从节点u 到节点v 的所有路径中最短的一条路径，则 称p 为从u 到v 的最短路径，其长度记作l ( u ，v ) ，并称为从u 到v 的距离。 为了寻找加权图d 中任意两个定点s 与t 之间最小长度的路，有很多种思路， 1 9 5 9 年狄克斯特( d i j k s t r a ) 提出的算法通常被认为是求解这类问题最有效的 算法之一，这个算法的主要思路是用逐点增长的方法构造一棵路径树，从而得到 从树根( 指定点) 到其它点的距离。具体实现如下： 从s 出发沿着弧的方向第一个到达而且路径最短的一点，一定是所有与s 有弧关联且弧的长度最小的那个点，称为第一短路径点，如果这个点就是t ，问 1 2 昆明理工大学硕士学位论文 题得到解决，如果不是t 而是另一点v 。，那么从s 出发的第二条短路径会到达哪 个点呢? 一定是与s 有关联弧且弧的长度最小的那个点( v 。除外) ，或者是由s