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

第十五章路径分析和网络应用2014-4-30

路径分析是基于栅格数据来确定像元间的最小耗费路径。应用：在道路、管线、运河等建设中耗费最低或环境影响最小。网络应用是基于矢量数据并已建立拓扑关系的网络。应用：找到网络中节点间的最短路径、查找最近设施、解决定位-配置问题等。栅格和矢量数据在GIS分析应用中的区别：路径分析是基于栅格数据来确定像元间的最小耗费路径。所需要素：源栅格：源栅格中仅源像元有像元值，所有其他像元都不赋值。源像元既可以是起点也可以是目标点或终点，路径分析得到的是一个像元对于源像元的最小耗费路径。耗费栅格：耗费栅格定义了穿过每个像元的耗费或阻抗。每个像元的耗费通常是不同耗费的总和，耗费可以是实际耗费也可以是相对耗费。

耗费距离量测：基于节点-链接像元的表示法。

生成最小累积耗费路径：对于一个给定耗费栅格，通过计算连接两个像元的每条连接的总耗费，可计算这两个像元间的累计耗费，得到最小。15.1路径分析

耗费距离量测：节点——像元的中心链接——横向链接或对角线链接横向链接的耗费距离是连接像元的平均耗费，如(1+2)/2=1.5对角线链接的耗费距离是平均耗费的1.44倍，如1.414*[(1+5)/2]=4.2从像元a到像元b的累积耗费是两个横向链接耗费之和，如1.0和3.5之和从像元a到像元c的累积耗费是对角线链接和横向链接的耗费之和，如4.2和2.5之和路径是很复杂的，连接两个并不直接紧邻的两个像元之间的路径有许多。寻找最小累积耗费路径是一个迭代过程最小累积成本格网的生成ArcGIS中的路径分析成本距离用耗费栅格计算每个像元到距离它最近的源像元的最小累积耗费，也能生成方向栅格和配置栅格；成本路径用距离和方向栅格，生成任意像元的最小耗费路径。路径分析的应用在道路、管线、运河以及交通线的规划方面非常有用；还可用于从低分辨率数字影像上提取线性特征，如道路和河流。1、网络：一个具有目标运动的合适属性的线要素系统。2、网络基本要素：节点网络中分布的中间点、交点等链路连接结点并具有运输能力的线段（弧段）网络的组成：15.2网络网络要素的主要属性：1、链路及链路阻抗链路——在道路网络中由两个节点所确定的路段，也称为边，是网络的基本要素阻抗——穿越链路的耗费不仅考虑链路的实际长度速度限制、交通情况的变化通行时间是方向性的——不同方向所耗费的时间不同存在离散的分段特性——一天内的不同时段，一周内的不同天等通行时间都可能不同2、节点和转弯阻抗节点——链路的一个交会点

如果链路与方向有关，链路的起点和终点都是节点（始节点、到节点）转弯——从一个链路到另一个链路的过渡发生在两个链路交叉或交会的节点处转弯阻抗——完成转弯所需的时间，通常是有方向性的直行可能花5秒钟，右转要等10秒钟，左转要等30秒负值的转弯阻抗说明限制转弯，如单行道转弯表——赋予网络中的转弯阻抗值3、单行道或禁行道可在属性表中指定字段标示：F—表示非单行道T—表示单行道N—任何方向都不能通行单行道的方向取决于线段的始节点和终节点4、天桥和地下通道交叉处表示为无节点的连续路径的非平面要素把天桥和地下通道视为平面要素：两段弧表示天桥交于一个节点，另两段弧表示天桥下的道路交于另一个节点15.3网络拼接建立道路网络包括三个步骤：聚集网络的线要素创建网络的基本拓扑关系赋予网络属性链路阻抗值——通常基于通行时间道路分类以及速度限制单行道转弯表——生成包括网络中所有十字路口和可能的拐弯或限制，如停止标记等见书P394图17.8-9从甲地到乙地的最短路径是什么？如何设定一个服务中心？特定位置的服务中心或服务范围？从一个位置到另一个位置的通行程度如何？从出发地到目的地，有多少条可行路线？如何在街道图上定位一个发生的事件？

