交通网络分析PPT课件

1 交通网络分析 陈艳艳教授 2 基本内容 图论基本概念路网基本概念最小树最短路最大流网络配流网络优化 3 第一节图论基本概念 图形是一种描述和解决问题直观 有效的手段 如公路网系统 城市公交系统 通信系统等 图论是研究图和网络模型特点 性质和方法的理论 4 第一节图论基本概念 一 基本概念 图 赋权图 图a所示公路交通网络 连线表示公路 节点表示城镇 由于不考虑长度 曲直 坡度 海拔等 所以可用图b表示图a 图a 5 第一节图论基本概念 一 基本概念 图 赋权图 图b为抽象图 既可以表示公路系统又可以表示道路系统 图b 6 第一节图论基本概念 什么叫赋权图 通常我们记图为G V E 其中V代表点的集合 V vi E代表边的集合 E ei 对G中每一条边 vi vj 相应的有权重W a wij 则连同边上的权称为赋权图 7 第一节图论基本概念 2 简单图 连通图 树什么是简单图 若一个图中某条边的两个端点重合 称为环 两点之间多于一条边时 称为多重边 简单图是指没有环 也没有多重边的图 图c为简单图 图c 8 第一节图论基本概念 若图中存在某种点与边的连续交替序列 则称这个点边序列为一条链 如图d所示 图d 9 第一节图论基本概念 连通图若两点之间至少存在一条链 称为连通图 否则称为不连通图 如图e所示为一不连通图 图e 10 第一节图论基本概念 树一个无圈的连通图称为树 如图f所示 图f 11 第一节图论基本概念 3 子图 支撑树子图 设有两图G1 G2 G1 V1 E1 G2 V2 E2 如果V2 V1 E2 E1 则称G2是G1的子图 支撑树 如果图G V E 的支撑子图T V E 是树 则称T为G的一个支撑树 图d是图c的支撑树 12 第二节路网基本概念 1 道路网络构成路段 link 节点 node 路网 network 路径 route 树 tree 小区质心 zonecentroid 小区连杆 centroidconnector 13 第二节路网基本概念 2 路网分解及表达是否要求表示每一条街道 交叉点 是否要求表示出交叉点处的每一次运动 研究结果与研究对象 分区的选择有关 14 第二节路网基本概念 15 第二节路网基本概念 16 第二节路网基本概念 17 第二节路网基本概念 3 路网类型线形路网 例如公路线 铁路线 没有路线选择方格路网 例如城市道路系统 具有多种路线选择具有超路径 hyperpaths 的公交网络具有特定运输模式的多种运输模式网络 18 第二节路网基本概念 4 路段 节点相关矩阵该矩阵用来表示路段与节点间的关系若路网结构中节点j为路段i的上游流入节点 则矩阵元素值为1若路网结构中节点j为路段i的下游流出节点 则矩阵元素值为 1否则矩阵元素值为0每一行包含两个非零元素 其和为0 19 第二节路网基本概念 20 第二节路网基本概念 5 路网赋权V linkflow 路段流量 h pathflow 路径流量 g pathcosts 路径阻抗 c linkcosts 路段阻抗 路段 路口 路网可靠性 21 6 路网模型示意图 22 7 交叉口表示 对偶图法 在实际路网中 交叉口是路线选择的决策点 交叉口转向限制常常改变最优路线的结果 据调查交叉口转向所引起的时间延误达到全部行程时间的17 35 因此 丰富的路口转向限制信息是进行路网描述的关键问题之一 对偶网络法是一种新的能够表达转向限制的路网表达方法 23 对偶网络法的基本思想实质上是将基于节点的网络转化为基于弧段的网络 并建立网络平面拓扑转向表来存储相邻两对偶网络虚拟节点间的转向信息及转向权重 从而将转向限制问题中的转向节点的三元组关系转化为转向弧段的二元组关系 可以直接利用一般的路线优化算法进行求解 24 对偶图的形成 25 对偶链的起点是原网络中的起始弧段 对偶链的终点是原网络中的备选弧段对偶网络中的起始节点和备选节点的组合表示交叉口的转向行为 26 原网络与对偶网络对应关系 27 对偶图法的优点 利用对偶网络法构造对偶网络的算法易于实现 只需稍加转化 就可以将原网络中的转向限制和节点权重转移到对偶链上 从而得到不带有节点权重的对偶网络 在对偶网络中利用一般的路线优化算法求得的最优路线易于 翻译 回原网络中 28 8 交通管制的表示 29 交通管制信息的表示方法 30 第三节无向赋权图优化 最小树问题 设有一连通图G V E 对于每一条边e vi vj 有一权wij 0 最小支撑树 简称最小树 就是图G的支撑树T 并使得 取得最小值 31 第三节无向赋权图优化 最小树问题 二 基本性质和定理1 树的充要条件图G是树的充要条件为 任意两顶点间有且仅有一条链 推论 在树中去掉一条边 则树成为不连通图 由此可知 在点集相同的所有图中 树是含边数最小的连通图 推论 在树中任何两个顶点问添上一条边 恰好得到一个圈 进一步说 如果再从这个圈上任意去掉一条边 可以得到一个树 32 第三节无向赋权图优化 最小树问题 2 最小树的充要条件若T 是图G的一棵树 则当且仅当对T 外的每条边 vi vj 有 时 它是最小树 其中 是树T 内连接点vi和点vj的唯一的链 也就是说 如果将最小树T 外任意一条边 vi vj 加入T 内 得到了唯一的一个圈 那么 vi vj 是这个圈上权最大的边 33 第三节无向赋权图优化 最小树问题 三 最小树问题求最小树方法 破圈法 找圈去大边 无圈为止 即在图中作找一圈 去掉其中权最大的一条边 在余下的图中 重复这个步骤 直到无圈为止 避圈法 避圈加小边 连通为止 即先选择图中权最小的边 以后每步从未选的边中 选一条权最小的边 使与已选的边不构成圈 直到图中所有的点都连通 即不存在孤立点 为止 34 第三节无向赋权图优化 最小树问题 例1 某城市有六个居民点 道路交通图G如图所示 现要沿道路铺设煤气管道 将六个居民点连成网 已知每条道路长度 求使管道长度最短的铺设方案 35 第三节无向赋权图优化 最小树问题 解 由于煤气管道只能沿着道路布设 并要求能到所有的居民点 帮表示煤气管道的图必为道路图的部分图 为了使管道总长最短 图中不应有圈 帮原问题是求G的最小树 即最小树问题 如图1 任取一圈 v1 v2 v6 v1 去掉最大边 v2 v6 图1 36 第三节无向赋权图优化 最小树问题 取圈 v3 v4 v5 v3 去掉边 v5 v4 取圈 v