GIS網(wǎng)絡(luò)分析城市道路尋優(yōu)中的應(yīng)用

韓俊卿

（太原師范學院,山西太原 030012）

GIS網(wǎng)絡(luò)分析城市道路尋優(yōu)中的應(yīng)用

韓俊卿

（太原師范學院,山西太原 030012）

針對城市道路網(wǎng)的特點,運用 GIS網(wǎng)絡(luò)分析功能,建立了基于路段連接的道路網(wǎng)絡(luò)模型,并選擇可達性作為道路權(quán)重對道路網(wǎng)進行了最短路徑分析.同時對經(jīng)典的Dijkstra算法加以改進,提出了求解道路網(wǎng)任意兩點間最短路徑的算法,該算法搜索速度快,具有較強的適用性.

最短路徑;道路權(quán)重;城市道路網(wǎng)

0 引言

隨著計算機和地理信息科學的發(fā)展,地理信息系統(tǒng)因其強大的功能得到日益廣泛和深入的應(yīng)用.網(wǎng)絡(luò)分析作為 GIS最主要的功能之一,在電子導航、交通旅游、城市規(guī)劃以及電力、通訊等各種管網(wǎng)、管線的布局設(shè)計中發(fā)揮了重要的作用,通用的網(wǎng)絡(luò)分析功能包括路徑分析、資源分配、連通分析、流分析等.網(wǎng)絡(luò)分析中最基本和最關(guān)鍵的問題是最短路徑問題,它作為許多領(lǐng)域中選擇最優(yōu)問題的基礎(chǔ),在交通網(wǎng)絡(luò)分析系統(tǒng)中占有重要地位.

從道路網(wǎng)絡(luò)模型的角度看,最短路徑分析就是在指定道路網(wǎng)絡(luò)的兩節(jié)點間找出一條阻礙強度最小的路徑.根據(jù)阻礙強度的不同定義,最短路徑不僅僅指一般地理意義上的距離最短,還可以引申到其他的度量,如時間、費用、線路容量等.相應(yīng)地,最短路徑問題就成為最快路徑問題、最低費用問題等.因此,城市道路網(wǎng)作為一種大型網(wǎng)絡(luò)設(shè)施有其本身的特征.它一方面包含網(wǎng)絡(luò)本身的拓撲特征,另一方面還包含了大量反應(yīng)地理位置特征的幾何數(shù)據(jù).本文根據(jù)道路網(wǎng)的特點,運用 GIS網(wǎng)絡(luò)分析功能對道路網(wǎng)絡(luò)模型、道路的權(quán)重選擇以及快速尋求路網(wǎng)中兩節(jié)點間的最短路徑算法分別進行了研究.

1 道路網(wǎng)模型及權(quán)重設(shè)置

1.1 道路網(wǎng)模型建立

城市道路網(wǎng)主要由眾多道路相交、相連構(gòu)成.在縱橫交織、錯綜復雜的道路網(wǎng)絡(luò)中,道路間的地理位置關(guān)系相當復雜,一條道路可能與若干條道路相交相連,且其相交相連的模式復雜.為了避免過多地考慮道路間的拓撲關(guān)系,抽取道路網(wǎng)中道路交叉路口作為分析對象,并對道路以交叉路口為結(jié)點進行分割,成為路段.這樣,整個網(wǎng)絡(luò)圖將由交叉路口點和路段組成,并定義交叉路口點為網(wǎng)絡(luò)的結(jié)點,路段為網(wǎng)絡(luò)的弧.從而建立基

式中,Rw代表道路網(wǎng)絡(luò);N代表結(jié)點集;R代表路段集合,其元素為有序?qū)Α磝,y〉,L（x,y）表示由結(jié)點x到結(jié)點y存在一條有向通路;LR代表路段長度集合,其元素lxy表示有向路段〈x,y〉的加權(quán)長度.其中,路段的加權(quán)長度是指根據(jù)目標函數(shù)要求,綜合各種動態(tài)實時信息和靜態(tài)屬性信息后所得的路段參數(shù),而并非真實意義下的長度.

1.2 道路網(wǎng)權(quán)重選擇

在交通路網(wǎng)中,兩點間最優(yōu)路徑算法的優(yōu)劣主要受到兩個因素的影響,即所使用的最短路徑算法和所選擇的道路權(quán)重.最短路徑算法是路徑選擇的搜索工具,決定了如何在龐大的路網(wǎng)數(shù)據(jù)庫中找到最佳的可行路徑.道路權(quán)重則是路徑選擇的搜索指標,是最短路徑算法的依據(jù).因此,道路權(quán)重的選擇直接影響到最優(yōu)路徑算法的合理性.

