空間網(wǎng)絡(luò)分析

1、4 空間網(wǎng)絡(luò)分析1 空間網(wǎng)絡(luò)的基本概念2 空間網(wǎng)絡(luò)的類型和構(gòu)成2.1 類型2.2 構(gòu)成3 空間網(wǎng)絡(luò)分析的方法3.1 路徑分析3.2 中心選址分析1網(wǎng)絡(luò)模型21網(wǎng)絡(luò)分析的基本概念 網(wǎng)絡(luò)是一個(gè)由點(diǎn)、線的二元關(guān)系構(gòu)成的系統(tǒng)，通常用來(lái)描述某種資源或物質(zhì)沿著路徑在空間上的運(yùn)動(dòng)。 在GIS中，網(wǎng)絡(luò)分析則是依據(jù)網(wǎng)絡(luò)拓?fù)潢P(guān)系（線性實(shí)體之間、線性實(shí)體與結(jié)點(diǎn)之間、結(jié)點(diǎn)與結(jié)點(diǎn)之間的連接、連通關(guān)系），通過(guò)考察網(wǎng)絡(luò)元素的空間及屬性數(shù)據(jù)，以數(shù)學(xué)理論模型為基礎(chǔ)，對(duì)網(wǎng)絡(luò)的性能特征進(jìn)行多方面的一種分析計(jì)算。其中，網(wǎng)絡(luò)圖論與數(shù)學(xué)模型是網(wǎng)絡(luò)分析的重要理論基礎(chǔ)。 目前，網(wǎng)絡(luò)分析在電子導(dǎo)航、交通旅游、城市規(guī)劃管理以及電力、通訊等各種管

2、網(wǎng)管線的布局設(shè)計(jì)中發(fā)揮了重要的作用。3例子20V5V0V4V1V3V210060301010505有向網(wǎng)絡(luò)鄰接矩陣4網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)1）幾何結(jié)構(gòu)：表示地理分布位置，用點(diǎn)、線表示2）拓?fù)浣Y(jié)構(gòu)：表示連接性，用圖表示5圖的定義：頂點(diǎn) 無(wú)序邊無(wú)向圖頂點(diǎn) 有序弧有向圖 有權(quán)重網(wǎng)絡(luò)GIS要進(jìn)行網(wǎng)絡(luò)分析，首先需要解決網(wǎng)絡(luò)的表達(dá)和存儲(chǔ)問(wèn)題。圖或網(wǎng)絡(luò)的表達(dá)：邊（弧、鏈）、點(diǎn)圖或網(wǎng)絡(luò)的存儲(chǔ)：鄰接矩陣61、鏈（Link） 網(wǎng)絡(luò)中流動(dòng)的管線如街道、河流、水管，其狀態(tài)屬性包括阻力和需求。2.1 圖或網(wǎng)絡(luò)的表達(dá)：2、結(jié)點(diǎn)（Node） 網(wǎng)絡(luò)中鏈的結(jié)點(diǎn)，如港口、車站等，其狀態(tài)屬性包括阻力和需求等。7GIS要進(jìn)行網(wǎng)絡(luò)分析，首先需

3、要解決網(wǎng)絡(luò)的表達(dá)和存儲(chǔ)問(wèn)題。某局部道路網(wǎng)絡(luò)如圖2所示，p1p9是結(jié)點(diǎn)編號(hào)，括號(hào)中的數(shù)字是道路阻強(qiáng) 81）結(jié)點(diǎn)p5是一公共汽車站點(diǎn)，平均每天上車人數(shù)為200人，下車人數(shù)為300人，具體表達(dá)為：結(jié)點(diǎn)號(hào)上載需求量（人）下載需求量（人）P52003009 2) 道路p1p7是一雙行道，且正向阻強(qiáng)為40km/s，負(fù)向阻強(qiáng)為35km/s，具體表達(dá)為鏈弧號(hào)起結(jié)點(diǎn)終結(jié)點(diǎn)正方向阻強(qiáng)（km/s）反方向阻強(qiáng)（km/s）p1p71740353）道路p6p8是一單行道，且阻強(qiáng)為20km/s，具體表達(dá)為：鏈弧號(hào)起結(jié)點(diǎn)終結(jié)點(diǎn)正方向阻強(qiáng)（km/s）反方向阻強(qiáng)（km/s）P6p86820-1(表不通)10結(jié)點(diǎn)中的特殊類型障礙（

4、Barrier），禁止網(wǎng)絡(luò)上流動(dòng)的點(diǎn)。拐點(diǎn)（Turn），出現(xiàn)在網(wǎng)絡(luò)中的分割點(diǎn)上，其狀態(tài)有屬性和阻力，如拐彎的時(shí)間和限制（如在8點(diǎn)到18點(diǎn)不允許左拐）。中心（Center），是接受或分配資源的位置，如水庫(kù)、商業(yè)中心，電站等，其狀態(tài)包括資源容量（如總量），阻力限額（中心到鏈的最大距離或時(shí)間）。站點(diǎn)（Stop），在路徑選擇中資源增減的結(jié)點(diǎn)，如庫(kù)房、車站等，其狀態(tài)屬性有資源需求，如產(chǎn)品數(shù)量。 11拐點(diǎn)12轉(zhuǎn)彎類型描述屬性表 0=無(wú)阻強(qiáng) -1=不允許拐彎U型拐彎指從6號(hào)弧至20號(hào)結(jié)點(diǎn)并從20號(hào)結(jié)點(diǎn)轉(zhuǎn)回6號(hào)弧，這是一個(gè)180度轉(zhuǎn)彎，花費(fèi)20秒時(shí)間?？奎c(diǎn)使得從6號(hào)弧至其他弧段直到7號(hào)弧，向左轉(zhuǎn)至8號(hào)弧，向右

