第十五章路径分析和网络应用ppt课件

《第十五章路径分析和网络应用ppt课件》由会员分享，可在线阅读，更多相关《第十五章路径分析和网络应用ppt课件（29页珍藏版）》请在装配图网上搜索。

1、第十五章第十五章 路径分析和网络应用路径分析和网络应用2014-4-30 路径分析是基于路径分析是基于栅格数据栅格数据来确定来确定像元间的像元间的最小耗费路径。最小耗费路径。应用：应用：在道路、管线、运河等建设中耗费最低或环境影响最小。在道路、管线、运河等建设中耗费最低或环境影响最小。网络应用网络应用是基于是基于矢量矢量数据数据并已建立拓扑关系的网络并已建立拓扑关系的网络。应用：应用：找到网络中节点间的最短路径、查找最近设施、解决定位找到网络中节点间的最短路径、查找最近设施、解决定位-配置问配置问题等。题等。栅格和矢量数据在栅格和矢量数据在GIS分析应用中的区别：分析应用中的区别：路径分析是基

2、于路径分析是基于栅格数据栅格数据来确定来确定像元间的像元间的最小耗费路径。最小耗费路径。所需要素所需要素：源栅格源栅格：源栅格中仅源像元有像元值，所有其他像元都不赋值。源栅格中仅源像元有像元值，所有其他像元都不赋值。源像元既可以是起点也可以是目标点或终点，路径分析得到的是一个像元对于源像元的最小耗费路径。耗费栅格耗费栅格：耗费栅格定义了穿过每个像元的耗费或阻抗。耗费栅格定义了穿过每个像元的耗费或阻抗。每个像元的耗费通常是不同耗费的总和，耗费可以是实际耗费也可以是相对耗费。耗费距离量测耗费距离量测：基于节点基于节点-链接像元的表示法。链接像元的表示法。生成生成最小累积耗费路径最小累积耗费路径：对

3、于一个给定耗费栅格，通过计算连接两个像对于一个给定耗费栅格，通过计算连接两个像元的每条连接的总耗费，可计算这两个像元间的累计耗费，得到最小。元的每条连接的总耗费，可计算这两个像元间的累计耗费，得到最小。15.115.1路径路径分析分析 耗费距离量测耗费距离量测：节点节点像元的中心像元的中心 链接链接横向链接或对角线链接横向链接或对角线链接横向链接的耗费距离是连接像元的平均耗费，如(1+2)/2=1.5对角线链接的耗费距离是平均耗费的1.44倍，如1.414*(1+5)/2=4.2从像元a到像元b的累积耗费是两个横向链接耗费之和，如1.0和3.5之和从像元a到像元c的累积耗费是对角线链接和横向链

4、接的耗费之和，如4.2和2.5之和路径是很复杂的，连接两个并不直接紧邻的两个像元之间的路径有许多。路径是很复杂的，连接两个并不直接紧邻的两个像元之间的路径有许多。寻找最小累积耗费路径是一个迭代过程寻找最小累积耗费路径是一个迭代过程最小累积成本格网的生成最小累积成本格网的生成ArcGIS中的中的路径分析路径分析成本距离成本距离 用耗费栅格计算每个像元到距用耗费栅格计算每个像元到距离它最近的源像元的最小累积耗费，也能离它最近的源像元的最小累积耗费，也能生成方向栅格和配置栅格；生成方向栅格和配置栅格；成本路径成本路径 用距离和方向栅格，生成任意用距离和方向栅格，生成任意像元的最小耗费路径。像元的最小

5、耗费路径。路径分析的应用路径分析的应用 在道路、管线、运河以及交通线的规划方面非常有用；在道路、管线、运河以及交通线的规划方面非常有用；还可用于从低分辨率数字影像上提取线性特征，如道路还可用于从低分辨率数字影像上提取线性特征，如道路和河流。和河流。1、网络：、网络：一个具有目标运动的合适属性的线要素系统。一个具有目标运动的合适属性的线要素系统。2、网络基本要素：、网络基本要素：节点节点网络中分布的中间点、交网络中分布的中间点、交点等点等链链路路连接结点并具有运输能力连接结点并具有运输能力的线段（弧段）的线段（弧段）网络的网络的组成：组成：15.215.2网络网络网络要素的网络要素的主要属性：主

6、要属性：1、链路及链路阻抗、链路及链路阻抗 链路在道路网络中由两个节点所确定的路段，也称为边，是网络的基本要素 阻抗穿越链路的耗费不仅考虑链路的实际长度 速度限制、交通情况的变化 通行时间是方向性的不同方向所耗费的时间不同 存在离散的分段特性一天内的不同时段，一周内的不同天等通行时间都可能不同2、节点和转弯阻抗、节点和转弯阻抗 节点链路的一个交会点 如果链路与方向有关，链路的起点和终点都是节点（始节点、到节点）转弯从一个链路到另一个链路的过渡发生在两个链路交叉或交会的节点处 转弯阻抗完成转弯所需的时间，通常是有方向性的 直行可能花5秒钟，右转要等10秒钟，左转要等30秒 负值的转弯阻抗说明限制