一個城市的道路網(wǎng)絡(luò)由不同等級的道路組成,不同等級的道路的通行能力和功能要求均不相同.只有整個城市的交通負載根據(jù)出行者目的的不同,均衡分布在不同等級的道路上,城市的路網(wǎng)才能得到最有效的利用.因此單純地選擇距離、時間或道路的通行能力作為道路權(quán)重都不太客觀,需要選擇一種比較綜合的指標作為道路權(quán)重.可達性是 Hansen于1959年首次提出的概念,用于定義交通網(wǎng)絡(luò)中各結(jié)點間相互作用機會的大小.其表述的是路網(wǎng)中任意點之間通達的可能性及難易程度,數(shù)學上指單位時間內(nèi)可實現(xiàn)通達的直線距離[2],即CK=D/t,CK（km/m）為可達能力,是可達性的量度.

可達性同時考慮了時間和距離的因素,把道路交通的固定設(shè)施和移動工具有機結(jié)合起來,而且避免了以道路通行能力作為權(quán)重可能造成的城市路網(wǎng)全局負載問題.因此以可達性為道路權(quán)重是一個比較綜合的指標,具有更大的合理性.

2 最短路徑算法

最短路徑問題的算法有很多種,包括基于限制條件的深度優(yōu)先搜索算法、Dijkstra算法、Floyd算法、A＊算法等,各種算法在空間復雜度、時間復雜度、易實現(xiàn)性等方面各具特色.其中,采用啟發(fā)式策略的Dijkstra算法是目前公認的求解最短路問題的經(jīng)典算法.但Dijkstra算法在基于網(wǎng)絡(luò)的權(quán)矩陣求解最短路問題的計算機算法和程序中,運用了關(guān)聯(lián)矩陣、鄰接矩陣和距離矩陣的概念.在存儲圖形數(shù)據(jù)和運算時,需要定義N×N的數(shù)組（其中N為網(wǎng)絡(luò)的結(jié)點數(shù)）,當網(wǎng)絡(luò)的結(jié)點數(shù)較大時,將占有大量的計算機內(nèi)存.如果不對Dijkstra算法進行優(yōu)化,該算法很難在實際中得到應(yīng)用.

在原始的Dijkstra算法中,每次在臨時標記點中搜索路徑最短的結(jié)點時都要遍歷所有的臨時標記結(jié)點.解決辦法就是將臨時標記結(jié)點按照最短路徑排序,每個搜索過程不必全部遍歷或者較少地遍歷臨時標記點.或者盡量減少最短路徑分析過程中搜索的臨時結(jié)點數(shù)量.

2.1 算法原理

利用兩點之間直線最短的原理,在道路網(wǎng)中,如果兩結(jié)點間存在一條邊,則該邊為兩結(jié)點間的最短路徑.若不存在一條邊,則連接起、止點的直線段代表了一個路線的趨勢,順著連線方向的某條邊是最短路徑的可能性最大[3].依據(jù)此思想,可以構(gòu)造兩個矢量,矢量1以當前結(jié)點為起點,目標點為終點;矢量2以當前結(jié)點為起點,當前結(jié)點的鄰接點為終點.將矢量2的方向值與矢量1的方向值相減得到兩矢量間的夾角.由夾角最小的邊組成的路徑最接近于最短路徑.

由于只依據(jù)矢量夾角作為求解最短路徑中路段集合的要素,可能造成求得的路徑因左右方向的震蕩而增加路徑的總長度,使求得的解大于實際最短路經(jīng)長,所以在每次搜索最短路徑頂點時,將當前結(jié)點的鄰接點按照矢量夾角大于0和小于0分為兩組,分別在兩組中選取矢量夾角絕對值的最小值對應(yīng)的結(jié)點.算法采用雙向搜索,從起點S開始進行正向搜索,同時從終點T進行逆向搜索.兩個方向每一步都要搜索與指定直線段左右兩側(cè)各一條夾角最小的邊,直到二者會合或直到目標點,最后取兩個方向搜索到的距離最短的路徑為所求解.

2.2 算法具體步驟

假設(shè)需要求解最短路徑的兩個結(jié)點分別為S點和T點,其中起點為S、終點為T.定義ds（i）表示源結(jié)點S到結(jié)點i的加權(quán)距離;dt（j）表示目標點T到結(jié)點j的加權(quán)距離;ps（m）,pt（m）表示結(jié)點m的狀態(tài),分為未標記結(jié)點（0）和標記結(jié)點（1）兩種,其中ps表示正向搜索（從S出發(fā)）過程中的狀態(tài),pt表示逆向搜索（從T出發(fā)）過程中的狀態(tài).

Step 1 初始化.對所有結(jié)點i,若i=S,則ds（i）=0,ps（i）=1;若i=T,則dt（i）=0,pt（i）=1;否則ds（i）→∞,dt（i）→∞,ps（i）=0,pt（i）=0.并定義一個數(shù)變量k作為循環(huán)變量,初始化為k=0.

Step 2 判斷S與T之間是否鄰接,若鄰接,則連接兩端點的邊即為所求最短路徑.否則,轉(zhuǎn)Step 3.

