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

科学技术与工程Sc ience Techno logy and Enginee ringVo l19 No18 Ap r. 20092009 Sc i1 Tech1Engng1第 9卷 第 8期 2009年 4月1671 21819 ( 2009) 822211 204城市交通路网数据模型的构建及其拓扑结构的研究李菲肖洪祥(桂林工学院电子与计算机系 ,桂林 541004 )摘 要 基于图论的思想 ,根据节点 、路段和转向这三个主要的网络要素构建了一个城市交通路网模型 ,并将其抽象成带转向的赋权有向图 。同时 ,通过一个含 4节点 、8路段的示例路网着重研究了交通路网拓扑结构的五种表达方式 。研究表明 ,路 网拓扑结构的表达方式不能单靠各方法的时间空间复杂度来决定 ,还需权衡问题求解算法的特点 。关键词 路网赋权有向图中图法分类号TP311. 12;拓扑结构文献标志码A交通的发展是国家兴旺发达的重要标志之一 。近年来 ,交通的拥挤 、道 路的 阻 塞越 来越 严 重地 困 扰着世界各国城市 。因此 ,深入研究 城市 交通 路网 的 数据 模型 及 其拓 扑 结构是非常必要的 ,交通系统的规划大多建立在它 的基础上 。节点与路段的集合 ,交通路网中的道路还包含了车流的行驶方向和各 种行 驶 限制 策略 等 , 如 : 单向 行 驶 、禁止左 转弯 等 。因 此 , 路网 又进 一 步定 义成 包含“节点 、路段 、转向 ”三个基本要素的交通路网 1 。2 交通路网的数据模型1 交通路网的基本元素2. 1 图论思想 2 图论 ( Grap h Theo ry) 是 数 学的 一个 分 支 , 它 以图为研究对象 。图论中 的 图是 由若 干 给定 的点 及 连接两点的线所构成的图形 ,这种图形通常用来描 述某些事物之间的 某种 特 定关 系 , 用点 代表 事 物 , 用连接 两 点 的 线 表 示 相 应 两 个 事 物 间 具 有 这 种 关系 。2. 2 模型构建根据图论的思想 , 将路网抽象成一个带转向的 赋权有向图 , 路网模型如下 3 :T = (N , R , W , F ) 。其中 : T表示一个城市的交通路网模型 ;城市的交 通路 网主 要由 大 量相 邻或 相 交的 道路组成 ,经研究发现 , 一 条道 路 通常 在与 若 干条 道 路相连的同时又与若 干 条道 路相 交 。但 若 单纯 的 只以道路为对象来研究交通路网拓扑关系的话 ,其 数据结构会显得很复杂 。因此 ,本文以交通路网中 的交叉口为基点展 开讨 论 , 定义 交叉 口 为节 点 , 两 相邻节点之间的道路为路段 。这样 ,整个路网可定 义成一 个 由 大 量 的 节 点 和 路 段 组 成 的 复 杂 网 络系统 。但交通路网不同于简单的道路网 ,道路网只是N = ni集合 ;i = 1, 2, n 表示交通路网中节点的2009 年 1 月 9 日收到广西教育厅科研项目(桂教科研 200701LX336 )资助R = r 表示交通路网中路段的集合 ,ni 、nj 为路网中任意相邻的两个节点 , r 指 从 ni 节点进入到 nj 节点离开的路段 , r 与第一作者简介 : 李 菲 ( 1983 ) , 女 , 桂林工学院电子与计算机系 ,硕士 ,研究方向 : 人工智能 , 模式识 别 。 E2m a il: life i07392001 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 至 j存在一条边 , 则认为第 ( i, j) 项的值为 1; 否则第( i, j)项的值为 0。即 :1, if E, o r ( i, j) E3 路网的拓扑结构及其表示方法3. 1 拓扑学拓扑学也是数学的一个分支 , 它属于几何学的 范畴 , 但它又与通常 的 平面 几何 、立 体几 何 很不 相同 。通常的平面几何或立体几何研究的对象是点 、 线 、面之间的位置关系以及它们的度量性质 。拓扑 学对于研究对象的长短 、大小 、面积 、体积等度量性 质和数量关系都无关 , 它旨在研究各对象之间的结 构关系 。3. 2 路网拓扑结构的多种表示方法交通路网的拓扑关系主要在于“节点 2路段 2转 向 ”之间的拓扑关系 , 当交通路网被抽象成有向图 时 , 其拓扑结构问题就转化成了有向图的结构问题 。有向图在 数学 和计 算机 领 域已 经被 研 究的 比 较透彻 , 关于它的表示方法现已出现了很多种 , 如 :关联矩阵 、邻接矩阵 、邻接表等 4, 5 。 现以实际 交通 网中 一个 简 单的 带转 向 的路 网(图 1 )来具体研究一下这几种典型的方法 。AG ( i, j) =0, o the rw ise上述示例路网用邻接矩阵表示如图 2。图 2 示例路网节点 ( a) 、路段转向 ( b)的邻接矩阵表示3. 2. 2 邻接表邻接表是邻接矩阵的改进 , 它对图中的每个节 点都建立一个邻接关系的单链表 , 并把它们的表头 指针存储 。有向图的邻 接 表就 是所 有 节点 的邻 接8期李 菲 ,等 :城市交通路网数据模型的构建及其拓扑结构的研究2213个单元实际对应于一条路段 , 路段的起点取决于链表头 , 终点取决于该单元存储的节点 。设 G (V , E ) 是一个有 n ( n 0 ) 个节点的图 , 在 邻接表的表示法中每一个节点对应一个链表 ,箭头 代表指向该 链表 下一 个 单元 的 指 针 , 代 表 链 表 结 束 。现用邻接表来表示上述示例路网 ,如图 3 所示 。表 1各表示法的时间空间复杂度比较查找邻接节点查找反向邻接节点插入或删除某条弧空间复杂度表示法时间复杂度邻接矩阵邻接表 反向邻接表 十字链表 星形表 反向星形表 双向星形表o ( 4 ) o ( 2 ) o ( 8 ) o ( 2 ) o ( 2 ) o ( 8 )o ( 2 )o ( 4 ) o ( 8 ) o ( 2 ) o ( 2 ) o ( 8 ) o ( 2 )o ( 2 )o ( 1 ) o ( 1 ) o ( 1 ) o ( 1 ) o ( 8 ) o ( 8 )o ( 8 )o ( 16 ) o ( 12 ) o ( 12 ) o ( 12 ) o ( 12 ) o ( 12 )o ( 12 )由表 1发现 , 就空间复杂度来说 , 邻接矩阵的存储效率明显不如邻接表和星形表 ; 但就时间复杂度 中的插入弧来说 , 邻接矩阵的效率又明显优于星形 表 。因此在实际运用中 , 到底该以哪种表示法来表示问题模型 , 我们需将问题求解算法的特点和各表 示法时间空间复杂度结合起来考虑 。总的来说 , 十 字链表的效率是最好的 , 它既可以快速检索邻接节点 , 也可以快速检索反向邻接节点 。图 3 示例路网的邻接表表示3. 2. 3 双向邻接表 (十字链表 )双向邻接 表是 对邻 接表 和 反向 邻接 表 的合 二 为一 ,又叫十字链表 。在这种结构中每个节点有 2个单向链表 , 一个列 出该 节 点的 所有 的 邻接 节点 ,另一个列出该节点的 所 有反 向邻 接 节点 。示例 路 网的双向邻接表如图 4 所示 : 图中由每个节点引出的横向链表串起了所有的邻接节点 ,竖向链表串起 了所有的反向邻接节点 。3. 2. 4 星形表 星形表实 际上 是邻 接表 的 一种 以顺 序 表为 结构的具体形式 ,它用两个数组代替了邻接表中的多个单向链表 。其中一个 数组 依 次存 储各 个 节点 的 所有邻接节点 ,另一个数组则记录每个节点的邻接节点在前一个数组中 的 起始 地址 。星形 表 也分 为 前向星形表 、反向星形表和双向星形表 。3. 3 几种表示方法的比较经研究发现 ,用邻接矩阵来表示路网拓扑结构都 比较简单和直接 ,但这种表示方法容易出现稀疏矩阵 ,如图的邻接矩阵表示需要用到 n n 个整数位 , 其时间复杂度为 ( n ) ,空间复杂度为 ( n2 ) , 当用其表 示交通路网 ,特别是大规模路网时则会浪费大量的存 储空间 。下面以图 1路网为例 ,就各表示法的时间和空间复杂度说明其缺点和优越性 (见表 1) 。图 4 示例路网路段转向的双向邻接表表示学出版社 , 2007(美 ) B uck ley F, L ew in te r M. 图论简明教程. 李慧霸 ,王凤芹 ,译.北京 :清华大学出版社 , 2005樊月珍. 基于交通流的车辆动态路径诱导方法研究. 博士学位 论文 . 北京 :中国农业大学 , 2005殷人昆 , 陶 永 雷 , 谢 若 阳 , 等. 数 据 结 构. 北 京 : 清 华 大 学 出 版 社 , 1999(美 ) Sahn i S. 数据结构 、算法与应用 C + +语言描述. 汪诗 林 ,孙晓东 ,译. 北京 : 机械工业出版社 , 200024 结论3数据模型是对真实世界中系统的抽象描述 , 本文中构建的城市交通路网数据模型 尽可 能 的完 成 了对实际交通路网的抽象 , 并将其用多种表示方法 表示出来 。通过分析各 表示 法 的时 间和 空 间复 杂 度 , 我们发现具体问 题 该具 体分 析 , 表示 法 的选 择 取决于求解问题的特点和表示法的效率 。45参 考 文 献1 任 刚. 交通管理措施下的交通分配模型与算法. 南京 : 东南大Urban Tran spor ta t ion Roa d Ne twork D a ta M ode l an d Its Topo logy S tudyL I Fe i, X IAO Hong2xiang(D ep a rtm en t of E lec tron ic and Comp u te r, Gu ilin U n ive rsity of Techno logy, Gu ilin 541004 , P. R. Ch ina) A b stra c t B a sed on the though t of the grap h theo ry, and acco rd ing to the node s, the road s and the d irec tion s tobu ild an u rban tran spo rta tion road ne two rk mode l, and ab strac t a s a o rien ted grap h w ith we igh t a re p re sen ted. A t the sam e tim e, focu sing on the five exp re ssion of the tran spo rt ne two rk topo logy th rough the road ne two rk w ith 4 2node and 8 2road sec tion is p re sen ted too. R e sea rch show s th