7、转弯，如单行道 转弯表赋予网络中的转弯阻抗值3、单行道或禁行道、单行道或禁行道可在属性表中指定字段指定字段标示：F表示非单行道 T表示单行道 N任何方向都不能通行单行道的方向取决于线段的始节点和终节点4、天桥和地下通道、天桥和地下通道交叉处表示为无节点的连续路径的非平面要素把天桥和地下通道视为平面要素：两段弧表示天桥交于一个节点，另两段弧表示天桥下的道路交于另一个节点15.315.3网络拼接网络拼接建立道路网络包括三个步骤：建立道路网络包括三个步骤：聚集网络的线要素聚集网络的线要素 创建网络的基本拓扑关系创建网络的基本拓扑关系 赋予网络属性赋予网络属性 链路阻抗值通常基于通行时间 道路分类以及

8、速度限制 单行道 转弯表生成包括网络中所有十字路口和可能的拐弯或限制，如停止标记等 见书P394图17.8-9从甲地到乙地的最短路径是什么？从甲地到乙地的最短路径是什么？如何设定一个服务中心？特定位置的服务中心或服务范围？如何设定一个服务中心？特定位置的服务中心或服务范围？从一个位置到另一个位置的通行程度如何？从一个位置到另一个位置的通行程度如何？从出发地到目的地，有多少条可行路线？从出发地到目的地，有多少条可行路线？如何在街道图上定位一个发生的事件？如何在街道图上定位一个发生的事件？第第四四节节 网络应用网络应用一、最短路径分析一、最短路径分析二、最近设施二、最近设施三、配置（服务区）三、配

9、置（服务区）四四、定位、定位-配置配置一般的线状空间数据必须经处理产生一般的线状空间数据必须经处理产生网网络数据集络数据集（network dataset）才能用）才能用于网络分析，网络数据集必须有于网络分析，网络数据集必须有运行成运行成本属性本属性（如长度）。（如长度）。一、最短路径分析（基于一、最短路径分析（基于矢量数据矢量数据）在网络中在网络中寻找节点间累积阻抗最小的寻找节点间累积阻抗最小的路径。路径。核心算法：核心算法：求两点间的权数最小路径。求两点间的权数最小路径。常用的算法是常用的算法是Dijkstra算法算法 应用广泛：应用广泛：帮助货车司机为多个交货点建立送货时间表帮助货车司机

10、为多个交货点建立送货时间表 联系事故处理站、事故地点和医院等紧急救援服务联系事故处理站、事故地点和医院等紧急救援服务 帮助司机找到导航线路确定最佳路线帮助司机找到导航线路确定最佳路线nDijkstra算法的算法的基本思想基本思想 按路径长度递增顺序求最短路径算法按路径长度递增顺序求最短路径算法。nDijkstra 算法的算法的基本步骤基本步骤 令令d(Y,X)表示点表示点Y到到X的距离，的距离，D(X)表示起始点表示起始点S到到X的最短距离。在搜索中还需假定两的最短距离。在搜索中还需假定两点之间的距离不为负。点之间的距离不为负。1）对起始点）对起始点S作标记，作标记，计算计算S点到所有其他节点

11、的距离点到所有其他节点的距离D(X)，最小节点记为最小节点记为Y。2）对所有未作标记的点按以下公式计算距离：）对所有未作标记的点按以下公式计算距离：D(X)minD(X),d(Y,X)D(Y)其中其中Y是最后一个作标记的点。是最后一个作标记的点。取具有最小值的取具有最小值的D(X)。若最小值的。若最小值的D(X,Y)为为，则说明，则说明S到所有未标记点到所有未标记点都没有回路，算法终止；否则继续。都没有回路，算法终止；否则继续。3）如果）如果Y等于等于终结点终结点T，则已找到，则已找到S到到T的最短路径，算法终止；否则转到的最短路径，算法终止；否则转到2）vDijkstra算法算法两点不直接相

12、连则为不通；两点不直接相连则为不通；路径长度为路径上边数的权值之和；路径长度为路径上边数的权值之和；最短路径为两结点权值之和最小的路径。最短路径为两结点权值之和最小的路径。1）对）对A作标记，计算作标记，计算A到到所有所有未未标记点的距离标记点的距离D(B)、D(C)、D(D)、D(E)D(B)=4，D(C)=，D(D)=1，D(E)=2 最小值为D(D)=12）对）对D作标记，按公式计算作标记，按公式计算D(B)、D(C)、D(E)D(B)=minD(B),d(D,B)+D(D)=min4,+1=4D(C)=minD(C),d(D,C)+D(D)=min,9+1=10D(E)=minD(E)

13、,d(D,E)+D(D)=min2,2+1=2 最小值为D(E)=23）对）对E作标记，计算作标记，计算D(B)、D(C)D(B)=minD(B),d(E,B)+D(E)=min4,1+2=3D(C)=minD(C),d(E,C)+D(E)=min10,6+2=8 最小值为D(B)=34）对）对B作标记，计算作标记，计算D(C)D(C)=minD(C),d(B,C)+D(B)=min8,7+3=85）对对C作标记，已是终结点结束搜索。作标记，已是终结点结束搜索。根据顺序记录的标记点以及最小值的取值根据顺序记录的标记点以及最小值的取值情况，可得到最短路径为情况，可得到最短路径为AEC，最短路径为