5、轉(zhuǎn)至9號(hào)弧的運(yùn)移減慢不允許從6號(hào)弧轉(zhuǎn)至9號(hào)弧，并賦予負(fù)值阻強(qiáng)；允許其他方向的轉(zhuǎn)變，其阻強(qiáng)為正高架道或地道允許直通而無(wú)延遲，如從6號(hào)弧至7號(hào)?。坏辉试S轉(zhuǎn)彎，此時(shí)以負(fù)的阻強(qiáng)表示，如從6號(hào)弧至8、9號(hào)弧968720U型轉(zhuǎn)彎角度至弧段從弧段結(jié)點(diǎn)號(hào)時(shí)間阻強(qiáng)/s968720高架道或地道968720?？奎c(diǎn)968720不準(zhǔn)轉(zhuǎn)彎662020076201590862020-909620101807620008620-1909620-1-909620-1-9076205086201090132.2 圖或網(wǎng)絡(luò)的存儲(chǔ) P170鄰接矩陣無(wú)向圖、有向圖 有向網(wǎng)絡(luò)1、0 1、&、0143空間網(wǎng)絡(luò)分析的方法3.1 路徑分析最

6、短路徑分析連通性分析-最小生成樹(shù)3.2 中心選址15 3.1.1 最短路徑求解最短路徑求解有多種不同的方法，其中Dijkstra算法適合于求解某個(gè)起點(diǎn)（源點(diǎn)）到網(wǎng)絡(luò)中的其它各個(gè)結(jié)點(diǎn)的最佳路徑。16例子20V5V0V4V1V3V210060301010505有向網(wǎng)絡(luò)17例子(思路)ACiBi 如圖所示，A為所求最短距離的起點(diǎn)，其他Bi, Ci 為終點(diǎn)。目的:求一系列最短距離。我們先假定這些最短距離互不相等。那么我們可以把這些最短距離按升序（從小到大）排列步驟:我們把所有頂點(diǎn)分為兩類C和B.令A(yù)到Bi這些頂點(diǎn)的最短距離不為無(wú)窮大,A到Ci這些頂點(diǎn)的最短距離為無(wú)窮大 這就說(shuō)明A到Ci中的點(diǎn)要么不通，

7、要么通過(guò)Bi中的點(diǎn)與之連接。 18例子(思路)ACiBi 這樣，對(duì)于A到Ci中任何一個(gè)點(diǎn)的最小距離，我們總可以在Bi中找到一點(diǎn)，使得A到這一點(diǎn)的最小距離小于前一個(gè)距離。（因?yàn)锳到Ci中的點(diǎn)要么不通，要么通過(guò)Bi中的點(diǎn)與之連通。 ） 因此，我們可以先不考慮Ci中的點(diǎn)。19例子(思路)于是，對(duì)于右圖，我們第一步只考慮下圖:V5V0V4V21003010Bi=v2,v4,v520V5V0V4V1V3V21006030101050520例子(思路)我們用mindist這個(gè)數(shù)組來(lái)保存由v0到其它頂點(diǎn)的最小距離，這些距離按升序排列?？紤]右圖：第一步，通過(guò)比較，我們知道 mindistancev0v2=mi

8、ndist0=10,（v0-v2)這是我們求出的第一個(gè)最小距離一旦我們得到v2，我們就可以知道：V5V0V4V21003010向量21例子(思路)V0跟 v2直接連通到的點(diǎn)v3 之間的最小距離不再是無(wú)窮大，它應(yīng)當(dāng)是mindistancev0v2+disv2v3, 這樣我們應(yīng)當(dāng)把v3放入前面的集合Bi中。（注意：有多少v2直接連通到的點(diǎn)都應(yīng)當(dāng)考慮進(jìn)來(lái)。）V5V0V4V3V2100301050Bi=v2,v4,v5,v322例子(思路)第二步，我們把與v2直接連通的點(diǎn)v3考慮進(jìn)來(lái)。dis05=100; dis04=30;dis02=10; dis03=60;除10以外，30是最小的。 我們可以證明