Step 3 令S,T分別為兩棵二叉樹的根節(jié)點,分別從S,T出發(fā),在直線段ST,TS左右兩側(cè)各尋找一條與ST,TS夾角最小的邊,把搜索到的邊加入對應(yīng)的二叉樹.設(shè)從S點出發(fā)搜尋到的兩條邊的另一端點分別為A1,A1′,計算SA1,SA1′的加權(quán)距離,分別記為ds（A1）,ds（A1′）;從T點出發(fā)搜尋到的兩條邊的另一端點分別為B1,B1′,記TB1,TB1′的加權(quán)距離分別為d t（B1）,dt（B1′）.

Step 4 將ds（A1）,ds（A1′）作為當前點A1,A1′的標記值,dt（B1）,dt（B1′）作為當前點B1,B1′的標記值.也就是將起點或終點至該臨時標記點子路徑上所有邊的權(quán)值之和作為當前點的標記值.同時ps（A1）,ps（A1′）,pt（B1）、pt（B1′）均變?yōu)?1.

Step 5 用A1,A1′分別代替S,B1,B1′分別代替T,然后變量k自增k=k+1,重復 Step2～Step 4,但 Step 3中是從A1（A1′）,B1（B1′）出發(fā),在直線段A1T（A1′T）,TB1（TB1′）左 右 兩 側(cè) 各 尋 找 一 條 與A1T（A′1T）,TB1（TB′1）夾角絕對值最小的邊.把搜索到的邊加入對應(yīng)的二叉樹,對二叉樹的當前點分別計算標記值并作標記.以此類推,直至An,Bn會合于一點,即正向和逆向搜索都對同一點進行了標記,則點列S,A1,…,An（Bn）,…,B1,T組成可能最短路徑,路徑長度為ds（An）+dt（Bn）.若二者沒有會合,也即雙向搜索都未對同一點進行標記,則正向搜索到終點T,逆向搜索到起點S,生成兩棵特殊的二叉樹.相應(yīng)方向已標記過的點不在搜索范圍之內(nèi).

Step 6 搜索結(jié)束后,若會合于一點,則取會合點處的標記值之和ds（An）+dt（Bn）作為可能最短路徑長度;若沒有會合,則取終點T（正向搜索）或起點S（逆向搜索）處的標記值ds（T）,dt（S）作為可能最短路徑長度.取其中最小值min{ds（An）+dt（Bn）,ds（T）,dt（S）}即為所求最短路徑長度.

如果所求最短路徑中包含會合點,則最短路徑由會合點開始沿與之相關(guān)聯(lián)的兩條邊依次尋找求解的最短路徑的標記結(jié)點,加入路徑隊列,直至S,T.若沒有會合點,則從起點S或終點T開始,在二叉樹中順次尋找所求最短路徑的相關(guān)結(jié)點,直至達到T或S,便得到最短路徑序列.搜索流程如圖1所示.

圖1 最短路徑搜索流程圖Fig.1 Flow chart of seeking the shortest path

3 結(jié)束語

本文根據(jù)城市交通道路網(wǎng)的特點,建立了道路網(wǎng)數(shù)據(jù)模型,并在綜合考慮人們出行時的時間消耗和能量消耗的情況下,選擇可達性作為道路權(quán)重,以此為搜索指標進行最短路徑分析.本文所用最短路徑算法對經(jīng)典的Dijkstra算法進行了改進,在每次搜索過程中,不必遍歷圖中所有未標記的結(jié)點,只搜索當前結(jié)點的鄰接結(jié)點.對于實際的道路網(wǎng),每個結(jié)點的鄰接點個數(shù)一般為2～5個,較之Dijkstra算法大大減少了搜索范圍.而且求解的只是源點到終點間的最短路徑,搜索的速度快,也增加了適用性.

[1] 王海梅,周獻中.時變道路網(wǎng)最短路徑算法的研究[J].火力與指揮控制,2005,30（7）:14-17

[2] 白 塵.交通路網(wǎng)中最優(yōu)路徑算法的道路權(quán)重選擇[J].中國管理信息化,2009,12（15）:54-56

[3] 嚴寒冰,劉迎春.基于GIS的城市道路網(wǎng)最短路徑算法探討[J].計算機學報,2000,23（2）:210-215

Application of GIS Network Analysis to Seek Optimum Path in City Road Net

Han Junqing
（Taiyuan Normal University,Taiyuan 030012,China）

A cco rding to the characteristics of a city road net and using GIS netwo rk analysis function,this paper discusses the road netmodel based on the road connecting and analyzes accessibility as the road weight to analyse the road sho rtest path.By imp roving the classic Dijkstra algorithm,the paper p roposes an algorithm for seeking the shortest path between two points in the road net.The algo rithm can increase seeking speed greatly and has good p racticability.

shortest path;weight of route;city road net

【責任編輯:王映苗】

1672-2027（2010）02-0123-04

P208

A

2010-03-17

韓俊卿（1975-）,女,山西忻州人,碩士,太原師范學院講師,主要從事地理信息系統(tǒng)的開發(fā)與應(yīng)用研究.