交通网络分析.ppt

交通网络分析陈艳艳 教授基本内容n图论基本概念n路网基本概念n最小树n最短路n最大流n网络配流n网络优化第一节 图论基本概念n图形是一种描述和解决问题直观、有效的手段，如公路网系统、城市公交系统、通信系统等n图论是研究图和网络模型特点、性质和方法的理论第一节 图论基本概念一、基本概念 １．图、赋权图ＡBＥD CF图a所示公路交通 网络，连线表示 公路，节点表示 城镇由于不考 虑长度、曲直、 坡度、海拔等， 所以可用图b表示 图a图 a第一节 图论基本概念一、基本概念 １．图、赋权图ＡＣ ＤＦＢＥ图b为抽象图，既可以表示公路系统又可以表示道路系统图 b第一节 图论基本概念n什么叫赋权图？ 通常我们记图为G＝(V，E) 其中 V代表点的集合，V={vi} E代表边的集合，E=(ei) 对G中每一条边[vi,vj],相应的有权重W(a)=wij ，则连同边上的权称为赋权图第一节 图论基本概念2. 简单图、连通图、树 什么是简单图？若一个图中某条边的两个端点重合，称为环 ；两点之间多于一条边时，称为多重边简单图是指没有环，也没有多重边的图ＡＣＤＢＥF图c为简单图图 c第一节 图论基本概念若图中存在某种点与边的连续交替序列，则 称这个点边序列为一条链。

如图d所示图d第一节 图论基本概念n连通图 若两点之间至少存在一条链，称为连通图， 否则称为不连通图如图e所示为一不连通图图 e第一节 图论基本概念n树 一个无圈的连通图称为树，如图f所示图f第一节 图论基本概念n3.子图、支撑树 子图： 设有两图G1、G2，G1=(V1,E1)， G2=(V2,E2) ，如果V2∈V1， E2∈E1，则称G2是G1的子 图. 支撑树： 如果图G=(V,E)的支撑子图T=(V’,E’)是树，则 称T为G的一个支撑树图d是图c的支撑树第二节 路网基本概念1. 道路网络构成n路段(link)n节点(node)n路网(network)n路径(route)n树(tree)n小区质心(zone centroid)n小区连杆(centroid connector)第二节 路网基本概念2、路网分解及表达n是否要求表示每一条街道、交叉点？n是否要求表示出交叉点处的每一次运动？n研究结果与研究对象、分区的选择有关 第二节 路网基本概念第二节 路网基本概念第二节 路网基本概念第二节 路网基本概念3、路网类型n线形路网（例如公路线、铁路线）没有路线 选择n方格路网（例如城市道路系统）具有多种路 线选择n具有超路径（hyperpaths）的公交网络n具有特定运输模式的多种运输模式网络第二节 路网基本概念4、路段～节点相关矩阵n该矩阵用来表示路段与节点间的关系n若路网结构中节点j为路段i的上游流入节点，则矩阵元素值为1n若路网结构中节点j为路段i的下游流出节点，则矩阵元素值为-1n否则矩阵元素值为0n每一行包含两个非零元素，其和为0第二节 路网基本概念第二节 路网基本概念5、路网赋权 V=link flow （路段流量） h=path flow （路径流量） g=path costs （路径阻抗） c=link costs （路段阻抗） 路段、路口、路网可靠性6、路网模型示意图7、交叉口表示——对偶图法n在实际路网中，交叉口是路线选择的决策点 ，交叉口转向限制常常改变最优路线的结果 。