第四节网络应用一、最短路径分析二、最近设施三、配置（服务区）四、定位-配置…一般的线状空间数据必须经处理产生网络数据集（networkdataset）才能用于网络分析，网络数据集必须有运行成本属性（如长度）。一、最短路径分析（基于矢量数据）在网络中寻找节点间累积阻抗最小的路径。核心算法：求两点间的权数最小路径。

常用的算法是Dijkstra算法

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

1）对起始点S作标记，计算S点到所有其他节点的距离D(X)，最小节点记为Y。

2）对所有未作标记的点按以下公式计算距离：D(X)＝min{D(X),d(Y,X)＋D(Y)}其中Y是最后一个作标记的点。取具有最小值的D(X)。若最小值的D(X,Y)为∞，则说明S到所有未标记点都没有回路，算法终止；否则继续。3）如果Y等于终结点T，则已找到S到T的最短路径，算法终止；否则转到2）Dijkstra算法两点不直接相连则为不通；路径长度为路径上边数的权值之和；最短路径为两结点权值之和最小的路径。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)=min{D(B),d(D,B)+D(D)}=min{4,∞+1}=4D(C)=min{D(C),d(D,C)+D(D)}=min{∞,9+1}=10D(E)=min{D(E),d(D,E)+D(D)}=min{2,2+1}=2最小值为D(E)=23）对E作标记，计算D(B)、D(C)D(B)=min{D(B),d(E,B)+D(E)}=min{4,1+2}=3D(C)=min{D(C),d(E,C)+D(E)}=min{10,6+2}=8最小值为D(B)=34）对B作标记，计算D(C)D(C)=min{D(C),d(B,C)+D(B)}=min{8,7+3}=85）对C作标记，已是终结点结束搜索。根据顺序记录的标记点以及最小值的取值情况，可得到最短路径为A－E－C，最短路径为8。如图，搜索A到C的最短路径？路径（Route）是网络分析的基础，路径必须经过有关站点（stop），避开障碍点（barrier），以交通成本最低产生分析结果。ArcGIS中的最短路径分析最短路径分析是基于矢量的，利用现有网络；路径分析是基于栅格的，用源栅格和耗费栅格来寻求最低耗费路径。1和2哪个去合适呢？12居民分布点服务点二、最近设施在网络上的任何地点寻找最近设施，如医院、消防站或ATM机）寻找最近设施的问题：最近设施算法首先计算选定地点到所有备选设施的最短路径然后从备选设施中选取最近设施可用于基于定位的服务（LBS），如找到最近的ATM取款机等最近设施（ClosestFacility）与路径相似，设施（facility）和事件（incident）之间的关系类似于两个站点。可以为每个事件查找单个最近设施，也可以同时查找多个设施，得到一个事件和多个设施之间的最佳路径。ArcGIS中的最近设施图书馆设在哪儿合适呢？居民分布点公共设施划分服务区的问题三、配置/服务区通过网络研究资源的空间分布。设施的分布决定了资源的服务范围。在紧急服务中，一般是以反应时间来衡量效率的服务区（ServiceArea）是路径分析的扩展，给定交通成本，产生离开服务点所有方向的最远路径，将路径最远点连接起来形成最大范围即服务区。ArcGIS中的服务区用目标与约束集来解决供与需的匹配问题。通过网络模拟，根据需求点的空间分布，在一些候选点中选择给定数量的供应点以使预定的目标方程达到供与需的最佳匹配。四、定位-配置定位问题是指已知需求源的分布，确定在哪里布设供应点最合适的问题。分配问题是确定这些需求源分别受哪个供应点服务的问题。一般用于规划重要的公共设施：普通设施——医院、学校、养老院等应急设施——消防站、急救站等在运筹学的理论中，定位与分配模型常可用线性规划求得全局性的最佳结果。由于其计算量以及内存需求巨大，所以在实际应用中常用一些启发式算法来逼近或求得最佳结果。

常用模型包括：最小距离模型（