空間網(wǎng)絡分析

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

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