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

胡于杰,李 響

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

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

胡于杰,李 響

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

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

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

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

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

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

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

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

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

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

2.2 最短路徑算法

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

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

(2）定義變量M IN_ID,用于存儲(chǔ)每次搜索過程中起點(diǎn)的編號(hào);定義變量M IND,用于存儲(chǔ)上述結(jié)點(diǎn)的阻值。1）判斷所有結(jié)點(diǎn)ischecked屬性,若全為true,則跳出第2步;2）在所有ischecked屬性為false的結(jié)點(diǎn)中搜索,若某結(jié)點(diǎn)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é)點(diǎn)中搜索與編號(hào)為M IN_ID的結(jié)點(diǎn)有路徑連通的結(jié)點(diǎn)nodej,若nodej.dist＞M IND+arck.im pedence(其中arck代表以nodei為起點(diǎn),nodej為終點(diǎn)的邊,編號(hào)為k）,則令nodej.dist=M IND+arck.im pedence;nodej.pre_node=nodeMIN_ID。

(3）對(duì)所有已標(biāo)記結(jié)點(diǎn)進(jìn)行判斷。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é)點(diǎn)賦阻值,第3步搜索并存儲(chǔ)所有在中心阻值范圍內(nèi)的邊。其中,即使某結(jié)點(diǎn)的ischecked屬性為true,它仍可參加為其鄰接結(jié)點(diǎn)賦最小阻值的運(yùn)算過程,因此將不會(huì)產(chǎn)生“漏邊”現(xiàn)象;而廣度優(yōu)先遍歷算法在某結(jié)點(diǎn)被訪問后,后續(xù)的遍歷過程將不再考慮該結(jié)點(diǎn),有可能產(chǎn)生“漏邊”現(xiàn)象,需要大量的后續(xù)處理來彌補(bǔ),從而增加了算法的運(yùn)算時(shí)間。

3 應(yīng)用實(shí)例

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

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

表1 實(shí)驗(yàn)用的7組數(shù)據(jù)

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

[3] 史照良,黃繼安.基于特征的非平面 GIS-T數(shù)據(jù)模型在中心服務(wù)范圍中的應(yīng)用[J].現(xiàn)代測(cè)繪,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àn)榭臻g覆蓋模型及優(yōu)化算法。E-mail:hueujee@mail.com