地理信息系統(tǒng)路徑分析與網(wǎng)絡(luò)應(yīng)用

地理信息系統(tǒng)路徑分析與網(wǎng)絡(luò)應(yīng)用第1頁(yè)/共54頁(yè)第2頁(yè)/共54頁(yè)第3頁(yè)/共54頁(yè)第4頁(yè)/共54頁(yè)第5頁(yè)/共54頁(yè)第6頁(yè)/共54頁(yè)最短路徑分析在最短路徑選擇中，兩點(diǎn)之間的距離可以定義為實(shí)際的距離，也可定義為兩點(diǎn)間的時(shí)間、運(yùn)費(fèi)、流量等，可定義為使用這條邊所需付出的代價(jià)。因此，可以對(duì)不同的專題內(nèi)容進(jìn)行最短路徑分析Dijkstra算法基本思想：把圖的頂點(diǎn)分為S,T兩類,若起始點(diǎn)u到某頂點(diǎn)x的最短通路己求出,則將x歸入S,其余歸入T,開(kāi)始時(shí)S中只有u,隨著程序運(yùn)行,T的元素逐個(gè)轉(zhuǎn)入S,直到目標(biāo)頂點(diǎn)v轉(zhuǎn)入后結(jié)束第7頁(yè)/共54頁(yè)一個(gè)道路網(wǎng)絡(luò)中的城市間的鏈路阻抗六個(gè)節(jié)點(diǎn)間的阻抗矩陣1319(6)1313(5)132558(4)19253953(3)3920(2)585320(1)(6)(5)(4)(3)(2)(1)第8頁(yè)/共54頁(yè)節(jié)點(diǎn)1到其他點(diǎn)的最短路徑72p13+p366171p14+p455158p144153p133120p1221最小累計(jì)阻抗最短路徑終節(jié)點(diǎn)始節(jié)點(diǎn)第9頁(yè)/共54頁(yè)0-51000-4300-2100-51000-4300-2-310+50=600-51000-4-530+60=900-4-330+20=500-2-310+50=600-51000-4-530+60=900-4-3-530+20+10=60054321第10頁(yè)/共54頁(yè)8.3路徑分析和網(wǎng)絡(luò)應(yīng)用兩者都涉及運(yùn)動(dòng)和線要素路徑分析是基于柵格數(shù)據(jù)網(wǎng)絡(luò)應(yīng)用是基于矢量并建立拓?fù)潢P(guān)系的數(shù)據(jù)共用相同的術(shù)語(yǔ)和概念，但是數(shù)據(jù)格式和數(shù)據(jù)分析環(huán)境不同第11頁(yè)/共54頁(yè)8.3.1路徑分析需要一個(gè)源柵格、一個(gè)費(fèi)用柵格，耗費(fèi)距離量測(cè)、和生成最小累計(jì)耗費(fèi)路徑的算法第12頁(yè)/共54頁(yè)1.1源柵格定義源柵格單元只有源位置有單元值，其他單元格沒(méi)有數(shù)值源位置單元可以是起點(diǎn)也可以作為目標(biāo)路徑分析獲得到源柵格單元最小耗費(fèi)路徑第13頁(yè)/共54頁(yè)1.2耗費(fèi)柵格定義移動(dòng)通過(guò)每個(gè)柵格的耗費(fèi)或阻抗兩大特征:1每個(gè)單元格的耗費(fèi)為不同耗費(fèi)的總和2花費(fèi)可以表示真實(shí)或相對(duì)花費(fèi)耗費(fèi)柵格生成從列出耗費(fèi)變量開(kāi)始然后對(duì)每個(gè)變量確定柵格單元的數(shù)據(jù)使用局部運(yùn)算將單獨(dú)的耗費(fèi)柵格加起來(lái)局部總和是經(jīng)過(guò)每個(gè)柵格單元的耗費(fèi)第14頁(yè)/共54頁(yè)1.3直線距離和耗費(fèi)距離直線距離為測(cè)量每一個(gè)像元到最近源的直線距離；多用在經(jīng)過(guò)路線沒(méi)有障礙或等同耗費(fèi)的情況下例如，在救援飛機(jī)飛往最近的醫(yī)院的實(shí)例中，直線距離柵格就可以確定從救援飛機(jī)所在地點(diǎn)到周圍各醫(yī)院的距離；然而，當(dāng)救援汽車開(kāi)往最近醫(yī)院的實(shí)例中，因?yàn)榈乇碛懈鞣N類型的障礙物，采用不同的路線的耗費(fèi)不盡相同耗費(fèi)距離是根據(jù)通過(guò)每個(gè)像元的某個(gè)或某幾個(gè)屬性因子的加權(quán)得到的實(shí)際到達(dá)源所需的耗費(fèi)值例如，翻越一座山直線路程耗費(fèi)較小，但時(shí)間耗費(fèi)比繞行的時(shí)間耗費(fèi)要多。實(shí)際的地表覆蓋類型多樣，通過(guò)直線距離來(lái)到達(dá)源是不可能的，必須要繞道以避開(kāi)如河流，高山等的障礙物耗費(fèi)距離是對(duì)直線距離的擴(kuò)展和延伸。第15頁(yè)/共54頁(yè)成本距離的計(jì)算原理

