胡于杰,李 響

(華東師范大學(xué)地理信息科學(xué)教育部重點實驗室,上海 200062）

利用最短路徑算法確定地理網(wǎng)絡(luò)中心服務(wù)范圍

胡于杰,李 響

(華東師范大學(xué)地理信息科學(xué)教育部重點實驗室,上海 200062）

設(shè)施服務(wù)范圍指在一定限制條件下(如時間、費用或路程等）設(shè)施所能提供服務(wù)的最大空間領(lǐng)域,在道路網(wǎng)絡(luò)環(huán)境中,它通常由一系列結(jié)點及邊組成[1]。例如,某救助站在接到求救電話后10 min所能到達的區(qū)域;某物流公司在配送貨物時500元花費所能到達的區(qū)域等。在GIS中稱尋找這類區(qū)域的問題為中心服務(wù)范圍問題。對于中心服務(wù)范圍的研究有助于解決消防站、學(xué)校及醫(yī)院等公共設(shè)施的服務(wù)范圍劃分問題。傳統(tǒng)方法(如廣度優(yōu)先遍歷算法）通常用以服務(wù)設(shè)施所在位置為中心、以時間(或距離）為半徑形成的圓形區(qū)域所構(gòu)成的等時區(qū)(或等距區(qū)）表示服務(wù)范圍。這種表示方法用直線距離評價通達性,只是一個概略的結(jié)果[2],不能反映從服務(wù)設(shè)施到需求點的實際通達情況。為此,本文在總結(jié)中心服務(wù)范圍典型算法的基礎(chǔ)上,提出利用最短路徑算法確定中心服務(wù)范圍的方法。

1 地理網(wǎng)絡(luò)中心服務(wù)范圍的形式化定義

中心服務(wù)范圍是指從中心點出發(fā),在限定條件下可達的區(qū)域,由一系列結(jié)點及邊構(gòu)成的網(wǎng)絡(luò)子集:

其中,c代表網(wǎng)絡(luò)的某個中心,N代表網(wǎng)絡(luò)的結(jié)點集合,E代表邊集合,ωc代表網(wǎng)絡(luò)中心的限制費用,ωci為中心點c至網(wǎng)絡(luò)結(jié)點i的累計費用,ωij為邊eij的費用[3]。

從中心出發(fā)任意路徑的費用不能超過中心的限制費用。在實際生活中,這種費用可以是時間、路程及花費的金錢等。

2 利用最短路徑算法確定地理網(wǎng)絡(luò)中心服務(wù)范圍

2.1 數(shù)據(jù)存儲結(jié)構(gòu)

本文利用自定義的類結(jié)構(gòu)存儲網(wǎng)絡(luò)結(jié)點及網(wǎng)絡(luò)邊,描述如下(為便于描述,下文將“費用”理解為“阻值”）:

該結(jié)構(gòu)可以完整地反映網(wǎng)絡(luò)中結(jié)點與其鄰接結(jié)點及邊的關(guān)系,能很好地反映網(wǎng)絡(luò)的拓撲關(guān)系。在此基礎(chǔ)上構(gòu)建了結(jié)點間的關(guān)聯(lián)矩陣,用于最短路徑算法。

2.2 最短路徑算法

本算法是對Dijkstra最短路徑算法[4]的改進(簡稱“最短路徑算法”）。首先,將網(wǎng)絡(luò)中所有結(jié)點初始化為未標記結(jié)點,除中心外所有結(jié)點的阻值(即費用）賦為無窮大。然后從起點(第一次搜索的起點為網(wǎng)絡(luò)中心）開始搜索與其有路徑連通的未標記結(jié)點,賦以合理的阻值,并將起點標記為已標記結(jié)點,再以阻值不為無窮大的未標記結(jié)點為起點開始搜索,重復(fù)上述過程,直到某結(jié)點的阻值超過網(wǎng)絡(luò)中心的阻值或所有結(jié)點均為已標記結(jié)點為止。最后,基于結(jié)點及邊的阻值搜索并存儲所有在中心阻值范圍內(nèi)的邊,這些邊和結(jié)點的集合為網(wǎng)絡(luò)中心的服務(wù)范圍。結(jié)合2.1中的數(shù)據(jù)結(jié)構(gòu),算法描述如下:

(1）將所有結(jié)點的dist置為∞,pre_node置為null,ischecked置為false;將起點from_node的dist置為0;定義網(wǎng)絡(luò)中心阻值為distance。

(2）定義變量M IN_ID,用于存儲每次搜索過程中起點的編號;定義變量M IND,用于存儲上述結(jié)點的阻值。1）判斷所有結(jié)點ischecked屬性,若全為true,則跳出第2步;2）在所有ischecked屬性為false的結(jié)點中搜索,若某結(jié)點nodei滿足nodei.dist＜∞,則M IND=nodei.dist,M IN_ID=nodei. id;3）判斷M IND與網(wǎng)絡(luò)中心阻值distance的大小,若前者大于后者,則跳出第2步;4）令nodeMIN_ID.ischecked=true;5）在所有結(jié)點中搜索與編號為M IN_ID的結(jié)點有路徑連通的結(jié)點nodej,若nodej.dist＞M IND+arck.im pedence(其中arck代表以nodei為起點,nodej為終點的邊,編號為k）,則令nodej.dist=M IND+arck.im pedence;nodej.pre_node=nodeMIN_ID。

(3）對所有已標記結(jié)點進行判斷。1）若網(wǎng)絡(luò)中某條邊arck滿足如下關(guān)系:arck.node_from.id==from_node.id或arck.node_to.id==from_node.id,且arck.im pedence＜distance,則將邊arck加入結(jié)果集中,即arck.isA dded=true;2）若邊arck滿足如下關(guān)系:arck.node_from.dist+arck.impedence＜distance或arck.node_to.dist+arck.im pedence＜distance,則將邊arck加入結(jié)果集中,即arck.isA d ded=true。

本算法第1步為搜索過程初始化,第2步為結(jié)點賦阻值,第3步搜索并存儲所有在中心阻值范圍內(nèi)的邊。其中,即使某結(jié)點的ischecked屬性為true,它仍可參加為其鄰接結(jié)點賦最小阻值的運算過程,因此將不會產(chǎn)生“漏邊”現(xiàn)象;而廣度優(yōu)先遍歷算法在某結(jié)點被訪問后,后續(xù)的遍歷過程將不再考慮該結(jié)點,有可能產(chǎn)生“漏邊”現(xiàn)象,需要大量的后續(xù)處理來彌補,從而增加了算法的運算時間。

3 應(yīng)用實例

以美國加利福尼亞州部分縣的道路交通網(wǎng)絡(luò)為例,結(jié)合面向?qū)ο笳Z言C#及A rcGIS Engine設(shè)計實現(xiàn)了利用最短路徑算法確定地理網(wǎng)絡(luò)中心服務(wù)范圍系統(tǒng),通過輸入網(wǎng)絡(luò)的中心及相應(yīng)的阻值(本實驗中為距離）,所有在中心服務(wù)范圍內(nèi)的道路均在地圖上高亮顯示。

在主頻為3.0 GHz、內(nèi)存為2 G、硬盤為160 G的環(huán)境中針對7組不同的數(shù)據(jù)進行實驗,其數(shù)據(jù)量依次增大(表1）。為了比較結(jié)果的準確性及算法的運算效率,針對每組數(shù)據(jù),隨機選擇一個網(wǎng)絡(luò)結(jié)點作為中心位置,同時給定一個40 km的中心阻值,將最短路徑算法和廣度優(yōu)先遍歷算法[3]分別應(yīng)用于上述7個數(shù)據(jù)集中,在道路網(wǎng)絡(luò)數(shù)據(jù)量不斷增大的情況下,兩種算法的運算時間如圖1a所示。

表1 實驗用的7組數(shù)據(jù)

由圖1a可知,隨著道路網(wǎng)絡(luò)數(shù)據(jù)量的增大,兩種算法在計算網(wǎng)絡(luò)中心服務(wù)范圍過程中的運算時間逐漸增長。其中,最短路徑算法的運算時間增長平穩(wěn),而廣度優(yōu)先遍歷算法卻出現(xiàn)了明顯的“拐點”,自該拐點后,運算時間增幅急劇增大。以第7組數(shù)據(jù)集為例,最短路徑算法的運算時間僅為廣度優(yōu)先遍歷算法的4.9%,大幅提高了運算效率。為進一步分析中心阻值對算法運算效率的影響,選取第5組道路網(wǎng)絡(luò),并隨機選取一個網(wǎng)絡(luò)結(jié)點作為中心位置,依次給出25組數(shù)據(jù),運行上述兩種算法,比較運算時間,結(jié)果如圖1b。

由圖1b可知,當網(wǎng)絡(luò)中心阻值小于14 km時,兩種算法的運算時間基本接近;當網(wǎng)絡(luò)中心阻值大于14 km后,隨著網(wǎng)絡(luò)中心阻值的增大,二者的運算時間均不斷增長,但廣度優(yōu)先遍歷算法的運算時間明顯比最短路徑算法的運算時間增幅大,且增幅隨著網(wǎng)絡(luò)中心阻值的增大不斷變大。以中心阻值56 km為例,最短路徑算法的運算時間僅為廣度優(yōu)先遍歷算法的2.6%。

此外,為了解網(wǎng)絡(luò)形態(tài)對算法運算效率的影響,同樣以第5組網(wǎng)絡(luò)數(shù)據(jù)為研究對象,通過給定中心阻值,變換中心位置,觀察運算時間的變化。實驗中,以道路網(wǎng)絡(luò)不同區(qū)域的稠密程度來展現(xiàn)不同的網(wǎng)絡(luò)形態(tài),城市道路網(wǎng)密度是城市道路中心線總長度與城市用地面積之比[5],基于此定義,得到網(wǎng)絡(luò)內(nèi)不同區(qū)域的密度(表2）,在密度不同的區(qū)域中隨機選擇7個網(wǎng)絡(luò)中心,并隨機給定中心阻值36 km,分別利用兩種算法計算網(wǎng)絡(luò)中心服務(wù)范圍,運算時間如圖1c所示。

表2 7組數(shù)據(jù)所處區(qū)域的道路網(wǎng)絡(luò)密度

圖1 最短路徑算法和廣度優(yōu)先遍歷算法運算時間比較

以道路網(wǎng)絡(luò)密度4 km/km2為界,根據(jù)表2可知,編號為1 378、2 498、3 007、5 261的點位于網(wǎng)絡(luò)的稠密區(qū),而其他3點位于網(wǎng)絡(luò)的稀疏區(qū)。結(jié)合實際情況可得如下結(jié)論:在本組實驗條件下,最短路徑算法的運算效率比廣度優(yōu)先遍歷算法高。以網(wǎng)絡(luò)中心編號1 378的點為例,最短路徑算法的運算時間為廣度優(yōu)先遍歷算法的3.3%,而且,隨著中心所處區(qū)域網(wǎng)絡(luò)密度的變化,相對于廣度優(yōu)先遍歷算法而言,最短路徑算法的運算時間基本不變。

4 結(jié)論

本文提出了一種基于最短路徑算法計算地理網(wǎng)絡(luò)中心服務(wù)范圍的新方法,針對同一網(wǎng)絡(luò)數(shù)據(jù)集,最短路徑算法比廣度優(yōu)先遍歷算法所需時間更短,隨著網(wǎng)絡(luò)尺度或中心阻值的增大,二者運算時間均有提高,但廣度優(yōu)先遍歷算法運算時間增幅遠高于最短路徑算法;當網(wǎng)絡(luò)中心位置發(fā)生變化時,最短路徑算法比廣度優(yōu)先遍歷算法所需運算時間更少,運算效率更穩(wěn)定。

本文提出的方法僅適用于單個中心服務(wù)范圍的劃分問題,當網(wǎng)絡(luò)中存在多個中心點時,一種方法就是將其作為多個單中心問題分別解決,但當服務(wù)范圍間存在競爭關(guān)系時,需同時考慮多個中心的影響,這將成為進一步的研究方向。

[1] 白玲,王家耀.基于GIS的地理網(wǎng)絡(luò)模型研究[J].信息工程大學(xué)學(xué)報,2000,1(4）:96-98.

[2] 龔潔暉,白玲.確定地理網(wǎng)絡(luò)中心服務(wù)范圍的一種算法[J].測繪學(xué)報,1998,27(4）:357-362.

[3] 史照良,黃繼安.基于特征的非平面 GIS-T數(shù)據(jù)模型在中心服務(wù)范圍中的應(yīng)用[J].現(xiàn)代測繪,2004,27(1）:3-6.

[4] D IJKSTRA E W.A note on two p roblem s in connexion w ith graphs[J].Numerische Mathematik,1959,1:269-271.

[5] 沈建武,吳瑞麟.城市道路與交通[M].武漢:武漢大學(xué)出版社, 2006.104-105.

2009-12-14;

2010-03-03

胡于杰(1987-）,男,碩士,研究方向為空間覆蓋模型及優(yōu)化算法。E-mail:hueujee@mail.com