第十五章路徑分析和網(wǎng)絡(luò)應(yīng)用

第十五章路徑分析和網(wǎng)絡(luò)應(yīng)用2014-4-30

路徑分析是基于柵格數(shù)據(jù)來確定像元間的最小耗費路徑。應(yīng)用：在道路、管線、運河等建設(shè)中耗費最低或環(huán)境影響最小。網(wǎng)絡(luò)應(yīng)用是基于矢量數(shù)據(jù)并已建立拓撲關(guān)系的網(wǎng)絡(luò)。應(yīng)用：找到網(wǎng)絡(luò)中節(jié)點間的最短路徑、查找最近設(shè)施、解決定位-配置問題等。柵格和矢量數(shù)據(jù)在GIS分析應(yīng)用中的區(qū)別：路徑分析是基于柵格數(shù)據(jù)來確定像元間的最小耗費路徑。所需要素：源柵格：源柵格中僅源像元有像元值，所有其他像元都不賦值。源像元既可以是起點也可以是目標點或終點，路徑分析得到的是一個像元對于源像元的最小耗費路徑。耗費柵格：耗費柵格定義了穿過每個像元的耗費或阻抗。每個像元的耗費通常是不同耗費的總和，耗費可以是實際耗費也可以是相對耗費。

耗費距離量測：基于節(jié)點-鏈接像元的表示法。

生成最小累積耗費路徑：對于一個給定耗費柵格，通過計算連接兩個像元的每條連接的總耗費，可計算這兩個像元間的累計耗費，得到最小。15.1路徑分析