accum_cost=a1+((cost_a+cost_b)/2)*Daccum_cost：某一單元b的累計(jì)通行成本

a1：上一個(gè)相鄰單元a的累計(jì)通行成本

cost_a：?jiǎn)卧猘的成本

cost_b：?jiǎn)卧猙的成本第16頁(yè)/共54頁(yè)橫向鏈接的成本距離：(1+2)/2=1.5對(duì)角鏈接的成本距離：1.4142x[(1+5)/2]=4.2第17頁(yè)/共54頁(yè)1.3耗費(fèi)距離量測(cè)第18頁(yè)/共54頁(yè)1.3耗費(fèi)距離量測(cè)在生成距離柵格的同時(shí)，還可以生成服務(wù)區(qū)柵格和方向柵格。服務(wù)區(qū)柵格：每一個(gè)單元格的值表示其被分配到的最近的地物。方向柵格：每一個(gè)單元格的值表示其到最近地物的方向。第19頁(yè)/共54頁(yè)1.4生成最小累計(jì)耗費(fèi)路徑很容易去計(jì)算兩個(gè)單元間的累計(jì)耗費(fèi)連接兩個(gè)單元格的每條鏈路的成本求和但是要找到最小累計(jì)耗費(fèi)路徑就有點(diǎn)困難路徑要復(fù)雜的多。許多不同的路徑都可以連接不相鄰的兩個(gè)單元找到最小累計(jì)耗費(fèi)路徑是一個(gè)迭代過(guò)程第20頁(yè)/共54頁(yè)Thecostdistanceforeachlink(c)andtheleastaccumulativecostdistancefromeachcell(d)arederivedusingthesourcecells(a)andthecostraster(b).SeeBox18.2forthederivation.第21頁(yè)/共54頁(yè)第22頁(yè)/共54頁(yè)第23頁(yè)/共54頁(yè)1.5耗費(fèi)距離量測(cè)的改進(jìn)現(xiàn)有的量測(cè)假定為一個(gè)同向性的表面(屬性單一、直線距離），實(shí)際上耗費(fèi)表面不一致，因?yàn)榈乇碓谄露?、高程、坡向均有變化現(xiàn)實(shí)的分析還需考慮由高程?hào)鸥裼?jì)算表面距離（測(cè)量真實(shí)地面距離）垂直和水平因子在計(jì)算距離柵格時(shí)，除了直接計(jì)算直線距離外，還可以考慮耗費(fèi)權(quán)重，比如坡度、土地利用類型等，計(jì)算耗費(fèi)距離柵格。第24頁(yè)/共54頁(yè)1.6路徑分析的應(yīng)用規(guī)劃道路、管線、溝渠、傳輸線路提取線性要素第25頁(yè)/共54頁(yè)8.3.2網(wǎng)絡(luò)應(yīng)用網(wǎng)絡(luò)分析是運(yùn)籌學(xué)模型中的一個(gè)基本模型，它的根本目的是研究、籌劃一項(xiàng)網(wǎng)絡(luò)工程如何安排，并使其運(yùn)行效果最好如一定資源的最佳分配，從一地到另一地的運(yùn)輸費(fèi)用最低等。其基本思想則在于人類活動(dòng)總是趨于按一定目標(biāo)選擇達(dá)到最佳效果的空間位置。GIS網(wǎng)絡(luò)分析的主要目的：對(duì)地理網(wǎng)絡(luò)（如交通網(wǎng)絡(luò)）、城市基礎(chǔ)設(shè)施網(wǎng)絡(luò)（如各種網(wǎng)線、電力線、電話線、供排水管線等）進(jìn)行地理分析和模型化。第26頁(yè)/共54頁(yè)網(wǎng)絡(luò)分析（NetworkAnalysis）矢量數(shù)據(jù)特有的空間分析方法。網(wǎng)絡(luò)是由一組互相關(guān)聯(lián)的弧段、結(jié)點(diǎn)和它們的屬性所組成的模型，用于表達(dá)現(xiàn)實(shí)世界中的道路、管線等事物。除此之外還要定義一些要素以模擬現(xiàn)實(shí)中的供給、需求、中心點(diǎn)等事物。網(wǎng)絡(luò)分析的基礎(chǔ)：線—點(diǎn)拓?fù)潢P(guān)系。依據(jù)網(wǎng)絡(luò)拓?fù)潢P(guān)系，根據(jù)網(wǎng)絡(luò)的空間數(shù)據(jù)、屬性數(shù)據(jù)，對(duì)網(wǎng)絡(luò)的特征、性能進(jìn)行分析。第27頁(yè)/共54頁(yè)2.1網(wǎng)絡(luò)組成網(wǎng)絡(luò)中的基本組成部分和屬性：鏈（Link）：網(wǎng)絡(luò)中流動(dòng)的管線，如街道、河流、水管等，其狀態(tài)屬性包括阻力和需求。結(jié)點(diǎn)（Node）：網(wǎng)絡(luò)中鏈的結(jié)點(diǎn)，如港口、車站、電站等，其狀態(tài)屬性包括阻力和需求等。結(jié)點(diǎn)中又有下面幾種特殊的類型。障礙（Barrier），禁止網(wǎng)絡(luò)中鏈上流動(dòng)的點(diǎn)。拐點(diǎn)（Turn），出現(xiàn)在網(wǎng)絡(luò)鏈中的分割結(jié)點(diǎn)上，狀態(tài)屬性有阻力，如拐彎的時(shí)間和限制(如不允許左拐)。中心（Center），是接受或分配資源的位置，如水庫(kù)、商業(yè)中心、電站等。其狀態(tài)屬性包括資源容量，如總的資源量；阻力限額，如中心與鏈之間的最大距離或時(shí)間限制。站點(diǎn)（Stop），在路徑選擇中資源增減的結(jié)點(diǎn)，如庫(kù)房、汽車站等，其狀態(tài)屬性有要被運(yùn)輸?shù)馁Y源需求，如產(chǎn)品數(shù)。第28頁(yè)/共54頁(yè)2.2網(wǎng)絡(luò)要素的表示1）鏈弧2)轉(zhuǎn)彎：M條弧相連共有轉(zhuǎn)彎個(gè)數(shù)N：425535鏈弧號(hào)起結(jié)點(diǎn)終結(jié)點(diǎn)長(zhǎng)度(km)正方向阻強(qiáng)(km/h)反方向阻強(qiáng)(km/h)資源需求量2024145.33555（-1:表示不通，單行道）…結(jié)點(diǎn)號(hào)從弧段至弧段角度時(shí)間阻強(qiáng)(s)34L2L1906034L1L11803034L2L3-90-1(不允許拐彎）34L1L300(無(wú)阻強(qiáng))34L1L2L3?？奎c(diǎn)第29頁(yè)/共54頁(yè)3）?？奎c(diǎn)、中心的屬性?？奎c(diǎn)：直接在相應(yīng)的結(jié)點(diǎn)上附上需求量屬性，負(fù)為下卸，正值為裝載，中心：資源最大容量、服務(wù)范圍和服務(wù)延遲數(shù)（在其它中心達(dá)到某個(gè)數(shù)量時(shí)才提供服務(wù)）。結(jié)點(diǎn)號(hào)需求量453546-20結(jié)點(diǎn)號(hào)資源最大容量服務(wù)范圍服務(wù)延遲數(shù)2410002000…………第30頁(yè)/共54頁(yè)2.3網(wǎng)絡(luò)分析應(yīng)用網(wǎng)絡(luò)分析的主要用途是：1選擇最佳路徑，包括路徑的查找和通達(dá)度測(cè)定；2選擇最佳布局中心的位置，包括配置問(wèn)題和城市交通規(guī)劃模型。網(wǎng)絡(luò)分析的基本方法：路徑分析最近設(shè)施服務(wù)區(qū)分析資源分配選址分析第31頁(yè)/共54頁(yè)2.3.1最佳路徑分析1、在網(wǎng)絡(luò)中從起點(diǎn)經(jīng)一系列特定的結(jié)點(diǎn)至終點(diǎn)的資源運(yùn)移的最佳路線，即阻力最小的路徑。在網(wǎng)絡(luò)的節(jié)點(diǎn)中尋找累計(jì)阻抗最小的路徑。由兩個(gè)節(jié)點(diǎn)連成，也可在兩點(diǎn)間有一些特定的站點(diǎn)可以幫助運(yùn)輸人員建立多個(gè)站點(diǎn)的時(shí)間表緊急響應(yīng)-最短時(shí)間到達(dá)事故現(xiàn)場(chǎng)2、所謂最佳路經(jīng)，是求解網(wǎng)絡(luò)中兩點(diǎn)之間阻抗最小的路經(jīng)，必須按照結(jié)點(diǎn)的選擇順序訪問(wèn)網(wǎng)絡(luò)中的結(jié)點(diǎn)。第32頁(yè)/共54頁(yè)最短路徑分析在最短路徑選擇中，兩點(diǎn)之間的距離可以定義為實(shí)際的距離，也可定義為兩點(diǎn)間的時(shí)間、運(yùn)費(fèi)、流量等，可定義為使用這條邊所需付出的代價(jià)。因此，可以對(duì)不同的專題內(nèi)容進(jìn)行最短路徑分析Dijkstra算法基本思想：把圖的頂點(diǎn)分為S,T兩類,若起始點(diǎn)u到某頂點(diǎn)x的最短通路己求出,則將x歸入S,其余歸入T,開(kāi)始時(shí)S中只有u,隨著程序運(yùn)行,T的元素逐個(gè)轉(zhuǎn)入S,直到目標(biāo)頂點(diǎn)v轉(zhuǎn)入后結(jié)束第33頁(yè)/共54頁(yè)旅行推銷員問(wèn)題在最短路徑分析中添加兩個(gè)約束推銷員必須僅訪問(wèn)選擇的各站點(diǎn)一次推銷員可以從任一站點(diǎn)出發(fā)，但必須回到出發(fā)點(diǎn)旅行商分析是無(wú)序的路徑分析。旅行商可以自己決定訪問(wèn)結(jié)點(diǎn)的順序，目標(biāo)是旅行路線阻抗總和最?。ɑ蚪咏钚。?。第34頁(yè)/共54頁(yè)1-3-2-4-5-…-101-3-10-9-5-6-8-7-4-2-1123456781091324567810913245678109第35頁(yè)/共54頁(yè)2.3.2最近設(shè)施分析指在網(wǎng)絡(luò)上給定一個(gè)事件點(diǎn)和一組設(shè)施點(diǎn)，為事件點(diǎn)查找以最小耗費(fèi)能到達(dá)的一個(gè)或幾個(gè)設(shè)施點(diǎn)。還可以設(shè)置查找的閾值，即搜索范圍，超過(guò)該范圍將不再進(jìn)行查找。首先計(jì)算選定地點(diǎn)到所有候選設(shè)施的最短路徑然后從候選設(shè)施中選擇最近的設(shè)施可以應(yīng)用于基于定位的服務(wù)，如自動(dòng)柜員機(jī)第36頁(yè)/共54頁(yè)方形標(biāo)志顯示為從所選地址到最近的消防站點(diǎn)的最短路徑第37頁(yè)/共54頁(yè)2.3.3服務(wù)區(qū)分析服務(wù)站點(diǎn)即服務(wù)中心點(diǎn)，就是提供某種特定服務(wù)的位置，如某一派出所、郵局、社區(qū)醫(yī)院、社區(qū)公園等。服務(wù)區(qū)：是以指定點(diǎn)為中心，在一定阻力范圍內(nèi)，包含所有可通達(dá)邊的一個(gè)區(qū)域。如某一社區(qū)派出所按行政區(qū)劃所管轄的社區(qū)。服務(wù)區(qū)分析就是指在滿足某種條件的前提下，查找網(wǎng)絡(luò)上指定的服務(wù)站點(diǎn)能夠提供服務(wù)的區(qū)域范圍。也可以理解為不考慮中心資源供給量和需求量，而只考慮供給方與需求方之間網(wǎng)絡(luò)弧段阻力的資源分配。可用于評(píng)估分析在某一位置郵局、醫(yī)院、超市等公共設(shè)施一般的服務(wù)范圍，從而為選擇公共設(shè)施的最佳位置提供參考。第38頁(yè)/共54頁(yè)第39頁(yè)/共54頁(yè)第40頁(yè)/共54頁(yè)2.3.4（配置）資源分配通過(guò)網(wǎng)絡(luò)來(lái)研究資源的空間分布例如學(xué)校、銀行、消防站的選址而資源的分布決定服務(wù)的范圍響應(yīng)時(shí)間資源分配網(wǎng)絡(luò)模型由中心點(diǎn)（分配中心或收集中心）及其屬性和網(wǎng)絡(luò)組成。分配有兩種形式，一種是由分配中心向四周分配，另一種是由四周向收集中心分配。資源分配的應(yīng)用包括消防站點(diǎn)分布和求援區(qū)劃分、學(xué)校選址、垃圾收集站點(diǎn)分布，停水停電對(duì)區(qū)域的社會(huì)、經(jīng)濟(jì)影響估計(jì)等第41頁(yè)/共54頁(yè)2分鐘響應(yīng)時(shí)間內(nèi)兩所消防站點(diǎn)的服務(wù)區(qū)域第42頁(yè)/共54頁(yè)5分鐘響應(yīng)時(shí)間內(nèi)兩所消防站點(diǎn)的服務(wù)區(qū)域第43頁(yè)/共54頁(yè)2.3.5定位-配置（選址分析）供給、需求和距離的匹配問(wèn)題供給由設(shè)施或點(diǎn)為中心組成需求由點(diǎn)、線或多邊形組成供給和需求之間的距離大小常以距離矩陣或距離列表表示定位與分配模型是根據(jù)需求點(diǎn)的空間分布，在一些候選點(diǎn)中選擇給定數(shù)量的供應(yīng)點(diǎn)以使預(yù)定的目標(biāo)方程達(dá)到最佳結(jié)果。---最佳分配中心，最優(yōu)配置。定位問(wèn)題是指已知需求源的分布，確定在哪里布設(shè)供應(yīng)點(diǎn)最合適的問(wèn)題；分配問(wèn)題是確定這些需求源分別受哪個(gè)供應(yīng)點(diǎn)服務(wù)的問(wèn)題。第44頁(yè)/共54頁(yè)2.3.5定位-配置（選址分析）選址分區(qū)分析是為了確定一個(gè)或多個(gè)待建設(shè)施的最佳或最優(yōu)位置，使得設(shè)施可以用一種最經(jīng)濟(jì)有效的方式為需求方提供服務(wù)或者商品。如餐館、郵局選址，工廠選址、圖書(shū)館、學(xué)校、醫(yī)院、消防站、工廠、飛機(jī)場(chǎng)、倉(cāng)庫(kù)等的最佳位置的確定。第45頁(yè)/共54頁(yè)算法在運(yùn)籌學(xué)的理論中，定位與分配模型常可用線性規(guī)劃求得全局性的最佳結(jié)果。由于其計(jì)算量以及內(nèi)存需求巨大，所以在實(shí)際