（计算机软件与理论专业论文）多因素约束的时间窗车辆路径寻优及其可视化研究.pdf

武汉理工大学硕士学位论文 摘要 本文针对城市交通道路网的特点，对g i s ( 地理信息系统) 环境下多因素 约束的时间窗车辆最优路径选择问题的关键技术进行了研究。旨在通过动态路 径寻优系统规划出到达目的地的最优路径。通过深入分析这一类问题的特点， 引入了桌面式g i s 开发平台- - m a p l n f o ，以武汉市区电子地图为基础，对路径 规划的算法进行了研究和改进。在此基础上，提出了一种实用、高效的动态路 径优化分析解决方案，实现了多因素约束下的车辆最优路径分析实验系统。本 文所做的主要研究工作包括： ( 1 ) 针对g i s 中的数据模型，数据的组织和管理形式，在分析了路网拓 扑结构的基础上，研究了路网拓扑结构表示的数据结构和g i s 环境下提取路网 拓扑结构的关键技术。 ( 2 ) 为了得到基于静态与动态多种因素约束的最优路径，本文把道路网权 值的计算分解为基本道路权值与动态权值两部分，使得寻优结果更具有现实意 义。 ( 3 ) 对多因素约束的时间窗车辆路径问题建模，并且利用蚁群算法卓越的 随机搜索寻优能力和自适应性分布式的计算特点，使用优化的蚁群算法求解最 优路径问题。 ( 4 ) 使用m a p l n f o 公司的m a p x t r e m e 2 0 0 4 控件，在v i s u a ls t u d i o n e t 集 成开发环境下，设计并实现了系统仿真。 关键字：多因素；路网拓扑结构；时间窗；地理信息系统；蚁群算法 武汉理 ：大学硕士学位论文 a b s t r a c t b a s e do nt h ef e a t u r e so ft h eu r b a nt r a f f i cr o a d sn e t w o r k ，t h i sp a p e rr e s e a r c h e s t h ek e yt e c h n o l o g yo fc h o o s i n gt h em u l t i f a c t o rr e s t r i c t e do p t i m u mv e h i c l em u t e w i t ht h et i m ew i n d o wi ng i s ( g e o g r a p h yi n f o r m a t i o ns y s t e m ) ，t h e nt h et h e s i s p u t sf o r w a r da l lo p t i m u mp a t ht od e s t i n a t i o nt h r o r i g hd y n a m i cr o u t i n gs y s t e m s c h e d u l i n g a f t e rd e e pa n a l y s i so fc h a r a c t e r i s t i c so ft h ep r o b l e m ，i ti n t r o d u c e s d e s k t o pg i sd e v e l o p m e n tp l a t f o r m m a p l n f o a n ds t u d i e so nr o u t e s c h e d u l i n g a l g o r i t h ma n di m p r o v e si tb a s e do nw u h a nu r b a nd i s t r i c te m a p o nt h i sb a s i s ，i t p u t sf o r w a r dap r a c t i c a la n dh i g he f f i c i e n td y n a m i cr o u t i n go p t i m i z a t i o ns o l u t i o n , a n di m p l e m e n t e dm u l t i f a c t o rv e h i c l er o u t i n go p t i m i z a t i o na n a l y s i se x p e r i m e n t s y s t e m n l ew o r kh a st h ef o l l o w i n g4 p o i n t s ： ( 1 ) f o c u so nd a t am o d e l ，o r g a n i z a t i o na n dm a n a g e m e n tf o r mi no l s ，t h i st h e s i s i n t r o d u c e st h ed a t as t r u c t u r ef i g u r e db yr o a dn e t w o r kt o p o l o g i c a ls t r u c t u r e ，f r o m w h i c he x t r a c t st h ek e yt e c h n i q u ea f t e ra 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 ( 2 ) t og e tt h em u l t i f a c t o rr e s t r i c t e do p t i m u mp a t ho nt h eb a s i so fs t a t i ca n d d y n a m i ca n a l y s i s ，t h ep a p e rd i v i d e st h ec a l c u l a t i o no ft h ev a l u eo fr o a dn e t w o r ki n t o t h eb a s i ca n dt h ed y n a m i cp a r t ，w h i c hm a k e st h er e s u l tm o r er e a l i s t i c ( 3 ) m o d e l i n gm u l t i f a c t o rv e h i c l er o u t i n gp r o b l e m 稍t ht i m ew i n d o w b a s e d o nc h a r a c t e r i s t i c so ft h eo u t s t a n d i n gr a n d o ms e a r c ha n dt h ea d a p t e dd i s t r i b u t i n g c a l c u l a t i o no fa n tc o l o n ya l g o r i t h m , t h et h e s i su s e st h eo p t i m u ma i t c o l o n y a l g o r i t h mt os o l v et h ev e h i c l er o u t ep r o b l e m ( 4 ) b yu s i n gt h em a p x t r e m e 2 0 0 4c o n t r o lo fm a p i n f oc o r p ，t h et h e s i sd e s i g n s a n di m p l e m e n t ss y s t e ms i m u l a t i o nu n d e rv i s u a ls t u d i o n e ti n t e g r a t e dd e v e l o p m e n t e n v i r o n m e n t k e y w o r d s ：m u l t i f a c t o r ；s t r u t u r eo fn e t w o r kt o p o l o g i c a l ；t i m ew i n d o w ；g i s ； a n tc o l o n ya l g o r i t h m i i 武汉理一l 人学硕十学位论文 1 1 课题研究背景 第1 章绪论 随着经济发展和技术进步，交通运输已经成为人们经济生活中不可缺少的 重要组成部分。它对保证社会经济体系及日常生活的正常运转发挥着越来越大 的作用。 近2 0 年来，世界各国先后建立了四通八达的交通运输网络，但交通工具的 增长速度远远高于道路和其他交通设施的增长。因此随之引起交通拥堵、环境 污染、交通事故等一系列交通问题，也造成了巨大的物质与经济损失。以美国 为例，在1 9 8 2 年至2 0 0 0 年之间，由于交通堵塞造成的时间和汽油的浪费而带 来的经济损失每年高达6 8 0 亿美元，而且这些数字还在以每年5 1 0 的速度 增长。在我国。虽然在“十五”计划期间我国城市交通投资已达8 0 0 0 亿人民币， 但由于我们道路基础设施薄弱，在道路上存在行人、自行车和机动车混行的状 况，加上机动车辆的增长速度已远远高于道路的增长，所以交通问题更是突出。 以2 0 0 1 年为例，全国的机动车保有量为6 8 5 2 万辆，比上年增长1 4 2 ，驾驶 员保有量为8 2 2 0 万人，比上年增长了1 0 。因此在有些城市中陷入了“拥有 了最宽阔的马路，也拥有了最宽阔的停车场”的困境。以北京为例，近期的调 查显示，多数北京人上班需花费l h 以上的时间，而在2 0 m i n 以内到达工作地 的仅占5 6 。除了堵塞和环境污染外，交通事故造成的损失也十分严重。近 几年来，全国道路交通事故呈上升趋势，2 0 0 1 年全国道路交通事故达7 6 万起， 平均每天有2 9 0 人被交通事故夺去宝贵生命。 这些情况表明，单纯依靠修建道路与交通设施和采用传统的管理方式来解 决交通问题，不仅成本昂贵、环境污染严重，而且其缓解交通拥堵、提高交通 运输效果也是十分有限的。开始大规模地进行道路交通运输智能化的研究，这 就导致了“智能交通系统”( 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 ) 的诞生。i t s 是利用现代的通信技术、定位技术、计算机技术、地理信息系统技术以及相关 信息产业来解决交通问题，提高路网资源效率的一项系统工程，其核心是车辆 识别和定位、交通监视、通信、信息处理等技术。 武汉理工大学硕士学位论文 交通诱导系统是i t s 研究的热门核心课题，预测未来时段道路上的交通状 况，给出行者提供实时有效的信息，帮助更好的进行路径选择，实现路径诱导， 以缩减行程时间，减少交通堵塞。 路径规划是交通诱导系统开发中的关键。在以往的路径研究中，一个重要 的参数路径运行成本常常被假定为静态的，在路径的制定和执行过程中不 会发生变化。但是在实际车辆行驶过程中，由于交通管理、交通流量、交通事 故、天气变化等因素的影响，行驶速度总是处在不断变化之中，导致了路网中 各个路段上的运行成本也相应的发生变化。这种动态变化的情况，传统静态网 络下的路径问题研究显然无法解决，而相应的基于多因素的动态路径寻优问题 的研究就显得格外具有实际意义。随着计算机通信以及信息处理技术的不断进 步和智能交通系统的日益完善，实时获取和处理交通信息己成为可能，也为在 动态路网中研究最优路径问题提供了有利条件。 1 2 课题研究的目的和意义 近年来，随着地理信息系统的发展，基于g i s 这个方向的研究与应用已经 非常广阔。g i s 因为其强大的数据分析功能、空间分析功能，己被广泛应用于各 种系统中与空间信息有密切关系的各个方面各种在实际中的系统如电力系统， 光缆系统涉及到最佳、最短抢修等问题都可以折合到交通道路网络中来进行分 析，故而交通道路网络中最短路径算法就可以广泛的应用于其它很多的最佳、 最短抢修或者报警系统。本文研究了交通道路网络系统中的一个重要议题 求解最短路径。 g i s 中最短路径的求解无论是在智能交通系统，还是在其他各种各样的商 业应用上，都是一个非常重要的核心问题，对这个领域进行研究的意义是不言 而喻的。 传统的最短路径求解的研究重点多偏向于最短路径算法的创新和改进，而 这些算法又大多出于对静态的因素，诸如：道路等级、行驶速度、行驶成本等， 来考虑进行最短路径的计算和选取。但是这样的选择结果运用于实际却难有很 好的效果，因为驾驶员的实际行驶路线很可能基于交通变化或者个人的偏好有 所改变，所以基于静态因素选取的行车路线对驾驶员指导意义不大，因此对基 于多因素约束的车辆路径寻优问题的解决具有很高的现实意义。 2 武汉理一r 大学硕士学位论文 有时间窗的车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w s v r p t w ) 是在v r p 的基础上增加了客户要求访问的时间窗口。由于现实生活中许 多问题都可以归结为v r p t w 来处理( 如邮政投递、电力及工业管理等) ，处理的 好坏也直接影响到一个企业的效益和顾客的利益，所以对v r p t w 的研究越来越 受到人们的重视。 时间窗可以分为软时间窗( s o f tt i m ew i n d o w s ) 和硬时间窗( h a r dt i m e w i n d o w s ) 。软时间窗是指：在用户规定的时间内，不能达到目的地，也给出相 应的行车路线：硬时间窗是指：在用户规定的时间内，若不能达到目的地，则 不接受系统给出的行车路线。本文研究的是软时间窗问题。 1 3 研究现状 1 3 1g i s 环境下的最短路径算法分类 根据解决问题的思想不同可将各种最短路径算法分为基于地理信息系统空 间查询语句( g s q l ) 最短路径分析和基于功能模块的最短路径分析两大类。 ( 1 ) 基于g i s 空间查询语言的最短路径算法 g s q l 语言是基于s q l 扩展的空间查询语言，包括数据模式定义、数据查 询、数据更新等。g s q l 对s q l 标准语句扩展，从而支持空间数据类型、空间数 据运算符、空间关系运算以及空间分析功能。在数据类型上，不但要支持结构化 的数据，而且要支持像点、线、面这样的空间数据类型。 这种方法目前更多的停留在理论研究阶段，如m a x 定义了一套空间查询 语言，对其完备性进行了证明，并举证分析了范围查询、时态查询、最邻近查 询的应用举例，通过形式化定义种适合于g i s ( g e o g r a p h i ci n f o r m m i o n s y s t e m s ) 空间查询的变量，查询代数拓展了一般查询代数的查询空间，从而完 成最短路径分析功能；提出边和区域的空间连接预处理和空间约束条件的预处 理两种优化方法，从而提出4 种空间路径查询处理优化策略。尽管针对基于 g i s 空间发展研究的g s q l 不失为一种处理最短路径的手段，但由于受g i s 数据库技术发展的制约，而实际应用领域与背景的不同，也使其离商业实际应 用还有很长的距离。 ( 2 ) 基于功能模块思想的最短路径算法 武汉理1 ：大学硕十学位论文 基于模块思想的最短路径算法研究是目前研究的热点。针对不同的应用领 域，不同的功能要求产生了各式各样的单源最短路径，算法按照不同的分类方 法、文体特征及实现技术的差异，可分为很多种，比如d i j k s t r a 算法，动态规 划方法，神经网络法，流体神经网络模拟交通网并结合遗传算法优化参数法， 遗传法优化路径参数的d i j k s t r a 法，基于路径模糊信息的最大满意度路径法等。 针对不同的背景应用需求及具体的软硬件环境，各种算法在空间复杂度和时间 复杂度易实现性等方面各具特色。其中，采用负心启发搜索策略的d i j k s t r a 算 法，是目前已知理论上最完善的算法，得到了广泛应用。 1 3 2 最短路径算法 单纯的最短路径是个古老的话题，而在g 1 s 路径中寻找最短路径的研究 将会有更多的内容，道路信息的结构，数据的组织，都是很重要的。国内外许 多组织，学者都在这个方向做了大量的研究工作。他们的研究大多集中于对最 短路径算法的改进和优化，其中以启发式搜索和d i j k s t r a 为多。 ( 1 ) 启发式搜索策略介绍 1 ) 穷举法 有深度优先与广度优先两种搜索算法。在一个连续的有限空间或离散无限 援索空间中，计算空间中每个点的目标函数值，且每次计算一个。这是最基本 的两种图搜索算法，它们实质上是对图中路径进行遍历的过程，单纯应用深度 优先或广度搜索策略的最短路径算法，显然，这种方法效率太低而鲁棒性不强。 许多实际问题所对应的搜索空间很大，不允许一点一点地馒慢求解。此类算法 不能保证所得到的路径是最佳路径。 2 ) 动态路径规划法 这种方法是一种步进式s t e p t a k i n g 搜索方法，要求每步都必须离目标 更近，即不得在反方向搜索，更适合于栅格数据中的路径搜索。这种算法利用 动态规划理论求解最短路径，即将始点到终点的路程分为若干状态，从而将之 转化为多阶段决策问题，这样就可用动态规划理论来解决。但这也必然决定了 它的局限性，即只有求解可进行状态划分的问题，而事实上有很多问题是不能 进行如此转化的，但这种算法却是在这种特殊条件下的最佳算法，因而也得到 一些应用。 3 ) 启发式搜索法 4 武汉理j - 9 学硕十学位论文 又叫i n f o r m e d 搜索方法，是一种首先对最有希望的节点进行搜索的策略。 在计算机搜索算法中，启发式策略指通过一定知识进行搜索，即通过选定一种 评估函数，在搜索过程中的每一步，寻找评估函数得分值最高的节点作为下一 个搜索扩展节点。启发式搜索策略的主要优点在于可将搜索限定在一定规模内， 寻找最佳路径的算法在实际应用中主要是指这种算法。启发式策略有很多种， 如贪心策略、方向策略、区域策略、层次策略等。基于启发式贪心策略的最短 路径算法包括贪心算法、爬山法、a + 算法等。其中贪心算法属于启发式搜索策 略中的b f s ( b e s tf i r s ts e a r c h ) 类型，即对节点评估函数值进行排序，评估值 最高者首先扩展。爬山法( h i l lc l i m b i n g ) 是另一种贪心搜索算法，它将当前 至终点的欧式距离作为扩展路径的启发式策略，对于处理规则交通网络中的最 短路径搜索，具有一定优势。a t 算法是一种在随机产生式系统中应用比较广泛 的启发式搜索算法，它与步进式算法类似，不同点在于当无法得到至终点的路 径时，a 算法允许路径的回溯与重新选择。 针对地理信息系统中特定的两点路径寻优问题，提出了一种基于先验知识 的快速搜索算法，该算法模拟人脑寻找路径的思维过程，首先针对实际问题建 立先验知识库，在路径搜索过程中，利用知识库中的信息剪去不可能的搜索路 径，构造出简化的查询树，从而大大提高最优路径的搜索速度；文献f 1 3 1 还提 出了方向优先的快速搜索算法，该算法在路径搜索过程中，首先搜索与前进方 向更加接近的方向，可以在搜索的早期找到最短路径，从而在以后的搜索中剪 去更多的节点和分支。 文献 1 6 探讨了基于启发式方法策略的最短路径算法，包括空间有效方法 的可控参数法、空间方向性优化算法等。其中空间有效方向的可控参数，通过 设置可调节系数，使得当有效方向上路径无效时能保证得到可用路径；空间方 向性优化算法是利用两点间直线最短的原理，通过构造二叉树来得到最短路径， 其实只是有损最短路径。基于启发式区域策略的最短路径算法，包括椭圆限制 搜索区域的最短路径算法、矩形限制区域的最短路径算法等。其中椭圆限制搜 索区域的最短路径算法以待求最短路径的起终结点作为焦点，构造椭圆限制区 域，进而在该限制区域内进行贪心搜索1 1 7 。 文献 1 8 】 1 9 2 0 【2 1 】讨论了几种基于启发式层次策略的最短路径算法，其 中包括层次空问推理的最短路径算法，层次编码路径视图( h i e r a r c h i c a le n c o d e d p a t h v i e w ，h e p v ) 结构的最短路径算法等。层次空间推理算法是根据路段等级 武汉理j i ：火学硕士学位论文 将交通网络划分成不同的层次，尽可能地在高阶层次完成最短路径的选择( 通 过过滤掉大量与欲解决问题无关的细节信息) ，实质上是一种有损最短路径。 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 g a l g o r i t h m s ) ，是目前理论最完善，迄今为止应用最广泛的非负权值网络最短路径 算法。标号设定法是一种基于贪心策略的最短路径算法，它要求在路径选择中 的每一步所选择的路径都是目前为止最好的。在局部最优而导致最优的假设下， 寻求最佳路径不同的实现方法，构成d i j k s t r a 算法的庞大家族，如a r c l n f o 中 的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 算法：采用动态段数据模式的双向比较追索法 的d i j 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 算法等【2 2 1 。 与a + 算法不同，为保证起点到当前节点的路径最优性，d 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 g a l g o r i t h m s ) 已有研究，标号改进法可以解决存在负权边的网络最短路径问题， 但它不是保证在每次循环中均能发现一条最优路径。其效率一般比标号设定法 低。由于交通网络中不存在负权边，所以交通网络最短路径算法常指标号设定 法，即改进的d i j k s t r a 算法。 另外，有不少研究是提出了新的算法，如文献 1 4 1 定义了有向图的代价邻 接矩阵和最短路径矩阵，给出称为“乘位加比小”的一种代价邻接矩阵间的新 运算，基于该矩阵运算，证明了一种称为“代价邻接矩阵乘位加比小算法”的 新的最短路径算法：文献 1 5 】 1 6 从城市道路网络的特点出发，分析了道路路段 间的连通关系，得出一种求城市道路网络两节点间的最短路径的算法，最后通 6 武汉理工大学硕士学位论文 过在g i s 软件m a p l n f o 中编制的算法程序实例，验证了算法的实用性和可靠 性。 1 4 本文研究内容 求解多因素约束的时间窗车辆路径寻优问题，就是要在g i s 环境下寻求 动态最优路径问题，由于是要解决城市道路最优路径问题，所以，要考虑到多 方面的问题。首先，必须考虑城市交通路网的情况。 城市道路网除具有一般道路网的特点之外，还有其特殊之处。对于大型城 市来说，城市道路网中的路段数往往动辄以成千上万计，数据量大。而且随着 城市的发展，城市交通系统越来越向复杂的方向发展，多车道、单行线、转弯 限制、立交系统等交通特征变得越来越普遍，加上新的越来越复杂的交通规则， 这些都使得城市道路网的结构变得非常复杂。因此，针对城市道路网进行最优 路径分析的研究不仅可以解决实际应用系统的应用需求，而且可以很方便地将 其研究成果推广到一般的道路网上面。 要对城市道路网进行最优路径分析，首先必须将现实中的城市道路网络实 体抽象化为网络图论理论中的网络图，然后通过图论中的网络分析理论来实现 道路网络的最优路径分析。在实际应用中，城市道路网的表现形式一般为数字 化的矢量地图，其网络空间特征中的交叉路口坐标和道路位置坐标是在地图上 借助图形来识别和解释的；而为了能够高效率地进行最短路径分析，必须首先 将其按结点和弧的关系抽象为图的结构。这就需要先对原始城市道路图进行预 处理，建立其相应的网络拓扑关系。预处理的工作主要包括： ( 1 ) 对城市数字地图道路层进行拓扑检查，生成线和线相互不相交叉的道 路图： ( 2 ) 对道路网络图定义其属性特征，如道路名称、道路距离等； ( 3 ) 生成有拓扑关系的拓扑文件。经过预处理后，当对城市道路网进行最 短路径分析操作时，系统直接从拓扑文件中提取道路网的网络拓扑结构并加载 到内存中，从而提高路径分析的效率。如果由于城市建设的发展，城市道路发 生了变化，地图更新后，只需重新进行预处理生成拓扑文件。 ( 4 ) 选择适当的算法计算出最优路径。 系统的整个工作流程见图1 1 所示： 武汉理【大学硕士学位论文 m a p l n f o 地图 生成拓扑文件 最优路径分析 把所求得的最优路径 显示在数字地图上 图1 1 系统的简单工作流程图 本文针对交通网络的地图表示及网络拓扑结构的提取和构建这两项关键技 术提出了实用、高效的解决方案。本文所作的主要工作是在g i s 环境下抽取 地图路网，并根据路网的特点结合算法的需要构建出了表示道路拓扑关系的数 据结构，并通过算法来对动态路径问题进行求解，按照动态最优路径问题所提 出的以动态因素的综合权值而不是距离作为运行成本来计算最优路径。更进一 步，通过限制搜索区域策略来求解最短路径。最后，利用c 群n e t 与m a p l n f o 作 为开发平台，实现了原型系统的可视化。 武汉理= 大学硕士学位论文 第2 章地理信息系统 2 1 地理信息系统概述 2 1 1 基础概念 地理信息系统( 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 s ，简称g i s ) 是一种采集、 存储、管理、分析、显示与应用地理信息的计算机系统，是分析和处理海量地 理数据的通用技术。他在最近的3 0 年内取得了惊人的发展，并广泛地应用于资 源调查、环境评估、区域发展规划、公共设施管理、交通安全等领域，成为一 个跨学科、多方向的研究领域。 作为一种通用的技术，地理信息系统按一种新的方式去组织和使用地理信 息，以便更有效的分析和生产新的地理信息；同时，地理信息系统的应用也改 变了地理信息分发和交换的方式。 地理信息系统是有关空间数据管理和空间信息分析的计算机系统。依照其 应用领域，地理信息系统可分为土地信息系统、资源管理信息系统、地学信息 系统；根据其使用的数据模型，可分为矢量、栅格和混合型信息系统；根据其 服务对象，可分为专题信息系统和区域信息系统。 图2 1 信息系统的分类 9 武汉理 大学硕士学位论文 2 1 2 发展历史及现状 1 国际发展状况 g i s 发展，尤其在北美地区，可以分为以下几个阶段： ( 1 ) 6 0 年代为地理信息系统开拓期，注重空间数据的地学处理。许多大 学研制了一些基于栅格系统的软件包，如哈佛的s y m a p 、马里兰大学的m a n s 等。 ( 2 ) 7 0 年代为g l s 的巩固发展期，注重空间地理信息的管理。在这个年 代，资源开发利用、环境保护问题成为政府首要解决的疑难问题，而且相应的 计算机技术迅速发展，数据处理速度加快，计算机硬件价格下降，专业化人才 不断在增加，许多大学也开始提供g i s 培训。这些有利因素推动了g i s 的良性 发展。 ( 3 ) 8 0 年代为g i s 大发展时期，注重与空闯决策支持分析。地理信息系 统的应用领域迅速扩大，从资源管理、环境规划到应急反应，从商业服务区域 划分到政治选举分区等，设计到了许多的学科与领域。许多国家制定了本国的 地理信息系统发展规划，如中国在1 9 8 5 年成立了资源与环境信息系统国家重点 实验室，美国于1 9 8 7 年成立了国家地理信息分析中心( n c g i a ) ，英国于1 9 8 7 年成立了地理信息协会。 ( 4 ) 9 0 年代为g i s 的用户时代。一方面g i s 已成为许多机构必备的工作 系统，另一方面，社会对g i s 的认识普遍提高需求大幅增加。国家级乃至全球 性的地理信息系统已成为公众关注的问题。目前，仅美国从事g i s 产业的公司 约有1 6 0 多个，他们提供包括数字化、数据转换和专业应用方面的不同服务其 中环境系统研究所( e r s i ) 和i n t e r g r a p h 公司就占了联邦和商业部门5 0 的g i s 市场。另外，前国防系统的一些销售商也瞄准了g i s 技术，并开始向这一市场 转变。这些行为有力地推动了g i s 技术由机助制图向社会普及的发展。 2 我国g i s 的发展 国内相对起步较晚，自2 0 世纪7 0 年代末开始，以1 9 8 0 年中国科学院遥感 应用研究所成立全国第一个g i s 研究室为标志，经历了准备( 1 9 7 8 1 9 8 0 年，正 式提出倡议，开始组建队伍、组织实验) 、起步( 1 9 8 1 1 9 8 5 年，理论探索和区 域性实验研究，并在此基础上制定国家地理信息系统规范) ，发展( 1 9 8 6 1 9 9 5 年) 、产业化( 1 9 9 6 年以后，地理信息系统得到广泛的关注和研究，并逐步和国 1 0 武汉理1 ：人学硕十学位论文 民经济建设相结合，取得了重要的进展和实际应用效益) 4 个阶段。 2 ，1 3 地理信息系统的基本功能及应用领域 1 地理信息系统的基本功能： ( 】) 数据采集、监测与编辑主要用于获取数据，保证地理信息系统数据 库中的数据在内容与空间上的完整性、数值逻辑一致性与正确性等。所以，g i s 必须具备将地图、野外调查、航空照片、卫星影像、磁带或报告等不同来源的 资料，透过文字，图形终端机、数字化仪、扫描仪等转换成计算机能够接受的 数值型式资料( d i g i t a ld a t a ) 之功能。 ( 2 ) 数据处理初步的数据处理主要包括数据格式化、转换、概括。数据 的格式化是指不同数据结构的数据间变换，是一种耗时、易错、需要大量计算 量的工作，应尽可能避免；数据转换包括数据格式转化、数据比例尺的变化等； 制图综合( g e n e r a l i z a t i o n ) 包括数据平滑、特征集结等。目前地理信息系统所提 供的数据概括功能极弱，与地图综合的要求还有很大差距，需要进一步发展。 ( 3 ) 数据存储与组织这是建立地理信息系统数据库的关键步骤，涉及到 空间数据和属性数据的组织。栅格模型、矢量模型或栅格矢量混合模型是常用 的空间据组织方法。空间数据结构的选择在一定程度上决定了系统所能执行的 数据与分析的功能；在地理数据组织与管理中，最为关键的是如何将空间数据 与属性数据融合为一体。 ( 4 ) 空间查询与分析空间查询是地理信息系统以及许多其它自动化地理 数据处理系统应具备的最基本的分析功能。空间分析是地理信息系统的核心功 能，也是地理信息系统与其它计算机系统的根本区别，模型分析是在地理信息 系统支持下，分析和解决现实世界中与空间相关的问题，它是地理信息系统应 用深化的重要标志。 ( 5 ) 图形与交互显示地理信息系统为用户提供了许多用于地理数据表现 的工具，其形式既可以是计算机屏幕显示，也可以是诸如报告、表格、地图等 硬拷贝图件，尤其要强调的是地理信息系统的地图输出功能。 2 地理信息系统的应用领域 ( 1 ) 资源清查：是地理信息系统最基本的职能，其主要任务是将各种来 源的数据汇集在一起，并通过系统的统计和覆盖分析功能，按多种边界和属性 条件，提供区域多种条件组合形式的资源统计和进行原始数据的快速再现。 武汉理 二大学硕士学位论文 ( 2 ) 城乡规划：城乡规划的处理涉及资源、环境、人口、交通、经济、 文化和金融等多个地理变量和大量数据。地理信息系统的数据库管理有利于将 这些数据信息归并到同一系统中，最后进行城市与区域多目标的开发和规划。 ( 3 ) 灾害监测：借助遥感遥测数据，利用地理信息系统，可以有效的用 于森林火灾的预测预报、洪水灾情检测和洪水淹没损失的估算，为救灾抢险和 防洪决策提供及时准确的信息。 ( 4 ) 土地调查：借助地理信息系统可以进行地籍数据的管理更新，开展 土地质量评价和经济评价，输出地籍圈，为土地的科学管理合理利用提供依据。 ( 5 ) 环境管理：环境管理信息系统可以为环境管理部门提供数据和信息 存储方法；可以建立环境污染的若干模型，为环境管理决策提供支持。 ( 6 ) 城市管网：管网是城市居民日常生活不可去少的基本条件，g i s 能 建立二维拓扑关系，其网络分析能力为城市管网的设计管理和规划建设提供了 强有利的工具。 ( 7 ) 作战指挥：军事领域中运用g i s 技术最成功的例子当属1 9 9 1 年海 湾战争。它与遥感技术集成的系统，能用自动影响匹配和自动目标识别技术处 理卫星和高低空侦察机实时获得的战场数据影像，及时地将反映战场现状的正 射影像图叠加到数字地图上，并将其传送到前线指挥和五角大楼，为军事决策 提供2 4 小数的实时服务。 ( 8 ) 宏观决策：g i s 利用拥有的数据库，通过一系列决策模型的构建和 分析，为国家宏观决策提供依据。如系统支持下的土地承载力的研究，可以解 决土地资源与人口容量的规划。 2 2 地理信息系统空间数据管理 2 2 1 空间数据结构 地理空间数据是指以地球表面空间位置为参照的自然、社会和人文景观数 据，可以是图形、图像、文字、表格和数字等，由系统的建立者通过数字化仪、 扫描仪、键盘、磁带机或其它通讯系统输入g i s ，是g i s 所表达的现实世界经 过模型抽象的实质性内容。空间数据结构是指地理实体的空间排列方式和相互 关系的抽象描述。g i s 空间数据结构主要有两种类型：矢量结构和栅格结构。 1 2 武汉理l ：大学硕士学位论文 1 栅格数据模型 在栅格模型中，空间被规则地划分为栅格( 通常为正方形) 。地理实体的 位置和状态是用它们占据的栅格的行、列来定义的。每个栅格的大小代表了定 义的空间分辨率。由于位置是由栅格行列号定义的，所以特定的位置由距它最 近的栅格记录决定。 在栅格方法中，统一的单位是栅格( 栅格是不可再分的，其属性用于表达 对应位置物体的性质) ，表达一个区域所用栅格的数量很大，但其栅格单元的 大小一样。栅格数据文件包含有上百万个栅格，每个栅格的位置都被严格定义。 栅格模型将空间分成一系列的单元，每个单元代表有限但确定的地球表面。单 元可以具有任何几何形状，只要能组合出表达研究区域的面即可。虽然栅格单 元有许多形状，如三角形、六角形，但通常采用固定大小的正方形。正方形的 栅格单元称为网格单元，空间事物就按其在网格种的行、列和取值来表示。网 格单元的大小代表了栅格型地图( 空间) 数据库的分辨率。这些离散的数据网 格具有叠加方便、迅速的特点，所以常被用来作为空间物体的背景图。 栅格模型的突出优点是，它可以直接利用遥感、数字摄影测量、扫描等方 式获取栅格形式的数据，且数据结构简单；空间数据的叠置和组合十分方便： 各类空间分析都很容易实现；数学模拟方便。其缺点是，随着精度的增大，数 据量不断增大，从而对设备的存储空间要求过高，且查询速度较慢。图形数据 量大：用大像元减少数据量时，图形精度和信息量受到损失，地图输出较差， 难以建立网络连接关系，投影变换十分耗时。栅格数据结构有利于多边形的叠 置、空间均值处理和空间分析，但输出的专题地图既不美观也不够精确。采用 该类方法，难予实现空间实体的旋转及坐标的变换操作，对空间实体的识别和 标识操作较麻烦。 武汉理一r 大学硕十学位论文 表2 - 1栅格数据模型 实体类型 地图表示法栅格表示法 数据矩阵 m a p r a s t e r f e a t u r et y p ed a t aa r r a y r e p r e s e n t a t i o nr e p r e s e n t a t i o n 0 10 0 l0 l0 l0 i 厂广广1 1 1 10 10 l0 l0 10 10 i 点状实体 旅馆 鳟嘏 io io i0 10 io f l f p o i n tf e a t u r eh o t e l 0 11 i0 1 o l0 l0 l 0 10 10 i i l0 l0 l 0 10 10 1o o lo i 0 l0 l0 10 10 10 1 线状实体 y 丫辫 1 1 1o i0 1 o l0 1 1 l l0 1 1 l0 1 1 l i 0 l l i n ef e a t t i r e 0 1 1 1 1 10 1 1 10 i 1 1 i 1 10 lo 0 10 f o io io l0 1o 0 i 离 冈锶 l i l i l l 3 l3 l3 l 回 散 | l 1 1 1 1 1 i3 l3 l 1 1 1 1 13 i3 i3 3 i 状 型 2 l2 i2 i3 14 l4 i 2 i2 l2 l4 l4 l4 l 实 d i s c r e r e2 i2 l2 l4 l4 l4 i 体连 h 口i4 4 i4 s i4 2 l3 3 13 0 i a r e a续 妒 1 4 2 i “l 7 l 相l4 d ，8 l 4 7 l5 2 i5 4 i5 ) j4 5 旧l f e a t u r e 趔 f 圳5 3 i _ f5 3 f4 5 f3 9 4 5 i4 6 i4 7 i 舯l4 7 i _ o i c o n t n 1 1 0 t i s 4 2 i4 5 4 5 1 4 6 i4 4 i4 2 i 2 矢量数据模型 栅格数据模型以网格为单位表示地理数据，矢量数据模型以点为基本单位 描述地理实体的分布特征，也即将每一个地理实体看作是由点组成的，每一个 点由一对( x ，v ) 坐标表示。这里的坐标可为地理坐标，也可以为平面直角坐 标。点状实体由一个单独的点表示，线状实体由一列有序点集表示，点的记录 顺序称为线的“方向”；面状实体由一列首、尾同点的有序点集表示。线状和 面状实体在显示时分别以直线段将组成他们的点链接成线段链( c h a i n ) 和多边 形( p o l y g o n ) 。矢量模型中的空间实体与要表达的现实世界中的空间实体具有 一定的对应关系，一条线可能表达一条道路，一个多边形可能表达一块林地等。 点( x ，y ) 山 图2 2 基本矢量图形的向量表达 4 ，y ) 区域 武汉理 二人学硕士学位论文 对于点实体，矢量结构中只记录其在特定坐标系下的坐标和属性代码；对 于线实体，在数字化时即进行量化，就是用一系列足够短的直线首尾相接表示 一条曲线，当曲线被分割成多而短的线段后，这些小线段可以近似地看成直线 段，而这条曲线也可以足够精确地由这些小直线段序列表示，矢量结构中只记 录这些小线段的端点坐标，将曲线表示为一个坐标序列，坐标之间认为是以直 线段相连，在一定精度范围内可以逼真地表示各种形状的线状地物；多边形在 地理信息系统中是指一个任意形状、边界完全闭合的空间区域。把这样的闭合 区域称为多边形是由于区域的边界线同前面介绍的线实体一样，可以被看作是 由一系列多而短的直线段组成，每个小线段作为这个区域的一条边，因此这种 区域就可以看作是由这些边组成的多边形了。 矢量数据模型非常适合于表示线状实体和面状实体的范围边界。不像栅格 数据模型那样要求记录和存储每个网格值，矢量数据模型只需要选取和记录反 映地理实体分佰形状特征的点。例如，一个呈正方形的面状实体只需要记录四 个角点，一条呈曲线的线状实体在弯曲处以较多的点表示，在较直的地方以较 少的点表示。地理实体形状特征愈复杂，所需、庀录的点就愈多。在使用矢量数 据模型时，点的选取以及点的属灵是影响地理实体描述精度、数据获取的时间 以及数据量大小的一个重要因素。对于某一线状或面状实体，选取的点太少， 就会歪曲他的形状特征，降低集合量测的精度；选取的点太多，会不必要地增 加数据获取所需的时间以及数据量。 3 两种数据结构模型的比较 表2 - 2 矢量数据结构与栅格数据结构的比较 l矢量数据结构栅格数据结构 数据存储量小数据存储量大 i 空间位置精度高空间位置精度低 用网络连接法能完整描述拓扑关系难于建立网络连接关系 输出简单容易，绘图细腻、精确、美观输出速度快，但绘图粗糙，不美观 可对图形及其属性进行检索、更新和综合便于面状数据处理 数据结构复杂数据结构简单 获取数据慢可快速获取大量数据 数学模拟困难数学模拟方便 多种地图叠合分析困难多种地图叠合分析方便 不能直接处理数字图像信息能直接处理数字图像信息 空间分析不容易实现空间分析易于进行 边界复杂和模糊的事物难以描述容易描述边界复杂和模糊的事物 数据输出的费用较高技术开发费用低 武汉理i ：人学硕十学位论文 2 2 2 地理信息系统的数据库管理 目前有四种基本的g i s 数据库管理解决方案：文件型、 d b m s 型和空间数据库型。根据所采用的数据库管理方法， 种类型i ”。如图2 3 ： ( 1 ) 文件型g i s 这种方法比较简单，也是最初的g i s 软件采用的方法， 据库管理系统，适合于小规模的g i s 。 ( 2 ) 双数据库型g i s 双数据库型、扩充 又可将g i s 分成四 没有集中控制的数 这种方法是利用一般的d b m s ( 多数是关系型的) 管理属性数据，专门的软 件管理空间数据，它们之间通过一定的操作相联接。用户既可以和两个数据库 分别打交道，也可以通过某种途径同时访问两个数据库，