（计算机应用技术专业论文）组件式gis交通路网分析系统的研究与开发.pdf

浙江工业大学硕士学位论文 组件式g i s 交通路网分析系统的研究与开发 摘 随着社会经济的飞速发展，各个地区的交流与合作越来越密切，单纯依靠增加公路里 程已不能解决日益严重的交通问题，人们开始探索基于先进科学技术管理道路交通的新方 法。基于g i s 的交通路网分析系统具有强大的图形显示及空间分析功能，可以有效解决交 通信息获取、存储、管理、分析等问题，对交通管理具有指导作用。 在查阅国内外相关文献的基础上，论文针对原始路网数据的拓扑完整性和一致性问 题，采用拓扑纠正和拓扑判定的方法进行解决；针对传统路径优化算法在海量数据处理中 所面临的时间复杂性问题，提出d i i k 咖算法和a 宰算法在实际路网分析中的实用方法，并 通过杭州市基础路网数据来验证该方法的有效性与可行性；结合当前流行的组件式g i s 开 发技术，设计并实现了基于m a p o b j e c t s 组件的城市交通路网分析系统。本文主要工作和成 果如下： 1 阐述了课题的研究背景、意义以及国内外研究现状，提出课题的研究内容。 2 针对实际路网的特点，归纳并总结空间网络分析的主要内容和网络图的基本理论知 识，为路网数据预处理和路网分析提供理论基础。 3 针对原始路网数据的拓扑完整性问题，分析和研究城市路网数据的结构特点，利用 a r c g i s 软件对其进行拓扑纠正；针对s h a p e f i l e 文件不能存储拓扑关系的问题，设计并实 现路网拓扑判定的方法，为路网分析提供数据基础。 4 针对传统最短路径算法在海量数据处理中的时间复杂度问题，研究d i j k s t r a 算法和 a 水算法的实用方法，给出关键问题的实现流程，并对应用该方法后的实验数据进行分析比 较，得出一些有益结论。 5 设计并开发了基于组件式g i s 的城市交通路网分析系统。该系统具有路径分析、路 障设置、空间量算、信息查询等多种功能，并且提供了良好的用户操作界面。 6 最后对本文研究内容进行总结，并提出系统存在的问题和进一步研究方向。 关键词：组件式g i s ，空间分析，最短路径算法，路网分析 浙江工业大学硕士学位论文 r e s e a r c ha n dd e v e l o p m e n to f u r b a nt r a n s p o r t a t i o nn e t w o r k a n a l y s i ss y s t e m sb a s e do nc o m g i s a b s t r a c t w i t ht h er a p i ds o c i 小e c o n o m i cd e v e l o p m e m ，t h ee x c h a n g e sa i l dc o o p e r a t i o no f 蠢la r e a s b e c o m em o r e 锄dm o r ec l o s e l y t h e 刚i n gt r a 币cp r o b l e m sc 锄n o tb e e ns 0 1 v e db yt h e i n c r e a s eo ft h eh i g h w a ym i l e a g e s ，a n dp e o p l eb e g i nt oe x p l o r et h en e wm e t h o d so ft r a n s p o r t a t i o n m a n a g e m e n tb a s e do 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 g i s _ b a s e dt r a n s p o r t a t i o nn e t w o r k a n a 】y s i ss y s t e m 、i t hp o w e 如lg r a p l l i c sa n ds p a t i a la n a l y s i s 如n c t i o n sc a nr e s o l v et h ep r o b l e m s o ft r a m ci n f o m a t i o ne 行e 砸v e l y ，s u c ha st r a j l s p o r t 撕o nd a t aq u e 吼s t o r a g e ，m a n a g e m e n t ， a n a l y s i sa n ds o0 n ，w h i c hc a ng u i d et h et r a 硒c o nt h eb a s i so fs t u d y i n gt h el i t e r a t u r ea th o m ea n da b r o a d ，t l l i sp a p e ru s e st h em e t h o d s0 f t o p o l o 鲥c o r r e c t i n ga n dt o p o l o g yj u d 舀n gt 0r e s o l v et h et o p o l o g yi n t e 鲥够a n dc o n s i s t e n c y p r o b l e m so ft h eo r i 百n a lf e a t u r ec l a s sd a t a f o rt h et i m ec o m p l e x i 够o ft l l et r a d i t i o n a jp a t h a 】g 嘶t h m si nt l l em a s s i v ed a t ap r o c e s s i n g ，s o m ep r a c t i c a la p p r o a c h e si nm ea c t u a ln e t w o r k a j l a j y s i sa u r ep r o p o s e do nd i j k s t r aa l l g o r i t l ma n da 宰a l g o t h m ，w h i c ha r ev a l i d a t e db yu s i n gt l l e n e 铆o r k ( 1 a t a0 fh a n g z h o u a c c o r d i n gt 0m ec u r r e n t l yp o p u l a u rt e c h n o l o 斟o fc o m g i s ，a 仃a n s p 嘣a t i o nn e m o r ka n a l y s i ss y s t e mi sd e s i g i l e da n di m p l e m e n t e db a s e do nm a p o b j e c t s c o m p o n e n t s t h em a i nw o r k 锄dc o n t r i b u t i o n0 f t i l ep a p e ra r ea sf o l l o w s ： f i r s t l y ，t h er e s e a r c hb a c k 鲈0 u n da n dt 1 1 er e s e a r c hs i t u a t i o n0 fr e l a t e ds u b je c t sa u r ed e s c r i b e d ， a n dt h e nt h em a i nc o n t e n t so fr e s e a r c ha r ep r e s e n t e d s e c o n d l y ，t h eb a s i ct l l e o e so fs p a t i a ln e t w o r ka n a j y s i sa n dg r a p ha r ei n 仃o d u c e df o r 仇e c h a r a c t e r i s t i c so fa c t u a ln e t w o r k ，w h i c hp r o v i d et h et t l e o r e t i c a jb a s i sf o rd a t ap r e p r o c e s s i n ga 1 1 d n 鲍v o r ka n a j y s i s t h i r d l y ，f o r t l l e t o p 0 1 0 9 yi n t e g r i 够 i s s u e so fo 百n a ln e t w o r k d a t a ，廿l e s t m c t u r a l c h a r a c t e r is t i c so fu r b a nn e 觚o r kd a t aa r es t u d i e da n da n a l y z e d ，a n dt h ea j c g i ss o f t w a r ei su s e d t oc o r r e c tt h et o p o l o g y s i n c et h es h a p e f i l es t o r a g es c h e m ac a n tc o n t a i nt 1 1 et o p o l o g ys t m c t u r e ， t h em e t h o d so ft o p o l o g yj u d g i n ga r ed e s i g n e da n dr e a l i z e d ，w h i c hp r o v i d et h ed a t ab a s i sf o r n e t w o r ka n a l y s is f 0 u n h l y ，f o rt h e1 0 we m c i e n c yo ft r a d i t i o n a lp a t ha l g o t h m si nt h em a s s i v ed a t ap r o c e s s i n g ， 浙江工业大学硕士学位论文 t h ep r a c t i c a ja p p r o a c h e si nt h ea c t l j mn e t 、o r ka 1 1 a l y s i sa r es t u d i e d0 nd i j k s t r aa j g 嘶t l l ma n da 宰 a l g o t h m ，a n dt h ec m c i a lp r o b l e m sa r er e s o l v e d ，w h i c ha r eu s e dt oa n a l y z et h ed a t aa n dm a l ( e s o m eu s e f u lc o n c l u s i o n s f i r l l l y ，a nu r b a l l 仃a n s p o r t a 矗o nn e 佃o r k 锄a l y s i ss y s t e mi sd e v e l 叩e di nv c + + 6 ob a s e do n c 0 m g i s ，w h i c hp r o v i d e sau s e r 铺e n d l yi n t e a c ea n ds e v e r a ls p 撕a 1a n a l y s i sm n 甜o n s ，s u c ha s p a t h 柚a l y s i s ，b a 币e rs e t ，s p 撕a lm e a s u r e ，i n f o 肌a t i o nq u e 叮a n ds oo n f i n a l l y ，t h er e s e a r c hw o r ki nt h i sp a p e ri sb r i e f l ys u m m 撕z e da n ds o m er e m a r k so nf u n h e r i m p r 0 e m e n to ft h es y s t e ma r ea l s op r e s e n t e d k e yw o r d s ： c o m 百s ，s p a t i 础a n a 】y s i s ，t h es h o r t e s tp a t ha l g o t h m ，n 印v o r ka n a l y s i s 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名：彳骁撇日期：如g 年明叫日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密吐 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 倪红孑趸 钐易 日期：厶。陴乙月乙f 日 日期谬年心月纠日 浙江工业大学硕士学位论文 1 1 课题研究背景及意义 第l 章绪论 随着社会经济的飞速发展，各个地区的交流与合作越来越密切，随之而来的是各种车 辆的呈几何级数级增长和高速公路的里程不断增加。我国近年来每年都投资数千个亿的资 金用于各种道路建设和车辆管理，但是仍然远远不能满足人们和各种商业车辆的出行需 求，困扰当今交通系统的三大难题( 交通安全、交通堵塞、环境污染) 仍然相当严重。近 年来人们已逐渐认识到单纯依靠增加公路里程不可能从根本上解决人们日益增加的出行 需求，还必须通过计算机、信息和通讯等高科技手段的辅助，充分利用现有的道路设施和 道路信息，对人们和商用车辆提供合理的出行参考和交通引导，对交通事故提供合理的专 家援助等。在这种形势下，基于g i s 技术的交通路网分析系统应运而生，它的作用和意义 在于： ， -， ( 1 ) 采用g i s 先进的数据采集手段和数据库存储技术来解决交通信息在获取、存储、管 理、分析等过程中的问题，通过对交通路网进行各种空间分析，如起始点和终点的最优路 径选择、资源配备点的分布等，提取有价值的信息，指导交通有序运行。 ( 2 ) 把地理位置和相关属性有机结合起来，根据实际需要准确真实、图文并茂地输出 给用户，满足城市建设、道路规划、企业管理、居民生活等对空间信息的要求，借助其独 有的路网分析功能和可视化表达，进行各种辅助决策，有效缓解交通压力。 ( 3 ) 利用生动形象地图形界面将有关道路的路况、交通流量、沿线环境等空间和属性 信息显示出来，使管理者对道路信息一目了然，并提供了多种类型的查询方式，如交通站 点、沿路环境、居民分布情况、路面质量、等级等属性方面的信息，还可以根据系统所具 有的空间关系进行几何空间上的拓扑查询，为人们提供合理的出行参考。 因此，在交通问题日益严重的形势下，研究与开发交通路网分析系统具有重大而现实 的意义。 1 2 课题研究现状 1 2 1 g i s 应用现状 1 9 6 3 年，加拿大测量学家r f t o m l i n s o n 首先提出了g i s 这一概念，并建成世界上第一 1 浙江工业大学硕士学位论文 个g i s ( 加拿大地理信息系统) ，用于自然资源的管理和规划f ”。7 0 年代以后，随着电子技 、一，、 术和计算机技术的迅速发展，使得空间数据地录入、存储、检索和输出功能不断增强，g i s 由理论雏形向实用性的应用系统进行发展，一些发达国家先后建立了许多不同规模、不同 专题、不同类型的土地信息系统和地理信息系统。8 0 年代g i s 的数据处理同数据模型、模 拟等决策相结合，使其应用领域不断增加。9 0 年代以后，g i s 已成为许多机构必备的工作 系统，尤其是一些政府决策部门，由于受地理信息系统影响而在一定程度上改变了现有机 构的运行方式、设置与工作计划等【2 1 。社会对地理信息系统认识普遍提高，需求大幅度增 加，从而导致地理信息系统应用的扩大与深化。 近年来，国内外对于g i s 研究主要体现在传统g i s 的功能扩展、数据问题、g i s 集成技 术研究三方面。传统的g i s 只能提供有限的空间分析功能，缺乏解决专业问题的模块，无 法实现优化选择、现实模拟、决策分析等功能，在应用上有很大的限制。n i i k a m p 和s c h 0 1 e n 在1 9 9 3 年提出可以将有关的空间分析模块植入g i s 中，用于解决城市与区域规划问题，使 g i s 在功能上得到扩展【3 】。在g i s 应用中，数据的采集与整理的时间占整个开发过程的8 0 。 在解决如何将空间属性信息加入g i s 的问题上，y a a k u p 和h e a l e y 在1 9 9 4 年提出g i s 应用很大 程度上取决于适当的数据获取与合理的数据组织1 4 1 。d m m m o n d 在1 9 9 5 年提出了地址匹配 ( a d d r e s sm a t c h i n g ) 的方法，可以方便地把调查访问的社会经济数据录入g i s 中使用嘲。随着 g i s 的发展，数据交换与数据共享的技术越来越成熟，这将吸引更多的注意力。在交通领 域，地理信息系统( g i s ) 、全球定位系统( g p s ) 、智能运输系统( i t s ) 是交通规划、管理与控 制的前沿技术。将三者有效地集成起来，能够大大提高交通的现代化和智能化程度。寻求 这些技术之间的合适切入点，包括三者的发展方向、集成方法与集成模式、空间数据标准 等都是当前的研究热剧6 1 。 在g i s 的具体应用方面，发达国家在城市规划、交通设施、公共服务、动态监测、抗 震救灾等方面都广泛应用g i s 进行科学决策【兀。美国首都华盛顿特区启用3 4 个地理信息子系 统进行城市动态管理，定时发布交通状况信息，导向车辆运行，纽约、佛罗里达州等也都 建立了公路网交通管理地理信息系统。美国弗吉尼亚州f a i 概县政府的g i s 系统，它包括 地理编码、自然地理信息、道路、入口分布、管线、规划分区、土地利用等7 5 层信息，实 际地理精度达到2 英尺，涉及到交通、规划、环境、统计等近2 0 个部门，g i s 规划与管理是 该系统的重要组成部分。加拿大c p p e nc o n s u l t a n t st h er e i dc o l l i n sa n da s s o c i a t e s 公司采用 g i s 完成了温哥华岛的一条长一百二十七公里公路的选择与初步设计工作。g i s 在该项目中 占有重要地位，主要解决信息管理、分析及提供决策依据。1 9 9 4 年洛杉矾大地震时，美国 浙江工业大学硕士学位论文 政府部门利用g i s 技术把各类图层数据进行叠加分析得出对应急有价值的信息，使有关机 构可以对地震灾害作出快速响应，最大程度地减少伤亡和损失，进行灾后应急响应决策支 持。 我国g i s 方面的工作从2 0 世纪8 0 年代初开始，以1 9 8 0 年中国科学院遥感应用研究所成 立的全国第一个地理信息系统研究室为标志。在几年的起步发展阶段中，我国在g i s 理论 探索、硬件配制、软件研制、规范制定、区域试验研究、局部系统建立、初步应用试验和 技术队伍培养等方面都取得了进步。9 0 年代后，随着计算机技术的迅速发展，国民经济建 设和城市化进程加快，全国各地抛起了一股g i s 研究热潮【8 】。在城市信息的查询、政府职能 部门的办公自动化、土地规划或房产管理的计算机化、乃至部分城市问题的分析与科学决 策，以及某些数据和信息的更新等方面，都不同程度地利用了g i s 这一关键技术，并产生 了非常明显的社会效益和经济效益。在交通管理方面，采用g i s 技术成功开发了宏观交通 管理信息系统、运营管理信息系统及更高层次的交通信息系统，如广东省综合交通管理地 理信息系统、四川省公路地理信息系统、陕西省公路地理信息系统、国道主千线管理信息 系统等。这些应用型g i s 大多是在商业g i s 平台软件的基础上二次开发出来的，系统比较稳 定、更新维护比较容易i9 1 。目前我国g i s 应用范围涉及国防、公安、金融、农业、林业、水 土资源、交通、城市规划、环境管理等各个部门。从目前的应用情况看，存在着巨大的发 展潜力，对g i s 的需求还将不断增加，发展前景十分广洲1 0 】。 虽然g i s 的应用已经取得了较大的进展，但还远远没有充分发挥g i s 的强大功能以解决 实际的规划、管理问题。g i s 自身的一些局限性，如专业模块有限、数据采集与录入的繁 琐、缺乏良好的用户界面、投资大、见效时间长等，在一定程度上制约了g i s 的发展。由 此可见，g i s 的应用研究任重道远。 1 2 2 最优路径算法研究现状 目前矢量地图最优路径问题的研究主要有以下几方面： 1 以d i i k s t r a 算法为基础对其进行优化，这是目前的研究热点。按其主要思想又可以分 为两类：( 1 ) 通过减少搜索的节点数和搜索空间来提高算法的执行效率。如文献 1 1 通过提 取网络中的关键结点组成个新图，然后将起点和终点插入到新图中，经过最多四次的排 列组合后选出最短路径，这种方法可以将网络结点力降到一个很小的值。文献【1 2 】详细说明 了基于d i j k s t r a 的邻接结点算法，该算法改进通过降低d 算法关联矩阵实现中0 ( 及) 的冗 余来实现，文献【1 3 提出的低值扩散算法是采用求两结点间最小深度的方法进行最短路径 浙江工业大学硕士学位论文 搜索，在运算时间上有很大提高，但是计算结果与实际情况有一些偏差。文献【1 4 】以十字 链表结构记录顶点和边，采用顶点分区和记录绝对地址的方法对算法进行优化。( 2 ) 通过优 化算法优先级队列的实现来提高算法的执行效率，改进传统的优先级队列的数组实现。如 文献【1 5 】在d u k s 舰算法基础上采用二叉堆结构来实现路径计算过程中优先级队列的一系列 操作，从而提高算法的分析效率。文献【1 6 】将所有弧的权值先转化为整数，所有的临时标 记结点通过使用一组b u c k e t s 数据结构来维护优先队列，但是当一个结点的权值和状态发生 变化时，需要改变它在b u c k e t s 序列中的位置，这样在数据调整上带来了额外开销。文献【1 7 采用快速排序和插入排序相结合的方式，并使用地址排序的方法，改进原有最短路径算法 中对最小权值顶点的搜索策略。文献【1 8 提出优先队列结构中堆的构建工作是比较复杂的 过程，对d i j 1 ( s t r a 算法中的优先队列结构堆作一些简单而有效的处理，使算法运算效率有了 比较大的提高。文献【1 9 】和文献【2 0 】中提出一种称之为直线优化的d 算法，具体思想是指在 应用d 算法的过程中，将临时标记结点到源点的最短路径与该结点到目标结点的直线距离 之和作为此临时标记结点的一个属性值，在搜索过程中总是选取属性值最小的临时结点作 为永久标记结点，此算法基本思想跟a 宰算法类似。文献【2 1 以启发式搜索思想为基础，在 d i i k s 仃a 算法中建立一个c o s t 函数，用以评价下一搜索结点的花费，选取花费最小的结点进 行搜索，以这种方式来提高算法效率。 2 对网络进行划分的思想。如文献【2 2 】提出了新的层次空间推理过程，为最短路径求 解寻找更为可靠的入口。文献 2 3 】基于分层网络拓扑结构( h i t o p o ) 提出了双向分层搜索 最优路径算法( b h w a ) ，该算法以分级网络的局部连通性作为划分子图的指标，在路径 计算过程中采取双向搜索策略。文献 2 4 】在网络划分子图的基础上，使最短路径算法在以 子图抽象的一个高层图上进行，缩小了查找范围。文献【2 5 】将网络图的源顶点和终点连接 起来做成直线，选取合适的m 值，依据以上划分方法把网络图划分为m 个子图，然后分别 对每个子图采用d i i k s t r a 算法，最后将子图的顶点连接起来，形成近似最优路径。这些算法 的显著优点是：( 1 ) 路径的分等级搜索，更加符合交通工具出行的实际情况。( 2 ) 子图中需要 搜索的节点数减少，总的算法效率得到了提高。但也存在明显的缺点：这些算法不能确保 得到的路径一定是最优的，是一种有损算法，因为从局部最优的和不能推出全局最优，但 是通过分析和比较的方法，保证了一个次最优或者近似最优的结果。 3 智能算法在最优路径搜索中的应用。如文献 2 6 】从数据结构方面入手，引入最小化 堆的方法遍历开启列表，引入链表对结点数据结构进行改进等手段给出a 宰算法的优化方 案。文献【2 7 】采用变长度整数编码的染色体表示路径，设计了适合于最优路径问题求解的 浙江工业大学硕士学位论文 遗传算子，给出了适应度调整函数，使最优路径算法的执行效率较高。文献 2 8 】使用a 宰算 法实现最优路径搜索，并且为保证一定是最优路径对算法进行如下优化：当使用a 木算法找 到一条“最优路径 后，立即从目标点回溯树。在回溯过程中将所找到的最优路径与其他 路径进行比较，且保留较短路径，当回溯到树根时则可保证找到最优路径。文献【2 9 】将动 态的最优路径算法按时问离散化为对一个时间序列的静态最优路径算法的研究。文献 3 0 】 和文献 31 】提出一种基于车辆识别和车辆诱导系统的动态源目的( o - d ) 评估方法，该方法 基于交通流状态预测的思想，可以从点对点关系中提取有价值的信息。文献 3 2 】在动态交 通网络中采用人工神经网络( a n n ) 来评价o - d 路径搜索时间，具体方法是用三种前授型 神经网络来模拟一天中不同时间段的运输时间行为，并对该a n n 模型和传统统计模型进行 研究和比较，验证该算法在动态最短路径分析中的效率。文献【3 3 】介绍了模糊神经网络 ( n 烈) ，并在此基础上提出了一种新的基于孙烈的平行算法用于路径诱导，通过一个子 搜索过程和参数优化的方法改进算法效率。文献【3 4 】用退火蚁群算法对最短路径问题进行 研究，针对最短路径的具体问题，构造了集中式模型和分布式模型两种全局优化的退火算 法。文献【3 5 】介绍了种基于最优路径分析的特殊遗传算法，该算法采用编码、交叉转变 等方式进行路径查找，这是一种在应用g i s 和i t s 中解决最短路径问题的新途径。文献【3 6 提出一种平行混合的启发式算法，将混合方式中的v n d 和s s 平行应用到主仆结构中，由仆 人通过适应性存储器处理通信。以上这些算法虽然在不同程度上提高了执行效率，但是利 用智能算法解决路径规划这类问题的难点在于合理模型的构建，这是一个比较复杂的过 程。 综上所述，国内外对最短路径算法的研究很多，但主要停留在理论意义上，在实际应 用中仍然存在一些问题，比如不能求得最优解或者效率有待提高，这些问题需要根据实际 情况对算法进行合理优化和改进。因此，对最短路径算法在实际应用方面的研究还有很多 内容可以探索。 1 3 课题研究内容 针对当今交通系统面临的问题，本文运用空间网络分析理论和g i s 先进技术，设计并 开发了城市交通路网分析系统，该系统对现有的道路交通信息进行综合分析，为人们和商 用车辆出行提供合理的参考依据，为交通管理和城市规划提供有价值的辅助决策意见。 本课题的研究内容主要包括以下几个方面： ( 1 ) 对g i s 应用现状和最优路径算法研究现状进行分析总结，提出当前g l s 应用在交 浙江工业大学硕士学位论文 通领域中存在的问题和最优路径算法在实际应用中的缺陷； ( 2 ) 根据实际路网分析的需要，对空间网络分析基础理论进行归纳和总结； ( 3 ) 研究解决原始路网数据完整性一致性问题的方法和解决路网数据拓扑判定问题的 方法； ( 4 ) 研究最短路径算法中的d i j k s 昀算法和a 宰算法，提出这些算法在实际路网分析中 的应用方法和实现流程； ( 5 ) 应用组件式g i s 技术设计并开发具有多种分析功能的交通路网分析系统，为交通 管理和城市规划提供有价值的参考意见。 1 4 论文组织结构 本文共六章，每章的具体内容安排如下： 第一章绪论。主要介绍了课题的研究背景及意义、g i s 应用现状和国内外对最优路径 算法的研究现状，然后对课题研究内容和论文组织结构进行阐述。 第二章空间网络分析基础。首先由g i s 的基本概念引出空间网络分析；然后对空间网 络分析的主要内容( 路径分析、地址匹配和资源分配) 进行简单介绍，并指出网络分析的 基础是非线性数据结构图；最后结合路网特点对网络图相关理论( 分类和表示方法) 进行 归纳和总结。 第三章路网数据预处理。首先介绍了城市路网数据的结构特点与存储方式；然后针对 原始路网数据拓扑完整性问题，采用心c g i s 软件对其进行拓扑纠正；最后针对s h a p e f i l e 文 件不能存储拓扑关系的问题，给出路网拓扑判定的部分方法和实现。 第四章最短路径算法实现。首先介绍了d i i k s 仃a 算法和a 木算法的基本原理，并从时间上 和空间上对算法效率进行评价；然后针对实际应用时需要考虑的因素，提出算法在海量数 据处理中的实用方法；接着对算法应用中遇到的一些关键问题给出实现流程；最后根据算 法的实验结果分析和比较d i i k s t r a 算法和a 宰算法优劣，验证该方法的有效性与可行性。 第五章系统的设计及实现。首先介绍了系统的实现目标、开发模式和总体设计；然后 给出数据访问( 连接、读写和显示) 实现的方法；接着对系统的主要功能使用及显示效果 进行演示；最后对本系统的功能特点进行归纳总结。 第六章结论与展望。对本文的研究工作进行总结，指出所做工作中存在的一些不足之 处，并对今后的研究方向进行展望。 浙江工业大学硕士学位论文 第2 章空间网络分析基础 地理信息系统( g e o g r a p h i c a li n f o 姗a t i o ns y s t e m ，简称g i s ) 是采集、存储、管理、描 述、分析地球表面及空间和地理分布有关的数据的信息系统。它是以地理空间数据库为基 础，在计算机软硬件环境的支持下，对空间相关数据进行采集、管理、操作、分析、模拟 和显示，并采用地理模型分析方法，适时提供多种空间和动态地理信息，为地理研究、综 合评价、管理、定量分析和决策服务而建立起来的一类计算机应用系统。简而言之，地理 信息系统是以计算机为工具，具有地理图形和空间定位功能的空间型数据管理系统，它是 一种特殊而又十分重要的信息系统【3 7 】。 空间分析是g i s 的重要功能，也是区别于一般信息系统的关键特征。空间分析是通过 对空间数据的深加工和分析而获取新的信息。g i s 的空间分析能力，是评价系统性能的主 要指标之一。空间分析方法可分为两种类型：一类是产生式分析，主要有空间数据量算分 析、空间叠合分析、缓冲区分析和空间网络分析；另一类是咨询式分析，主要指空间集合 分析和空间查询分析【3 8 1 。 2 1 空间网络分析 空间网络分析是空间分析的重要内容，它主要包括路径分析、地址匹配和资源分配。 网络分析的主要用途是：寻找最佳路径和选择最佳布局中心的位置。 ( 1 ) 路径分析 路径分析主要解决的是最短路径问题。它包括：分析网络中的两结点间是否有路径存 在，或者从一个结点出发到其他各结点之间的最短路径，或者是每对结点之间的最短路径 进行分析和求解。图2 1 是对确定经过结点的最短路径分析。如果对路段赋上权值，最短 路径问题转化为最佳路径问题。两地之间的最短路径不一定是最佳路径，道路拥挤、路面 质量等因素会对其产生很大的影响【3 9 1 。 路径分析是空间网络分析的重要组成部分，在交通运输、信息传输、消防救灾等应用 领域中具有特殊意义。如何快速地选择运输费用最低、时间最短的路线，是解决交通问题 的一个重要方面。 浙江工业大学硕士学位论文 国2 1 列点间最佳j ! 各径不意图 ( 2 ) 地址匹配 地址匹配实质是对地理位置的查询，它涉及到地址的编码。地址匹配与其它网络分析 功能结合起来可以满足实际工作中非常复杂的分析要求。所需输入的数据，包括地址表 和含地址范围的街道网络驶待查询地址的属性值。 ( 3 1 资源分配 资源分配网络模型由中心点( 分配中心) 及其状态_ 性和网络组成。资源分配有两种 方式，一种是由分配中心向四周输出，另一种是由四周向中心集中。这种分配功能可以解 决资源的有效流动和合理分配，其在地理网络中的应用与区位论中的中心地理论类似。在 资源分配模型中研究区可以是机能区，根据网络流的阻力等来研究中心的吸引区，为网 络中的每一链接寻找最近的中心，以实现最佳的服务0 4 ”。 资源分配模型可用来计算巾心地的等时区、等交通距离r 、等费用距离区等：可用来 进行商业中心、城镇中心或港门等地的吸引范围分析以亩找【夏域中蛙近的商业中心、进 行各种区划和港口腹地的模拟等。 2 2 网络图分类 叫络分析的娃仙是非线性数j l j ：结构瞄i ，路l 叫数抑：n 计算机中粟川削的表币方式对文 巾；蔷理沙戍刮罔作。简蟹介 “_ 手| | 总结 浙江工业大学硕士学位论文 ( 1 ) 有向图和无向图 图是由一些结点和连接结点的边组成的。有向图是指每一条边都是有方向的，反之则 是无向图。混合图是指图中一些边是有向边，一些边是无向边。 实际路网大多数是混合图，因为一些城市中为减轻交通流量，往往在一些路段设置单 向航道，车辆只能沿着单方向行驶，而在一些交通流量较小的地方，车辆则可以双向行驶。 但是由于我们得到的地理数据中不包含路段航向属性，这里将路网定义为无向图，即各路 段间可以双向行驶。而且地理数据中也不存在正向路阻和反向路阻的属性值，我们只能以 路段长度来代替路段的正向和反向路阻。 0 图2 2 多重图 0 图2 3 简单图 图2 4 带环和平行边的路网 庄 ( 2 ) 多重图 在实际路网中，有些结点对之间往往有两条以上的边，称这些边为平行边。如图2 2 所示，多重图是指含有平行边的图。关联于同一结点的一条边称为环或自回路，路网数据 中经常出现两结点间有两条路段相连的情况，还有从当前结点出发，又回到当前结点的路 浙江工业大学硕士学位论文 段，这些情况都是在构建算法关联矩阵时要进行处理的。 ( 3 ) 简单图 如图2 3 所示，简单图中不含有平行边和环。在最短路径算法中，关联矩阵对应的路 网是简单图，因此必须经过计算将平等边和环去除。实际路网中带环和平行边的情况如图 2 - 4 所示。 2 3 路网表示方法 当前表示路网的主要方法有：关联矩阵表示和邻接目录表示【4 3 1 。 ( 1 ) 关联矩阵的表示方法： 图的结点对应路网中的结点，图的边对应路网中的路段。如果将路网中的刀个结点都 标号( 芦o ，1 ，2 ，刀1 ) ，构建一个玎维矩阵肋纺【川咖】，矩阵的行号和列号与结点标号对应， 如果结点f 和结点歹之间存在路段相连( f 歹) ，那么砌砌【f 们= 路段长度；如果结点f 和结 点_ ，之间不存在路段相连( ，歹) ，那么砌历【司阴= o 。我们将p 砒矩阵称为这个路网的关联 矩阵，对应于简单图2 3 的关联矩阵如下： o6 60 o9 81 2 o8 91 2 oo 00 关联矩阵对多重图的处理方法：在多重图中存在平行边和环，选取平行边中长度最短 的边存入关联矩阵。在最短路径计算中，环是没有意义的。因为自身点的最短路程就是0 ， 不需要绕个弯再回到原地。因此，将关联矩阵中只口嘶f 】f 7 赋值为o 。从上面的描述可以看 出，其实每个多重图都对应为一个简单图，而关联矩阵的赋值实际上可以简单图作参考。 ( 2 ) 邻接目录表的表示方法： 利用一个数组和一个矩阵表示网络的邻接关系，一维数组尺【力表示与f 结点相连接的 边的条数，邻接矩阵h 订阴表示与f 结点相邻接的第个结点的结点号。如表2 1 是邻接目 录表的表示方法，表中的值对应于图2 3 。 由于城市路网属于一种大型稀疏网络，因此可以采用邻接目录表的形式存储网络结 构，这样在最短路径算法过程中既能节省存储空间，又能快速方便地进行几何信息处理。 但是，邻接目录表没有赋带边的权值，必须另外构建一个对应于邻接矩阵坎，) 的距离矩阵 以，记录研司阴= 边 的长度。而且在构建邻接目录表之前，必须对整个图搜索， 找出每个结点的邻接边和邻接结点，需要花费一定的时间。另外，邻接目录表同样需要对 1 0 浙江工业大学硕士学位论文 平行边和环作处理。因此，可以先将路网转化为关联矩阵，再将关联矩阵转化为邻接目录 表形式，这样可以充分发挥两者的优势，总体上提高算法的效率。 表2 1 邻接目录表方法 结点f 月【司妇阴目妇们 0 2 l ，36 ，8 l3 o ，2 ，36 ，9 ，1 2 2l19 32 0 ，18 ，1 2 2 4 本章小结 本章首先对空间网络分析的主要内容进行了简单介绍，指出空间网络分析的基础是非 线性数据结构图，进而在结合实际路网数据特点的基础上分析和讲解相关的图论知识，包 括网络图的三种类型和主要的两种表示方法，这些内容为路网数据的预处理和路网分析提 供了理论基础。 浙江工业大学硕士学位论文 3 1 城市路网的特点 第3 章路网数据预处理 路网数据是路网分析的基础，为了能快速、有效、准确地在地图上显示并处理路网信 息，就需要对路网数据的结构特点进行分析和研究，实际的城市道路网自身的特点表现在 如下的几个方面： ( 1 ) 结点数巨大，例如杭州市的路网数据图层的道路结点有6 0 0 0 个左右。 ( 2 ) 城市路网对应的网络图是不完全的，不规范的，其结点的度数不尽相同，度数通 常比较小。 ( 3 ) 可以将城市路网看成平面网络，这种网络中的结点和其周围的路段存在连接关系。 ( 4 ) 如果考虑到时间的因素，路段的权值会随着时间的变化而变化。 3 2 路网数据的存储 3 2 1 路网的描述 图3 1 路段、结点和形状点 路网描述的特点：作为一种特殊的网络，除了遵从一般的网络表示方法和存储结构外， 必然还有其特殊性，符合需要的路网表达方法和存储结构应满足以下要求：1 ) 存储量小； 1 2 浙江工业大学硕士学位论文 2 ) 充分考虑路网的特殊性一大型稀疏网络；3 ) 能够表达路网要素及拓扑结构。 在最短路径分析中必须将地理形式的路网数据表示成数学形式。数学形式上一般使用 线段表示路段，它的结点类型按路段结点来定义，有时外加相对高度。路网数据中对结点、 路段和形状点的定义： ( 1 ) 结点是通常是一条街道或道路的交叉点或端点，也可能是度数为2 的点，它是路网 数据中最小单位路段的端点，在图3 1 中用橙色小圆点标出。 ( 2 ) 路段是两结点间的一段道路，在图3 1 中用绿色线条标出。 ( 3 ) 形状点是处于两最小单位路段之间的点的有序集，主要用于描述路段的形状。 3 2 2 s h a p e f i l e 存储 s h a p e f i l e 文件f 删是e s r j 公司在其g i s 产品中使用的一种主要文件格式，用于存储空间 实体的空间位置数据和属性数据，但不能存储拓扑关系。创建s h a p e f i l e 文件的方法有：使 用a r c i n f o 、s p a t i a ld a t a b a s ee n g i n e 、觚v i e wg i s 等软件将数据源导出为s h a p e 格式；使用 a r c v i e wg i s 的对象创建工具创建s h a p 娟l e 文件；用a v e n u em a p o b j e c t s 、时cm a c r 0 l a n g u a g e ( a m 【，) 在程序中动态创建s h a p 娟l e 文件。 e s r js h a p e f i l e 文件格式将位置信息和属性信息分别存放在一组扩展文件名特定的文件中 ( 这些文件存放在同一目录中) 。这组文件包含一个s h a p e 主文件，一个d b a s e 表格文件和一 个i n d e x 索引文件。三种文件关系如图3 2 所示。 。 固 f 卜1 a r e an 锄e l 影i l 2 0 0 0a r3 0 0 0 b r 爿 4 0 0 0c l s h x 索引文件 s h p 主文件 d b f 属性文件 图3 2 三种文件的关系 一1 3 浙江工业大学硕士学位论文 主文件以s h p 为扩展名，是一个直接存取的记录长度不一的文件。其中每一条记录存 储一个对象的几何信息( 以存储其所有顶点的方式) 。 索引文件以s 1 1 ) 【为扩展名，在索引文件中，每一条记录保存主文件中对应的一条记录 其相对于主文件起始位置的偏移值。 d b a s e 表格文件以d b f 为扩展名，它包含对象的属性信息( 一条记录对应一个对象) ， 属性和对象的联系是基于r e c o r dn u m b e r 的。属性记录在d b a s e 表格文件的存储顺序与其对 应的地理( 位置信息) 记录在主文件中的顺序一致。 当在s h a p e f i l e 文件上执行一个操作时，可能导致一些具有相同文件名的s h a p e f i l e 文件 生成，如执行b u i l d i n d i c e s 将导致g c d 文件的创建，执行b u i l d i n d e x 将创建s b n 和s b x 文件。 这些文件将在s h a p e 文件同一目录下创建，他们并不是必须的，因此可以在复制数据库的时 候忽略他们。但是复制他们可以避免因再次创建而带来的额外的性能开销。总之，应用程 序假定这些文件不存在，而在不