基于城市道路网的最短路径分析解决方案

                                            基于城市道路网的最短路径分析解决 刘云翔　陈　荦　李　军　陈宏盛 (国防科技大学电子科学与学院, 湖南长沙 410073) 摘　要:  近年来 G IS 对网络分析功能的需求迅速增长. 网络分析中的一个关键问题是最短路径问题, 它作为许多领域 中选择最优问题的基础, 在交通网络分析系统中占有重要地位. 由于最短路径分析常用于汽车导航系统以及各种城市 应急系统(如 110 报警、119 火警以及 120 急救系统) , 本文针对城市道路网的特点, 提出了一种实用、高效的最短路径 分析解决方案. 关键词:  最短路径;  D ijk st ra 算法;  城市道路网 中图分类号:  T P 391. 4     文献标识码: A       文章编号: 1000 1220 (2003) 07 1390 04 An  Im p lem en ta t ion of  the Shor te st Pa th Ana lys is Ba sed on C ity Road Ne twork   2 , 2         L IU Yun X iang, CH EN L uo , L I J un CH EN H o ng Sheng       (S chool of E lectron ic S cience and E ng ineering , N a tiona l U n iv ersity of D ef ense T echnology , C hang sha 410073, C h ina)   Abstrac t In recen t yea r s, N e tw o rk ana ly se s have becom e m o re and m o re im po r tan t in G IS. A s the key p ro b lem o f             2 ne tw o rk ana ly se s, com p u t ing sho r te st p a th s o ve r a ne tw o rk ha s becom e an im po r tan t ta sk in m any ne tw o rk and t ran s po r ta t io n re la ted ana ly se s. Sho r te st p a th ana ly sis is o f ten u sed in veh icle nav iga t io n sy stem     2 and city em e rgency sy s tem s. T h is p ap e r in t ro duce s a p ract ica l and eff icien t rea liza t io n o f sho r te st p a th ana ly sis acco rd ing to the cha racte r ist ics   2         2 o f city ro ad ne tw o rk. W e run o u r a lgo r ithm o n a m idd le range p e r so na l com p u te r w ith re la t ive ly la rge da ta se t. T he ex   p e r im en ta l re su lt is ve ry p rom ising, thu s p ro ve s the eff iciency o f the p ropo sed a lgo r ithm. 2 2   Key words sho r te st p a th; d ijk st ra a lgo r ithm s; ro ad ne tw o rk   2                 1 引　言 近年来由于普遍使用 G IS 管理大型网状设施(如城市中 的道路网、各类地下管线、通讯线路等) , 使得对网络分析功能 的需求迅速增长. 通用的网络分析功能包括路径分析、资源分 配、连通分析、流分析等.  网络分析中最基本的问题是最短路 径问题, 它作为许多领域中选择最优问题的基础, 在交通网络 分析系统中占有重要地位. 从网络模型的角度看, 最短路径分 析就是在指定网络中两结点间找一条阻碍强度最小的路径. 根据阻碍强度的不同定义, 最短路径不仅仅指一般地理意义 上的距离最短, 还可以引申到其它的度量, 如时间、费用、线路 容量等.  由于最短路径问题在实际中常用于汽车导航系统以 及各种城市应急系统等(如 110 报警、119 火警以及 120 急救 系统) , 本文对基于城市道路网的最短路径分析进行了深入研 究. 2　实现机制 要对城市道路网进行最短路径分析, 首先必须将现实中 的城市道路网络实体抽象化为网络图论理论中的网络图, 然 后通过图论中的网络分析理论来实现道路网络的最短路径分 析. 在实际应用中, 城市道路网的表现形式一般为数字化的矢 量地图, 其网络空间特征中的交叉路口坐标和道路位置坐标 是在地图上借助图形来识别和解释的; 而为了能够高效率地 进行最短路径分析, 必须首先将其按结点和弧的关系抽象为 图的结构. 这就需要先对原始道路图进行预处理, 建立其相应 的网络拓扑关系. 预处理的工作主要包括: · 对原始的道路图进行线元素的拓扑检查、进行剪断处 理, 生成线和线相互不相交叉的道路图; · 对剪断后的道路图创建拓扑关系, 并定义其属性特 征, 如道路名称、道路距离、交通流量等; · 生成有拓扑关系的拓扑文件. 经过预处理后, 最短路径分析算法直接从拓扑文件中提 取道路网的网络拓扑结构并加载到内存中, 从而提高路径分 析的效率. 如果由于城市建设的快速发展, 城市道路发生了变 化, 地图更新后, 只需重新进行预处理生成拓扑文件.  系统的 整个工作流程见图 1. 要实现这样的系统主要需解决两个关键问题: (1) 如何用地图表示城市道路网以及提取网络拓扑结构; 收稿日期: 2001208224　作者简介: 刘云翔, 硕士研究生, 主要研究领域为地理信息系统与数据库技术. 李军, 博士, 讲师, 主要研究领域为地 理信息系统与信息可视化技术. 陈宏盛, 硕士, 副教授, 主要研究领域为人工智能与数据库. 陈荦, 硕士, 讲师, 主要研究领域为地理信息系统与 数据库技术. ? 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd.  All rights reserved. 7 期      　    刘云翔等: 基于城市道路网的最短路径分析解决方案              1391 (2)  如何高效率地进行最短路径分析. 本文将对这两个问题分别提出解决方案. 图 1　系统工作流程 F ig. 1 T he w o rkf low o f sy stem 3　城市道路网的地图表示和网络拓扑结构的提取 G IS 中的矢量地图是按图层组织的, 即将一幅地图分成 多个层层叠加的透明层, 这些透明层就称为图层. 每个图层存 放一类专题或一类信息, 它由点、线、面等空间对象的集合组 成. 一般将描述空间对象的数据分为两类, 即空间数据和属性 数据.  其中, 空间数据的是空间对象的位置、拓扑关系和 几何特征; 属性数据是对空间数据的语义描述, 反映了空间对 象的本质特征. 典型的属性数据有空间对象的名称、类型和对 象特征等.  一般在 G IS 中, 空间数据和属性数据是分别存储 的.  如在M ap Info 中, 属性数据以数据库的形式存储为一张 表, 而空间数据则以M ap Info 自己定义的格式保存于文件之 中. 两者之间通过一定的索引机制联系起来. 针对图层组织的特点, 我们将城市道路网单独作为一个 图层处理, 称之为道路层. 将实际的城市道路网转化到地图的 图层中时, 若将每一条街道(在网络图中对应于每一条弧) 和 街道的交叉路口(在网络图中对应于每一个结点) 都作为地理 对象保存在图层中, 不仅会给地图的制作造成很大的工作量, 而且不利于日后地图的维护.  同时, 在最短路径分析时, 用户 往往关心的只是街道的相关信息.  因此我们只将各条街道作 为线对象保存在图层中.  至于街道的属性数据和交叉路口的 坐标信息, 虽然各 G IS 软件对其属性数据文件和空间数据文 件的具体格式是不公开的, 很难从中直接提取. 但它们均提供 了相应的数据交换文件, 以用于空间数据和属性数据的数据 交换. 如M ap Info 的. M IF 和. M ID 文件, A rc Info 的 shap ef ile 文件等. 为了方便起见, 在以下的讨论中, 我们仅针对M ap In2 fo 的文件结构进行讨论. 在M ap Info 中, 每个图层均有其对应的属性数据表结构 文件(. TA B ).  属性数据表结构文件定义了图层中空间对象 的属性数据的表结构, 包括字段数、字段名称、字段类型和字 段宽度等, 另外还指出索引字段及一些用于显示的参数设置 等. 因此我们在道路层的属性数据表结构文件中定义街道的 属性信息字段如下: 表 1　街道的属性信息字段 T ab le 1 T he a t t r ibu te f ie ld o f st ree t s 街道 ID    街道名称 正向权值 反向权值 其中, 街道 ID 是街道唯一的标识号; 街道名称是街道的 物理名称; 街道的正向、反向权值是不同方向上街道的权值, 其方向是由地图绘制的方向确定. M ap Info 对地图中的每一 图层可以生成一种交换格式文件, 它将地图空间数据与属性 数据用文字的方式表示了出来.  交换格式文件包含有两类文 件, 其中. M IF 文件主要包含了空间数据, 指明了地图的坐标 系、属性表结构、地图对象的类型和地理坐标信息等(其文件 结构如图 2 所示). . M ID 文件则详细描述了各地图对象的属 性信息, 它的记录排列顺序与. M IF 文件中空间对象的排列 顺序一致. V e r sio n 2 D e lim ite r " , " Index 1, 3 Coo rdSy s Ea r th P ro jiect io n 1, 104 Co lum n s 3 S t ree t C ha r (40)   T yp e In tege r   D a ta L ine 122. 4677 37. 7866 122. 4675 37. 7847 P en (1, 2, 0)         L ine 122. 4675 37. 7847 122. 4675 37. 7828 P en (1, 2, 0)         L ine 122. 4675 37. 7828 122. 4674 37. 7809 P en (1, 2, 0)         L ine 122. 4767 37. 7809 122. 4673 37. 779 P en (1, 2, 0) 2       2         2   2       2   2       2   2                   图 2 M IF 文件结构示例 F ig. 2 A n exam p le o f . M IF f ile st ructu re 从图 2 中可以看出, 在. M IF 文件中对于图层中的每一 个线对象, 均记录了该线对象的起点和终点的经纬度坐标. 因 此我们可以直接对. M IF 文件进行操作, 从中提取出各结点 的坐标信息, 并对各结点编号, 生成结点表; 同时从. M ID 文 件中提取各街道的属性数据, 生成弧段表.  结点表和弧段表 ( 格式如图 3 所示) 一起作为拓扑文件表达了网络的拓扑结 构.  当地图更新时, 只需重新生成结点表和弧段表, 然后就能 从中提取出网络的拓扑结构, 并用适当的数据结构来表示. 对 于A rc Info , 针对其 shap ef ile 文件可以根据同样的处理思路 来提取网络的拓扑结构.