9、30是v0到其它頂點(diǎn)除10以外最小的。V5V0V4V3V2100301050向量23例子(思路)這樣我們得到我們的第二個(gè)最小距離：Mindistancev0v4=mindist1=30 ,(v0-v4)接下來(lái)，我們把v4與之直接連通的點(diǎn)考慮進(jìn)來(lái)。V5V0V4V3V2100301050Bi24例子以v0為起點(diǎn)，計(jì)算它到其它各頂點(diǎn)的最短路徑，計(jì)算過(guò)程中最短路徑長(zhǎng)度向量D的變化見(jiàn)D0-D4，計(jì)算出的各條最短路徑。25例子20V5V0V4V1V3V210060301010505有向網(wǎng)絡(luò)261227例子起點(diǎn)終點(diǎn)最短路徑路徑長(zhǎng)度v0v1無(wú)v2(v0,v2)10v3(v0,v4,v3)50v4(v0,v4)

10、30v5(v0,v4,v3,v5)602820V5V0V4V1V3V210060301010505帶權(quán)有向圖作業(yè)1: 求V0到V5的最短路徑291230起點(diǎn)終點(diǎn)最短路徑路徑長(zhǎng)度v0v1無(wú)v2(v0,v2)10v3(v0, v3)30v4無(wú)v5(v0, v3,v5)4031規(guī)律(步驟)制作N* N的矩陣第m行就意味著有m個(gè)值(距離)已經(jīng)確定在確定一個(gè)點(diǎn)后,與該點(diǎn)相鄰接的點(diǎn)的距離重新計(jì)算,與該點(diǎn)不相鄰的則保持不變(直接照抄之前的)在重新計(jì)算點(diǎn)的距離時(shí),只要考慮與該點(diǎn)相鄰的所有點(diǎn)的最短距離.32v6v8v1v7v5v4v2v389363253757作業(yè)2: 求V1到其他各點(diǎn)的最短路徑33343.1.

11、2 連通性分析-最小生成樹(shù)（1）概念連通圖：在一個(gè)圖中，任意兩個(gè)節(jié)點(diǎn)之間都存在一條路。樹(shù)：若一個(gè)連通圖中不存在任何回路，則稱為樹(shù)。生成樹(shù)的權(quán)數(shù)：生成樹(shù)中各邊的權(quán)數(shù)之和。最小生成樹(shù)：圖的極小連通子圖。（2）應(yīng)用：通信線路、快遞5635（3）構(gòu)造最小生成樹(shù)的依據(jù)：在網(wǎng)中選擇N-1條邊連接網(wǎng)的N個(gè)頂點(diǎn)盡可能選取權(quán)值為最小的邊3.1.2 連通性分析-最小生成樹(shù)36(4)算法（Kruskal，克羅斯克爾算法，也叫“避圈”法）1）先把圖中的各邊按權(quán)數(shù)從小到大重新排列，并取權(quán)數(shù)最小的一條邊為最小生成樹(shù)中的邊。2）在剩下的邊中，按順序取下一條邊。若該邊與最小生成樹(shù)中已有的邊，構(gòu)成回路，則舍去該邊，否則選中生成

12、樹(shù)。3）重復(fù)2），直到有M-1條邊被選進(jìn)生成樹(shù)中，這M-1條邊就構(gòu)成最小生成樹(shù)3.1.2 連通性分析-最小生成樹(shù)373.1.2 連通性分析-最小生成樹(shù)具體步驟38請(qǐng)應(yīng)用克羅斯克爾算法確定下圖的最小生成樹(shù)（含步驟）。12345647710131718152228作業(yè)：39894612752715V6V1V2V3V4V5V7404.2 中心選址問(wèn)題 中心點(diǎn)選址問(wèn)題中，最佳選址位置的判定標(biāo)準(zhǔn)，是使其所在的頂點(diǎn)與圖中其它頂點(diǎn)之間的最大距離達(dá)到最小，或者使其所在的頂點(diǎn)到圖中其它頂點(diǎn)之間的距離之和達(dá)到最小。 這個(gè)選址問(wèn)題實(shí)際上就是求網(wǎng)絡(luò)圖的中心點(diǎn)問(wèn)題。這類選址問(wèn)題適宜于醫(yī)院、消防站等服務(wù)設(shè)施的布局問(wèn)題。 41v6v8v1v7v5v4v2v389363253757中心選址問(wèn)題的實(shí)例例如，某縣要在其所轄的8個(gè)鄉(xiāng)鎮(zhèn)之一修建一個(gè)消防站，為8個(gè)鄉(xiāng)鎮(zhèn)服務(wù)，要求消防站至最遠(yuǎn)鄉(xiāng)鎮(zhèn)的距離達(dá)到最小。假設(shè)該8個(gè)鄉(xiāng)鎮(zhèn)之間的交通網(wǎng)絡(luò)被抽象為無(wú)向賦權(quán)連通圖，權(quán)值為鄉(xiāng)鎮(zhèn)之間的距離。下面求解消防站應(yīng)設(shè)在哪個(gè)鄉(xiāng)鎮(zhèn)，即哪個(gè)頂點(diǎn)？42首先，用Dijkstra算法計(jì)算出每一個(gè)頂點(diǎn)vi至其它各頂點(diǎn)vj的最短路徑長(zhǎng)度dij(i, j=1,2,6)，寫出距離矩陣： 中心選址問(wèn)題的實(shí)例606191615256547343其次，求距離矩陣中每行的最大值，即各個(gè)頂點(diǎn)的最大服務(wù)距離，得e(v1)=14, e