地理信息系统路径分析与网络应用.ppt

第8章GIS空间分析,最短路径分析在最短路径选择中，两点之间的距离可以定义为实际的距离，也可定义为两点间的时间、运费、流量等，可定义为使用这条边所需付出的代价。因此，可以对不同的专题内容进行最短路径分析Dijkstra算法基本思想：把图的顶点分为S,T两类,若起始点u到某顶点x的最短通路己求出,则将x归入S,其余归入T,开始时S中只有u,随着程序运行,T的元素逐个转入S,直到目标顶点v转入后结束,一个道路网络中的城市间的链路阻抗,六个节点间的阻抗矩阵,节点1到其他点的最短路径,0-51000-4300-210,0-51000-4300-2-310+50=60,0-51000-4-530+60=900-4-330+20=500-2-310+50=60,0-51000-4-530+60=900-4-3-530+20+10=60,8.3路径分析和网络应用,两者都涉及运动和线要素路径分析是基于栅格数据网络应用是基于矢量并建立拓扑关系的数据共用相同的术语和概念，但是数据格式和数据分析环境不同,8.3.1路径分析,需要一个源栅格、一个费用栅格，耗费距离量测、和生成最小累计耗费路径的算法,1.1源栅格,定义源栅格单元只有源位置有单元值，其他单元格没有数值源位置单元可以是起点也可以作为目标路径分析获得到源栅格单元最小耗费路径,1.2耗费栅格,定义移动通过每个栅格的耗费或阻抗两大特征:1每个单元格的耗费为不同耗费的总和2花费可以表示真实或相对花费耗费栅格生成从列出耗费变量开始然后对每个变量确定栅格单元的数据使用局部运算将单独的耗费栅格加起来局部总和是经过每个栅格单元的耗费,1.3直线距离和耗费距离,直线距离为测量每一个像元到最近源的直线距离；多用在经过路线没有障碍或等同耗费的情况下例如，在救援飞机飞往最近的医院的实例中，直线距离栅格就可以确定从救援飞机所在地点到周围各医院的距离；然而，当救援汽车开往最近医院的实例中，因为地表有各种类型的障碍物，采用不同的路线的耗费不尽相同耗费距离是根据通过每个像元的某个或某几个属性因子的加权得到的实际到达源所需的耗费值例如，翻越一座山直线路程耗费较小，但时间耗费比绕行的时间耗费要多。实际的地表覆盖类型多样，通过直线距离来到达源是不可能的，必须要绕道以避开如河流，高山等的障碍物耗费距离是对直线距离的扩展和延伸。,成本距离的计算原理,accum_cost=a1+(cost_a+cost_b)/2)*Daccum_cost：某一单元b的累计通行成本a1：上一个相邻单元a的累计通行成本cost_a：单元a的成本cost_b：单元b的成本,横向链接的成本距离：(1+2)/2=1.5对角链接的成本距离：1.4142x(1+5)/2=4.2,1.3耗费距离量测,1.3耗费距离量测,在生成距离栅格的同时，还可以生成服务区栅格和方向栅格。服务区栅格：每一个单元格的值表示其被分配到的最近的地物。方向栅格：每一个单元格的值表示其到最近地物的方向。,1.4生成最小累计耗费路径,很容易去计算两个单元间的累计耗费连接两个单元格的每条链路的成本求和但是要找到最小累计耗费路径就有点困难路径要复杂的多。许多不同的路径都可以连接不相邻的两个单元找到最小累计耗费路径是一个迭代过程,Thecostdistanceforeachlink(c)andtheleastaccumulativecostdistancefromeachcell(d)arederivedusingthesourcecells(a)andthecostraster(b).SeeBox18.2forthederivation.,1.5耗费距离量测的改进,现有的量测假定为一个同向性的表面(属性单一、直线距离），实际上耗费表面不一致，因为地表在坡度、高程、坡向均有变化现实的分析还需考虑由高程栅格计算表面距离（测量真实地面距离）垂直和水平因子在计算距离栅格时，除了直接计算直线距离外，还可以考虑耗费权重，比如坡度、土地利用类型等，计算耗费距离栅格。,1.6路径分析的应用,规划道路、管线、沟渠、传输线路提取线性要素,8.3.2网络应用,网络分析是运筹学模型中的一个基本模型，它的根本目的是研究、筹划一项网络工程如何安排，并使其运行效果最好如一定资源的最佳分配，从一地到另一地的运输费用最低等。其基本思想则在于人类活动总是趋于按一定目标选择达到最佳效果的空间位置。GIS网络分析的主要目的：对地理网络（如交通网络）、城市基础设施网络（如各种网线、电力线、电话线、供排水管线等）进行地理分析和模型化。,网络分析（NetworkAnalysis）,矢量数据特有的空间分析方法。网络是由一组互相关联的弧段、结点和它们的属性所组成的模型，用于表达现实世界中的道路、管线等事物。除此之外还要定义一些要素以模拟现实中的供给、需求、中心点等事物。网络分析的基础：线点拓扑关系。依据网络拓扑关系，根据网络的空间数据、属性数据，对网络的特征、性能进行分析。,2.1网络组成,网络中的基本组成部分和属性：链（Link）：网络中流动的管线，如街道、河流、水管等，其状态属性包括阻力和需求。结点（Node）：网络中链的结点，如港口、车站、电站等，其状态属性包括阻力和需求等。结点中又有下面几种特殊的类型。障碍（Barrier），禁止网络中链上流动的点。拐点（Turn），出现在网络链中的分割结点上，状态属性有阻力，如拐弯的时间和限制(如不允许左拐)。中心（Center），是接受或分配资源的位置，如水库、商业中心、电站等。其状态属性包括资源容量，如总的资源量；阻力限额，如中心与链之间的最大距离或时间限制。站点（Stop），在路径选择中资源增减的结点，如库房、汽车站等，其状态属性有要被运输的资源需求，如产品数。,2.2网络要素的表示,1）链弧2)转弯：M条弧相连共有转弯个数N：,4,2,55,35,34,L1,L2,L3,停靠点,3）停靠点、中心的属性,停靠点：直接在相应的结点上附上需求量属性，负为下卸，正值为装载，中心：资源最大容量、服务范围和服务延迟数（在其它中心达到某个数量时才提供服务）。,2.3网络分析应用,网络分析的主要用途是：1选择最佳路径，包括路径的查找和通达度测定；2选择最佳布局中心的位置，包括配置问题和城市交通规划模型。网络分析的基本方法：路径分析最近设施服务区分析资源分配选址分析,2.3.1最佳路径分析,1、在网络中从起点经一系列特定的结点至终点的资源运移的最佳路线，即阻力最小的路径。在网络的节点中寻找累计阻抗最小的路径。由两个节点连成，也可在两点间有一些特定的站点可以帮助运输人员建立多个站点的时间表紧急响应-最短时间到达事故现场2、所谓最佳路经，是求解网络中两点之间阻抗最小的路经，必须按照结点的选择顺序访问网络中的结点。,最短路径分析在最短路径选择中，两点之间的距离可以定义为实际的距离，也可定义为两点间的时间、运费、流量等，可定义为使用这条边所需付出的代价。因此，可以对不同的专题内容进行最短路径分析Dijkstra算法基本思想：把图的顶点分为S,T两类,若起始点u到某顶点x的最短通路己求出,则将x归入S,其余归入T,开始时S中只有u,随着程序运行,T的元素逐个转入S,直到目标顶点v转入后结束,旅行推销员问题,在最短路径分析中添加两个约束推销员必须仅访问选择的各站点一次推销员可以从任一站点出发，但必须回到出发点旅行商分析是无序的路径分析。旅行商可以自己决定访问结点的顺序，目标是旅行路线阻抗总和最小（或接近最小）。,1-3-2-4-5-10,1-3-10-9-5-6-8-7-4-2-1,2.3.2最近设施分析,指在网络上给定一个事件点和一组设施点，为事件点查找以最小耗费能到达的一个或几个设施点。还可以设置查找的阈值，即搜索范围，超过该范围将不再进行查找。首先计算选定地点到所有候选设施的最短路径然后从候选设施中选择最近的设施可以应用于基于定位的服务，如自动柜员机,方形标志显示为从所选地址到最近的消防站点的最短路径,2.3.3服务区分析,服务站点即服务中心点，就是提供某种特定服务的位置，如某一派出所、邮局、社区医院、社区公园等。服务区：是以指定点为中心，在一定阻力范围内，包含所有可通达边的一个区域。如某一社区派出所按行政区划所管辖的社区。服务区分析就是指在满足某种条件的前提下，查找网络上指定的服务站点能够提供服务的区域范围。也可以理解为不考虑中心资源供给量和需求量，而只考虑供给方与需求方之间网络弧段阻力的资源分配。可用于评估分析在某一位置邮局、医院、超市等公共设施一般的服务范围，从而为选择公共设施的最佳位置提供参考。,2.3.4（配置）资源分配,通过网络来研究资源的空间分布例如学校、银行、消防站的选址而资源的分布决定服务的范围响应时间资源分配网络模型由中心点（分配中心或收集中心）及其属性和网络组成。分配有两种形式，一种是由分配中心向四周分配，另一种是由四周向收集中心分配。资源分配的应用包括消防站点分布和求援区划分、学校选址、垃圾收集站点分布，停水停电对区域的社会、经济影响估计等,2分钟响应时间内两所消防站点的服务区域,5分钟响应时间内两所消防站点的服务区域,2.3.5定位-配置（选址分析）,供给、需求和距离的匹配问题供给由设施或点为中心组成需求由点、线或多边形组成供给和需求之间的距离大小常以距离矩阵或距离列表表示定位与分配模型是根据需求点的空间分布，在一些候选点中选择给定数量的供应点以使预定的目标方程达到最佳结果。-最佳分配中心，最优配置。定位问题是指已知需求源的分布，确定在哪里布设供应点最合适的问题；分配问题是确定这些需求源分别受哪个供应点服务的问题。,2.3.5定位-配置（选址分析）,选址分区分析是为了确定一个或多个待建设施的最佳或最优位置，使得设施可以用一种最经济有效的方式为需求方提供服务或者商品。如餐馆、邮局选址，工厂选址、图书馆、学校、医院、消防站、工厂、飞机场、仓库等的最佳位置的确定。,算法在运筹学的理论中，定位与分配模型常可用线性规划求得全局性的最佳结果。由于其计算量以及内存需求巨大，所以在实际应用中常用一些启发式算法来逼近或求得最佳结果。如P中心的定位分配问题：在m个候选点中选择P个供应点为n个需求点服务，使得为这几个需求点服务的总距离(时间或费用)为最少。实际应用中，选择供应点时，并不只是要使总的加权距离为最小，有时需要使总的服务范围为最大，有时又限定服务的最大距离不能超过一定的值，因此仅仅是P中心模型不足以解决更多的实际问题，需要进行修改、扩充。,定位/配置模型,最小距离模型要求所有需求点到最近的供给点的总行程最小最大覆盖模型在指定的时间或距离内达到需求覆盖最大化,公共