基于arcgis最短路径分析课件

1 网络分析 1 网络分析概述2 网络分析实现 2 1 网络分析 NetWork 网络是用于实现资源运输和信息交流的一系列相互联接的线性特征组合 1 1什么是网络分析 在GIS中 网络分析是指依据网络拓扑关系 结点与弧段拓扑 弧段的连通性 通过考察网络元素的空间及属性数据 以数学理论模型为基础 对网络的性能特征进行多方面研究的一种分析计算 3 由一系列相互连通的点和线组成 用来描述地理要素 资源 的流动情况 4 1 2网络分析主要内容 网络数据模型网络分析功能网络跟踪 Trace 路径分析 PathFinding 资源分配 Allocation 其他网络分析 1 网络分析 NetWork 5 地理网络的类型 定向网络流向由源 source 至汇 sink 网络中流动的资源自身不能决定流向 如 水流 电流 非定向网络流向不完全由系统控制网络中流动的资源可以决定流向 如 交通系统 6 网络数据模型 网络模型是对现实世界网络的抽象 在模型中 网络由链 Link 结点 Node 站点 Stop 中心 Center 和转向点 Turn 组成 建立一个好的网络模型的关键是清楚地认识现实网络的各种特性与以网络模型的要素 Link Node Stop Center Turn 表示的特性之间的关系 7 网络组成要素 结点 Node 网络中任意两条线段的交点 属性如资源数量等链 Link 连接两个结点的弧段 供物体运营的通道 链间的连接关系由弧段 结点拓扑数据结构来表达 属性如资源流动的时间 速度等中心 Center 网络中位于结点处 具有沿着链收集和发放资源能力的设施 如邮局 电站 水库等站点 Stop 资源沿着网络路径流动时被分配或收集的位置 如邮件投放点 公共汽车站 属性如资源需求量转向点 拐点 Turn 链路相交处 资源流向发生改变的点 8 网络组成要素 9 网络分析功能 网络跟踪路径分析资源分配定位配置分析地址地理编码 10 网络跟踪 Trace 概念 网络中用于研究网络中资源和信息的流向就是网络跟踪的过程 在点污染研究中 可以跟踪污染物从污染源开始 沿河流向下游扩散的过程 在电网应用中 可以根据不同开关的开 关状态 确定电力的流向 数据结构的拓扑基础 网络跟踪中涉及的一个重要概念是 连通性 Connectivity 这定义了网络中弧段与弧段的连接方式 也决定了资源与信息在网络中流动时的走向 11 路径分析 在网络分析过程中 路径系统起着相当重要的作用 事实上很多网络分析的结果都是以路径系统的形式体现出来的 内容 路径分析是用于模拟两个或两个以上地点之间资源流动的路径寻找过程 当选择了起点 终点和路径必须通过的若干中间点后 就可以通过路径分析功能按照指定的条件寻找最优路径 12 路径选择 PathFinding 应用 在远距离送货 物资派发 急救服务和邮递等服务中 经常需要在一次行程中同时访问多个站点 收货方 邮件主人 物资储备站等 如何寻找到一个最短和最经济的路径 保证访问到所有站点 同时最快最省地完成一次行程 这是很多机构经常遇到的问题 这类分析中 道路网络的不同弧段 网络模型中的Link 有不同的影响物流通过的因素 路径选择分析必须充分考虑到这些因素 在保证遍历需要访问的站点的同时 为用户寻找出一条最佳 距离 时间或费用等 的运行路径 13 路径选择 PathFinding 两种方式 Path和Tour ArcInfo有两个路径选择分析命令 Path和Tour 共同点 都是在网络中寻找遍历所有站点最经济的路径 区别 在遍历网络的所有站点过程中 处理站点的顺序有所不同 PATH 必须按照指定的顺序访问网站中的所有站点 例如 救护车必须从急救中心 STOP1 出发 然后前往事故地点 STOP2 然后负责将伤员送往最近的医院 STOP3 最后返回急救中心 STOP4 14 TOUR 进行路径选择分析时 在保证在一次行程中访问所有站点的前提下 访问站点的次序是由TOUR自己决定的 因此TOUR分析的结果既包括所选择的路径 也包括它所确定的最优的访问次序 例如 卡车司机要在一天时间内向若干个站点送货 只要保证在当天内将货物送到每一个站点就可以了 先送哪个站点 后送哪个站点 完全由司机本人决定 TOUR就负责完成确定访问次序 并寻找最经济路径的任务 路径选择 PathFinding 15 资源分配 Allocation 反映现实世界网络中资源的供需关系模型 可以解决资源的有效利用和合理分配 确定最近中心 实现最佳服务 供 Supply 代表一定数量的资源或货物 它们位于被称之为 CENTER 的设施中 需 Demand 指对资源的利用 Allocate分析就是在空间中的一个或多个点之间分配资源的过程 为了实现供需关系 在网络中必然存在资源的运输和流动 资源要么由供方送到需方 要么由需需方到供方索取 16 关于Allocate的两个例子 Supply To Demand的例子 负荷设计 时间与距离损耗估算电能从电站产生 并通过电网传送到客户那里去 在这里 电站就是网络模型中的 Center 因为它可以提供电力供应 电能的客户沿电网的线路 网络模型中的Link 分布 他们产生了 Demand 在这种情况下 资源是通过网络由供方传输到需方来实现资源分配 可用来分析输电系统是否超载 停电的社会 经济影响估计等 17 关于Allocate的两个例子 Demand To Supply的例子 学校选址学校与学生的关系也构成一种在网络中供需分配关系 学校是资源提供方 它负责提供名额供适龄儿童入学 适龄儿童是资源的需求方 他们要求入学 作为需求方的适龄儿童沿街道网络分布 他们产生了对作为供给方的学校的资源 学生名额的需求 这种情况下 资源 的流向是由适龄儿童前往学校 18 Location Allocation 选址和分区 分析Location allocation分析是决定一个或多个服务设施的最优位置的过程 它的定位力求保证服务设施可以以最经济有效的方式为它所服务的人群提供服务 在此分析中 即有定位过程 也有资源分配过程 定位配置分析 选址和分区 19 定位配置分析的实质是线性规划问题 主要的算法包括 p 中心问题 在m个候选点中 选择p个供应点 为n个需求点服务 并使得从服务中心到需求点之间的距离 或时间 费用 最小 中心服务范围的确定 中心服务范围是指一个服务设施在给定的时间或距离内 能够到达的区域 中心资源的分配范围 资源分配就是将空间网络的边或者结点 按照中心的供应量及网络边和结点的需求量 分配给一个中心的过程 用来模拟空间网络上资源的供需关系 Allocation 定位配置分析 选址和分区 20 地址编码与匹配 GeoCoding 利用人们习惯的地址 街道门牌号 信息确定它在地图上的确切位置的技术 地址编码与匹配就是在含地址的表格数据与相关图层之间建立联系 并为表格数据创建一个相应的点要素层 当对表格数据进行编码后 就可以对表格数据进行空间定位查询和分析 地址编码与匹配 GeoCoding 21 网络分析实现理论 教材p313 软件 ArcMapSuperMAP 22 网络分析实现软件 ArcMAP 23 ArcGIS支持的网络类型 几何网络 Geometricnetworks 用于定向网络分析 如 水流 电流等 线 点 GeometricnetworkArcMap中使用UtilityNetworkAnalyst工具条网络数据集 Networkdatasets 用于非定向网络分析 如 交通问题 线 点 转弯 turns Networkdataset使用ArcGISNetworkAnalyst扩展模块 要素类不能同时参与构成GeometricNetwork和NetworkDataset 24 网络分析需要解决的问题 路径分析 点对点最优路径多目标点访问 如物流配送障碍分析服务区域判定 服务范围生成查找最邻近设施导航 导航图生成 交通 医疗 公共安全 教育 公共事业 地方政府 商业等等 25 网络数据集基本概念 名词 道路网络是线要素图层 具有拓扑属性和用于对象流 如交通 的适当属性 26 网络数据集 ArcGIS网络分析所使用的网络存储在网络数据集中它由一系列元素参与网络的要素构成是一种高级的连通性模型可以模拟复杂的场景 如多模的交通网络也可以对复杂的网络属性进行处理 例如各种限制 网络等级等 27 网络数据集由两部分组成 物理网络 用于构建网络并生成网络元素 边线 edges 交汇点 junctions 和转弯 turns 逻辑网络 由一系列属性表组成 用来模拟网络的连通性 定义网络元素的关系 28 构造网络数据集的数据 边线数据 线数据 参与网络数据集的边线被定义为双向的 交汇点数据 点数据 交汇点可以连接任意多条边线 转弯数据 转弯数据 该类型数据专门用于网络数据集 可由线数据或描述边界转向关系的turn表生成 29 天桥和地下通道 在网络中有两种方法来表示天桥和地下通道 边线与交汇点的连通策略 天桥和其下的道路在它们的交叉处都表示无节点的连续路径高程方法 是把天桥和地下通道视为平面要素 如果代表天桥的两条弧段相交于一个节点 高程为0 那么代表天桥下面的街道的两条弧段就相交于另一节点 高程为1 30 1 网络数据集的连通性 Connectivity 连通性可在参与网络的要素类中定义也可以在要素类子类 subtype 中定义可以使用高程字段判断连通性 31 连通组和连通策略 连通组对点或线要素的逻辑分组 用来定义哪些网络元素是连通的 默认情况下 参与要素存在于一个连通组中 连通策略用来定义一个连通组内的网络元素相互之间的连通方式 32 连通组 ConnectivityGroups 默认情况下参与网络要素处于同一个连通组也可以在一个网络数据集中定义多个组 用来进行高级网络建模 多连通组构建多模式网络的基础 33 连通策略 ConnectivityPolicies 线要素 边线 端点连通 Endpoints 任意节点 Anyvertexes 点要素 交汇点 依据边线规则 Honor 交点处连通 Override 高程字段 ElevationField 34 每个子类要素只能只能参与到一个连通组中连通策略在同一个连通组中定义默认情况下 不同连通组中的线要素不连通可以使用点要素定义不同连通组中的线要素的连通性 边线连通性 35 边线连通策略 端点连通 Endpoints 任意节点连通 Anyvertexes 在两条相交线段交点处添加交汇点 junction 可以连通 两个线要素在交点处并没有打断 所以不连通 36 交汇点连通性 可以参与到多个连通组中可以将同一或不同连通组中的线要素连 37 交汇点连通性策略 依边线连通 Honor 由边线决定是否连通交点处连通 Override 38 连通性策略 39 连通性 高程字段 通过应用高程字段 使得网络数据集能够表达线要素的高度起伏关系 通过高程字段判定边线的连通性 通常命名为z elevation或z levels 40 连通性 高程字段 连通 高程值相等 平交路口 41 连通性 高程字段 不连通 高程值不等 天桥和地下通道 42 2 转弯 Turns 转弯是网络中一个弧段到另一个弧段的过渡 描述了两到多个边线元素的转向特征 用于模拟网络中流动资源的通行成本或者限制 转弯成本是完成转弯所需的时间 通过转弯表记录转弯成本 转弯表 一个转弯表有三个项目 交叉的节点数 转弯涉及的弧段数和转弯成本 43 转弯表 ArcInfo Arcview 44 转弯要素 ArcGIS 基于线要素创建的特殊要素类 45 46 3 网络数据集属性 Attributes 可以通过数据集的属性控制网络的走向 比如网络中的要素流动时的阻值 单行路等设置 每个属性都有相应的名称 Name 用途 Usage 单位 Units 数据类型 Datatype 用户可以根据需要添加 删除这些属性 47 网络属性 成本 Cost 限制 Restriction 等级 Hierarchy 描述符 Descriptor 48 成本 Cost 属性 穿过网络元素时累积的某种属性值 如行车时间 步行时间 距离等 通过属性字段确定成本 49 限制 Restriction 布尔表达式 Restricted true 或者Traversable false单行道或封禁的街道可以用字段标示在网络属性表中 字段值可显示单行道的交通方向 如FT表示允许从弧段的始节点到终节点 TF表示允许从弧段的终节点到始节点 而N表示在任何方向都不能通行 50 51 等级 Hierarchy 通过整型值对边线元素进行等级划分用于在网络数据集中查找路径默认支持三个等级如 RoadType1 highway2 majorroad3 localstreet 52 主干道 次干道 支路 启动道路 53 描述符 Descriptor 用于描述网络元素的整体特征 如 车道数 材质等属性信息 54 网络属性的使用 在网络分析中使用属性 可以影响分析结果分析设置 如 Impedance 阻尼 LengthRestriction 限制 Onewaystreets 55 网络分析的流程 56 最佳路径分析 基于道路网络有多个经停位置 在道路网络上找到要达到多个目的地的最佳路径 合理安排经过停靠点的顺序 57 最佳路径分析 Dijkstra算法原理 Dijkstra算法是由荷兰计算机科学家狄克斯特拉 Dijkstra 于1959年提出的 因此又叫狄克斯特拉算法 是从一个顶点到其余各顶点的最短路径算法 解决的是有向图中最短路径问题 58 最佳路径分析 Dijkstra算法 狄克斯特拉算法 首先做有向权图 即成本图 绿色的是节点红色的为权值箭头为可通行的标志 求从0节点到12节点找一条最优路径 59 最佳路径分析 DIJKSTAR算法中要定义两个表 OPEN和CLOSE 其实可以看作链表 他的原理就是把没有遍历的点放在OPEN表中 把从OPEN表中遍历到的最短权值的点放入CLOSE表中当插入CLOSE表中的节点的编号与我们要的重合时算法结束然后按照父节点 pParent 向上递归就可以得到我们要的最优路径了 60 最佳路径分析 第一步 应为OPEN和CLOSE表都是空的 把起点 0节点 插入CLOSE标中 它的权值为0 把起点 0节点 附近的节点 因该为可通行的 插入OPEN表中 第2步 从OPEN表中找到权值最小的节点 把它插入CLOSE表中 把这个节点的可连通的节点插入 表 如果 表中存在要插入的点 如果要插入的节点的权值比已经存在的小 就把已经插入的权值改为最小的 如果要插入的节点的权值比已经存在的大 就忽落它 Dijkstra最短路径算法过程 F S0 B C D E G 2 1 3 2 1 4 2 1 初始化OPEN表和CLOSE表 在OPEN表中放置初始节点S0 g S0 0设n 0 S0是目标节点 No OPEN表为空 No 将OPEN表中最小路径代价的节点S0放入CLOSE中 编号为n 现扩展刚移入CLOSE表的节点S0 S0有两个后继节点 可以扩展 扩展S0子节点C C未在OPEN和CLOSE表中 向OPEN中增加 父节点编码为n 路径为1 扩展S0子节点B B未在OPEN和CLOSE表中 向OPEN中增加 父节点编码为n 路径为2 扩展S0完毕 n n 1 1 将OPEN表中最小路径代价的节点C放入CLOSE中 编号为n 现扩展刚移入CLOSE表的节点C C有三个后继节点 可以扩展 扩展C子节点S0 S0在CLOSE表中 取消扩展 扩展C子节点B B在OPEN表中 但当前路径2不小于OPEN表中B的路径 取消扩展 扩展C子节点E E未在OPEN和CLOSE表中 向OPEN中增加 父节点编码为n 路径为3 扩展C完毕 n n 1 2 将OPEN表中最小路径代价的节点B放入CLOSE中 编号为n 现扩展刚移入CLOSE表的节点B 扩展B子节点S0 S0在CLOSE表中 取消扩展 扩展B子节点C C在CLOSE表中 取消扩展 扩展B子节点D D未在OPEN和CLOSE表中 向OPEN中增加 父节点编码为n 路径为5 扩展B完毕 n n 1 3 将OPEN表中最小路径代价的节点E放入CLOSE中 编号为n 4 5 6 S0 C B E D G 现扩展刚移入CLOSE表的节点E 扩展E子节点C C在CLOSE表中 取消扩展 扩展E子节点G G未在OPEN和CLOSE表中 向OPEN中增加 父节点编码为n 路径为5 扩展E子节点F F未在OPEN和CLOSE表中 向OPEN中增加 父节点编码为n 路径为7 注意 此时虽然已经找到目标节点 但并未找到他的最短路径 需要继续 扩展E完毕 n n 1 将OPEN表中最小路径代价的节点D放入CLOSE中 编号为n 现扩展刚移入CLOSE表的节点D 扩展D子节点B B在CLOSE表中 取消扩展 扩展D子节点F F在OPEN表中 且当前路径6小于OPEN表中B的路径 更新OPEN中节点F的路径代价为6 修改父节点编码为n 扩展D完毕 n n 1 将OPEN表中最小路径代价的节点G放入CLOSE中 编号为n 现扩展刚移入CLOSE表的节点G 扩展G子节点E B在CLOSE表中 取消扩展 扩展G完毕 n n 1 将OPEN表中最小路径代价的节点F放入CLOSE中 编号为n 刚移至CLOSE表的节点就是目标节点 找到最短路径 算法结束 最短路径代价已经求出但路径怎么求 CLOSE表中记录的节点顺序有无规律 F F F F F F 61 63 最佳路径分析 创建分析图层 添加网络位置 具有网络结构的道路网络图层停靠点图层 64 最佳路径分析 设置分析选项 65 最佳路径