基于arcgis最短路径分析_第1页
基于arcgis最短路径分析_第2页
基于arcgis最短路径分析_第3页
基于arcgis最短路径分析_第4页
基于arcgis最短路径分析_第5页
已阅读5页,还剩83页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1网络分析1、网络分析概述2、网络分析实现21.网络分析(NetWork)网络是用于实现资源运输和信息交流的一系列相互联接的线性特征组合。

1.1什么是网络分析?在GIS中,网络分析是指依据网络拓扑关系〔结点与弧段拓扑、弧段的连通性〕,通过考察网络元素的空间及属性数据,以数学理论模型为根底,对网络的性能特征进行多方面研究的一种分析计算。3由一系列相互连通的点和线组成,用来描述地理要素〔资源〕的流动情况。41.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).14TOUR:进行路径选择分析时,在保证在一次行程中访问所有站点的前提下,访问站点的次序是由TOUR自己决定的。因此TOUR分析的结果既包括所选择的路径,也包括它所确定的最优的访问次序。例如:卡车司机要在一天时间内向假设干个站点送货,只要保证在当天内将货物送到每一个站点就可以了,先送哪个站点,后送哪个站点,完全由司机本人决定。TOUR就负责完成确定访问次序,并寻找最经济路径的任务。

路径选择(PathFinding)15资源分配(Allocation)反映现实世界网络中资源的供需关系模型。可以解决资源的有效利用和合理分配;确定最近中心,实现最正确效劳“供(Supply)〞代表一定数量的资源或货物,它们位于被称之为“CENTER〞的设施中。“需(Demand)〞指对资源的利用。Allocate分析就是在空间中的一个或多个点之间分配资源的过程。为了实现供需关系,在网络中必然存在资源的运输和流动。资源要么由供方送到需方,要么由需需方到供方索取。16关于Allocate的两个例子Supply-To-Demand的例子:负荷设计、时间与距离损耗估算电能从电站产生,并通过电网传送到客户那里去。在这里,电站就是网络模型中的“Center〞,因为它可以提供电力供给。电能的客户沿电网的线路(网络模型中的Link)分布,他们产生了“Demand〞。在这种情况下,资源是通过网络由供方传输到需方来实现资源分配。可用来分析输电系统是否超载;停电的社会、经济影响估计等。17关于Allocate的两个例子Demand-To-Supply的例子:学校选址学校与学生的关系也构成一种在网络中供需分配关系。学校是资源提供方,它负责提供名额供适龄儿童入学。适龄儿童是资源的需求方,他们要求入学。作为需求方的适龄儿童沿街道网络分布,他们产生了对作为供给方的学校的资源--学生名额的需求。这种情况下,“资源〞的流向是由适龄儿童前往学校18Location-Allocation(选址和分区)分析 Location-allocation分析是决定一个或多个效劳设施的最优位置的过程,它的定位力求保证效劳设施可以以最经济有效的方式为它所效劳的人群提供效劳。在此分析中,即有定位过程,也有资源分配过程。定位配置分析(选址和分区)19定位配置分析的实质是线性规划问题。主要的算法包括:p-中心问题:在m个候选点中,选择p个供给点,为n个需求点效劳,并使得从效劳中心到需求点之间的距离〔或时间、费用〕最小。中心效劳范围确实定:中心效劳范围是指一个效劳设施在给定的时间或距离内,能够到达的区域。中心资源的分配范围:资源分配就是将空间网络的边或者结点,按照中心的供给量及网络边和结点的需求量,分配给一个中心的过程,用来模拟空间网络上资源的供需关系(Allocation〕。定位配置分析(选址和分区)20地址编码与匹配(GeoCoding) 利用人们习惯的地址(街道门牌号)信息确定它在地图上确实切位置的技术.地址编码与匹配就是在含地址的表格数据与相关图层之间建立联系,并为表格数据创立一个相应的点要素层。当对表格数据进行编码后,就可以对表格数据进行空间定位查询和分析地址编码与匹配(GeoCoding)21网络分析实现

理论:〔教材p313〕

软件:

ArcMap

SuperMAP22网络分析实现

软件:ArcMAP23ArcGIS支持的网络类型几何网络〔Geometricnetworks〕用于定向网络分析〔如:水流、电流等〕线&点->GeometricnetworkArcMap中使用UtilityNetworkAnalyst工具条网络数据集〔Networkdatasets〕用于非定向网络分析〔如:交通问题〕线,点&转弯〔turns〕-> Networkdataset使用ArcGISNetworkAnalyst扩展模块*要素类不能同时参与构成GeometricNetwork和NetworkDataset24网络分析需要解决的问题

路径分析:点对点最优路径多目标点访问,如物流配送障碍分析效劳区域判定:效劳范围生成查找最邻近设施导航:导航图生成交通,医疗,公共平安,教育,公共事业,地方政府,商业等等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-levels40连通性:高程字段连通〔高程值相等〕:平交路口41连通性:高程字段不连通〔高程值不等〕:天桥和地下通道42(2)转弯(Turns)转弯是网络中一个弧段到另一个弧段的过渡。描述了两到多个边线元素的转向特征。用于模拟网络中流动资源的通行本钱或者限制。转弯本钱是完成转弯所需的时间。通过转弯表记录转弯本钱。转弯表:一个转弯表有三个工程:交叉的节点数、转弯涉及的弧段数和转弯本钱43转弯表:ArcInfo/Arcview44转弯要素:ArcGIS基于线要素创立的特殊要素类4546〔3)网络数据集属性〔Attributes〕可以通过数据集的属性控制网络的走向。比方网络中的要素流动时的阻值、单行路等设置。每个属性都有相应的名称〔Name〕、用途〔Usage〕、单位〔Units〕、数据类型〔Datatype〕。用户可以根据需要添加/删除这些属性。47网络属性本钱〔Cost〕限制〔Restriction〕等级〔Hierarchy〕描述符〔Descriptor〕48本钱〔Cost〕属性穿过网络元素时累积的某种属性值。如行车时间,步行时间,距离等。通过属性字段确定本钱49限制〔Restriction〕布尔表达式:Restricted(true)或者Traversable(false单行道或封禁的街道可以用字段标示在网络属性表中。字段值可显示单行道的交通方向,如FT表示允许从弧段的始节点到终节点。TF表示允许从弧段的终节点到始节点,而N表示在任何方向都不能通行。5051等级〔Hierarchy〕通过整型值对边线元素进行等级划分用于在网络数据集中查找路径默认支持三个等级如:RoadType

1=highway2=majorroad3=localstreet52主干道次干道支路启动道路53描述符〔Descriptor〕用于描述网络元素的整体特征。如:车道数、材质等属性信息。54网络属性的使用在网络分析中使用属性,可以影响分析结果分析设置〔如〕:Impedance〔阻尼〕–LengthRestriction〔限制〕–Onewaystreets55网络分析的流程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表中,把这个节点的可连通的节点插入OPEN表,如果OPEN表中存在要插入的点,如果要插入的节点的权值比已经存在的小,就把已经插入的权值改为最小的,如果要插入的节点的权值比已经存在的大,就忽落它.Dijkstra最短路径算法过程FS0BCDEG21321421初始化OPEN表和CLOSE表OPEN表路径父节点编码节点号变量n0CLOSE表路径父节点编码节点号编号在OPEN表中放置初始节点S0,g〔S0〕=0设n=0。S0

是目标节点?NoOPEN表为空?No将OPEN表中最小路径代价的节点S0放入CLOSE中,编号为n。现扩展刚移入CLOSE表的节点S0S0有两个后继节点,可以扩展扩展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。20B现扩展刚移入CLOSE表的节点CC有三个后继节点,可以扩展扩展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。31E现扩展刚移入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。52D453G73F564F6S0CBEDG现扩展刚移入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表中记录的节点顺序有

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论