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

4.3空間網(wǎng)絡(luò)分析方法路徑分析(pathanalysis)在空間網(wǎng)絡(luò)分析中，路徑問題占有重要位置。人們常想知道在地理空間網(wǎng)絡(luò)的兩指定結(jié)點(diǎn)間是否存在路徑，如果有則特別希望找出其中的最短路徑。這種路徑問題對(duì)于交通、消防、信息傳輸、救災(zāi)、搶險(xiǎn)等有著重要的意義。在運(yùn)輸網(wǎng)絡(luò)中，有時(shí)要找出運(yùn)輸費(fèi)用最小的路徑;在通訊網(wǎng)絡(luò)中，要找出雨點(diǎn)間進(jìn)行信息傳遞具有最大可靠性的路徑等等。由于大量的最優(yōu)化問題等價(jià)于找一個(gè)網(wǎng)絡(luò)圖的最短路徑的問題，因而引起了人們對(duì)于最短路徑分析的極大興趣。下面介紹的最短路徑搜索算法是Dijkstra在1959年提出的，被公認(rèn)為是最好的算法之一。為了求出最短路徑，需先計(jì)算網(wǎng)絡(luò)任意兩點(diǎn)間的距離，并形成nxn階距離矩陣或權(quán)矩陣。W=[Wij]式中:wij為網(wǎng)絡(luò)中的邊eij的距離。在矩陣W中，wij>0,當(dāng)i,j間有邊相連接時(shí)，對(duì)于無向圖，wij=wji(i黃j);wij=8，當(dāng)i,j間無邊相連接時(shí)；wij=0，當(dāng)i=j時(shí)。圖5-43給出一無向圖G,它的距離矩陣W如式(5-37)所示。圖3-43加權(quán)無向圖G(據(jù)陳樹柏等)