14、，最短路径为8。如图，如图，搜索搜索A到到C的最短路径？的最短路径？路径（路径（Route）是网络分析的）是网络分析的基础，路径必须经过有关站点基础，路径必须经过有关站点（stop），避开障碍点），避开障碍点（barrier），以交通成本最低），以交通成本最低产生分析结果。产生分析结果。ArcGIS中的中的最短路径分析最短路径分析最短路径分析是基于矢量的，利用现有网络；最短路径分析是基于矢量的，利用现有网络；路径分析是基于栅格的，用源栅格和耗费栅格来寻求最低耗费路径。路径分析是基于栅格的，用源栅格和耗费栅格来寻求最低耗费路径。1和和2哪个去合适呢？哪个去合适呢？12居民分布点居民分布点服务点服

15、务点二、二、最近设施最近设施在网络上的任何地点寻找最近设施，如医院、消防站或在网络上的任何地点寻找最近设施，如医院、消防站或ATM机）机）寻找最近设施的问题寻找最近设施的问题：最近设施算法首先计算选定地点到所有备选设施的最短路径 然后从备选设施中选取最近设施 可用于基于定位的服务（LBS），如找到最近的ATM取款机等最近设施（最近设施（Closest Facility）与路径相似，设施（）与路径相似，设施（facility）和）和事件（事件（incident）之间的关系类似于两个站点。可以为每个事件）之间的关系类似于两个站点。可以为每个事件查找单个最近设施，也可以同时查找多个设施，得到一个事件

16、和查找单个最近设施，也可以同时查找多个设施，得到一个事件和多个设施之间的最佳路径。多个设施之间的最佳路径。ArcGIS中的中的最近设施最近设施图书馆设在哪儿合图书馆设在哪儿合适呢？适呢？居民分布点居民分布点公共设施公共设施划分服务区的问题划分服务区的问题三三、配置配置/服务区服务区通过网络研究资源的空间分布。通过网络研究资源的空间分布。设施的分布决定了资源的服务范围。设施的分布决定了资源的服务范围。在紧急服务中，一般是以反应时间来衡量效率的在紧急服务中，一般是以反应时间来衡量效率的服务区（服务区（Service Area）是路径分析的扩展，给定交通成本，产）是路径分析的扩展，给定交通成本，产生

17、离开服务点所有方向的最远路径，将路径最远点连接起来形成生离开服务点所有方向的最远路径，将路径最远点连接起来形成最大范围即服务区。最大范围即服务区。ArcGIS中的中的服务区服务区 用目标与约束集来解决供与需的匹配问题用目标与约束集来解决供与需的匹配问题。通过网络模拟，根据需求点的空间通过网络模拟，根据需求点的空间分布，在一些候选点中选择给定数量的供应点以使预定的目标方程达到分布，在一些候选点中选择给定数量的供应点以使预定的目标方程达到供与需供与需的的最佳最佳匹配匹配。四四、定位、定位-配置配置定位问题定位问题是指已知是指已知需求源需求源的分布，确定在哪里布设的分布，确定在哪里布设供应点供应点最

18、合适的问题最合适的问题。分配问题分配问题是确定这些需求源分别受哪个供应点服务的问题。是确定这些需求源分别受哪个供应点服务的问题。一般用于规划重要的公共设施：一般用于规划重要的公共设施：普通设施普通设施医院、学校、养老院等医院、学校、养老院等 应急设施应急设施消防站、急救站等消防站、急救站等 在运筹学的理论中，定位与分配模型常可用在运筹学的理论中，定位与分配模型常可用线性规划线性规划求得全局性的最佳结果。由求得全局性的最佳结果。由于其计算量以及内存需求巨大，所以在实际应用中常用一些于其计算量以及内存需求巨大，所以在实际应用中常用一些启发式算法启发式算法来逼近或求来逼近或求得最佳结果。得最佳结果。

19、常用模型包括：常用模型包括：最小距离模型（最小距离模型（P-中值定位模型）：中值定位模型）：在在m个候选点中选择个候选点中选择P个供应点为个供应点为n个需求点服务，个需求点服务，使得为这几个需求点服务的总距离使得为这几个需求点服务的总距离(或时间或费用或时间或费用)为最少。常用于为最少。常用于图书馆、食物配送、图书馆、食物配送、健康设施、垃圾站设置等。健康设施、垃圾站设置等。最大覆盖模型：最大覆盖模型：指定时间或距离到达需求的覆盖面最大，常用于指定时间或距离到达需求的覆盖面最大，常用于紧急救护、消防服务等。紧急救护、消防服务等。理解基于矢量的最短路径分析与基于栅格的路径分析的不理解基于矢量的最短路径分析与基于栅格的路径分析的不同；同；理解理解网络网络应用中最近设施、服务区及定位应用中最近设施、服务区及定位-配置的含义，配置的含义，及其及其在现实生活中应用在现实生活中应用。复习题复习题