耗費距離量測：節(jié)點——像元的中心鏈接——橫向鏈接或?qū)蔷€鏈接橫向鏈接的耗費距離是連接像元的平均耗費，如(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之和路徑是很復(fù)雜的，連接兩個并不直接緊鄰的兩個像元之間的路徑有許多。尋找最小累積耗費路徑是一個迭代過程最小累積成本格網(wǎng)的生成ArcGIS中的路徑分析成本距離用耗費柵格計算每個像元到距離它最近的源像元的最小累積耗費，也能生成方向柵格和配置柵格；成本路徑用距離和方向柵格，生成任意像元的最小耗費路徑。路徑分析的應(yīng)用在道路、管線、運河以及交通線的規(guī)劃方面非常有用；還可用于從低分辨率數(shù)字影像上提取線性特征，如道路和河流。1、網(wǎng)絡(luò)：一個具有目標運動的合適屬性的線要素系統(tǒng)。2、網(wǎng)絡(luò)基本要素：節(jié)點網(wǎng)絡(luò)中分布的中間點、交點等鏈路連接結(jié)點并具有運輸能力的線段（弧段）網(wǎng)絡(luò)的組成：15.2網(wǎng)絡(luò)網(wǎng)絡(luò)要素的主要屬性：1、鏈路及鏈路阻抗鏈路——在道路網(wǎng)絡(luò)中由兩個節(jié)點所確定的路段，也稱為邊，是網(wǎng)絡(luò)的基本要素阻抗——穿越鏈路的耗費不僅考慮鏈路的實際長度速度限制、交通情況的變化通行時間是方向性的——不同方向所耗費的時間不同存在離散的分段特性——一天內(nèi)的不同時段，一周內(nèi)的不同天等通行時間都可能不同2、節(jié)點和轉(zhuǎn)彎阻抗節(jié)點——鏈路的一個交會點

如果鏈路與方向有關(guān)，鏈路的起點和終點都是節(jié)點（始節(jié)點、到節(jié)點）轉(zhuǎn)彎——從一個鏈路到另一個鏈路的過渡發(fā)生在兩個鏈路交叉或交會的節(jié)點處轉(zhuǎn)彎阻抗——完成轉(zhuǎn)彎所需的時間，通常是有方向性的直行可能花5秒鐘，右轉(zhuǎn)要等10秒鐘，左轉(zhuǎn)要等30秒負值的轉(zhuǎn)彎阻抗說明限制轉(zhuǎn)彎，如單行道轉(zhuǎn)彎表——賦予網(wǎng)絡(luò)中的轉(zhuǎn)彎阻抗值3、單行道或禁行道可在屬性表中指定字段標示：F—表示非單行道T—表示單行道N—任何方向都不能通行單行道的方向取決于線段的始節(jié)點和終節(jié)點4、天橋和地下通道交叉處表示為無節(jié)點的連續(xù)路徑的非平面要素把天橋和地下通道視為平面要素：兩段弧表示天橋交于一個節(jié)點，另兩段弧表示天橋下的道路交于另一個節(jié)點15.3網(wǎng)絡(luò)拼接建立道路網(wǎng)絡(luò)包括三個步驟：聚集網(wǎng)絡(luò)的線要素創(chuàng)建網(wǎng)絡(luò)的基本拓撲關(guān)系賦予網(wǎng)絡(luò)屬性鏈路阻抗值——通?；谕ㄐ袝r間道路分類以及速度限制單行道轉(zhuǎn)彎表——生成包括網(wǎng)絡(luò)中所有十字路口和可能的拐彎或限制，如停止標記等見書P394圖17.8-9從甲地到乙地的最短路徑是什么？如何設(shè)定一個服務(wù)中心？特定位置的服務(wù)中心或服務(wù)范圍？從一個位置到另一個位置的通行程度如何？從出發(fā)地到目的地，有多少條可行路線？如何在街道圖上定位一個發(fā)生的事件？

第四節(jié)網(wǎng)絡(luò)應(yīng)用一、最短路徑分析二、最近設(shè)施三、配置（服務(wù)區(qū)）四、定位-配置…一般的線狀空間數(shù)據(jù)必須經(jīng)處理產(chǎn)生網(wǎng)絡(luò)數(shù)據(jù)集（networkdataset）才能用于網(wǎng)絡(luò)分析，網(wǎng)絡(luò)數(shù)據(jù)集必須有運行成本屬性（如長度）。一、最短路徑分析（基于矢量數(shù)據(jù)）在網(wǎng)絡(luò)中尋找節(jié)點間累積阻抗最小的路徑。核心算法：求兩點間的權(quán)數(shù)最小路徑。

常用的算法是Dijkstra算法

應(yīng)用廣泛：幫助貨車司機為多個交貨點建立送貨時間表聯(lián)系事故處理站、事故地點和醫(yī)院等緊急救援服務(wù)幫助司機找到導(dǎo)航線路確定最佳路線…Dijkstra算法的基本思想按路徑長度遞增順序求最短路徑算法。Dijkstra算法的基本步驟令d(Y,X)表示點Y到X的距離，D(X)表示起始點S到X的最短距離。在搜索中還需假定兩點之間的距離不為負。

1）對起始點S作標記，計算S點到所有其他節(jié)點的距離D(X)，最小節(jié)點記為Y。

2）對所有未作標記的點按以下公式計算距離：D(X)＝min{D(X),d(Y,X)＋D(Y)}其中Y是最后一個作標記的點。取具有最小值的D(X)。若最小值的D(X,Y)為∞，則說明S到所有未標記點都沒有回路，算法終止；否則繼續(xù)。3）如果Y等于終結(jié)點T，則已找到S到T的最短路徑，算法終止；否則轉(zhuǎn)到2）Dijkstra算法兩點不直接相連則為不通；路徑長度為路徑上邊數(shù)的權(quán)值之和；最短路徑為兩結(jié)點權(quán)值之和最小的路徑。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作標記，已是終結(jié)點結(jié)束搜索。根據(jù)順序記錄的標記點以及最小值的取值情況，可得到最短路徑為A－E－C，最短路徑為8。如圖，搜索A到C的最短路徑？路徑（Route）是網(wǎng)絡(luò)分析的基礎(chǔ)，路徑必須經(jīng)過有關(guān)站點（stop），避開障礙點（barrier），以交通成本最低產(chǎn)生分析結(jié)果。ArcGIS中的最短路徑分析最短路徑分析是基于矢量的，利用現(xiàn)有網(wǎng)絡(luò)；路徑分析是基于柵格的，用源柵格和耗費柵格來尋求最低耗費路徑。1和2哪個去合適呢？12居民分布點服務(wù)點二、最近設(shè)施在網(wǎng)絡(luò)上的任何地點尋找最近設(shè)施，如醫(yī)院、消防站或ATM機）尋找最近設(shè)施的問題：最近設(shè)施算法首先計算選定地點到所有備選設(shè)施的最短路徑然后從備選設(shè)施中選取最近設(shè)施可用于基于定位的服務(wù)（LBS），如找到最近的ATM取款機等最近設(shè)施（ClosestFacility）與路徑相似，設(shè)施（facility）和事件（incident）之間的關(guān)系類似于兩個站點?？梢詾槊總€事件查找單個最近設(shè)施，也可以同時查找多個設(shè)施，得到一個事件和多個設(shè)施之間的最佳路徑。ArcGIS中的最近設(shè)施圖書館設(shè)在哪兒合適呢？居民分布點公共設(shè)施劃分服務(wù)區(qū)的問題三、配置/服務(wù)區(qū)通過網(wǎng)絡(luò)研究資源的空間分布。設(shè)施的分布決定了資源的服務(wù)范圍。在緊急服務(wù)中，一般是以反應(yīng)時間來衡量效率的服務(wù)區(qū)（ServiceArea）是路徑分析的擴展，給定交通成本，產(chǎn)生離開服務(wù)點所有方向的最遠路徑，將路徑最遠點連接起來形成最大范圍即服務(wù)區(qū)。ArcGIS中的服務(wù)區(qū)用目標與約束集來解決供與需的匹配問題。通過網(wǎng)絡(luò)模擬，根據(jù)需求點的空間分布，在一些候選點中選擇給定數(shù)量的供應(yīng)點以使預(yù)定的目標方程達到供與需的最佳匹配。四、定位-配置定位問題是指已知需求源的分布，確定在哪里布設(shè)供應(yīng)點最合適的問題。分配問題是確定這些需求源分別受哪個供應(yīng)點服務(wù)的問題。一般用于規(guī)劃重要的公共設(shè)施：普通設(shè)施——醫(yī)院、學(xué)校、養(yǎng)老院等應(yīng)急設(shè)施——消防站、急救站等在運籌學(xué)的理論中，定位與分配模型?？捎镁€性規(guī)劃求得全局性的最佳結(jié)果。由于其計算量以及內(nèi)存需求巨大，所以在實際應(yīng)用中常用一些啟發(fā)式算法來逼近或求得最佳結(jié)果。

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