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

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

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

耗費(fèi)距離量測(cè)：基于節(jié)點(diǎn)-鏈接像元的表示法。

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

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

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

常用的算法是Dijkstra算法

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

1）對(duì)起始點(diǎn)S作標(biāo)記，計(jì)算S點(diǎn)到所有其他節(jié)點(diǎn)的距離D(X)，最小節(jié)點(diǎn)記為Y。

2）對(duì)所有未作標(biāo)記的點(diǎn)按以下公式計(jì)算距離：D(X)＝min{D(X),d(Y,X)＋D(Y)}其中Y是最后一個(gè)作標(biāo)記的點(diǎn)。取具有最小值的D(X)。若最小值的D(X,Y)為∞，則說明S到所有未標(biāo)記點(diǎn)都沒有回路，算法終止；否則繼續(xù)。3）如果Y等于終結(jié)點(diǎn)T，則已找到S到T的最短路徑，算法終止；否則轉(zhuǎn)到2）Dijkstra算法兩點(diǎn)不直接相連則為不通；路徑長(zhǎng)度為路徑上邊數(shù)的權(quán)值之和；最短路徑為兩結(jié)點(diǎn)權(quán)值之和最小的路徑。1）對(duì)A作標(biāo)記，計(jì)算A到所有未標(biāo)記點(diǎn)的距離D(B)、D(C)、D(D)

、D(E)D(B)=4，D(C)=∞

，D(D)=1，D(E)=2

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

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