据调查交叉口转向所引起的时间延误达到 全部行程时间的17%~35%n因此，丰富的路口转向限制信息是进行路网 描述的关键问题之一 n对偶网络法是一种新的能够表达转向限制的 路网表达方法n对偶网络法的基本思想实质上是将基于节点的网 络转化为基于弧段的网络，并建立网络平面拓扑 转向表来存储相邻两对偶网络虚拟节点间的转向 信息及转向权重从而将转向限制问题中的转向 节点的三元组关系转化为转向弧段的二元组关系 ，可以直接利用一般的路线优化算法进行求解对偶图的形成n对偶链的起点是原网络中的起始弧段 n对偶链的终点是原网络中的备选弧段 n对偶网络中的起始节点和备选节点的组合表示交叉口的转向行为原网络与对偶网络对应关系 对偶图法的优点n利用对偶网络法构造对偶网络的算法易于实 现，只需稍加转化，就可以将原网络中的转 向限制和节点权重转移到对偶链上，从而得 到不带有节点权重的对偶网络n在对偶网络中利用一般的路线优化算法求得 的最优路线易于“翻译”回原网络中 8、交通管制的表示标识码转向编码起始节点终止节点是否联通禁行时段TurnIDSubTypeF_nodeT_nodeImpedanceForbidTime15031412501241350234145014337:00-22:00 55034137:00-22:00 65024237:00-22:00 750145185034619502471105025437:00-22:00 115036437:00-22:00 125017437:00-22:00交通管制信息的表示方法第三节 无向赋权图优化－最小树问题n设有一连通图G=(V,E)，对于每一条边 e=[vi,vj]，有一权wij≥0,最小支撑树（简称最 小树）就是图G的支撑树T*,并使得：取得最小值第三节 无向赋权图优化－最小树问题n二、基本性质和定理 1.树的充要条件 图G是树的充要条件为：任意两顶点间有且 仅有一条链。

推论１：在树中去掉一条边，则树成为不连 通图由此可知，在点集相同的所有图中， 树是含边数最小的连通图 推论２：在树中任何两个顶点问添上一条边 ，恰好得到一个圈进一步说，如果再从这 个圈上任意去掉一条边，可以得到一个树第三节 无向赋权图优化－最小树问题n2.最小树的充要条件若T*是图G的一棵树，则当且仅当对T*外的 每条边[vi,vj]有时，它是最小树，其中是树T*内连接点vi和点vj的唯一的链也就是 说，如果将最小树T*外任意一条边[vi,vj]加入T* 内，得到了唯一的一个圈，那么[vi,vj]是这个圈 上权最大的边第三节 无向赋权图优化－最小树问题n三、最小树问题 求最小树方法： ü破圈法 “找圈去大边，无圈为止”即在图中作找一 圈，去掉其中权最大的一条边，在余下的图 中，重复这个步骤，直到无圈为止 ü避圈法 “避圈加小边，连通为止”即先选择图中权 最小的边，以后每步从未选的边中，选一条 权最小的边，使与已选的边不构成圈，直到 图中所有的点都连通（即不存在孤立点）为 止第三节 无向赋权图优化－最小树问题n例1：某城市有六个居民点，道路交通图G如 图所示，现要沿道路铺设煤气管道，将六个 居民点连成网，已知每条道路长度，求使管 道长度最短的铺设方案。

v2v6v5v3v4v1212322354第三节 无向赋权图优化－最小树问题n解：由于煤气管道只能沿着道路布设，并要 求能到所有的居民点，帮表示煤气管道的图 必为道路图的部分图为了使管道总长最短 ，图中不应有圈，帮原问题是求G的最小树 ，即最小树问题如图1，任取一圈 {v1,v2,v6,v1},去掉最大边[v2,v6]v2v6v1124图1第三节 无向赋权图优化－最小树问题取圈{v3,v4,v5,v3}, 去掉边[v5,v4]取圈{v2,v3,v5,v2}, 去掉边[v2,v5]v5v3v4235图 2v2v5v3232图3第三节 无向赋权图优化－最小树问题取圈{v1,v2,v3,v5,v6,v1}，去掉[v6,v5]这时 图中已经无圈了，于是得到如图5所示的最小 树该图即为管道总长为最短的铺设方案， 管道总长为10个单位v2v6v5v3v12 1222v2v6v5v3v4v12 1223图 4图 5n习题。