城市交通路网数据模型的构建及其拓扑结构的研究

《城市交通路网数据模型的构建及其拓扑结构的研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、科学技术与工程ScienceTechnologyandEngineeringVol19No18Apr.20092009Sci1Tech1Engng1第9卷第8期2009年4月167121819(2009)822211204Ζ城市交通路网数据模型的构建及其拓扑结构的研究李菲肖洪祥(桂林工学院电子与计算机系,桂林541004)摘要基于图论的思想,根据节点、路段和转向这三个主要的网络要素构建了一个城市交通路网模型,并将其抽象成带转向的赋权有向图。同时,通过一个含4节点、8路段的示例路网着重研究了交通路网拓扑结构的五种表达方式。研究表明,路网拓扑结构的表达方式不能单靠各方

2、法的时间空间复杂度来决定,还需权衡问题求解算法的特点。关键词路网赋权有向图中图法分类号TP311.12;拓扑结构文献标志码A交通的发展是国家兴旺发达的重要标志之一。近年来,交通的拥挤、道路的阻塞越来越严重地困扰着世界各国城市。因此,深入研究城市交通路网的数据模型及其拓扑结构是非常必要的,交通系统的规划大多建立在它的基础上。节点与路段的集合,交通路网中的道路还包含了车流的行驶方向和各种行驶限制策略等,如:单向行驶、禁止左转弯等。因此,路网又进一步定义成包含“节点、路段、转向”三个基本要素的交通路网[1]。2交通路网的数据模型1交通路网的基本元素2.1图论思想[2]图

3、论(GraphTheory)是数学的一个分支,它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。2.2模型构建根据图论的思想,将路网抽象成一个带转向的赋权有向图,路网模型如下[3]:T=(N,R,W,F)。其中:T表示一个城市的交通路网模型;城市的交通路网主要由大量相邻或相交的道路组成,经研究发现,一条道路通常在与若干条道路相连的同时又与若干条道路相交。但若单纯的只以道路为对象来研究交通路网拓扑关系的话,其数据结构会显得很复杂。因此,本

4、文以交通路网中的交叉口为基点展开讨论,定义交叉口为节点,两相邻节点之间的道路为路段。这样,整个路网可定义成一个由大量的节点和路段组成的复杂网络系统。但交通路网不同于简单的道路网,道路网只是N={ni集合;i=1,2,,n}表示交通路网中节点的2009年1月9日收到广西教育厅科研项目(桂教科研200701LX336)资助R={r}表示交通路网中路段的集合,ni、nj为路网中任意相邻的两个节点,r指从ni节点进入到nj节点离开的路段,r与第一作者简介:李菲(1983—),女,桂林工学院电子与计算机系,硕士,研究方向:人工智能,

5、模式识别。E2mail:lifei07392001@sina.com。r表示的行驶方向完全相反;W={w}表示交通路网中路段权值的集合;F={f(,)}表示路段的转向,若f=+∞,则说明禁止从路段r转向路段r。表路段的行驶方向,虚线箭头代表路段之间的转向,小括号内的数字代表路段权值。3.2.1邻接矩阵邻接矩阵是表示图形中顶点之间相邻关系的矩阵。若设图G=(V,E)是一个有n(n>0)个节点的图,其中V表示节点,E表示边,则图的邻接矩阵AG是一个二维的n×n矩阵。对于该矩阵,若顶点i

6、至j存在一条边,则认为第(i,j)项的值为1;否则第(i,j)项的值为0。即:1,if∈E,or(i,j)∈E3路网的拓扑结构及其表示方法3.1拓扑学拓扑学也是数学的一个分支,它属于几何学的范畴,但它又与通常的平面几何、立体几何很不相同。通常的平面几何或立体几何研究的对象是点、线、面之间的位置关系以及它们的度量性质。拓扑学对于研究对象的长短、大小、面积、体积等度量性质和数量关系都无关,它旨在研究各对象之间的结构关系。3.2路网拓扑结构的多种表示方法交通路网的拓扑关系主要在于“节点2路段2转向”之间的拓扑关系,当交通路网被抽象成有向图时,其拓扑结构问题就转

7、化成了有向图的结构问题。有向图在数学和计算机领域已经被研究的比较透彻,关于它的表示方法现已出现了很多种,如:关联矩阵、邻接矩阵、邻接表等[4,5]。现以实际交通网中一个简单的带转向的路网(图1)来具体研究一下这几种典型的方法。AG(i,j)=0,otherwise上述示例路网用邻接矩阵表示如图2。图2示例路网节点(a)、路段转向(b)的邻接矩阵表示3.2.2邻接表邻接表是邻接矩阵的改进,它对图中的每个节点都建立一个邻接关系的单链表,并把它们的表头指针存储。有向图的邻接表就是所有节点的邻接8期李菲,等:城市交通路网数据模型的构建及其拓扑结构的研究2213个单元实际对

8、应于一条路