（地图学与地理信息系统专业论文）空间网络分析关键技术研究.pdf

摘要 空间分析是地理信息系统的一个重要特征，空间网络分析是空间分析的重要 组成部分。近些年来随着城市数字化建设的兴起，以及交通、电力等地理网络的 迅速发展，空间网络分析的重要性已越来越突出，对空间网络分析的研究也越来 越深入。然而，由于地理网络的特殊性，网络分析算法的效率难于应用到实践中。 同时，目前网络分析的数据模型也制约空间网络分析的发展，因此，对空间网络 分析算法效率的改进、设计新的空间数据模型和对空间数据进行组织就成为空间 网络分析研究的重要课题。本文旨在通过对空间网络分析的路径算法、空间数据 模型和空间数据组织等几方面问题的研究，从理论和实践进行分析与设计，为以 后的研究提供一些新的思路和见解。本文的主要研究内容包括： 本文系统分析了路径分析的各种数据结构，验证了四叉堆在这些数据结构 中空间复杂度和时间复杂度是最优的。然后，本文引入代价函数来分析路径分析 算法的效率，通过对a + 算法的分析指出启发性函数的选择对算法的效率影响巨 大。针对a t 算法结点重复展开的缺陷，本文设计了一种高效具有启发信息的基 于四叉堆的d i j k s t r a 算法。通过实验对本文的方法进行了验证和分析。 在空间数据模型方面，首先分析了目前常用的三种空间数据模型一矢量数 据模型、镶嵌数据模型和混合数据模型。然后针对目前空间数据模型由于平面强 化造成的影响，本文提出用基于特征的空间数据模型来建立g i s 空间网络模型。 采用面向对象的范例和超图数据模型对交通网络进行基于特征的g i s 建模。 针对城市网络特征的多重表达，分析了多重表达的意义和难点。然后对城 市网络多重表达的方式和表达模型进行了分析，提出了基于超图数据模型的城市 网络特征的多重表达。 智能交通系统的研究在这几年得到很大的发展，随着交通管理智能化的发 展，智能交通系统的应用将会得到更大的发展。本文首先对智能交通系统的意义、 定义和国内外的发展现状进行了归纳，然后对智能交通系统中的重要部分一智能 导航定位系统，从原理、系统框架、导航数据组织和数据索引方法进行了分析， 利用具有启发信息的基于四叉堆的d i j k s t r a 算法，本文设计了导航定位系统三 层s s 逻辑框架。 总结本文的研究工作，主要创新点可概括如下： 结合四叉堆和a 水算法的优势，本文提出一种高效且能避免结点重展的路径 搜索算法，该算法能够很好地应用到智能交通系统中。 提出了一种新的基于特征的空间数据模型，该数据模型能够兼顾空间语义 信息和空间拓扑关系，从而能够很好地应用在时空网络模型中，运用该模型能够 很好地对交通网络进行建模。 焚键词：空间网络分析启发性函数簇于特征的空间数攒模型超蓬数据模 型多重表达 r e s e a r c ho nk e yt e c h n o l o g i e sa b o u t t h es p a t i a ln e t w o r k a n a l y s i s w a n gs h i f e n g ( c a r t o g r a p h ya n dg e o g r a p h i ci n f o r m a t i o ns y s t e m ) d i r e c t e db yp r o f y a n gc h o n g i u n i n s t i t u t eo f r e m o t es e n s i n g a p p l i c a t i o n s , c a s , b e i j i n g ( 1 0 0 1 0 1 ) a b s t r a c t s p a t i a la n a l y s i si sa l li m p o r t a n tc h a r a c t e ro fg e o g r a p h yi n f o r m a t i o ns y s t e m ( g i s ) s p a t i a ln e t w o r ka n a l y s i si sap r o m i n e n tp a r to fs p a t i a la n a l y s i s i nr e c e n ty e a r s ， w i t ht h ec o n s t r u c t i o no fd i g i t a lu r b a n , g e o g r a p h i c a ln e t w o r k ss u c ha st r a n s p o r t a t i o n , p o w e ra n ds oo nh a v eb e e nf a s td e v e l o p e d ，w h i c hh a v em a d et h es p a t i a ln e t w o r k a n a l y s i sm o r ea n dm o r ei m p o r t a n t t h e r e f o r e ，t h er e s e a r c h e st os p a t i a ln e t w o r k a n a l y s i sb e c o m em o r ea n dm o r ed e e p h o w e v e r , o w i n gt ot h es p e c i a lc h a r a c t e r s ，t h e e f f i c i e n c i e so fs p a t i a ln e t w o r ka l g o r i t h ma r en o ta p p l i e dt op r a c t i c e m e a n w h i l e ，t h e c u r r e n ts p a t i a ln e t w o r kd a t am o d e l sa l s oi n f l u e n c et h ed e v e l o p m e n to fs p a t i a ln e t w o r k a n a l y s i s s o ，t h ee f f i c i e n c i e so fs p a t i a ln e t w o r ka n a l y s i sa l g o r i t h m s ，t h en e wr o b u s t s p a t i a ld a t am o d e l sa n dt h es p a t i a ld a t aa r r a n g e m e n t sh a v eb e c a m et h em a i nr e s e a r c h t o p i c s 1 1 l i sp a p e ri n t e n d st op u tf o r w a r dn e wt h o u g h t sa n dm e t h o d so np a t h a l g o r i t h m s o fs p a t i a ln e t w o r k a n a l y s i s ，s p a t i a l d a t am o d e l sa n d s p a t i a l d a t a a r r a n g e m e n t st h r o u g ht h e o r ya n dp r a c t i c e m a i nr e s e a r c hc a nb eg e n e r a l i z e da s f o l l o w s ： 1 1 1 i sp a p e rs y s t e m i c a l l ya n a l y z e sv a r i o u sd a t as t r u c t u r e so f p a t ha l g o r i t h ma n d c o n c l u d e st h a tq u a dh e a ps t r u c t u r ei st h em o s to p t i m i z ed a t as t r u c t u r ei nb o t hs p a c e c o m p l e xa n dt i m ec o m p l e x i no r d e rt od e c r e a s et h et i m ec o m p l e xo fp a t ha l g o r i t h m , t h ep a p e re m p l o y st h ec o s tf u n c t i o nt oa n a l y s i st h ei m p r o v e m e n to fp a t ha l g o r i t h m t h i sp a p e ri n d i c a t e st h a tt h eh e u r i s t i cf u n c t i o nh a sb i ge f f e c to np a t ha l g o r i t h ma f t e r a n a l y z i n gt h ea s t a ra l g o r i t h m a g a i n s tt h es h o r t c o m i n go fas t a ra l g o r i t h mw h i c hi s t h er e o p e no fn o d e s ，t h ep a p e rd e s i g n san e wq u a d h e a p b a s e dd i j k s t r aa l g o r i t h m w h i c hh a sh i g he f f i c i e n c ya n dh e u r i s t i c i n f o r m a t i o n f i n a l l y , e x p e r i m e n t s a r e c o n d u c t e dt op r o v et h ev a l i d i t yo f o u rm e t h o d t h i sp a p e rr e v i e w st h et h r e es p a t i a ld a t am o d e l s v e c t o rm o d e l t e s s e l l a t i o n m o d e la n dh y b r i dm o d e l t h e nt h ep a p e rp r e s e n taf e a t u r e b a s e ds p a t i a ld a t am o d e lt o b u i l dt h eg i s s p a t i a ln e t w o r km o d e l c o n s i d e r i n gt h ee f f e c t so f p l a n a re n f o r c e m e n to f c u r r e n ts p a t i a ld a t am o d e l f i n a l l y , t h ep a p e re m p l o y st h eo b j e c to r i e n t e dp a r a d i g m a n dh y p e r - g r a p ht ob u i l dt h ef e a t u r e b a s e dt r a n s p o r t a t i o nn e t w o r km o d e l ( 勤t h ep a p e ra n a l y z e st h es i g n i f i c a n c ea n dd i f f i c u l t i e so fm u l t i p l er e p r e s e n t a t i o n s i t h e nt h eu r b a nn e t w o r km u l t i p l er e p r e s e n t a t i o nt y p e sa n dm o d e l sa l ed i s c u s s e d 。 f i n a l l y , t h ep a p e rp u t sf o r w a r da na p p r o a c ht h a tt h eu r b a nn e t w o r kf e a t u r e sa r e m u l t i p l er e p r e s e n t e db yh y p e r - g r a p hd a t am o d e l 。 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 ) h a sb e e nr e s e a r c h e df o rm a n yy e a r s a n dw i t ht h ed e v e l o p m e n to f t r a n s p o r t a t i o ni n t e l l i g e n tm a n a g e m e n t ，t h ea p p l i c a t i o no f 疆sw i l lb ee x 鼬堪蕊。碰sp a p e rt r a c k s t h es i g n i f i c a t i o n , t h ed e f i n i t i o na n d d e v e l o p m e n th i s t o r yo f e a c hn a t i o no fi t s t h e n , t h i sp a p e rr e s e a r c h e st h e i n t e l l i g e n c el o c a t i o na n dn a v i g a t i o ns y s t e m ( i l n s ) a tt h ep o i n to ft h ep r i n c i p l e ，t h e s y s t e n la r c h i t e c t u r e ，t h en a v i g a t ed a t ao r g a n i z a t i o na n dt 1 1 ed a t ai n d e xm e t h o d s 豫s p a p e rp r e s e n t st h r e e - d en a v i g a t i o na n dl o c a t i o ns y s t e ma r c h i t e c t u r eo fb sm o d e l u s i n gt h eq u a d h e a p - b a s e dd i j k s t r aa l g o r i t h mw i t hh e u r i s t i ci n f o r m a t i o n t h em a i nc o n t r i b u t i o no f t h i sp a p e rc a l lb ec o n c l u d e da sf o l l o w s ： sp a p e rp r e s e n t san e wa n dh i 曲e f f i c i e n tp a t ha l g o r i t h mw h i c hc o m b i n e s t h ea d v a n t a g e so ft h eq 激d - h e a pa n dt h eas t a ra l g o r i t h ma n da v o i d st h er e o p e no f n o d e s 轴ea l g o r i t h mc a nb ee m p l o y e dt oi 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 ) n e wf e a t u r e - b a s e ds p a t i a ld a t am o d e li sp r e s e n t e da tt h i sp a p e r t h en e w a l g o r i t h mc o n s i d e r st h es p a t i a ls e m a n t i ci n f o r m a t i o n a n dt h es p a t i a lt o p o l o g y r e l a t i o n s h i p 确e n t h en e wf e a t u r e - b a s e ds p a t i a ld a t am o d e li sw e l le m p l o y e dt ot h e t r a n s p o r t a t i o nn e t w o r k k e y w o r d s ：s p a t i a ln e t w o r ka n a l y s i s ；h e u r i s t i cf u n c t i o n ；f e a t u r e b a s e ds p a t i a ld a t a m o d e l ；h y p e r - g r a p hd a t am o d e l ；m u l t i p l er e p r e s e n t a t i o n 中国科学院遥感应用研究所 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不含任何其他个人或集体已经发表或撰写过的作品或成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 声明的法律结果由本人承担。 论文作者签名： 日期：。洲百年 ；王诗锌 f 月别日 第一章绪论 第一章绪论 经过数十年和数代人的努力，人类在空间科学技术、遥感、地理信息系统、全 球定位系统等领域取得了巨大发展。特别是随着全球范围内对地观测系统、国家信 息高速公路、国家空间数据基础设施等重大计划的实施，人类对地球不同层面，不 同现象的综合观测能力以及信息的处理、传输和应用能力达到了空前的水平。据于 此，1 9 9 8 年1 月美国前副总统戈尔在美国加利福尼亚科学中心发表了题为一数字地 球：二十一世纪认识地球的方式“的讲演，首次提出了“数字地球”的概念。数字 地球强调了一个真实三维地理信息的表示和操作。 事实上，人类生活中的8 0 的数据都与空间相关，因此，全球的、国家的信息系 统如果不能提供与地理空间有关的信息，那么这个信息系统一定是不完善的( 徐冠华 1 9 9 9 ) 。目前我们正处在一个信息化社会，应用信息流技术去调控人流、物流和能量 流，使之朝着期望的状态和方式发展。实现动态平衡和持续发展，是当前地球信息 科学研究的内容，而应用空间分析方法完成对地球空间信息的认识则是其基础( 陈述 彭1 9 9 9 ) 。 1 1 研究背景 地理信息系统( g e o g r a p h yi n f o r m a t i o ns y s t e m ，g i s ) ( 陈述彭1 9 9 9 ) 具有空间数据 的输入、存储、管理、分析和输出等功能，地理信息系统的主要目的是为了分析空 间数据，以提供空间决策支持信息。因此，空间分析是地理信息系统的主要功能， 是核心，是灵魂，也是评价地理信息系统功能的主要指标之一( 郭仁忠2 0 0 1 ) 。地理 信息系统是从实际应用中产生发展过来的，在初期主要是处理日益剧增的地理数据， 而地理数据固有的复杂性导致人们的努力多集中在地理信息的表达、数据的存储管 理和模拟纸质地图的信息传递，而无暇顾及数据之上的空间信息的分析。因此，地 理信息空间分析技术一直相对滞后于空间数据库的理论与技术。近几年来作为g i s 核 心的空间分析得到了长足的发展，然而对空间分析的定义却没有取得一致的认识。 g o o d c h i l d 认为空间分析应分为四大部分，即空间统计分析、空间相互作用、空间依 赖和空间决策等( g o o d e h i l d1 9 9 4 ) ，而r o b e r th m n i n g ( h a i n i n g1 9 9 0 ) 则认为空间分析 主要由三大部分组成，分别是：统计分析、地图分析和数学模型。由于侧重点不一 样，所以现在对空间分析的研究重点也不一样，从而产生了不同的空间分析方法。 在传统的g i s 中，空间分析主要局限于空间统计以及叠置、缓冲区分析等内容 ( g o o d c h i l d1 9 9 1 ) 。随着g i s 在城市交通、地下管网、电力、通讯、有线电视等部门 的广泛应用，对空间分析功能提出了更高、更新的要求。由于这些部门的基础数据 是由点和线组成的网状数据，因此要想全面地描述这些网状数据及它们的相互联系 的内在联系，就需要g i s 提供强大、灵活的网络分析功能( 龚健雅2 0 0 1 ) ，包括路径 中潮科学院遥感应用研究所礤士论文空间弼络分艟荚键技术研究 分孝斤、资源分配、连通分板、流分掇、个体雩亍为分柝和城枣空闯形态等。 地理信息系统的最终曩的是支持魏理决策，阐样，建立网络分析模型的最终目的 是为了进行有效的分析，给决策提供有效的参考。在数学领域内，网络分析的基础 是图论与运筹学。将溪论孛阙络戆羧念弓| 天裂逸理空瘸紫来慈述秘褒达基予爨络瓣 地理目标，就称之为地理网络。对地理网络进行地理分析和模型化，在分析方法上 引入运筹学模型和图论算法，这就是嫩理信息系统的网络分析功能。 1 ，1 1 空间网络分析的必要憾 逑毽网终是互掇连接致程互搏露懿线毪实体戆基本缝擒形式。器耱霞线、魄力线、 电话线、交通路线、河流水系、通讯镣都是地理网络的袭现形式。地理网络照区域 物质与自源流动的载体，大楚南水北调、北煤南运、硒电东送等国家级的物质和能 源调动需求，夸至入民生活鹣方方委颓，无不与遣理网络傣藏相关。选理黼络要素 的相互作用及能流、物流在作为载体的地理网络上的传输，形成了丰富的地理与社 会现象，菸虽将蟪瑷实体套皴地联系在一起。可以毫不夸张遗说，圭敷理网络楚形成 客观世界和人文社会的基本臀架，也怒联系客躐世界和人文社会的凝本纽带。随着 城市规模的扩大和城市基础设施的复杂化，地理网络也变得越来越照要和越来越复 杂。 目前，几乎所有的大中型g i s 平台都提供了对地理网络分析的空间网络分析功能。 然而，这些网络分析更多的跫利用网络的几何拓扑信息采对地理网络的几何傣息进 行操作，谣缀少浚覆于网络分拆功能本身静算法和遣理瓣络的语义信息酶表遮。同 时，对地理网络数据模型的研究也比较薄弱，多采用与其它专题数据相同的经过平 嚣强化戆平瑟蚕数摄模型，纛此基础上弓l 入线渡参照系绞( 1 i n e a r r e f e r e r l c es y s t e m ) 、 动态分段( d y n a m i cs e g m e n t a t i o n ) 和地址编码( g e o c o d i n g ) 技术，以满足涉及多种 属性的动态管理和简单查询( f l e t c h e r1 9 8 7 ，g o o d c h i l d1 9 9 2 ，李沃璋l o u k e s 1 9 9 6 ，d u e k e r & b u t l e r1 9 9 8 ) 。平瑟蚕数据模型强溺粒蹙霹死侮蔫惑鹣表达，嚣辩速理 网络建模而言，建立在逻辑网络之上的网络拓扑和语义信息的表达往往更为爨要， 也就是说，地理网络建模强调的是对逻辑网络中的节点和联线的隧终拓扑和谬义操 作过程。阂j 毙，缺乏语义建禳及复杂阏络拓芥表达能力的平面图数据模型在地理网 络建模中并不十分适用。 续“数字遣球”之爱提爨夔“数字孩枣”，燹是对g i s 察窝霹终分掇葫掇窭了 更高的要求。所谓“数字化城市”，指的是充分剩用数字化，空间信息处理技术及 其相关计算机技术和手段，对城市基础设旌与生活发展相关的各方蕊内容进行全方 健靛售惑讫楚瑾葙翻用，其蠢对城枣穗理、资滚、生态、环凌、入嗣、经济、社会 等复杂系统的数字网络化管理、服务与决策功能的信息体系。当前，很多发选国家 开始了“数字城市”的建设。薮加坡雷先提出了舞能城市的设想，并在积极邀行中。 2 第一章绪论 美国与日本等己分别建成一批智能化生活小区( 数字社区) 的示范工程，美国约有5 0 个城市正在打算建设“数字城市”。“数字城市”的研究在我国虽然刚起步，但已 经呈现了很强的发展势头，上海市已率先上马，其城市骨干a t e 网的建设己经开始， 并同时组建i p 电话系统、电子商务i c p ( 网络内容服务商) 、电子社区等增值系统、国 际远程医疗中心等；深圳、南海等城市均已初步建成覆盖全市区的a t m 骨干网络，并 正在向数字城市的纵深方向发展。因此，可以预想，“数字城市”的发展极大地推 动了空间网络分析的发展，促使空间网络分析在算法、空间数据模型以及应用等方 面得到充分的研究与应用。 1 1 2g i s 空间数据模型 模型是把一个域( 源域) 的组成部分表现在另一个域( 目标域) 中的一种结构， 通过建模把源域简单化和抽象化( 陈述彭1 9 9 9 ) 。数据模型是通过数据手段对现实世 界抽象。数据模型提供了数据库的概念结构及信息表达的形式化手段，决定了需要 在数据库中表达的特征及其如何描述它们之间的相互关系，定义了在数据上的各种 操作。数据模型的内容包括三方面：数据结构类型集、数据操作算子集和数据库状 态的完备性约束规则集( c o d d1 9 9 0 ，f r a n k & e g e r t h o f e r1 9 9 2 ，d a t e1 9 9 5 ，t a n g & a d a m se ta l1 9 9 6 ) 。 随着应用领域的扩大，计算机介入了许多非传统的数据应用领域，如c a d c a m 、 地理数据处理等，传统的数据模型( 关系、网络与层次模型) 对这些领域显然力不 从心，因此，设计和实现面向特定应用领域的数据模型成为发展的必然。 空间数据模型是真实世界实体与现象的抽象，即具有空间分布特征的实体集及其 实体集之间关系的概括性描述( p e u q u e t1 9 8 4 ，g a r d e l s1 9 9 7 ) ，反映了现实世界中空间 实体及其相互之间的联系，为空间数据组织和空间数据库模式设计提供了基本的概 念和方法。空间数据模型一般理解为由概念数据模型、逻辑数据模型与物理数据模 型三个阶段或层次组成( s a v a g e1 9 9 5 ，陈军1 9 9 5 ) 。概念数据模型是关于实体及实体 间联系的抽象概念集，逻辑数据模型表达概念数据模型中数据实体( 或记录) 及其 相互关系，而物理数据模型则描述数据在计算机中的组织与存储方法。 ( 1 ) 概念数据模型 g i s 空间概念模型的目标是确定需要处理的空间对象或实体，明确空间对象或实 体之间的相互关系，从而决定数据库的存储内容。按照人类对客观世界的感知方式， 有两种认识空间现象的观点，即连续场观点( f i e l dv i e w ) 和离散目标观点( o b j e c t v i e w ) 。连续场观点是把空间本身看成是由明确的区块组成的空间顺序集，而离散目 标观点把空间看成被明确的离散空间目标所干扰的区域( g o o d c h i l d1 9 9 2 ) 。连续场所 对应的数据模型有面片模型、等值线模型和样点模型三种。而离散目标数据模型主 要是指基于矢量的图数据模型。 中国辩学靛遥感麻用研究所硕士谂义空闻网络分析关键技术研究 将o b j e c t f i e l d 形式的表达方法转化为平面单值方程的过程称为平面强化 ( p l a n a re n f o r c e m e n t ) 。平面强化迸一步将人们对空间现象或实体的理解简化为平面 形式，以便于描述与袭达。这样就产生了目前普遍采用的基于平面图的离散目标点、 线、丽数据模型与基于涟续铺盖的镶嵌数据模型。 ( 2 ) 滋疆数据模型 逻辑数据模型楚穰念数据模型所确定豹空闯实体及关系的逻辑表这，可分为蕊 向绪构模型和面向操作模型两大类( 陈军，1 9 9 5 ) 。 u 蔺向结构模型显式地表达了数据实体之间的关系。它包括羼次数据模型、网络数 据模溅和面向对象数据模型三种基本类型。其中的层次数据模型按树形结构组织数 攒 瑟滚，趿反映数据之阔蟾隶属或层次关鬃。它越缦好地表达l ：n 兹关系，健表这 共攀点线豹拓羚结稼魄较困难。弼络数据模鍪是层次数据模登豹一释广义影式，通 过指针联接来表达m ：n 的关系，其缺点是警弱标关系复杂时，搬针将变得相当复杂。 面向对象的数据模型通过把g i s 需要处理的空间目标抽象为不同的对象，建立各类 对象的联系图，并将备炎对象的属性与操作予以封装。面向对蒙的数据模型是当前 g i s 镦阀数据模型的一个发展热点。 囊涵摄终豹逻罄鼗攥羧鍪包摇关系数据糗整与扩曩关系模黧。关系数据模墼楚痰 用聚为广泛的数据模型。它通过满足一定条件的二维表的形式来表达数据之间的逻 辑结构。关系表由一系列同类的元组构成。每个元组表达个实体，通过关系操作 提取溅查询数据实体之间的关系。关系模趔恳有十分严格的理论基础，比较适合属 性数据的存储。但由于受关系范式( n o r m a lf o r m ) 的限制，关系模型难以表达复杂 关系。扩震关系模登怒戮翅嚣岛对象静方法，对黄统夔关系模疆遴牙改迸，爱箕戆 处瑷变长字段属性，支持空闻操作。 ( 3 ) 物理数据模型 逻辑数据模型必须转化为计算机能够处理的方式才能实现，这种方式就叫物瑷 数据模型。物理数据模勰通过一定的数据结构，完成空间数据的物理组织、空间存 取及索零 方法匏设诗。谯褥瑾数握模型除歉，除了要考虑魏髓选择会逶戆矢量与掇 穆凡何数据结稳来实躐掰设计的概念咒麓禳黧外，还要考虑懿蔼实现对专蘧倍感鹣 操作，即实现专题与语义数据模型的方法。此外，采用何种设计方法来完成几何数 据模烈与专题、语义数搠模型的关联也是一个必须认真考虑的问题。 当前，空间数据模型诞朝着综合性模型与定向性模型结合方向发展。事实上，如 栗一个模型越代表真嶷健器，越灵活，就越具有应愚潜力。阉辩，如果一令模黧 越遥会予疫覆嚣蠡，越誓一，就莛戆充分零l 瘸计算援懿存储窆阗，氇裁效率越蔫。 1 1 3 地理空间网络的特殊性 网络是数学和计算机领域的概念，指的是点和边按照一定的规则组成的一种数 4 第一章绪论 据结构，它是对现实世界中的事物及其关系的抽象。在网络中的顶点和边具有一定 的现实意义。顶点可以代表某一事物，而边代表事物之间的关系。通过抽象就把现 实中的复杂的事物之间的关系用简洁的点与点之间的关系表现出来了，从而给人提 供了一种直观的对现实世界的理解。 然而，g i s 研究的地理网络是一种特殊的地理网络。它是以地理空间数据为基础， 以空间相互作用关系为源动力的一种时空数据模型。具体而言，地理空间网络具有 下面一些特性： ( 1 ) 空间性 地理空间网络是由地理空间数据组成，在地理空间坐标系下具有一定的位置。 这个位置是三维的，因而也是空间。地理空间网络的空间性决定地理空间网络特殊 性，如在平面上相交的地理网络在空间上并不一定相交。 ( 2 ) 地理参照性 地理空间网络下的顶点一般都具有明确的空间位置，即空间坐标。和一般的迪 卡尔坐标系不一样的是地理空间网络中的顶点的坐标具有地物参照性，它一般是根 据地物之间的相互作用关系建立的。 ( 3 ) 多重性 地理空间网络的抽象和地图比例尺有关。不同比例尺下的地理空间网络的表示 形式不一样。如城市自来水地理网络，在大比例尺下，管道阀门，支线等要做为独 立的顶点和边表示出来，而在小比例尺的情况下，就可以把他们抽象成独立的顶点。 ( 4 ) 相互作用性 地理空间网络中的边表示的是地理实体之间的相互关系，包括空间的和非空间 的。这些相互关系是相互依赖，相互影响的，如电信网络中的通信线之间相互连通 的，这样才能保证某条线路有问题而不会出现通信问题。 ( 5 ) 时序性 地理空间网络具有时空性。一般意义上的网络是静态的，而地理空间网络是动态 的，随着时间和空间的变化而变化。如城市交通网络，随着市政工程和城市交通的 发展，交通网络也随着变化，表现为道路的变化和线路的增加等。 1 1 4 空间网络分析的空间化 目前，随着计算机技术的飞速发展和计算机图形学理论的日趋完善，g i s 作为一 门新兴的边缘学科也日趋完善，许多商品化的g i s 软件纷纷涌现，出现了很多专门的 空间分析模块，如e s r i 的s p a t i a la n a l y s i s 等等。然而，由于历史和技术的原因， 绝大多数的商品化g i s 软件包还只是在基于二维的基础上模拟并处理现实世界上所 遇到的现象和问题，对三维问题的处理能力很弱。空间分析是g i s 与其它学科相区别 的主要功能特征，而空间分析是具有三维、时空等特性的，因此，空间分析必须时 中国科学院遥感庶用研究所硕十论文空间网络分析关键技术研究 空化，才能真正体现其空间含义。 空间网络分析是空间分析的一个重要部分，目前的空间网络分析能力差，空间网 络建模能力也差。一般情况下，空间网络模型都必须与具体的专业应用知识相结合， 因此，空间网络分析的空间化更是任重道远。 1 2 研究内容 空间网络分析随着城市建设，特别“数字城市”的提出后得到迅速发展的。目前 交通，电信和导航等应用领域的迅猛发展，给空间网络分析提供了更大的发展空间。 然而，空间网络分析在国内g i s 业界一直研究得不多，目前大多数研究集中在基于平 面图的最短路径算法和资源分配问题上。系统的地理网络数据模型的研究在国内尚 少涉足。在本文里，我们系统研究了空间网络分析的关键算法，对算法的改进、算 法所涉及的空间数据模型以及城市特征的多重表达等方面内容进行了研究。 1 2 1 空间网络分析的关键算法 长期以来，网络分析算法都是集中在计算机和统筹学等领域，而在g i s 领域里研 究得很少。但随着g i s 的深入发展和各专业领域知识的渗入，网络分析算法在g i s 领 域里也得到了一定的发展。目前对于网络分析的研究，多集中于算法和特定部门专 业网络系统实现的研究上。在算法方面，主要是集中在最佳路径、资源分配、节点 或弧段的游历( 旅行推销员问题、中国邮递员问题) 以及最小连通树、最大( 小) 流、 连通性等问题上，其相应的模型和算法也比较多，如”d i j k s t r a 最短路径算法的一种 高效率实现”( 乐阳，龚建雅，1 9 9 9 ) ，“基于层次空间推理的交通网络行车最优路径 算法“( 陆锋，周成虎e t a l2 0 0 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 ) ，配电网地理信息系统和“数字城市” 等。另外，由于对象关系数据库在g i s 中的广泛采用，使得空间数据的存储发生了质 的变化，从而也需要空间网络分析算法做出相应的改变。因此，如何设计高效的具 有时空特征的网络分析算法就成为本文研究的问题之一。 1 2 2 空间网络数据模型和网络数据结构 在g i s 发展过程中，受传统的空间数据表达框架和平面图数据表现方法，特别是 制图模型的影响，g i s 在语义上着重于地理特征语义差异的表达，采用地理分层的表 达方式构造空间数据集。例如对地理实体的分类，用平面强化的限制，以其几何特 6 第一章绪论 征点，线，面等为标志。这种以几何目标为主要模拟对象的空间数据模型不但在传 统的关系型地理信息系统得到应用，而且在各种面向对象的地理信息系统中也得到 一定的研究。 随着g i s 逐步向以多源数据集成与共享、多尺度、多维空间分析为特征的企业级、 社会化方向发展，基于地理分层的空间数据表达方法及平面图概念模型只重视空间 现象或实体的几何要素描述、忽视现象或实体之间的语义关系、空间关系表达效率 不高、难以处理动态的时序特征等缺陷越来越突出。这种缺陷极大地影响了g i s 的数 据表达与空间分析能力。为此，专家学者们纷纷提出需要一种高层次的、综合的方 案来描述地理现象，完整地描述空间目标类型与相互之间的语义与空间关系，基于 特征( f e a t u r e b a s e d ) 的g i s 空间数据模型就应运而生。 基于特征( f e a t u r e b a s e d ) 的建模方法是在七、八十年代出现、相对于空间数据的 图层组织方法而提出的新方法。基于地理分层和平面图的数据模型割裂了网络特征 之间、特征与组成要素之间以及组成要素相互之间的语义关系，忽视了通过网络相 互连接的地理特征之间的相互作用，造成在这种概念模型下建立的网络分析效率不 高，很多分析模型难以实现，难于表达特征的时态特性。而基于特征的g i s 数据模型， 可以从几何、语义、属性、拓扑和时态等各方面将地理网络要素及其关系表达纳入 一个统一的框架之中，强化了空间特征固有的内在联系，克服了地理分层和平面图 数据模型的不足之处。 空间数据结构是“数据结构”概念在空间信息科学中的拓展，即空间数据是带有 结构的空间数据单元的集合( 崔伟宏1 9 9 5 ) 。传统的g i s 空间数据结构主要有三种： p o l y v r t 、t i g e r ( t o p o l o g i c a l l yi n t e g r a t e dg e o g r a p h i ce n c o d i n ga n dr e f e r e n c i n g ) 和空间 数据交换标准( s p a t i a ld a t at r a n s f e rs t a n d a r d ，s d t s ) 。近些年来，超图数据结构在地 理信息系统方面得到了很大的发展。然而，对地理空间网络数据结构的研究却鲜少 出现在文献里。由于地理空间网络的特殊性，因此研究空间网络数据结构是必要的。 本文对基于特征的地理空间网络数据模型，从语义关系和相对应的特征数据结 构着手研究，使基于特征的空间数据模型能够更好地运用n g i s 的其它领域，如交通， 电力等等。 1 2 3 城市特征的多重表达 城市是由各种道路、交通线路、城市管网等等地理网络所组成的错综复杂的有机 体。尺度是地理空间数据的一个重要特征，在不同的尺度下，各个地理实体具有不 同的空间形态、结构和细节。同样地，在不同的尺度下，城市也呈现不同的空间形 态、结构和细节，从而形成了对城市特征的多重抽象表达。城市的多重表达反映了 城市在不同尺度上的动态联系，为研究城市特征的变化规律提供了很好的理论基础。 当前对城市特征的多重表达主要集中在对城市特征多重表达的概念模型研究和 中国科学院遥感应用研究所硕士论文空间网络分析关键技术研究 城市网络特征的多重表达模型设计上。为了利用g i s 技术提供由整体到局部、由抽象 到具体的地理实体和地学过程的分析及可视化功能其中要素的多尺度概念模型是 解决该问题的基础和先决条件。p a r e n t ( p a r e m1 9 9 8 ) 认为同一地理要素在不同表达下 的对应属性及属性值从较高抽象层次到较低抽象层次的变化可能是一个重新定义 ( r e d e f i n e ) 或细化( r e f i n e ) 的过程，而在网络多重表达里则认为多重表达的目的有二： 一是减少节点的复杂度，二是减少节点间的连通度。 随着“数字城市”的发展以及空间数据建模能力和几何网络的发展，基于平面 图模型和铺盖模型进行概念模型设计的方法对复杂特征的多重表达己显的无能为力 了。构建地理要素的多尺度数据模型是进行多尺度空间数据库建库工作的理论基础 和实现保障，因此，如何利用面向对象的方法来表示城市特征的多尺度性就成为本 文研究的另一重要问题。 1 3 论文组织 论文分为六章，各章的内容介绍如下： 第一章为绪论部分，介绍研究的背景，研究的主要内容。 第二章归纳了最短路径所用到的各种数据结构和对算法本身的改善，设计了具 有启发性信息的路径搜索算法，指出了路径搜索算法的发展方向。 第三章对智能交通系统的国内外发展趋势进行了分析，以近些年来研究较多的 智能导航系统为例，分析了智能导航系统的定位原理、数据组织和索引方法，然后 设计了在p d a 上具有导航定位功能的智能导航系统的逻辑体系结构。 第四章从空间网络分析所用到的数据模型着手，分析了当前所用到的空间数据 模型，对基于特征的空间数据模型从概念建模和逻辑建模两方面进行了分析，并对 交通网络的基于特征的g i s 建模进行了研究。 第五章从地理网络本身的表示出发，对其的多重表达意义和难点进行了分析。 研究了城市网络特征的多重表达方式。 第六章总结了论文的研究成果，给出了进一步的研究方向。 其中第二、三、四章是构成论文的核心内容。 第二章最短路径算法 第二章最短路径算法 最短路径算法一直是计算机科学、统筹学、人工智能等领域研究的一个重点。 到目前为止已出现了许多种类的最短路径算法。最短路径算法在g i s 领域也得到 了很大的研究与发展，已有很多成熟的商业软件提供了最短路径功能，如e s r i 公司的a r c g i s ，武汉地质大学的m a p g i s 等软件。最短路径中的“最短”含义不 局限于长度最短，它是个抽象概念，指的是所研究的对象的某一或某几种可量测 综合属性的最优。 2 1 最短路径理论 最短路径指的是在图上选定一个起点和终点，分析从起点到终点的长度或价 格或其它某种标准下的最优路径。其数学描叙为：设g = ( n ，e ) 为一有向图，n 为节 点集，e 为边集