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

基于城市道路网的最短路径分析解决方案刘云翔陈荦李军陈宏盛(国防科技大学电子科学与工程学院,湖南长沙410073)摘要:近年来GIS对网络分析功能的需求迅速增长.网络分析中的一个关键问题是最短路径问题,它作为许多领域中选择最优问题的基础,在交通网络分析系统中占有重要地位.由于最短路径分析常用于汽车导航系统以及各种城市应急系统(如110报警、119火警以及120急救系统),本文针对城市道路网的特点,提出了一种实用、高效的最短路径分析解决方案.关键词:最短路径;Dijkstra算法;城市道路网中图分类号:TP391.4文献标识码:A文章编号:10001220(2003)07139004AnImplementationoftheShortestPathAnalysisBasedonCityRoadNetwork2,2LIUYunXiang,CHENLuo,LIJunCHENHongSheng(SchoolofElectronicScienceandEngineering,NationalUniversityofDefenseTechnology,Changsha410073,China)AbstractInrecentyears,NetworkanalyseshavebecomemoreandmoreimportantinGIS.Asthekeyproblemof2networkanalyses,computingshortestpathsoveranetworkhasbecomeanimportanttaskinmanynetworkandtransportationrelatedanalyses.Shortestpathanalysisisoftenusedinvehiclenavigationsystem2andcityemergencysystems.Thispaperintroducesapracticalandefficientrealizationofshortestpathanalysisaccordingtothecharacteristics22ofcityroadnetwork.Werunouralgorithmonamiddlerangepersonalcomputerwithrelativelylargedataset.Theexperimentalresultisverypromising,thusprovestheefficiencyoftheproposedalgorithm.22Keywordsshortestpath;dijkstraalgorithms;roadnetwork21引言近年来由于普遍使用GIS管理大型网状设施(如城市中的道路网、各类地下管线、通讯线路等),使得对网络分析功能的需求迅速增长.通用的网络分析功能包括路径分析、资源分配、连通分析、流分析等.网络分析中最基本的问题是最短路径问题,它作为许多领域中选择最优问题的基础,在交通网络分析系统中占有重要地位.从网络模型的角度看,最短路径分析就是在指定网络中两结点间找一条阻碍强度最小的路径.根据阻碍强度的不同定义,最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等.由于最短路径问题在实际中常用于汽车导航系统以及各种城市应急系统等(如110报警、119火警以及120急救系统),本文对基于城市道路网的最短路径分析进行了深入研究.2实现机制要对城市道路网进行最短路径分析,首先必须将现实中的城市道路网络实体抽象化为网络图论理论中的网络图,然后通过图论中的网络分析理论来实现道路网络的最短路径分析.在实际应用中,城市道路网的表现形式一般为数字化的矢量地图,其网络空间特征中的交叉路口坐标和道路位置坐标是在地图上借助图形来识别和解释的;而为了能够高效率地进行最短路径分析,必须首先将其按结点和弧的关系抽象为图的结构.这就需要先对原始道路图进行预处理,建立其相应的网络拓扑关系.预处理的工作主要包括:·对原始的道路图进行线元素的拓扑检查、进行剪断处理,生成线和线相互不相交叉的道路图;·对剪断后的道路图创建拓扑关系,并定义其属性特征,如道路名称、道路距离、交通流量等;·生成有拓扑关系的拓扑文件.经过预处理后,最短路径分析算法直接从拓扑文件中提取道路网的网络拓扑结构并加载到内存中,从而提高路径分析的效率.如果由于城市建设的快速发展,城市道路发生了变化,地图更新后,只需重新进行预处理生成拓扑文件.系统的整个工作流程见图1.要实现这样的系统主要需解决两个关键问题:(1)如何用地图表示城市道路网以及提取网络拓扑结构;收稿日期:2001208224作者简介:刘云翔,硕士研究生,主要研究领域为地理信息系统与数据库技术.李军,博士,讲师,主要研究领域为地理信息系统与信息可视化技术.陈宏盛,硕士,副教授,主要研究领域为人工智能与数据库.陈荦,硕士,讲师,主要研究领域为地理信息系统与数据库技术.©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.7期刘云翔等:基于城市道路网的最短路径分析解决方案1391(2)如何高效率地进行最短路径分析.本文将对这两个问题分别提出解决方案.图1系统工作流程Fig.1Theworkflowofsystem3城市道路网的地图表示和网络拓扑结构的提取GIS中的矢量地图是按图层组织的,即将一幅地图分成多个层层叠加的透明层,这些透明层就称为图层.每个图层存放一类专题或一类信息,它由点、线、面等空间对象的集合组成.一般将描述空间对象的数据分为两类,即空间数据和属性数据.其中,空间数据记录的是空间对象的位置、拓扑关系和几何特征;属性数据是对空间数据的语义描述,反映了空间对象的本质特征.典型的属性数据有空间对象的名称、类型和对象特征等.一般在GIS中,空间数据和属性数据是分别存储的.如在MapInfo中,属性数据以数据库的形式存储为一张表,而空间数据则以MapInfo自己定义的格式保存于文件之中.两者之间通过一定的索引机制联系起来.针对图层组织的特点,我们将城市道路网单独作为一个图层处理,称之为道路层.将实际的城市道路网转化到地图的图层中时,若将每一条街道(在网络图中对应于每一条弧)和街道的交叉路口(在网络图中对应于每一个结点)都作为地理对象保存在图层中,不仅会给地图的制作造成很大的工作量,而且不利于日后地图的维护.同时,在最短路径分析时,用户往往关心的只是街道的相关信息.因此我们只将各条街道作为线对象保存在图层中.至于街道的属性数据和交叉路口的坐标信息,虽然各GIS软件对其属性数据文件和空间数据文件的具体格式是不公开的,很难从中直接提取.但它们均提供了相应的数据交换文件,以用于空间数据和属性数据的数据交换.如MapInfo的.MIF和.MID文件,ArcInfo的shapefile文件等.为了方便起见,在以下的讨论中,我们仅针对MapIn2fo的文件结构进行讨论.在MapInfo中,每个图层均有其对应的属性数据表结构文件(.TAB).属性数据表结构文件定义了图层中空间对象的属性数据的表结构,包括字段数、字段名称、字段类型和字段宽度等,另外还指出索引字段及一些用于显示的参数设置等.因此我们在道路层的属性数据表结构文件中定义街道的属性信息字段如下:表1街道的属性信息字段Table1Theattributefieldofstreets街道ID街道名称正向权值反向权值其中,街道ID是街道唯一的标识号;街道名称是街道的物理名称;街道的正向、反向权值是不同方向上街道的权值,其方向是由地图绘制的方向确定.MapInfo对地图中的每一图层可以生成一种交换格式文件,它将地图空间数据与属性数据用文字的方式表示了出来.交换格式文件包含有两类文件,其中.MIF文件主要包含了空间数据,指明了地图的坐标系、属性表结构、地图对象的类型和地理坐标信息等(其文件结构如图2所示)..MID文件则详细描述了各地图对象的属性信息,它的记录排列顺序与.MIF文件中空间对象的排列顺序一致.Version2Delimiter,Index1,3CoordSysEarthProjiection1,104Columns3StreetChar(40)TypeIntegerDataLine122.467737.7866122.467537.7847Pen(1,2,0)Line122.467537.7847122.467537.7828Pen(1,2,0)Line122.467537.7828122.467437.7809Pen(1,2,0)Line122.476737.7809122.467337.779Pen(1,2,0)22222222图2MIF文件结构示例Fig.2Anexampleof.MIFfilestructure从图2中可以看出,在.MIF文件中对于图层中的每一个线对象,均记录了该线对象的起点和终点的经纬度坐标.因此我们可以直接对.MIF文件进行操作,从中提取出各结点的坐标信息,并对各结点编号,生成结点表;同时从.MID文件中提取各街道的属性数据,生成弧段表.结点表和弧段表(格式如图3所示)一起作为拓扑文件表达了网络的拓扑结构.当地图更新时,只需重新生成结点表和弧段表,然后就能从中提取出网络的拓扑结构,并用适当的数据结构来表示.对于ArcInfo,针对其shapefile文件可以根据同样的处理思路来提取网络的拓扑结构.图3结点表和弧段表的格式Fig.3Theformatofnodetableandarctable表示网络的数据结构有很多,例如邻接矩阵、邻接表、十字链表等.以往的研究证明针对最短路径分析,表示网络的数〔3〕.据结构中最有效的是ForwardStar表示法该表示法使用两个数组来表示网络的拓扑关系.一个数组存储和弧相关的数据,另一个数组存储和结点相关的数据.网络中所有的弧按照一定的顺序排列在数组中,即以结点1,2,3,为起点的©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.1392小型微型计算机系统2003年弧在数组中顺序排列,起点相同的弧则可以任意排列.弧的属性数据,如起点、终点、权值等,以某种方式和弧保存在一起.对于结点数组,第i个元素和结点i相对应,它存储的是以结点i为起点的第一条弧在与弧相关的数组中的位置.4最短路径算法我们所讨论的最短路径算法主要针对平面有向图,一些相关定义如下:定义1有向图G={N,A},N为结点集合,A为弧的集合;结点数n=ûNû,弧数m=ûAû;s表示源结点,t表示目的结点.定义2d(i)表示源结点s到结点i的加权距离;l(i,j)表示连接结点i和j的弧的权值;S(j)表示结点j的状态,分为未标记结点(unreached),临时标记结点(temporarilylabeled)和永久标记结点(permanentlylabeled)三种状态.〔2〕经典的最短路径算法—Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础,其求解源结点s到目的结点t的最短路径的基本过程如下:(1)初始化网络.对所有结点i,如果i≠s,则d(i)←+∞,S(i)=unreached,否则d(i)=0,S(i)=perma2nentlylabeled;(2)T←N;(3)从T中取出权值最小的结点k,d(k)=min〔d(j),j∈T〕;S(k)=permanentlylabeled;(4)如果k=t,则算法结束;(5)对于和k相连的每个结点j,j∈T.如果d(j)d(k)+l(k,j),则d(j)←d(k)+l(k,j),S(j)=temporarilylabeled;(6)T←T-{k},转到步骤(3).由于算法将临时标记结点以无序的形式存放在一个链表或数组中.那么要选择一个权值最小的结点就必须把所有的点都扫描一遍.在大数据量的情况下,这无疑是一个制约计算速度的瓶颈