空間網(wǎng)絡分析

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

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

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

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

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

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

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

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

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

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

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

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