（计算机应用技术专业论文）gis环境下动态路径优化算法问题的研究.pdf

摘要 本文对在g i s ( 地理信息系统) 环境下求解动态路径优化算法及相关技术 进行了研究。最短路径问题是网络分析中的基本的问题，它作为许多领域中选择 最优值的一个基本却又是一个十分重要的问题。特别是在交通诱导系统中占有重 要地位。本文分析了g i s 环境下动态路径优化算法的特点，对g i s 环境下城市 路网的最优路径选择问题的关键技术进行了研究和验证。 主要工作有以下三点：一、针对g i s 中的数据模型，数据的组织和管理形式， 在分析了路网拓扑结构的基础上，研究了路网拓扑结构表示的数据结构和g i s 环境下提取路网拓扑结构的关键技术。二、在分析现有路径优化算法的基础上， 提出了基于不定长编码的改进遗传算法，设计了相应的交叉、变异算子，保证生 成路径的合法性，减小了搜索空间，提高了搜索效率。三、考虑现实世界中随着 城市路网规模的日益增大和复杂程度不断增加的情况，充分利用g i s 的特点，探 讨了通过限制搜索区域求解最短路径的策略，大大减少了搜索的时间。 在上述研究的基础上，在m a p i n f o 平台上利用面向对象的程序设计语言c + + 在v i s u a lc + + 6 0 集成开发环境下，设计实现了路网抽取和构建的c m a p 类，实 现了改进遗传算法的c i n d i v i d u a l 类，c p o p u l a t i o n 类及c s h o r t e s t w a y 类，并构建 了原型系统。实验表明，论文所提出的改进遗传算法和限制搜索区域策略在解决 路径优化问题上具有良好的效果。 关键词：动态路径优化；地理信息系统；网络分析：遗传算法：限制搜索区域 a b s t r a c t t h i sp a p e rs t u d i e st h ek e yt e c h n i q u e so ft h es h o r t e s tp a t hb yu s i n gd y n a m i cp a t h o p t i m u ma l g o r i t h mu n d e rg i s t h es h o r t e s tp a t hp r o b l e mi sab a s i cp r o b l e mi n n e t w o r ka n a l y s i s ；i ti sn o to n l yab a s i cb u ta l s oa ni m p o r t a n tp r o b l e ma ss e l e c t i n gt h e b e s tv a l u ei nm a n yf i e l d s ，i th a sa ne s p e c i a l l yi m p o r t a n tu s ei nt l f f l ci n d u c e m e n t s y s t e m t h i sp a p e ra n a l y s e ss o m ec h a r a c t e r so fd y n a m i cp a t ho p t i m u ma l g o r i t h m , s t u d i e sa n dv e r i f i e st h ek e yt e c h n i q u e so ft h eo p t i m u mp a t ho fc i t yr o a dn e t w o r k u n d e rg i s t h em a t e r i a lj o b sa r et h r e ed i r e c t i o n s f i r s t l y , i tr e s e a r c ht h ed a t as t r u c t u r ew h i c h w a sf i g u r e db yr o a dn e t w o r ka n dt h ek e yt e c h n i q u eo fe x t r a c t i n gr o a dn e t w o r k s t r u c t u r ef o c u s i n gi nd a t am o d e l ，o r g a n i ca n dm a n a g e m e n tf o r mo fd a t aa f t e r a n a l y z i n gt h er o a dn e t w o r kt o p o l o g y s e c o n d l y , i tp u tf o r w a r da ni m p r o v e dg a a l g o r i t h mb a s e do nn o te q u a t i o nl o n gc o d ea n dd e s i g n st h e c r o s sa n dm u t a t i n g a r i t h m e t i co p e r a t o r , t h i sm e t h o dc a ng u a r a n t e et h ec o r r e c to fm a k i n gp a t h ，d e c r e a s e t h es e a r c h i n gs c o p e ；s oe n h a n c et h es e a r c h i n ge f f i c i e n c y t h i r d l y , i tp r o b et h es t r a t e g y o fs e a r c h i n gr e g i o nl i m i t e dt os o l v et h es h o r t e s tp a t ha f t e rc o n s i d e r i n gt h ei n c r e a s eo f t h es i z eo f c i t yr o a dn e t w o r ka n dc o m p l e xd e g r e eb ym a k i n gu s e o ft h ec h a r a c t e d s f i c s o fg i si nr e a l i t y ；t h es t r a t e g yd e c r e a s et h es e a r c h i n gt i m ev e r yg r e a t l y a f t e rt h eb a s eo fa b o v er e s e a r c h ，t h i sp a p e rd e s i g nc m a pc l a s so fe x t r a c t i n ga n d b u i l d i n g r o a dn e t w o r k , r e a l i z ec i n d i v i d u a l c l a s s ，c p o p u l a t i o n c l a s sa n d c s h o r t e s t w a yc l a s so fi m p r o v e dg aa l g o r i t h mb ym a k i n gu s i n go fp r o g r a m m i n g l a n g u a g ec + + u n d e rv i s u a lc + + 6 0i d ea n dm a p i n f op l a t f o r m , t h e nb u i l dt h e p r o t o t y p es y s t e m t h ee x p e r i m e n ti n d i c a t et h ei m p r o v e dg aa l g o r i t h ma n ds e a r c h i n g r e g i o nl i m i t e dt h a tt h i sp a p e rp u tf o r w a r dt oh a v eb e r e te f f i c i e n c yo ns o l v i n gp a t h o p t i m u mp r o b l e m k e y w o r d s ：d y n a m i cp a t ho p t i m i z a t i o n ；g i s ；n e t w o r ka n a l y s i s ；g aa l g o r i t h m ； s e a r c h i n gr e g i o nl i m i t e d 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 孝渗 日期：辟妇侈日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名：教姊日期：诽 月增日 导师签名：僭- 咴 日期一年r 月1 8 r 日 1 1 研究背景 第一章绪论 随着经济的发展，人民生活水平的提高以及人们之间交流的日益广泛，城市 交通网的压力也越来越大。因此对道路交通网的研究已经被提到了一个十分重要 的高度。然而，在以往的路径研究中，一个重要的参数路径运行成本( 时间) 常常被假定为静态的，在路径的制定和执行过程中不会发生变化。但在实际车辆 行驶过程中，由于交通管理、交通流量、交通事故、天气变化等因素的影响，行 驶速度总是处在不断变化之中，导致了路网中各个路段上的运行成本( 时间) 也 相应地发生变化。这种动态变化的情况，传统静态网络下的路径问题研究方法显 然无法解决，对动态路径优化问题的研究具有重要意义n 】1 2 】。随着计算机通信以 及信息处理技术的不断进步和智能交通系统的日益完善，实时获取和处理交通信 息已成为可能，也为在动态路网中研究车辆路径问题提供了有利条件。 另一方面，计算机技术的进步，地理信息系统( g i s ) 得到了飞速的发展。地 理信息系统是采集、存储、管理、检索、分析和描述整个或部分地球表面与空问 地理分布数据的空间信息系统。它是一种能把图形管理系统和数据管理系统有机 地结合起来的信息技术，既管理对象的位置又管理对象的其它属性，而且位置和 其它属性是自动关联的。它最基本的功能是将分散收集到的各种空间、非空间信 息输入到计算机中，建立起有相互联系的数据库。当外界情况发生变化时，只要 更改局部的数据，就可维持数据库的有效性和现实性【3 】【4 】，g i $ 为动态路径优化 问题的研究提供了良好的环境。 目前g i s 带动的产业急剧膨胀，已经应用到各个方面。网络分析作为地理信 息系统最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等 各种管网、管线的布局设计中发挥了重要的作用阁。文献【6 】阴说明了g i s 在城 市道路网中的应用情况。而路网分析中基本问题之一是动态路径优化问题。所谓 动态路径，不仅仅指一般地理意义上的距离最短，还可以应用到其他的参数，如 时间、费用、流量等。相应的，动态路径问题就成为最快路径问题、最低费用问 题等。图论的理论发展与不断完善的计算机数据结构以及算法的有效结合，使得 新的动态路径算法不断涌现。实际上，无论是距离最短、时间最快还是费用最低， 他们的核心算法都是最短路径算法嗍。传统的最短路径算法d i j k s u a 算法是 目前多数系统解决动态路径问题采用的理论基础，然而，该算法存在的种种问题 促使了各种不同的算法的出现。目前提出的解决此类动态路径的算法有很多种。 但是我们知道，很多算法都是在特定的情况下对于求解特定的相关问题提出来 的。或者是根据某个自然规律得出的。因此，这些算法如果不加变通的直接应用 于求解动态路径问题方面，会有各种各样的困扰与难题要去面对。 1 2 研究现状 g i s 因为其强大的数据分析功能、空间分析功能，已被广泛应用于各种系统中 与空间信息有密切关系的各个方面各种在实际中的系统如电力系统，光缆系统 涉及到最佳、最短抢修等问题都可以折合到交通网络中来进行分析，故而交通网 络中最短路径算法就可以广泛的应用于其它很多的最佳、最短抢修或者报警系统 中去 5 1 。 最短路径问题是g i s 网络分析功能的应用。最短路径问题可分为单源最短路 径问题及所有节点间最短路径问题，其中单源最短路径更具有普遍意义【9 】。基于 本论文所讨论的主要是单源情况。所以只讨论单源最短路径问题。 1 2 1g l s 环境下的最短路径算法分类 根据解决闯题的思想不同可将各种最短路径算法分为基于g i s 空间查询语 句( 如：g e o s q l ) 最短路径分析1 0 1 1 1 】和基于专门设计的功能模块的最短路径分 析两大类【1 2 1 。 ( 1 ) 基于g i s 空间查询语言的最短路径算法 这种方法目前更多的停留在理论研究阶段，如m a x 定义了一套空间查询语 言，对其完备性进行了证明，并举证分析了范围查询、时态查询、最邻近查询的 应用举例，通过形式化定义一种适合于g i s 空间查询的变量，查询代数拓展了一 般查询代数的查询空间，从而完成最短路径分析功能；提出边和区域的空间连接 预处理和空间约束条件的预处理两种优化方法，从而提出4 种空间路径查询处理 优化策略。尽管针对基于g i s 空间发展研究的g e o s q l 不失为一种处理最短路 径的手段，但由于受g i s 数据库技术发展的制约，而实际应用领域与背景的不同， 也使其离商业实际应用还有很长的距离。 ( 2 ) 基于功能模块思想的最短路径算法 基于模块思想的最短路径算法研究是目前研究的热点。针对不同的应用领 域，不同的功能要求产生了各式各样的单源最短路径，算法按照不同的分类方法、 文体特征及实现技术的差异，可分为很多种【1 3 1 ，比如d i j k s t r a 算法，动态规划方 法，神经网络法，流体神经网络模拟交通网并结合遗传算法优化参数法，遗传法 优化路径参数的d i j k s t r a 澍1 4 1 ，基于路径模糊信息的最大满意度路径法【1 5 1 等。针 对不同的背景应用需求及具体的软硬件环境，各种算法在空间复杂度和时间复杂 度易实现性等方面各具特色。其中，采用贪心启发搜索策略的d i j k s t r a 算法，是 2 目前已知理论上最完善的算法，得到了广泛应用。 1 2 2 空间推理中的启发式搜索策略 ( 1 ) 启发式搜索策略介绍 对于图的搜索主要有以下几种策略。 1 ) 穷举法 又叫u n i n f o r m e d 或b l i n d 搜索方法，包括深度优先与广度优先两种搜索算法。 这是最基本的两种图搜索算法，它们实质上是对图中路径进行遍历的过程，单纯 应用深度优先或广度搜索策略的最短路径算法，其效率将随着交通网络的扩大迅 速降低。此外因为要求在遍历过程中到达目标节点即返回，此类算法不能保证所 得到的路径是最佳路径。 2 ) 动态路径规划法 这种方法是一种步进式s t e p - t a k i n g 搜索方法，要求每一步都必须离目标更 近，即不得在反方向搜索，更适合于栅格数据中的路径搜索。 3 ) 启发式搜索法 又叫i n f o r m e d 搜索方法，是一种首先对最有希望的节点进行搜索的策略。 在计算机搜索算法中，启发式策略指通过一定知识进行搜索，即通过选定一种评 估函数，在搜索过程中的每一步，寻找评估函数得分值最高的节点作为下一个搜 索扩展节点。启发式搜索策略的主要优点在于可将搜索限定在一定规模内，寻找 最佳路径的算法在实际应用中主要是指这种算法。 启发式策略有很多种，如贪心策略、方向策略、区域策略、层次策略等。基 于启发式贪心策略的最短路径算法包括贪心算法、爬山法、a + 算法等。其中贪 心算法属于启发式搜索策略中的b f s ( b e s t f i r s t s e a r c h ) 类型，即对节点评估函 数值进行排序，评估值最高者首先扩展。爬山法( h i l lc l i m b i n g ) 是另一种贪心 搜索算法，它将当前至终点的欧式距离作为扩展路径的启发式策略，对于处理规 则交通网络中的最短路径搜索，具有一定优势。a 算法是一种在随机产生式系 统中应用比较广泛的启发式搜索算法，它与步进式算法类似，不同点在于当无法 得到至终点的路径时，a + 算法允许路径的回溯与重新选择。 文献【1 6 】探讨了基于启发式方法策略的最短路径算法，包括空间有效方法的 可控参数法、空间方向性优化算法等。其中空间有效方向的可控参数，通过设置 可调节系数，使得当有效方向上路径无效时能保证得到可用路径；空间方向性优 化算法是利用两点间直线最短的原理，通过构造二叉树来得到最短路径，其实只 是有损最短路径。 基于启发式区域策略的最短路径算法，包括椭圆限制搜索区域的最短路径算 法、矩形限制区域的最短路径算法等。其中椭圆限制搜索区域的最短路径算法以 3 待求最短路径的起终结点作为焦点，构造椭圆限制区域，进而在该限制区域内进 行贪心搜索u “。 文献 1 8 1 1 9 2 0 2 1 1 讨论了几种基于启发式层次策略的最短路径算法，其中 包括层次空间推理的最短路径算法，层次编码路径视图( i - f i e r a r c h i c a le n c o d e dp a t h v i e w , h e p v ) 结构的最短路径算法等。层次空间推理算法是根据路段等级将交通 网络划分成不同的层次，尽可能地在高阶层次完成最短路径的选择( 通过过滤掉 大量与欲解决问题无关的细节信息) ，实质上是一种有损最短路径。h e p v 结构 的最短路径算法提出同h e p v 结构层次化平面图，并实例化最短路径，即预先计 算和存储最短路径，来保证实时最短路径查询的响应时间。 上述多种启发式搜索策略结合可有效提高最短路径算法的效率。从严格意义 上讲，这里所描述的各种算法只是搜索策略的逻辑描述，需要结合交通网络的具 体存储结构，才能在计算机中有效实现，从而形成各种实用的最短路径算法，如 基于邻接矩阵的d i j k s t r a 算法和基于邻接表的d i j k s t r a 算法等。 ( 2 ) 基于贪心策略的d i j k s t r a 最短路径算法 荷兰数学家e w d i j k s t r a ( 1 9 5 9 ) 提出的标号设定法( l a b e ls e t t i n ga l g o r i t h m s ) ， 是目前理论最完善，迄今为止应用最广泛的非负权值网络最短路径算法。标号设 定法是一种基于贪心策略的最短路径算法，它要求在路径选择中的每一步所选择 的路径都是目前为止最好的。在局部最优而导致最优的假设下，寻求最佳路径不 同的实现方法，构成d i j k s t r a 算法的庞大家族，如a i 恤f 0 中的n e t w o r k 采用二 叉堆优先级队列来实现d i j k s t r a 算法；g e o s t a r 采用快速排序得f i f o 队列来实现 d i j k s t r a 算法；采用动态段数据模式的双向比较追索法的驯k s t r a 算法；采用最 大邻接节点树构造节点矩阵的d i j k s t r a 算法：采用改进型o p e n c l o s e 表的 d i j k s t r a 算法等嘲。 与a + 算法不同，为保证起点到当前节点的路径最优性，i ) i j k s t r a 算法要求对 所有未访问的节点进行搜索，包括反方向搜索。与爬山法搜索策略不同，d i j k s t r a 算法以起点至当前节点路径权的和作为贪心选择策略。 针对网络中可能存在的负权边的问题，采用不同启发式策略的标号改正法 ( l a b e lc o r r e c t i n ga l g o d t h m s ) 有研究，标号改进法可以解决存在负权边的网络 最短路径问题，但它不是保证在每次循环中均能发现一条最优路径，其效率一般 比标号设定法低。由于交通网络中不存在负权边，所以交通网络最短路径算法常 指标号设定法，即改进的d i j k s t r a 算法。 1 3 研究所要解决的问题及主要工作 对于求解g i s 环境下的动态最优路径问题，由于是解决城市道路最优路径问 4 题。所以，要考虑到多方面的问题。首先，必须考虑城市交通路网的情况。 城市道路网除具有一般道路网的特点之外，还有其特殊之处。主要表现在： ( 1 ) 数据量大 对于大型城市来说，城市道路网中的路段数往往动辄以成千上万计。 ( 2 ) 结构复杂 随着城市的发展，城市交通系统越来越向复杂的方向发展，多车道、单行线、 转弯限制、立交系统等交通特征变得越来越普遍，加上新的越来越复杂的交通规 则，这些都使得城市道路网的结构变得非常复杂。 因此，针对城市道路网进行最优路径分析的研究不仅可以解决实际应用系统 的应用需求，而且可以很方便地将其研究成果推广到一般的道路网上面。 要对城市道路网进行最优路径分析，首先必须将现实中的城市道路网络实体 抽象化为网络图论理论中的网络图，然后通过图论中的网络分析理论来实现道路 网络的最优路径分析阿。 在实际应用中，城市道路网的表现形式一般为数字化的矢量地图，其网络空 间特征中的交叉路口坐标和道路位置坐标是在地图上借助图形来识别和解释的； 而为了能够高效率地进行最短路径分析，必须首先将其按结点和弧的关系抽象为 图的结构刚。这就需要先对原始城市道路图进行预处理，建立其相应的网络拓扑 关系。 预处理的工作主要包括： ( 1 ) 对原始的道路图进行线元素的拓扑检查、进行剪断处理，生成线和线 相互不相交叉的道路图； ( 2 ) 对剪断后的道路图创建拓扑关系，并定义其属性特征，如道路名称、 道路距离、交通流量等； ( 3 ) 生成有拓扑关系的拓扑文件。 经过预处理后，当对城市道路网进行最短路径分析操作时，系统直接从拓扑 文件中提取道路网的网络拓扑结构并加载到内存中，从而提高路径分析的效率。 如果由于城市建设的发展，城市道路发生了变化，地图更新后，只需重新进行预 处理生成拓扑文件。 系统的整个工作流程见图i 1 所示： m a l d i n f o 格式地图 i 创建拓扑关系 i 生成拓扑文件 i 读取并打开拓扑文件 i 最优路径分析 i 保存路径分析所得最 优路径分析文件 l 把求得的最优路径反 映在m a p i n f o 地图上 图1 1 系统的工作流程 由以上的流程图可以看出，该设计最重要的部分在于以下三个方面： ( 1 ) 地图网络拓扑结构的读取与构建； ( 2 ) 最优路径的分析和实现； ( 3 ) 原型系统的设计； 在g i s 中多数的网络都是有向带权图，如道路有单双向问题，电流、水流都 有方向( 如果是无向图也可归为有向图的特例) ，且不同的方向都有可能有不同 的权值。将实际的交通网络转化到地图的图层中去时，必须充分考虑到这些情况， 并且应方便于提取弧段和节点的信息，从而构建出正确的网络模型。 另外，g i s 中的数据( 如道路、管网、线路等) 要进行最短路径的计算，就 必须首先将其按节点和边的关系抽象成图的结构，这个在g i s 中称为构建网络的 拓扑关系。本文针对交通网络的地图表示及网络拓扑结构的提取和构建这两项关 键技术提出了实用、高效的解决方案。由于在实际应用中对最短路径分析的处理 要求很高，因此论文研究的关键和主要技术难点也就集中在如何高效率地生成最 优路线。 本文所作的主要工作是在g i s 环境下抽取地图路网，并根据路网的特点结合 算法的需要构建出了表示道路拓扑关系的数据结构，并通过不定长编码的遗传算 6 法来对动态路径问题进行求解，按照动态最优路径问题所提出的以时间而不是距 离作为运行成本来计算最优路径。更进一步，通过限制搜索区域策略来求解最短 路径。最后，利用v c + + 6 0 与m a p i n f o 作为开发平台，实现了原型系统的可视 化。 1 4 论文的组织结构 由前所述，本文的意义主要表现在两个方面。首先：动态路径优化问题是一 个典型的最优路径问题，而对最优路径的研究实质上是对算法的研究与改进，所 以有很强的理论意义。其次，随着城市交通道路的发展，城市路网越来越复杂， 在g i s 环境下来动态求解路径的优化问题对于城市交通流的畅通无阻，人们出行 的方便，都有很好的现实意义。 论文主要包括五章的内容，结构如下所述： 第一章介绍了论文的背景、g i s 环境下动态路径优化算法的研究现状以及论 文的研究内容。 第二章介绍了地理信息系统的概念，数据模型。讨论了g i s 环境下城市道路 网络拓扑结构的提取和构建技术。 第三章在分析现有路径优化算法的基础上，提出了基于不定长编码的改进遗 传算法，设计了相应的交叉、变异算子。并对限制搜索区域策略进行了探讨。 第四章介绍了在m a p i n f o 平台上实现原型系统所要做的主要工作。 第五章对论文进行了总结并对进一步的工作进行了展望。 7 第二章g i s 环境下道路网拓扑结构的提取和构建 道路网拓扑结构是求解路径分析问题的基础，它描述了路网中点、线、面的 连通关系( 拓扑关系) 。提取和构建城市道路网的路网拓扑结构是指：从矢量地 图中提取道路网中各路段的属性数据以及各交叉路口的坐标信息，并利用提取的 网络拓扑信息，通过适当的数据结构来正确构建道路网的网络拓扑结构。 在网络拓扑结构的提取过程中涉及到有关g i s 的一些基础知识，g i s 的系统 数据模型，数据的组织形式，g i s 环境下的网络分析情况以及图论方面的知识。 下面一一介绍。 2 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 年，美国国 家地理信息与分析中心定义) 【4 j 。这里的空间定位数据是指采用不同方式的遥感 和非遥感手段所获得的数据，它有多种数据类型，包括地图、遥感、统计数据等， 它们的共同特点都有确定的空间位置。地理信息系统的处理对象是空间实体，其 处理过程正是依据空间实体的空间位置和空间关系进行的闭。 图2 1g i s 体系结构 地理信息系统的外在表现为计算机软硬件系统，其内涵却是由计算机程序和 地理数据组织而成的地理空间信息模型。当具有一定地理学知识的用户使用地理 信息系统时，他所面对的数据不再是毫无意义的，而是把客观世界抽象为模型化 的空间数据。用户可以按照应用的目的观测这个现实世界模型的各个方面的内 容，取得自然过程的分析和预测的信息，用于管理和决策，这就是地理信息系统 的意义。个逻辑缩小的、高度信息化的地理系统，从视觉、计量和逻辑上对地 理系统在功能上进行模拟，信息流动以及信息流动的结果，完全由计算机程序的 运行和数据的变换来仿真。地理学家可以在地理信息系统支持下提取地理系统各 个不同侧面、不同层次的空间和时间特征，也可以快速地模拟自然过程演变成思 维过程的结果，取得地理预测或“实验”的结果，选择优化方案，用于管理与决 策【2 6 1 。 一个完整的g i s 主要有四个部分构成，即计算机硬件系统、计算机软件系统、 地理数据( 或空间数据) 和系统管理操作人员。其核心部分是计算机系统( 硬件 和软件) ，地理数据反映g i s 的地理内容，而管理人员和用户则决定系统的工作 方式以及信息表示方式。 2 2 地理信息系统数据模型 地理信息是用来表示地理实体特征的数据，是g i s 的研究、作用对象。地理 实体具有三个基本特征： ( 1 ) 属性特征：属性特征是用来描述地理实体的特征，如地理实体的类别、 等级、数量和名称等。 ( 2 ) 空间特征：空间特征是用来描述地理实体的地理位置以及空间相互关 系，又称几何特征和拓扑特征，前者如界桩的经纬度，后者如中国和印度接壤。 ( 3 ) 时间特征：时间特征是用来描述实体随时间的变化，例如人口密度的 逐年变化。 目前地理实体的时间特征的应用较少，多考虑其属性特征与空间特征的结 合。因此现在g i s 系统常用的表示地理实体特征的数据主要有两类，即：空间数 据和属性数据唧。 2 2 1 空间数据模型 空间数据表示地理实体的空间位置或现在所处的地理位置，表达了物体地理 实体的几何定位特征，一般以坐标数据来表示，如城市和道路交叉口在交通网络 中的空间位置等；属性数据表达了地理实体的与几何位置无关的属性特征，如交 通网络中的路段的路线编号、等级、里程、路段交通量等表示路段的属性特征。 地理空间数据是以地球表面空间位置为参照的自然、社会和人文景观数据， 可以是图形、图像、文字、表格和数字等，由系统的建立者通过数字化仪、扫描 仪、键盘、磁带机或其它通讯系统输入g i s ，是g i s 所表达的现实世界经过模型 9 抽象的实质性内容。空间数据结构是指地理实体的空间排列方式和相互关系的抽 象描述。g i s 空间数据结构主要有两种类型：矢量结构和栅格结构。 目前，主要有两类用于空间数据处理的通用数据模型：基于实体的模型 ( e n t i t y - b a s e dm o d e l ) 和基于域的模型( f i e l d b a s e dm o d e l ) 。前者将空间信息 表示成离散的、可标识的空间实体。后者处理的是空间分布信息，每种空间分布 都可以表示成一个从空闻框架( s p a t i a lf r a m e w o r k ) 勤属性域( a t t r i b u t ed o m a i n ) 的函数，地形高程、降雨量和温度的分布就属于这种模型。在进行计算机图形处 理中，这两种模型分别转化为栅格( r a s t e r ) 模型和矢量( v e c t o r ) 模型。 ( 1 ) 栅格模型 栅格模型将空间分成一系列的单元，每个单元代表有限但确定的的地球表 面。单元可以具有任何几何形状，只要能组合出表达研究区域的面即可。虽然栅 格单元有许多形状，如三角形、六角形，但通常采用固定大小的正方形。正方形 的栅格单元称为网格单元，空间事物就按其在网络中的行、列和取值来表示。网 格单元的大小代表了栅格型地图( 空间) 数据库的分辨率。这些离散的数据网格 具有叠放方便、迅速的特点，所以常被用来作为空间物体的背景图。 在基于网格或栅格的系统中，有两种基本方法可以赋予实体( 对象) 属性数 据。最简单一种是为每一个网格赋一个数值代表属性( 如土地覆盖) ，这样，根 据属性值的分布就可以表示实体的位置。例如：如果用1 0 代表水，作为x 或列 方向和y 或行方向的第一个数，左上网格单元就使地图表面代表水的位置。每个 网格单元在所给地图中只能有一个属性值。还有一种，就是第一种的扩展，它把 网格单元与数据库管理系统相互连接，一个网格单元就可以有多种属性。这种方 法的使用日益广泛，不仅由于可以较少必须存储的数据量，而且也可以很容易地 同其他数据结构建立关联，在数据库管理系统下进行数据的存储、查询与处理。 图2 2 地图栅格模型 1 0 栅格模型突出的特点是，它可以直接利用遥感、数字摄影测量、扫描等方式 获取栅格形式的数据，且数据结构简单；空间数据的叠置和组合十分方便；各类 空间分析都很容易实现；数学模拟方便。其缺点是：随着精度的增大，数据量不 断增大，从而对设备的存储空间要求过高，且查询速度较慢。图形数据量大；用 大像元减少数据量时，图形精度和信息量受到损失，地图输出差；难以建立网络 连接关系：投影变换十分耗时。栅格数据结构有利于多边形的叠置、空间均值处 理和空间分析，但输出的专题地图既不美观也不够精确，采用该类方法，难于实 现空间实体的旋转及坐标的变换操作，对空间实体的识别和标示操作较麻烦。 ( 2 ) 矢量模型 矢量模型假定地理空间是连续的，而不是量化为互相独立的小栅格，点用独 立的空间坐标对表示，线用一系列坐标对表示，面是由首尾相连的线构成的多边 形。 ( x ，y ) 图2 3 基本矢量地图 矢量模型对地图上出现的多维实体更具有表达力，实体数据和属性数据分别 存储在不同文件中在数据库管理系统中，再用某种方法把两者连接起来。这 是用简单的图例对表达实体的扩展，使得矢量模型更加图形化，更能形象地表达 地图表面。在栅格模型中，是基于栅格位置来存储属性数据和定位空间，然而矢 量模型的表示方法却完全不同，实体数据独立存储在一个地方，通过一定的关系 与其独立的属性数据相连。 在矢量模型中，线由两个或多个坐标对构成，与这条线相关的属性数据存储 在另一个文件中。一条直线用两个坐标对足以表示其空间位置和方向，复杂一些 的线由许多线段表示，每个线段由两个坐标对确定。对于复杂的线，必须增加线 段以表示线段方向的不断变化，线段越短，表示的复杂度也越准确。虽然矢量模 型更能精确表达实体的空间位置，但并不绝对准确，它仍然是地理位置的抽象。 与栅格模型的数据结构相比，矢量模型的数据机构是一种更加紧密的数据结 构。所需的存储空间较少，精度不受限制，原始地图的精度即是矢量化地图的精 绒 o 时 度。定位明显，属性隐含，容易定义和操作单个空间实体。矢量数据结构能够进 行有效的拓扑编码，便于进行空间拓扑分析。在进行图形操作时，可以直接利用 计算机图形学的许多算法，如长度、面积的计算，图形编辑、几何变换等，操作 效率高，精度高。 矢量数据模型的确定是数据结构复杂，算法难以实现，尤其是数据的编辑、 更新和处理比较复杂。不能有效地支持图像代数运算，复合操作很难以实现，且 要占用大量的计算时间。在表示具有高度变化的地物时也有困难，定位存取性能 较差，处理拓扑关系( 如相交、包含、邻接等) 较为困难，连续变化的空间数据 不能表示成矢量结构，这些都是矢量结构的不足。在与遥感数据相结合处理时， 需要将矢量结构转换成网络结构。但是与栅格结构拓扑关系表达上的障碍相比， 计算机上的难度是可以通过硬、软件技术的进步加以克服的。 空间数据的栅格结构和矢量结构是模拟地理信息的截然不同的两种方法：栅 格数据结构需要大量的计算机内存来存储和处理地理数据，才能达到与矢量数据 结构相同的空间分辨率。栅格数据结构有利于多边形的叠置、空间均值处理和空 间分析，但输出的专题地图既不美观也不够精确；矢量数据结构在某些特定形式 的处理中，如多边形的置叠、空间均值处理和空间分析等较为困难，但有利于网 络分析( 交通、排水) ，能输出精美的地图。栅格数据结构和矢量数据结构都有 一定的优点和局限性，因此二者同时存在，不能相互代替1 4 。 2 2 2 属性数据模型 属性数据相对于空间数据库来说，通常呈相对独立的变化，即空间位置不变， 但属性类型可能已发生了变化，如交通网络中的路段空间位置未变，但技术等级 提高了。因此，空间数据的管理是非常复杂的。有效的空间数据管理要求空间数 据和属性数据单独存放，并用不同软件来处理这两类数据。这种数据组织方法， 对于经常变化的数据，具有更大的灵活性。 属性数据是g i s 的重要特征，它有两重含义：一是它用来确定地物是什么， 属于哪一类；二是用来描述地物的详细信息。所以有时g i s 中属性数据的采集量 比空间图形数据的采集量还要大。地理信息系统的重要特征之一，就是把图形数 据与属性数据综合到一个单一的系统中，这使得空间数据与非空间数据之间交互 的复杂分析与建模成为可能。作为地理数据组成部分的属性数据区别于一般的商 业化数据的一个重要特征是它具有位置标识或定位坐标，每一个属性数据总是有 某一个或一组地理实体相对应的。目前，在地理信息系统中对属性数据的处理普 遍采用关系数据库系统嗍。 关系模型严格按照符合现代数据模型的定义，数据结构简单清晰，存取路径 完全对用户隐蔽。关系模型的最大特色是描述的一致性和独立性，实体之间的联 1 2 系不是用指针表示，而是由数据本身通过公共值( 关键字) 隐含地表达它们之间 的联系，采用关系代数和关系运算来描述和处理数据，具有严格的数据基础，是 当前数据库中最常用的数据模型。目前，大部分g i s 中的属性数据采用关系数据 模型。以纪录组( 或数据表) 的形式组织数据，以便于利用各种实体( 图形) 与 属性之间的关系进行数据存取和变换，不分层也无指针。 关系数据库以建立空间和非空间数据之间的关系为主要目标来组织数据。 点、线、面图形数据的记录中都包含一个有序特征值，此特征值也可成为关键字， 其后存储其它信息。整个记录称为一个“元组”，多个元组组成一张二维表，称 为“关系”。每个关系通常是一个独立的文件。 关系数据模型的优点有以下几个方面： ( 1 ) 查询操作是非结构化的。通过查询语言的各种操作符来连接不同的表 格并抽取数据库中的数据。 ( 2 ) 关系数据库的用户视图比较简单，是由若干张二维表格组成的，用户 可以非常容易地想象存储在数据库中的数据。 ( 3 ) 在数据库增加数据项的方式有两种：产生一个新表或向已有的表中追 加数据项。当数据库需要修改或更新时，不需要重新组织数据结构。 但是，关系模型在效率、数据语义、模型扩充、实体标识和程序交互等还存 在着一些缺陷，特别是在处理空间数据库所涉及的复杂对象方面，显得难以适应。 2 3 地理信息系统数据的组织和管理 地理信息系统中的数据是按照一定的方法来组织的，这里就引入了图层的概 念，而对图层中的数据要按照一定的规则进行管理，在g i s 中主要是通过数据库 的管理模式来管理。 2 3 1 空间数据的组织 在地理信息系统中，通常用“层”的概念来分别存储不同的空间信息，即每 一层存放一种专题或一类信息，并有一组对应的数据文件。各个图层可以单独操 作也可以同时对几个图层一起操作。 构成专题的是地图要素，也就是说，专题是地图要素的集合。可以将专题当 作逻辑上的“层”来看待。根据信息处理的需要，一个地图要素可以出现在一个 地图中，也可以重复出现在多个图层中。 地图按不同专题分层的方法能够突出主题，不同行业和人员可根据各自的需 要，选择关心的专题图层，既优化了计算机的信息管理，又减轻了人脑信息获取、 分析和运用的工作量。 2 3 2 地理信息系统的数据库管理 g i s 数据库的管理，目前又有四种基本的解决方案：文件型、双数据库型、 扩充d b m s 型和空间数据库型。根据所采用的数据库管理方法，又可将g i s 分成 四种类型嗍，如图2 4 所示。 i 应用界面 南l 焘 i 空间与属性数据库 应用界面 i l 空间ii 属性 处理i i 处理 i l 空间数据 管理功能 扩展 事务管理用的 d b m s 空间与属性数据库 l 应用界面 由蔗 l 搠= 髓 i 空间与属性数据库 文件型g i s双数据库型g i s 扩展d b m s 型g i s空间数据库型g i s 图2 4g i s 数据库的管理 ( 1 ) 文件型g i s 这种方法比较简单，也是最初的g i s 软件采用的方法，没有集中控制的数据 库管理系统，适合于小规模的g i s 。 ( 2 ) 双数据库型g i s 这种方法是利用一般的d b m s ( 多数是关系型的) 管理属性数据，专门的软 件管理空间数据，它们之间通过一定的操作相联接。用户既可以和两个数据库分 别打交道，也可以通过某种途径同时访问两个数据库，目前大部分g i s 软件都采 用这种方法。 ( 3 ) 扩充d 蹦s 型g i s 这种方法是对一个通用事务管理用的d b m s ( 一般是关系型的) 进行功能扩 展，增加空间数据的管理能力，使之适合g i s 用户的特殊需要。这种方法是空间 和属性数据之间的联系比较紧密，趋于一体化，还便于利用某些d b m s 产品的现 成功能( 如：客户机月艮务器的运行模式等) ，但是为了使空间数据适应关系模型， 1 4 则要牺牲软件运行的效率。 ( 4 ) 空间数据库g i s 这种方法采用空间数据库系统来集中管理空间和属性数据，它使属性数据的 管理和空间数据的管理完全一体化了，用户界面也容易做的简洁。但空间数据库 型g i s 发展历史较短，技术还不够成熟。 目前的g i s 软件中，a r c i n f 0 、m a p l n f o 、g e n a m a p 、m g e 等属于双数据库类 型，g e 0 v i s i o n 、s i c a d 0 p e n 、s y s t e m 9 等属于扩充d b 峪类型，以栅格模型为主 的软件大多数采用第一种或者第四种类型，四分树结构的软件也可采用第二种类 型。 2 4 地理信息系统的网络分析 对交通网络、城市基础设施网络( 如各种网线、电力线、电话线、供排水管 线等) 进行地理分析和模型化，是地理信息系统功能的一个主要方面。它的根本 目的是研究、筹划一项网络工程如何安排，并使其运行效果最好，如一定资源的 最佳分配，从一地到另一地的运输费用最低等。其基本思想则在于人类活动总是 趋于按一定目标选择达到最佳效果的空间位置。这类问题在社会经济活动中不胜 枚举，因此在地理信息系统中此类问题的研究具有重要意义。 ( 1 ) 路径分析 路径分析是g i s 中最基本的功能，核心是对最佳路径和最短路径的求解【1 9 1 。 从网络模型的角度看，最佳路径求解就是在指定网络中两结点问找一条阻碍强度 最小的路径。最佳路径的产生基于网线和结点转角( 如果模型中结点具有转角数 据) 的阻碍强度。例如，如果要找最快的路径，阻碍强度要预先设定为通过网线 或在结点处转弯所花费的时间；如果要找费用最小的路径，阻碍强度就应该是费 用。当网线在顺逆两个方向上的阻碍强度都是该网线的长度，而结点无转角数据 或转角数据都是0 时，最佳路径就成为最短路径。在某