（计算机应用技术专业论文）gis环境下警卫路线规划的研究和实现.pdf

重庆大学硕士学位论文 中文摘要 摘要 如何根据实际应用，寻找能够满足需要的行车路线是城市交通中一个重要 的研究课题。警卫路线规划是针对特殊应用环境下的路径选优问题。所谓警卫 路线是重要警卫对象乘车活动时的行经路线。为保障警卫对象的安全，对警卫 路线实施全线部署和重点控制，必须提前制定合理的路线方案。对于常用道路 路线和备用道路路线要求系统能够提供三条路线作为参考方案，选择其中的两 条路线。临时道路路线因常用于紧急情况下，必须做到能及时提供参考方案。 这样，警卫路线的规划制定就必须要解决前k 优路径的快速生成问题。论文主 要针对这一应用背景，对前k 优警卫路线快速生成的关键技术进行研究，并在 g i s 环境下实现。 论文首先阐述了地理信息系统发展的背景，对地理信息系统技术在城市交 通上的应用进行了总结和归纳，接着对路径分析中常用的d i j k s t r a 算法和a 算法进行了效能的比较。为保证警卫对象乘车途中的安全，在路径选择时要求 达到行驶速度和距离的双重优化平衡，避免影响安全因素的路段，并且系统执 行必须是高效的。针对开发背景要求和城市交通道路网络的特点，文中采用多 种启发式策略结合的方法，建立两层的道路网络模型，在提取网络拓扑结构的 过程中消除了影响安全影响因素的路段。在该道路网络模型的基础上，通过构 造合理的启发函数，提出一种基于a + 算法的快速路径生成方法，最终实现了前 k 优路径算法。 为实现系统相关功能，在g i s 开发平台上，我们选用了m a p o b j e c t s 2 2 作 为二次开发组件，使用v i s u a lb a s i c 6 0 作为开发语言，实现了网络拓扑结构的 提取和构建、前k 优路径算法的高效实现等关键技术，并能够对生成的路线进 行查询和修改。最后，通过与传统d i j k s t r a 算法进行对比分析，表明该算法主 要性能指标达到要求，实现了预期功能，基本适应路线警卫工作的需要，能够 为警卫对象出行路线规划提供较好的决策支持。 关键词：地理信息系统，网络分析，启发式策略，警卫路线，前k 优路径，a + 算法 重庆大学硕士学位论文 英文摘要 a b s t r a c t f i n d i n gr e a s o n a b l ea n ds a t i s f a c t o r yr o u t e su n d e rv a r i o u sa p p l i c a t i o n si sak e y r e s e a r c ht o p i ci nt h et r a f f i cm a n a g e m e n ts y s t e m i nt h i st h e s i s ，w ep u tf o r w a r dt h e p r o b l e mo fg u a r dr o u t ep l a n n i n gw h i c ha i m sa tf i n d i n go p t i m a lr o u t e si na k i n do f p a r t i c u l a rs i t u a t i o n t h eg u a r dr o u t ei sd e f i n e da sar o u t ep l a n n e df o rs o m e b o d y u n d e rt h ep r o t e c t i o no fg u a r d so ra r m y t os a f e g u a r ds o m e b o d y , t h er o u t es h o u l db e d e c i d e di na d v a n c e t h e r e f o r e ，w es u p p l yt h r e es e t so fp l a n n i n gf o rt h er o u t i n er o u t e a n dt h ea l t e r n a t i v er o u t e i na d d i t i o n ，t h ee m e r g e n c er o u t ei su s e da sb a c k u pf o r e m e r g e n c e a c c o r d i n gt ot h e s ef e a t u r e so ft h eg u a r dr o u t e ，w es t u d yk e yt e c h n i q u e s u s e dt of i n dk s h o r t e s tg u a r dr o u t e sf a s t ，a n dr e a l i z et h e mi ng i s i nt h i st h e s i s ，w ef i r s ti n t r o d u c et h eb a c k g r o u n dk n o w l e d g eo ft h ed e v e l o p m e n t o fg i s ，a n ds u m m a r i z et h eg i sa p p l i c a t i o n si nt h em u n i c i p a lt r a f f i cm a n a g e m e n t s y s t e m t h e nw ec o m p a r et h ee f f e c t i v e n e s s b e t w e e nd i j k s t r aa l g o r i t h ma n da 。 a l g o r i t h m d u et ot h es a f e g u a r d ，t h ed r i v i n gs p e e da n dd i s t a n c es h o u l db eb a l a n c e d w e l l ，a n dt h es a f e t ys h o u l db eh i g h l yg u a r a n t e e di nt h er o u t ep l a n n i n g m o r e o v e r , t h e p l a n n i n gs h o u l db ee f f i c i e n t l ye x e c u t e da tt h er u n n i n gt i m e a sar e s u l t ，b a s e do nt h e c h a r a c t e r i s t i c so f t h eg u a r dr o u t ea n dr o a dn e t w o r ki nt h et r a f f i cm a n a g e m e n ts y s t e m ， o u rp l a n n i n gm e r g e sw i t hm u l t i p l eo p t i m a ls t r a t e g i e s ，a n db u i l d sat w o l e v e lr o a d n e t w o r k i na d d i t i o n ，w ea p p l yar e a s o n a b l eh e u r i s t i cf u n c t i o nt oa a l g o r i t h m ，a n d p r o p o s eaf a s tr o u t ep l a n n i n gt or e a l i z et h ek - s h o r t e s tp a t ha l g o r i t h m m a p o b j e c t s ，t h eg i sc o m p o n e n to fe s r ic o m p a n y , i sc h o s e na s0 1 1 1 s o f t w a r e p l a t f o r m w ec h o o s ev i s u a lb a s i c 6 0t oc o n s t r u c tt h et o p o l o g yo fo u r r o a dn e t w o r k ，a n d r e a l i z ek - s h o r t e s t p a t ha l g o r i t h m c o m p a r e dw i t hc l a s s i c a ld i j k s t r aa l g o r i t h m t h r o u g ho u re x p e r i m e n t a lr e s u l t s ，t h ee f f e c t i v e n e s sa n dt h ee f f i c i e n c yo fo u rs y s t e ma r e s a t i s f a e t o r yi nt e r m so f t h en e e do f t h eg u a r dr o u t e k e y w o r d s ：g i s ，n e t w o r ka n a l y s i s ，h e u r i s t i cs t r a t e g y , g u a r dr o u t e ，k - s h o r t e s tp a t h ， a + a l g o r i t h m i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重迭盔堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：钐洛 签字日期：2 田7 1 年f 月；。日 l 1 学位论文版权使用授权书 本学位论文作者完全了解重庆太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重庆太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 、) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名：郝勉 i 签字日期：叼年r 月狗日 导师签名：匆青 签字醐溯7 年期扣日 重庆大学硕士学位论文1 绪论 1 绪论 1 1 研究背景和意义 随着计算机技术的迅速发展，在现代信息社会里，g i s ( g e o g r a p h i c a li n f o r m a t i o n s y s t e m ) 作为一种集地理空间特征和各种统计信息为一体的特殊信息系统，己成为信 息高速公路上的节点和基础设施，受到全社会的广泛关注，是目前国内外热门的研 究课题。当今，国内外g i s 在城市交通管理和控制中的运用也越来越广泛。 在诸多g i s 软件中，最基本最重要的一项功能就是实现最短路径查询。从网络 模型的角度来看，最短路径分析就是在指定网络中两节点问找一条阻碍强度最小的 路径。根据阻碍强度的不同定义，最短路径不仅仅指一般意义上的距离最短，还可 以引申为其它的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为 最快路径问题、最低费用问题等【1 1 。所以如何根据实际应用，寻找能够满足需要的 行车路线是城市交通中一个重要的研究课题。最短路径问题一直是计算机科学、运 筹学、交通工程学、地理信息科学等学科的一个研究热点。它是资源分配、路线设 计及分析等优化问题的基础。经典的与不断发展完善的计算机数据结构及算法的有 效结合使得新的最短路径算法不断涌现。通过最短路径的选择，还可以将无序的交 通出行变得有序，优化客流分布，减少出行的盲目性，提高城市道路网的运行效率， 并可以利用于某些特殊场合，如1 1 0 报警、1 1 9 火警、医疗救护系统的路线制定。 在一些实际应用中，用户在使用咨询系统或决策支持系统时，除了希望得到最短路 径作为参考以外，还要得到两节点间的第二、第三乃至第k 条最短路径作为参考。 这时，就是求前k 优路径问题，前k 优路径问题的基础和核心也就是最短路径问 题。 论文课题来源于“武汉市交通监控管理地理信息系统”，警卫路线的规划和查 询是该系统下的一个主要功能。课题要求结合地理环境和道路信息，在复杂矢量化 地图上，实现约束条件下的路径优选，为重要警卫对象的出行提供多条可选的路径 方案，使所选道路达到安全、快捷、合理的要求，并且便于执行路线警卫工作。警 卫路线通常分为三种：常用道路路线、备用道路路线、临时道路路线。对于常用道 路路线、备用道路路线必须预先制定路线方案，用户要求提供三条路线作为参考 方案，选择其中的两条路线。临时道路路线，是由于遇有特殊情况，如突然前方 道路受阻或安全受到威胁，必须改变原计划路线，此时要求系统一定要有足够快的 响应速度，能根据监控位置及时提供一条新的可选路径方案。为了给用户提供更多 的参考，这时也提供三条可选路线让用户择优而选其一，并且要求系统能够保证在 3 s 内完成计算。这样问题就归结为前k 优路径的快速生成问题。根据系统的要求， 重庆大学硕士学位论文1 绪论 此时我们选取k = 3 。因此，首先必须对最短路径问题进行深入研究。 目前，在国内g i s 运用中，仅有少数城市的交通监控管理地理信息系统中能够 提供警卫路线制定功能，为警卫对象出行路线提供有科学依据的决策支持。但就其 道路网络模型而言，没有结合警卫路线的特点，而只是沿用了普通城市行车路线中 最短路径的选择，没有考虑路线的安全性影响等问题，不能实现警力的有效指挥与 合理调度；就其反应速度而言，也适应不了应急的需要，常因数据结构不合理、组 合爆炸等问题而影响了效率，没有取得时间和结果优化的平衡，一旦有突发事件， 不能及时提供决策依据，从而影响到人员安全；就其功能而言也过于单一，不能适 应警卫路线选择的灵活性需求。因此，在实际应用中有针对性地解决上述存在的问 题，研究前k 优警卫路线的快速生成和规划问题，对于提高警卫工作效率，保障警 卫对象的安全和应对复杂情况的能力具有很重要的现实意义。 1 2 国内外研究现状 最短路径问题是g i s 网络分析功能的应用。最短路径问题可分为单源最短路径问 题及全源最短路径问题两种，其中单源最短路径更具有普遍意义 2 1 。根据解决问题的 思想不同可将单源最短路径算法分为基于g i s 空间查询语句( 如：g e o s q l ) 最短路径分 析w 】和基于专门设计的功能模块的最短路径分析两大类【5 l 。 基于功能模块思想的最短路径算法研究是目前研究的热点。针对不同的应用领 域，不同的功能要求产生了各式各样的单源最短路径，算法按照不同的分类方法、问 题特征及实现技术的差异，可分为很多种【6 】，比如：d i j k s t r a j g 法、a 。算法、动态规划 方法、神经网络法、流体神经网络模拟交通网并结合遗传算法优化参数法、遗传法优 化路径参数的d i j k s t r a 法、基于路径模糊信息的最大满意度路径法等。针对不同的背 景应用需求及具体的软硬件环境，各种算法在空间复杂度和时间复杂度的易实现性等 方面各具特色。其中，采用贪心启发搜索策略的d i j k s t r a 算法，是目前己知理论上最 完善的算法【3 1 ，得到了广泛应用。但是，可以说针对最短路径研究，几乎已经达到了 理论上的时间复杂度的极限【7 1 。目前主要研究的热点：针对实际网络特征优化运行 结构，在统一时间复杂度的基础上尽可能地提高算法的运行效率；对网络特征进行 限制，以便采用合理的数据结构设计算法的运行结构；采用有损算法进行搜索； 采用拓扑层次编码路径视图，对最短路径进行部分实例化编码存储；采用并行算法， 为并行计算机服判”。 经典的最短路径算法- d i j k s t m 算法是目前多数系统解决最短路径问题采用的 理论基础，只是不同系统对d i j k s t r a 算法采用了不同的实现方法。故现在国内外的 g i s 软件中绝大多数使用的均是这种算法。这种算法采用的是广度优先的方式来查 询各个节点的，这样虽然最准确的方式，但是效率较低。因此有必要对已有的算法 2 重庆大学硕士学位论文1 绪论 重新进行考虑并改进。d i l k s 仃a 算法在网络点数很多的时候有其局限：一是用矩阵 来存储弧段信息的方法内存开销比较大；二是由于其算法复杂度为o ( n 2 ) ，n 很大时， 运算速度很慢。针对上述局限性，很多学者提出了不少的改进算法，主要体现在： 针对稀疏图可以把图的矩阵表示更改为邻接表表示以节省存储空间；通过尝试各种 不同排序和搜索方法，减少算法中的排序和搜索次数。不同系统对d o k s 仃a 算法采 用了不同的实现方法。据统计，目前提出的此类最短路径的算法大约有1 7 种。 e b e n j a m i nz h a n 等人对其中的1 5 种进行了测试，结果显示有3 种效果比较好，它 们分别是：t q q ( g r a p hg r o w t hw i t ht w oq u e u e s ) 、d k a ( t h ed o k s 仃a sa l g o r i t h m i m p l e m e n t e d w i t l l a p p r o x i m a t eb u c k e t s ) 以及d k d ( t h ed i j k s t m sa l g o r i t h m i m p l e m e n t e dw i t hd o u b l eb u c k e t s ) ”。其中t q q 算法的基础是图增长理论，较适合 于计算单源点到其他所有点间的最短距离；后两种算法则是基于d i j k s 仃a 的算法， 更适合于计算两点间的最短路径问题。故而现在国内外的g i s 软件中绝大多数使用 的均是这种算法。但是不同的数据结构在排序、搜索和插入时的时间复杂度又各有 优劣，在不同数据量的情况下很难说在具体的应用中哪种方法实现起来速度更快。 目前，在国内外动态环境下的最短路径研究是一个趋势。在动态最短路径问题 中，弧段权值、节点耗费等问题均为时间t 的函数。在动态最短路径计算时弧段权 值、节点耗费等既可来自于一个记录着过去交通状况的历史数据库，也可来自于实 时交通信息。在本系统实现环境中，对这两种形式的数据采集实现起来存在一定的 困难。因此，论文仅研究的是静态环境下的路径分析功能。 1 3 论文研究的目的和内容 1 3 1 研究目的 深入研究最短路径算法，针对警卫路线的特点，提出一种实用、快速的前k 优警 卫路线的生成方法，实现系统要求的功能，达到预期的响应速度，为各种警卫路线的 制定提供合理的参考方案。 1 3 2 研究的主要内容 对警卫路线的特点进行深入地分析，建立合理的道路网络模型 根据警卫路线的要求和特点，结合对人们出行习惯的分析，利用层次空间推理方 法，将路网分为两层路网结构，较好地解决了在计算最优路径过程中实现行驶时间和 距离双重最优问题。论文利用该路网模型结构提取网络拓扑，为提高路径生成效率打 好基础。 提出适合需要的优化路线快速生成方法 如何根据实际应用，寻找能够满足需要的行车路线是城市交通中一个重要的研究 课题。现行的算法以及其改进方法较多，但在不同的情况下具体实现方法和算法都有 3 重庆大学硕士学位论文1 绪论 所不同。在研究的过程中，对常用的d i i k s 仃a 算法和a + 算法进行了深入地研究比较， 在论文建立的路网模型的基础上，提出了一种前k 优路径的快速生成方法，提高算法 的性能。 利用g i s 组件进行二次开发，实现g i s 功能 为实现系统要求的相关g i s 功能，我们利用v i s u a lb a s i c 6 0 作为开发平台，结 合m a p o b j e e t s 2 2 进行g i s 二次开发，使用a r c s d e 作为空间数据引擎来访问和管 理o r a c l e 中的空间数据，在交通监控地理信息系统中实现路径分析的相关功能。 4 重庆大学硕士学位论文2 地理信息系统技术基础 2 地理信息系统技术基础 2 1 地理信息系统概述 2 1 1 地理信息系统定义 地理信息系统( 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 ) 是一种将空间位置信 息和属性数据结合在一起的系统，是一种为了获取、存储、检索、分析和显示空 间定位数据而建立的计算机化的数据库管理系统( 1 9 9 8 ，美国国家地理信息与分析 中心n c g i a 定义) 。这里得空间定位数据是指采用不同方式的遥感与非遥感手段 所获得的数据，它有多种数据类型，包括地图、遥感、统计数据等，它们的共同 特点都有确定的空间位置。地理信息系统的处理对象是空间实体，其处理过程正 是依据空间实体的空间位置和空间关系进行的 1 0 1 。简而言之，地理信息系统是以 计算机为工具，具有地理图形和空间定位功能的空间型数据管理系统，它是一种 特殊而又十分重要的信息系统。 2 1 2 发展历史及发展趋势 地理信息系统萌芽于2 0 世纪6 0 年代初。1 9 6 2 年，加拿大的r o g e r et o m l i n s o n 提出利用数字计算机处理和分析大量的土地利用地图数据，并建议加拿大土地调 查局建立加拿大地理信息系统( c g i s ) 。2 0 世纪6 0 、7 0 年代，随着资源开发与利 用、环境保护等问题的日益突出，人类社会迫切需要一种能够有效地分析、处理 空间信息的技术、方法和系统。与此同时，计算机软硬件技术也得到了飞速地发 展，与此相关的计算机图形和数据库技术也开始走向成熟。这也为地理信息系统 理论和技术方法的创立提供了动力和技术支持，使地理信息系统得到了全面的发 展【1 l 】。 纵观g i s 发展，可将地理信息系统的发展分为以下几个阶段： 2 0 世纪6 0 年代一地理信息系统的开拓发展阶段； 2 4 世纪7 0 年代一地理信息系统的巩固阶段； 2 0 实际8 0 年代一地理信息系统的突破阶段： 2 0 世纪9 0 年代一地理信息系统的社会化阶段。 自从2 0 世纪6 0 年代地理信息系统问世以来，经过4 0 多年的发展，g i s 系统 软件和应用软件日趋成熟和完善，但地理信息系统技术的发展还远没有止境，并 且正处于急剧变化之中。主要体现在以下几个方面：网络g i s ( w e bg i s ) ； 开放式g l s ( o p e l lg s ) ；组件式g i s ( c o mg i s ) ；虚拟g i s ( v g i s ) ；多媒 体g i s ( m g i s ) ；三维g i s ( 3 dg i s ) ；时态g i s ( t g i s ) , 无线通信与g i s 。 除了以上的发展趋势，地理信息系统还会朝着标准化、商业化、企业化、全 球化、大众化的方向发展【i ”。 5 重庆大学硕士学位论文 2 地理信息系统技术基础 2 1 3g i s 一r g i s 是一门以应用为目的的信息产业，其应用可以深入到各行各业、千家万 户。地理信息系统在最近的3 0 多年内取得了惊人的发展，广泛应用于资源调查、 环境评估、灾害预测、国土管理、城市规划、邮电通讯、交通运输、军事公安、 水利电力、公共设施管理、农林牧业、统计、商业金融等几乎所有领域【1 2 】。 交通地理信息系统( 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 mf o rt r a n s p o r t a t i o n ，g i s t ) 是在传统g i s 基础上，加入空间网络概念、线的叠置和动态分段等技术，并配以 专门的交通建模手段而组成的专门系统。g i s t 不但可以存储、管理和更新城市 交通网络的空间数据库，辅助城市交通线路规划和交通管理，更重要的是，通过 g p s 技术、无线通讯、互联网络、虚拟现实等高新技术的有机结合，可以建立广 泛的实时数字交通信息用户服务体系，实现全数字化交通信息的实时发布、存储 和检索，为城市交通管理、车辆的人工及智能导航、客货运输调度及居民出行等 提供有效的技术支持。目前，人们已将g i s 运用到交通行业的许多方面，尤其是 在交通工程领域，采用g i s 技术和方法研究交通规划、工程管理、交通运输及其 相关的问题，与其他传统的方法相比，具有无可比拟的优点，如快速灵活性、客 观定量性、强大的分析模拟能力等。 2 2 地理信息系统数据的组织和管理 2 2 1 数据特征和模型 地理数据是有关地理实体的性质、特征和状态的表征及一切有用的知识，表 达了地理特征与地理现象之间的关系。地理数据一般具有三个基本特征【l ”： 属性特征：用来描述地理实体的特性，如地理实体的类别、等级、数量和 名称等。 空间特征：用来描述地理实体的地理位置以及空间相互关系，又称几何特 征和拓扑特征，前者如界桩的经纬度，后者如中国、印度接壤。 时间特征：用来描述实体随时间的变化，例如人口密度的逐年变化。 目前地理实体的时间特征应用较少，多考虑其属性特征与空间特征的结合。 因此，现在g i s 系统常用的表示地理实体特征的数据主要有两类，即：空间数据 和属性数据。 在g i s 中与空间信息有关的信息模型有三个：即基于对象( 要素) ( f e a t u r e ) 的模 型、网络( n e t w o r k ) 模型以及场( f i e l d ) 模型。基于对象( 要素) 的模型强调了离散对 象，根据它们的边界线以及组成它们或与它们相关的其他对象，可以详细的描述 离散对象。网络模型表示了特殊对象之间的交互，如水或者交通流。场模型表示 了在二维或者三维空间中被看作是连续变化的数据【1 2 1 。在进行计算机图形处理 中，这些模型分别转化为矢量( 、k t o r ) 模型和栅格( r a s t e r ) 模型 1 4 j 5 。 6 重庆大学硕士学位论文 2 地理信息系统技术基础 属性数据是g i s 的重要特征，它有两重含义：一是它用来确定地物是什么， 属于哪一类；二是用来描述地物的详细信息。作为地理数据组成部分的属性数据 区别于一般的商业化数据的一个重要特征是它具有位置标识或定位坐标，每一个 属性数据总是与某一个或一组地理实体相对应的。目前，在地理信息系统中对属 性数据的处理普遍采用关系数据库系统。 2 2 2 空间数据的组织 在地理信息系统中，通常用“层”的概念来分别存储不同的空间信息，即每 一层存放一种专题或一类信息，并有一组对应的数据文件。各个图层可以单独操 作也可以同时对几个图层一起操作。 构成专题的是地图要素，也就是说，专题是地图要素的集合。可以将专题当 作逻辑上的“层”来看待。根据信息处理的需要，一个地图要素可以出现在一个 地中，也可以重复出现在多个图层中。 地图按不同专题分层的方法能够突出主题，不同行业和人员可根据各自的需 要，选择关心的专题图层，既优化了计算机的信息管理，又减轻了人脑信息获取、 分析和运用的工作量。 2 2 3 数据库的管理 g i s 数据库的管理，目前有四种基本的解决方案：文件型、双数据库型、扩 充d b m s 型和空间数据库型。根据所采用的数据库管理方法，又可将g i s 分成四 种类型【姗，如图2 1 所示。 文件型g i s 这种方法比较简单，也是最初的g i s 软件采用的方法，没有集中控制的数据 库管理系统，适合于小规模的g i s 。 双数据库型g i s 这种方法是利用一般的d b m s ( 多数是关系型的) 管理属性数据，专门的软件 管理空间数据，它们之间通过一定的操作相联接。用户既可以和两个数据库分别 打交道，也可以通过某种途径同时访问两个数据库，目前大部分g i s 软件都采用 这种方法。 扩充d b m s 型g i s 这种方法是对一个通用事务管理用的d b m s ( - - 般是关系型的) 进行功能扩 展，增加空间数据的管理能力，使之适合g i s 用户的特殊需要。这种方法使空间 和属性数据之间的联系比较紧密，趋于一体化，还便于利用某些d b m s 产品的现 成功能( 如：客户机服务器的运行模式等) ，但是为了使空间数据适应关系模型， 须牺牲软件运行的效率。 空间数据库型g i s 这种方法采用空间数据库系统来集中管理空间和属性数据，它使属性数据的 7 重庆大学硕士学位论文2 地理信息系统技术基础 管理和空间数据的管理完全一体化了，用户界面也容易做得简洁。但空间数据库 型g i s 发展历史较短，技术还不够成熟。 应用再面 富卞 应用界面 中中 空间教据库管理系统 ll i空间与属性数据库 职敷据库型g i s扩展d b m s 型g i s空间数据库垂 g i s 图2 1 四种常用的g i s 数据库系统管理结构 f i g 2 1f o u r f r a m e w o r k s o f g i sd a t a b a s es y s t e m 目前得g i s 软件种，a r c i n f o 、m a p l n f o 、g e n a m a p 、m g e 等属于双数据库类 型，g e o v i s i o n 、s i c a d o p e n 等属于扩充d b m s 类型，以栅格模型为主的软件大 多采用第一种或者第四种类型。 2 - 3 地理信息系统的网络分析 2 3 1 网络分析 空间数据的分析是地理信息系统中的核心部分，空间数据分析的主要功能包 括：查询检索、形态分析、地形分析、叠置分析、邻域分析、网络分析、图像分 析、应用模型分析【l ”。 网络分析作为空间分析的一种，在地理信息系统中有着广泛的应用领域。网 络分析，是依据网络拓扑关系( 线性实体之间、线性实体与节点之间、节点与节点 之间的连结、连通关系) ，并通过考察网络元素的空间、属性数据，对网络的性能 特征进行多方面的分析计算。常规的网络分析功能主要包括：路径分析、资源分 配、连通分析、流分析、选址。 与g i s 的其他分析功能相比，网络分析的研究一直比较少，但是近年来由于 普遍使用g i s 管理大型网状设施( 如城市中的各类地下管线、交通线、通讯线等) ， 使得对网络分析功能的需求迅速增长，各种g i s 平台软件纷纷推出自己的网络分 析子系统。相对于国际上网络分析的研究不断升温的状况，国内几个较有影响的 g i s 系统已开始提供或多或少的网络分析功能。应该看到，网络分析在当前国内 外的应用和需求相当广泛和迫切，这必将对网络分析的研究产生巨大的推动作用。 8 重庆大学硕士学位论文2 地理信息系统技术基础 2 3 2 网络数据结构 当对地理网络( 如交通网络) 、城市基础设施网络( 如各种网线、电力线、电话 线、供排水管线等) 进行网络最短路径分析时，需要将网络转换成有向图。此时， 网络数据结构的基本组成部分和属性如下： 链( l i n k ) 网络中流动的管线，如街道、河流、水管等，其状态属性包括阻力和需求。 节点( n o d e ) 网络中链的节点，如港口、车站、电站等，其状态属性包括阻力和需求等。 节点中又有下面几种特殊的类型：障碍( b a r t i e r ) 、拐点( t u r n ) 、中一已, ( c e n t e r ) 、站点 ( s t o p ) 。 除了基本的组成部分外，有时还要增加一些特殊结构，如邻接点链表用来辅 助进行路径分析。 2 3 3 动态分段技术 交通模型的一个特点是，多种线性物体，重叠在同一个路网上，如限速区段、 公共交通线路都与路网重叠，这使得g i s 在应用于交通时遇到困难，而动态分段 ( d y n a m i cs e g m e n t a t i o n ) 方法较好地解决了该问题。 动态分段技术是g i s 网络分析中的一种重要的技术手段，它是一种基于线性 特征的动态分析、显示和绘图技术。动态分段的思想是1 9 8 7 年由美国威斯康星交 通厅的戴维弗莱特首先提出。它是从网络重叠的概念发展而来的，即将有关特征 的属性合并成一个独立的网络映射到原先的几何网络上。通过弧段的分解与合并， 建立特征目标、事件与弧段一节点数据结构之间的映射关系。采用动态分段之后， 一个路段( s e g m e n t ) ，是路网上两个交点间连线或者弧的一部分，路段的长度用其 占连线的比例来表示，具有唯一的标识码。在g i s 数据库中，路段是依附于路网 数据，本身没有坐标。由于采用动态分段将道路的各种属性以及其分布集中在一 个图层中进行管理，采用线性定位方法，因而容易实现各种“点线”以及“线线” 的叠加查询分析n 2 1 。高勇等在文献 1 7 】引进动态分段的概念，提出链一动态节点 模型对弧段一节点模型进行进一步的扩充。 动态分段技术的出现为g i s 特别是g i s t 的应用开辟了广阔的前景。考虑到城 市交通地理信息系统的需要，有必要引入动态分段。在路网分析中动态分段主要 体现在附属于路径上的地理属性发生变化，要根据属性分段点重新对网络进行划 分，并对网络边的权重新配置。 2 4 本章小结 本章从导航方面入手介绍了g i s 技术的基础知识，包括：g i s 的概述和发展 状况；g i s 的数据模型；g i s 数据的组织与管理；g i s 网络分析功能。近年来g i s 9 重庆大学硕士学位论文2 地理信息系统技术基础 技术发展迅速，其主要的源动力来自于日益广泛的应用领域对地理信息系统不断 提高的要求。另一方面，计算机科学的飞速发展也为地理信息系统提供了先进的 工具和手段，许多计算机领域的新技术，如面向对象技术、三维技术、图像处理 技术和人工智能技术都可直接应用到地理信息系统中去。 1 0 重庆大学硕士学位论文 3 最优路径算法 3 最优路径算法 3 1 图论的存储和搜索 3 1 1 图的存储方式 在图结构中，节点之间的关系可以是任意的，图中任意两个顶点之间都可能 相关1 1 8 】。图的应用极为广泛，特别是近年来的迅速发展，渗入到诸如语言学、物 理、化学、逻辑学、电信工程、计算机科学以及数学的其他分支中。路径分析是 g i s 空间分析最基本的功能，其核心是对最短路径、最佳路径的求解。为了进行 最短路径分析，需要将城市道路网络转换成有向图。为方便后文的讨论，在此对 图的相关符号做如下规定：给定一带权有向图g = ，其中v = v d l i n ， n 为顶点数) ，记v 为图g 的节点集；e = i 铂= ，v l 、v j e v ，记e 为图g 的边集；w = w 1 j = w ( ) 1 w i 】o ，e ) ，记w 为关于图g 所有边的权值集。在图g 中，令s 表示起始节点，t 表示目的节点。 网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表示。一般 而言，无向图可以用邻接矩阵和邻接多重表来表示，而有向图则可以用邻接表和 十字链表表示，具体可参考数据结构相关书籍。 表3 1 几种图的存储结构比较 t a b l e3 1c o m p a r i s o no f g r a p hs t o r a g es t r u e t u r 名称实现方法优点缺点时问复杂度 1 、易判断两点的关系 邻接矩阵二维数组占用空间大 o ( n 2 + n l * n ) 2 、容易求得顶点的度 1 、节省空间 l 、不易判断 邻接表链表2 、容易求得顶点的出 两点的关系 o ( n + r n ) 或者 2 、不易求得o ( n m ) 度 顶点的入度 l 、空间要求较小 o ( n + m ) 或者 十字链表链表2 、易求得顶点的出度结构较复杂 和入度 o ( n + m ) l 、节省空间 o ( n + m ) 或者 邻接多重表链表结构较复杂 2 、易判断两点的关系o ( n + n 1 ) 以往的研究已经证明针对最短路径分析，前向星型结构( f o r w a r ds t a r 重庆大学硕士学位论文3 最优路径算法 r 印r e s c n t a t i o n ) 是最有效的表达网络拓扑结构的数据结构【”2 0 1 。该表示法使用两个 数组来表示网络的拓扑关系。一个数组存储和弧相关的数据，称之为弧段数组； 另一个数组存储和节点相关的数据，称之为节点数组。网络中所有的弧按照一定 的顺序存储在弧段数组中，即以节点l 、2 、3 为起点的弧在数组中顺序排列， 起点相同的弧则可以任意排列。弧的属性数据，如起点、终点、权值等，以某种 方式和弧保存在一起。弧段数组类似于邻接矩阵的压缩存储方式，其内容则具有 邻接多重表的特点，即一条弧以两节点表示。节点数组相当于一个记录了节点出 度的索引表，通过它可以很容易地得到此节点的出度以及与它相连的第一条弧段 在弧段数组中的位置。在节点数组中，第i 个元素和节点相对应，它存储的是以 节点由起点的第一条弧在弧段数组中的位置以及节点i 的出度。 3 1 2 图的搜索策略 对于图的搜索主要有以下几种策略： 穷举法 又叫u n i n f o r m e d 或b l i n d 搜索方法，包括深度优先( d e p t hf i r s ts e a r c h ) 与广 度优先( b r e a d t hf i r s ts e a r c h ) 两种搜索算法。这是最基本的两种图的搜索算法，它 们实质上是对图中路径进行遍历的过程，单纯应用深度优先或广度搜索策略的最 短路径算法，其效率将随着交通网络的扩大迅速降低。此外因为要求在遍历过程 中到达目标节点即返回，此类算法不能保证所得到的路径是最佳路径。 动态规划法【2 1 】 这种方法是一种步进式( s t e p t a k i n g ) 搜索方法，要求每一步都必须距目标更 近，即不得在反方向搜索，更适合于栅格数据中的路径搜索。 启发式( h e u r i s t i cs e a r c h ) 方法【2 2 】 又叫i n f o r m e d 搜索方法，是一种首先对最有希望的节点进行搜索的搜索策略。 在计算机搜索算法中，启发式策略指通过一定知识进行搜索，即通过选定一种评 估函数，在搜索过程中的每一步，寻找评估函数得分值最高的节点作为下一个搜 索扩展节点。启发式搜索策略的主要优点在于可将搜索限定在一定规模内，寻找 最优路径的算法在实际应用中主要是指这种算法。 启发式策略有很多种，如贪心策略、方向策略、区域策略、层次策略等。基 于启发式策略的最短路径算法包括c o s t e d 算法【2 3 1 、分枝界定法 2 4 , 2 5 1 、贪心算法、 a + 算法【2 6 】等。c o s t e d 算法、分枝界定法、贪心算法属于启发式搜索策略中的 b f s ( b e s tf i r s ts e a r c h ) 类型。a 算法是一种在随机产生式系统中应用比较广泛的启 发式搜索算法，它与步进式算法类似，但a + 允许路径的回溯与重新选择。最短路 径算法中最常用的d “k s 昀算法在人工智能中称为一致代价搜索( u n i n f o r m e dc o s t s e a r c h ) 。它可以被看作是广度优先搜索的变种，也可以被认为是启发式搜索的特 1 2 重庆大学硕士学位论文 3 最优路径算法 例。d i j k s t r a 算法所采用的一致代价搜索在人工智能中称为贪心搜索策略，它是初 级的启发式搜索策略口7 】。 3 2 最优路径算法 3 2 1 最优路径涵义 地理网络的最优路径是指在地理网络中满足某种最优化条件的一条路径。所 谓最优化就是对于给定的目标函数和约束条件，使目标函数在约束条件下达到最 大值或最小值。 以最短路径为主的最优路径问题一直是计算机科学、运筹学、交通工程学、 地理信息科学等学科的一个研究热点。有很多最优路径问题可以转化为最短路径 问题，而且网络最优化的其它许多问题也都可以转化为最短路径问题或者用最短 路径的算法作为其求解的子过程。最短路径不仅仅指一般地理意义上的距离最短， 还可以引申到其它的度量，如时间、费用、线路容量等。相应地，最短路径问题 就成为最快路径问题、最低费用问题等。比如司机用汽车运输货物从a 城到b 城， 他就会考虑走路程最短或者时间最少的道路。这里所考虑的是路程最短问题或最 快路径问题。又比如在两地之间铺设煤气管道，则要根据地形、土壤、是否经过 江河、泥塘、农田、公路等各种情况，来选择铺设费用最小的铺设路线，这是考 虑费用的最短路径问题。论文中的最优路径就是要尽量使生成的警卫路线做到安 全、速度和距离的最优平衡。经典的图论与不断发展完善的计算机数据结构及算 法的有效结合使得新的最短路径算法不断涌现。经过几十年的发展，最短路径算 法种类繁多、结构各异，但大都借助于对图的搜索技术来获取最短路径。 3 2 2d i j k s t r a 算法 荷兰数学家e w d i j k s t r a ( 1 9 5 9 ) 提出的d i j k s t r a 算法是目前理论最完善，迄今 为止应用最广泛的非负权值网络最短路径算法。d i j k s l r a 算法可以用于计算从有向 图中任意一个节点到其它节点的最短路径。假设某路网经转换形成如图3 1 的带 权的有向图和邻接矩阵，则该算法的描述如下： 用带权的邻接矩阵c o s t 来表示带权的n 个节点的有向图，c o s t i ，j 】表示弧 的权值，如果从v i 到b 不连通，则c o s t i ，j 】= 一。图3 1 表示了一个带权 有向图以及其邻接矩阵。 然后，引进一个辅助向量d i s t ，每个分量d i s t i 表示从起始点到每个终点v l 的最短路径长度。假定起始点在有向图中的序号为i o ，并设定该向量的初始值为： d i s t i = c o s t i o ，i 】 v 。v 令s 为已经