匕吟**>T012gca8SOKJ%10333COoa002302CG0000OG00320態(tài).3003003co20300oa000DCK3301OG*00300oaoa101coCO43oc310DijKstra算法是一種對(duì)結(jié)點(diǎn)不斷進(jìn)行標(biāo)號(hào)的算法。每次標(biāo)號(hào)一個(gè)結(jié)點(diǎn)，標(biāo)號(hào)的值即為從給定起點(diǎn)到該點(diǎn)的最短路徑長(zhǎng)度。在標(biāo)定一個(gè)結(jié)點(diǎn)的同時(shí)，還對(duì)所有未標(biāo)號(hào)結(jié)點(diǎn)給出了"暫時(shí)標(biāo)號(hào)"即當(dāng)時(shí)能夠確定的相對(duì)最小值。設(shè)定K表示待確定最短路徑的起點(diǎn)，L表示終點(diǎn)，則最短路徑搜索的步驟如下：令起點(diǎn)K標(biāo)號(hào)為零，其他結(jié)點(diǎn)標(biāo)號(hào)為8。對(duì)未被定標(biāo)的結(jié)點(diǎn)全部給出暫時(shí)標(biāo)號(hào)，其值為min[j的舊標(biāo)號(hào)，(i的舊標(biāo)號(hào)+wij)]，這里i是前一步剛被標(biāo)定的結(jié)點(diǎn)，wij是邊eij的權(quán)，如果結(jié)點(diǎn)i和j不相鄰接，wij=8。找出所有暫時(shí)標(biāo)號(hào)的最小值，用它作為相應(yīng)結(jié)點(diǎn)的固定標(biāo)號(hào)。如果存在幾個(gè)有同一最小標(biāo)號(hào)值的結(jié)點(diǎn)，則可任取一個(gè)加以定標(biāo)。重復(fù)進(jìn)行(2)與(3)，直至指定的終點(diǎn)L被定標(biāo)時(shí)為止。用此法可直接得到由起點(diǎn)K到其他結(jié)點(diǎn)的最短路徑的長(zhǎng)度，那就是該結(jié)點(diǎn)的定標(biāo)數(shù)值。對(duì)于圖5-43中的加權(quán)無向圖G,從結(jié)點(diǎn)v1到v2的最短路徑的標(biāo)號(hào)過程如下:方%VT 說確定起點(diǎn)0何)㈣㈣(司標(biāo)定丫10⑴:⑵(00)向(湖標(biāo)定嶼01:⑵㈣㈣（以）標(biāo)定毋012傳㈣㈣口)標(biāo)定為0124C7）㈣（6）標(biāo)定此01244㈣頃標(biāo)定楠01244'冬)￡標(biāo)定巧01244勺)1￡其中括號(hào)內(nèi)的是暫時(shí)標(biāo)號(hào)，沒有括號(hào)的為定標(biāo)。距離起點(diǎn)越近的頂點(diǎn)，越早得到固定標(biāo)號(hào)。采用回溯的方法可以得到從起點(diǎn)K到其他結(jié)點(diǎn)的最短路徑經(jīng)由的結(jié)點(diǎn)。因此，從結(jié)點(diǎn)v1到v7的最短路徑長(zhǎng)度為7,經(jīng)由的路徑為v1—v3—v8—v7定位一配置分析（location-allocationanalysis）定位一配置分析是指根據(jù)中心地理論框架，通過對(duì)供給系統(tǒng)和需求系統(tǒng)兩者空間行為相互作用的分析，來實(shí)現(xiàn)網(wǎng)絡(luò)設(shè)施布局的最優(yōu)化。其中，若已設(shè)定需求點(diǎn)，求供給點(diǎn)，則涉及定位問題location);若已設(shè)定供給點(diǎn)，求需求分配點(diǎn)，則涉及配置問題(allocation);若同時(shí)求供給點(diǎn)和需求分配點(diǎn)，則涉及定位_配置問題(location-allocation)。這類問題在城市與區(qū)域規(guī)劃中應(yīng)用非常廣泛，例如選擇最佳布局中心，或者從一批候選位置中選定若干地點(diǎn)來建設(shè)公共設(shè)施，為區(qū)域的需求點(diǎn)提供服務(wù)。這些服務(wù)設(shè)施諸如醫(yī)療保健、郵電通訊、交通站點(diǎn)、行政中心等，它們是城市或區(qū)域規(guī)劃的重要內(nèi)容。定位一配置分析也是GIS空間分析研究的熱點(diǎn)之一。定位-配置分析涉及的因素比較多，除了網(wǎng)絡(luò)的元素?cái)?shù)據(jù)，還包括規(guī)劃時(shí)間范圍、問題空間類型、公共設(shè)施服務(wù)方式、費(fèi)用對(duì)象、設(shè)施使用類型、需求點(diǎn)分配類型、附屬區(qū)域等。因此，當(dāng)進(jìn)行定位—配置分析時(shí)，首先要建立一系列邊界條件和確定若干目標(biāo)函數(shù)。邊界條件代表了規(guī)劃目標(biāo)所必須滿足的規(guī)劃條件，例如，要求所有需求點(diǎn)都有相應(yīng)的供給點(diǎn)等，作為問題解決的約束條件;日標(biāo)函數(shù)是給出極大值或極小值，例如規(guī)定所有設(shè)施和需求點(diǎn)之間的總加權(quán)距離為最小等，其意義是在于能獲得一個(gè)明確的分析結(jié)果。定位-配置分析的算法包括P一中心問題、中心服務(wù)范圍的確定和中心資源的分配范圍等，它們是定位—配置分析或規(guī)劃的重要工具，以下分別予以介紹。P一中心問題。這一問題是要在m個(gè)候選點(diǎn)中，選擇P個(gè)供應(yīng)點(diǎn)，為n個(gè)需求點(diǎn)服務(wù)，并使得從服務(wù)中心到需求點(diǎn)之間的總距離(或時(shí)間、費(fèi)用)為最小。P一中心問題可以描述為：皿,嶼■此)2Z%=1 =P并滿足村 保證每個(gè)需求點(diǎn)i(i=1,2,...，n)都被服務(wù)和村將服務(wù)中心的數(shù)量限定為P個(gè)。上述兩個(gè)約束條件是為了保證每個(gè)需求點(diǎn)僅受一個(gè)供應(yīng)點(diǎn)服務(wù)，并且只有P個(gè)供應(yīng)點(diǎn)。式中：i、n分別為需求點(diǎn)的位置和數(shù)量；j、m為候選點(diǎn)的位置和數(shù)量；P為要確定的服務(wù)中心的數(shù)量；wi為需求點(diǎn)i的需求量；dij為需求點(diǎn)i到服務(wù)點(diǎn)j的距離。并且yiNxij，的，叫，只有第j個(gè)中心被選中時(shí)，需求點(diǎn)i才能分配到該中心；yj=0或1,相任何一個(gè)候選點(diǎn)被選中時(shí)為l;否則為0;xij=0,巳，相需求點(diǎn)有中心押艮務(wù)時(shí)為l;否則為0。P一中心問題可以用線性規(guī)劃方法求得全局性的最佳結(jié)果，但由于計(jì)算量及內(nèi)存需求量巨大，在實(shí)際應(yīng)用中常用一些啟發(fā)式算法來逼近或求得最佳結(jié)果，其中著名的有Teitz-Bart算法。該算法的主要步驟如下：先選P個(gè)候選點(diǎn)作為起始供應(yīng)點(diǎn)集Pt:C1，C2,...,Cp。將所有的需求點(diǎn)分配給它們最鄰近的供應(yīng)點(diǎn)，使其距離為最短。計(jì)算總的加權(quán)距離為Bt。從未被選取的候選點(diǎn)集中選一候選點(diǎn)Cb。對(duì)Pt中的每個(gè)供應(yīng)點(diǎn)Cj用Cb替換之，并計(jì)算其總加權(quán)距離的變化Mj。如果用Cb替換某個(gè)Cj后，可以使總加權(quán)距離減少，那么就替換總加權(quán)距離減少最多的供應(yīng)點(diǎn)Ck，令Bt=Bt-Abk，并將Pt修改為也所在的供應(yīng)點(diǎn)。重復(fù)③-⑤步，直至未被選取的候選點(diǎn)集為空。當(dāng)所有不在Pt中的候選點(diǎn)都試過后，其結(jié)果記為，并取代Pt。繼續(xù)重復(fù)②-⑦步，如果沒有任何取代能減少總的加權(quán)距離，則停止。其最后的結(jié)果乩，即為所求的P個(gè)中心的供應(yīng)點(diǎn)。中心服務(wù)范圍的確定。中心服務(wù)范圍是指一個(gè)服務(wù)設(shè)施在給定的時(shí)間或距離內(nèi)，能夠到達(dá)的區(qū)域。設(shè)一個(gè)帶中心的空間網(wǎng)絡(luò)G=(V,E,C)，其中V表示空間網(wǎng)絡(luò)結(jié)點(diǎn)的集合,E表示邊的集合，C為該網(wǎng)絡(luò)的一個(gè)中心。若已知該中心的阻值為cw，網(wǎng)絡(luò)邊eij的費(fèi)用為wij,r表示空間網(wǎng)絡(luò)上任何結(jié)點(diǎn)到中心的(vi,ve)間的一條路徑，ric是該路徑的費(fèi)用，那么在不考慮貨源量和需求量的情況下，中心的服務(wù)范圍應(yīng)為滿足下列條件的網(wǎng)絡(luò)邊和結(jié)點(diǎn)的集合F：F二何|%&神叫er)勘魅十神廿W河、er)為確定該中心的服務(wù)范圍，須依次求出到服務(wù)中心費(fèi)用不超過中心最大阻值的路徑，于是組成這些路徑的網(wǎng)絡(luò)結(jié)點(diǎn)和邊的集合，就構(gòu)成該中心的服務(wù)范圍。具體處理時(shí)，將空間網(wǎng)絡(luò)看作是以該中心為根的一棵樹，用寬度優(yōu)先法搜索，搜索時(shí)需考慮到網(wǎng)絡(luò)邊和結(jié)點(diǎn)的屬性。其具體的算法步驟如下：將中心結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)，并存入到達(dá)結(jié)點(diǎn)表中，同時(shí)掃描它的關(guān)聯(lián)結(jié)點(diǎn)，檢查這些結(jié)點(diǎn)是否在服務(wù)范圍內(nèi)，將其中滿足條件的關(guān)聯(lián)結(jié)點(diǎn)存入搜索結(jié)點(diǎn)表中。如果已搜索結(jié)點(diǎn)表為空，則結(jié)束;否則，繼續(xù)第③步。在已搜索結(jié)點(diǎn)表中，按表中記錄的順序取出關(guān)聯(lián)結(jié)點(diǎn)，作為當(dāng)前已到達(dá)結(jié)點(diǎn)，存入已檢查到達(dá)結(jié)點(diǎn)表中，同時(shí)記錄該結(jié)點(diǎn)所在的邊。掃描當(dāng)前結(jié)點(diǎn)的關(guān)聯(lián)結(jié)點(diǎn)，檢查這些結(jié)點(diǎn)是否在服務(wù)范圍內(nèi)，將滿足條件的關(guān)聯(lián)結(jié)點(diǎn)存入已搜索結(jié)點(diǎn)表中。重復(fù)執(zhí)行第②—④步。求解中心服務(wù)范圍的程序框圖如圖5—44所示。州蕙it；席日1宇?-讓SiSf"-V^Sjr；ji-Y^幣=書1」■［典嘵｝圖5—44求解中心服務(wù)范圍的程序框圖中心資源的分配范圍。資源分配就是將空間網(wǎng)絡(luò)的邊或結(jié)點(diǎn)，按照中心的供應(yīng)量及網(wǎng)絡(luò)邊和結(jié)點(diǎn)的需求量，分配給一個(gè)中心的過程，它用來模擬空間網(wǎng)絡(luò)上資源的供需關(guān)系。設(shè)一個(gè)帶中心的空間網(wǎng)絡(luò)G=(V,E,C),其中V表示空間網(wǎng)絡(luò)結(jié)點(diǎn)的集合，E表示網(wǎng)絡(luò)邊的集合，C為網(wǎng)絡(luò)的一個(gè)中心。已知中心的貨源量CS,中心的阻值cw，dij和wij分別表示網(wǎng)絡(luò)邊eij的需求量和費(fèi)用，r表示網(wǎng)絡(luò)上任何結(jié)到中心的(vi，vc)間的最短路徑，ric是該路徑的費(fèi)用，m是網(wǎng)絡(luò)當(dāng)前的總需求量。則資源的分配范圍定義為滿足下列條件的網(wǎng)絡(luò)邊和結(jié)點(diǎn)的集合P:P=熾|rjc.<u祁,m<cs,氏er)u{s;.-|r記十神可Mtw,冊(cè)十神即.<cs^er)資源分配范圍的求解思想是，依次求出到服務(wù)中心費(fèi)用不超過中心最大阻值，同時(shí)網(wǎng)絡(luò)的總需求量不超過中心的貨源量的路徑，組成這些路徑的網(wǎng)絡(luò)結(jié)點(diǎn)和邊的集合就構(gòu)成了該中心資源分配的范圍。處理時(shí)同時(shí)考慮到網(wǎng)絡(luò)和網(wǎng)絡(luò)結(jié)點(diǎn)的需求量。具體處理時(shí)與服務(wù)范圍的搜索方式類似。算法的主要步驟如下：（初始化）將中心所在的結(jié)點(diǎn)作為V0,存入己標(biāo)記結(jié)點(diǎn)集S中，并初始化有關(guān)變量。如果整個(gè)網(wǎng)絡(luò)都已被分配，則停止;否則，執(zhí)行第④步。如果總貨源量都已被分配，則停止;否則，執(zhí)行第④步。在尚未分配的結(jié)點(diǎn)集忘中，尋找距離中Mv0路徑最短的結(jié)點(diǎn)vn，假設(shè)vn的前一點(diǎn)是vm，將（vm，vn）作為當(dāng)前處理的邊。判斷網(wǎng)絡(luò)流在邊（vm，vn）上的運(yùn)行情況：邊接受到來自vm點(diǎn)的流量:LRmn=min{LLmn,POm}邊消耗掉的流量:LFmn=min{LDmn，LRmn}由該邊流向vn的流量:LOmn=LRmn-LFmn其中，LDmn,LLmn分別為（vm，vn）邊的需求量和通行能力;POm為vm點(diǎn)發(fā)出的流量。如果（vm，vn）邊流向vn點(diǎn)的流最為0，則該邊停止運(yùn)輸。如果（vm，vn）邊流向vn點(diǎn)的流量小于該邊的需求最，則將該邊的一部分分配給中心后，停止運(yùn)輸。如果（vm，vn）邊流向vn點(diǎn)的流量大于該邊的需求量，則考察網(wǎng)絡(luò)流在vn點(diǎn)上的接受最PRn、消耗量PFn和發(fā)出量POn。判斷網(wǎng)絡(luò)流在結(jié)點(diǎn)vn上的運(yùn)行情況，與網(wǎng)絡(luò)流在邊上的運(yùn)行情況類似：結(jié)點(diǎn)vn接受到來自（vm，vn）的流量:PRn=min{PLn,POn}結(jié)點(diǎn)vn消耗掉的流量:PFn=min{PDn,PRn}由結(jié)點(diǎn)vn流向相鄰邊的流量:POn=PRn-PFn其中,PDn，PLn分別為結(jié)點(diǎn)vn的需求量和通行能力。如果POn<0，則該點(diǎn)停止運(yùn)輸。如果POn>