基于RTree的路網(wǎng)模型設(shè)計及實現(xiàn)

薛梅，向華

(重慶數(shù)字城市科技有限公司，重慶 400020)

基于RTree的路網(wǎng)模型設(shè)計及實現(xiàn)

薛梅?，向華

(重慶數(shù)字城市科技有限公司，重慶 400020)

通過對交通要素的分析，提出了基于RTree空間索引的路網(wǎng)模型，用于進行公交、自駕、軌道交通等不同場景的最優(yōu)路線選擇，提高了路網(wǎng)分析、索引效率。

RTree；路網(wǎng)模型

1 引 言

在現(xiàn)實社會中，范圍巨大的交通網(wǎng)絡(luò)覆蓋著城市、農(nóng)村，決定著人們從出發(fā)地移動到目的地的路線和方式。在數(shù)學(xué)領(lǐng)域，通過圖論來解決點、線的相關(guān)關(guān)系問題。在地理信息領(lǐng)域，通過對路網(wǎng)要素建立拓撲關(guān)系，利用迪杰斯特拉算法(Dijsktra)，A?算法解決最短路徑、最優(yōu)路徑問題。但未經(jīng)優(yōu)化的路網(wǎng)模型在索引時，效率極低，無法滿足應(yīng)用需求。

本文通過分析交通要素，提出了基于RTree空間索引的路網(wǎng)模型，用于進行公交、自駕、軌道交通等不同場景的最優(yōu)路線選擇。

2 現(xiàn)實世界網(wǎng)絡(luò)模型及其抽象

2.1 現(xiàn)實世界網(wǎng)絡(luò)模型

固定路網(wǎng)由各種類型的交通要素組成。在基礎(chǔ)數(shù)據(jù)中，參照相關(guān)標(biāo)準(zhǔn)及現(xiàn)實情況，可將交通中涉及的路網(wǎng)要素分為兩個大類型:

(1)普通交通

主要包括以下道路類型:

①國道

②省道

③縣道

④城市主干道

⑤城市次干道

⑥城市支路

⑦步行道

(2)定線交通

和普通交通路線不同，定線交通需要一些額外的信息，用于描述和判斷定線交通內(nèi)部、定線交通和普通交通之間的連通性。完整的線路連通信息包括:線路、站點、出入口、定線交通與普通線路的換乘線(參見ArcGIS92附帶的Tutorial Data，巴黎路網(wǎng)數(shù)據(jù))。如果條件不足以收集到足夠的軌道連通數(shù)據(jù)，則某些信息可省略，但線路、站點是必需的。城市定線交通包括以下道路類型:

①高速公路

②輕軌

③地鐵

④公交線路

2.2 抽象網(wǎng)絡(luò)模型

根據(jù)路網(wǎng)分析常見應(yīng)用，我們將現(xiàn)實世界中的路網(wǎng)抽象為兩大類別的網(wǎng)絡(luò)模型:自駕網(wǎng)絡(luò)和換乘網(wǎng)絡(luò)。其中，自駕網(wǎng)絡(luò)是真正意義上的傳輸網(wǎng)絡(luò)。在自駕網(wǎng)絡(luò)中，汽車是可以自由移動的物體，具有主觀選擇路線和方向的能力。換乘網(wǎng)絡(luò)由公交、地鐵、輕軌等人們在出行時可能選擇的城市交通路線組成，在換乘網(wǎng)絡(luò)中，所有路線都是事先預(yù)定的，例如地鐵線路沿途站點和路徑，不以人們意志為轉(zhuǎn)移。從分析角度而言，更類似于效用網(wǎng)絡(luò)。

圖1 路網(wǎng)模型目標(biāo)

①自駕網(wǎng)絡(luò)數(shù)據(jù)模型

自駕網(wǎng)絡(luò)數(shù)據(jù)模型 表1

②換乘網(wǎng)絡(luò)數(shù)據(jù)模型

換乘網(wǎng)絡(luò)數(shù)據(jù)模型 表2

3 關(guān)鍵技術(shù)及實現(xiàn)效果

3.1 空間索引算法

空間索引算法在空間查詢和分析中至關(guān)重要，它決定了結(jié)果的準(zhǔn)確性和速度。經(jīng)過考察，采用基于RTree的空間索引構(gòu)建路網(wǎng)模型。

R－Tree空間索引算法是B＋Tree在多維情況的自然擴展，同樣是一個高度自平衡樹。在R－Tree中，所有索引記錄存在于葉結(jié)點中，中間結(jié)點用于確定查詢等操作的路徑。葉結(jié)點包含索引對象的最小外接矩形和索引標(biāo)識符，形式為:(MRR，LeafID)。R－Tree按數(shù)據(jù)來組織索引結(jié)構(gòu)，無須預(yù)知整個空間對象所在的空間范圍，就能建立空間索引。并且具有與B＋Tree相似的結(jié)構(gòu)和特性，使其能夠很好地與傳統(tǒng)的關(guān)系型數(shù)據(jù)庫相融合，因此發(fā)展為一種重要的空間索引方法。

這種空間索引算法具有快速、方便的優(yōu)點。假如我們有20 000個節(jié)點，要找出任意一個矩形范圍內(nèi)的節(jié)點，采用遍歷方法，復(fù)雜度是20 000次遍歷；利用R－Tree進行索引，復(fù)雜度迅速降低到30次以下，大大提高了搜索效率。利用R－Tree索引進行搜索的方法是給定一個矩形區(qū)域，查詢所有在該區(qū)域內(nèi)或與該區(qū)域有交的索引項，查詢算法自根節(jié)點開始，搜索所有MBR與查詢區(qū)域有關(guān)的結(jié)點，并給出所有與查詢區(qū)域有關(guān)的索引項，然后遞推搜索索引項的各個分支，得到結(jié)果。

圖2 RTree算法

3.2 點和多段線空間算法

“點和多段線空間算法”主要用于計算點和點之間、線和線之間、點和線之間的空間關(guān)系。在路網(wǎng)模型中主要解決的主要空間算法包括:

基礎(chǔ)空間算法 表3

3.3 最優(yōu)路徑算法

最優(yōu)路徑算法可簡要描述為:計算單源出發(fā)點到單源目標(biāo)點之間最優(yōu)路徑的算法。NetworkService主要利用最優(yōu)路徑算法來進行自駕最優(yōu)路徑分析。

目前業(yè)界通用的最優(yōu)路徑算法主要包括兩個方向:以Dijsktra算法為代表的遍歷算法和以A?算法為代表的啟發(fā)式算法。前者勝在準(zhǔn)確，找出的路徑一定是最優(yōu)的，但是遍歷導(dǎo)致的時間復(fù)雜度往往不可接受；后者勝在快速，但找出來的路徑不一定最優(yōu)，路徑的最優(yōu)程度取決于H值(Heuristic)的選取。

圖3 采用Manhattan公式的A?算法

在測試用的自駕網(wǎng)絡(luò)中，一共包含21 717個節(jié)點。如果采用Dijsktra遍歷，那么復(fù)雜度為n2(21717?21717)，顯然是難以接受的；因此采用A?算法進行最優(yōu)路徑計算勢在必行。

A?算法的流程是:

(1)生成一個只包含開始節(jié)點n0的搜索圖G，把n0放在一個叫OPEN的列表上。

(2)生成一個列表CLOSED，它的初始值為空。

(3)如果OPEN為空，則失敗退出。

(4)選擇OPEN上的第一個節(jié)點，把它從OPEN中移入CLOSED，稱該節(jié)點為n。

(5)如果n是目標(biāo)節(jié)點，順著G中，從n到n0的指針找到一條路徑，獲得解決方案，成功退出(該指針定義了一個搜索樹，在第7步建立)。

(6)擴展節(jié)點n，生成其后繼節(jié)點集M1，在G中，n的祖先不能在M1中。在G中安置M1的成員，使它們成為n的后繼。

(7)從M1的每一個不在G中的成員建立一個指向n的指針(例如，既不在OPEN中，也不在CLOSED中)。把M1的這些成員加到OPEN中。對M1的每一個已在OPEN中或CLOSED中的成員m，如果到目前為止找到的到達m的最好路徑通過n，就把它的指針指向n。對已在CLOSE中的M1的每一個成員，重定向它在G中的每一個后繼，以使它們順著到目前為止發(fā)現(xiàn)的最好路徑指向它們的祖先。

(8)按遞增值，重排OPEN(相同最小值可根據(jù)搜索樹中的最深節(jié)點來解決)。

(9)返回第3步

在本次應(yīng)用中，采用了Manhattan算法計算H值(Manhattan distance曼哈頓距離:兩點在南北方向上的距離加上在東西方向上的距離，計算公式:H＝｜Dx｜＋｜Dy｜＋｜Dz｜)，采用PriorityQueue(二叉堆)進行G，H排序，提高了原有A?算法的效率(測試環(huán)境下最長時間復(fù)雜度為500毫秒，普通時間復(fù)雜度為10毫秒～100毫秒)

3.4 基于空間分析的換乘算法

在中國，公交換乘是空間應(yīng)用一個熱門話題，由此也衍生出一批有中國特色的公交算法[3，4]。這些算法基本上原理近似，描述如下:

基于出行次數(shù)最小的換乘算法 表4

表4描述的算法進行公交換乘，效率并不理想。可以看出，換乘次數(shù)越高，遍歷的復(fù)雜度越高，而且容易產(chǎn)生一些冗余的結(jié)果。在此基礎(chǔ)上，筆者自創(chuàng)了一種基于空間關(guān)系的換乘算法，較好地解決了上個換乘算法的問題。

改進的基于空間分析的換乘算法 表5

表5所述算法充分利用了空間索引的優(yōu)勢，極大地降低了遍歷次數(shù)。由于加入了步行換乘的考慮因素，在主城區(qū)范圍，基本能找到一次換乘方案。因此目前并沒有加入二次換乘的計算。經(jīng)過實踐，使用此算法的時間復(fù)雜度在10毫秒～100毫秒之間，能夠滿足要求。

3.5 完成效果

(1)自駕最優(yōu)路徑分析(Find Best Route)

綜合路網(wǎng)的各種因素(Cost:長度、行駛時間等；Restriction:是否單行；Hierarchy:等級路網(wǎng))，得到單源點到目標(biāo)點1條最優(yōu)路徑。

圖4 自駕分析效果

通過綜合路網(wǎng)分析，可按照高速優(yōu)先、距離最短優(yōu)先等多種條件獲取最優(yōu)路徑結(jié)果，如圖4所示，將得到的最優(yōu)路徑按路段進行分段展示，可提示轉(zhuǎn)彎路口等信息。

(2)換乘分析(Find Best Transfer Solutions)

綜合各種軌道交通(輕軌、公交、有軌電車等)，得到單源點到目標(biāo)點的1個或多個最優(yōu)換乘方案。

圖5 換乘分析效果

公交換乘可根據(jù)最少換乘次數(shù)、最短距離等多種條件進行分析，得到最優(yōu)換乘方案。如圖5所示，換乘方案中按照換乘的車輛編號和起點站終點站進行排列，可直觀的展示給用戶計劃的換乘站點。

4 結(jié) 語

本文在現(xiàn)實世界的交通要素基礎(chǔ)上，對路網(wǎng)模型進行抽象，將其分為自駕網(wǎng)絡(luò)模型和換乘網(wǎng)絡(luò)模型。然后基于RTree實現(xiàn)路網(wǎng)模型的空間索引，利用基于二叉堆的A?算法實現(xiàn)最優(yōu)路徑分析，自創(chuàng)基于空間分析的換乘算法實現(xiàn)換乘分析。經(jīng)過驗證，基于RTree的路網(wǎng)模型具有更高的效率，解決了地理信息應(yīng)用中基礎(chǔ)的路網(wǎng)問題。

[1] CormenH.Thomas.Introduction to Algorithms[M].The MIT Press，2001.ISBN:0262032937

[2] 張宏，溫永寧，張愛利.地理信息系統(tǒng)算法基礎(chǔ)[M].北京:科學(xué)出版社，2006.ISBN 7－03－016868－2

[3] 楊新苗，馬文騰.基于GIS的公交乘客出行路徑選擇模型[J].東南大學(xué)學(xué)報:自然科學(xué)版，2000，30(6):87～91

[4] 王建林.基于換乘次數(shù)最少的城市公交網(wǎng)絡(luò)最優(yōu)路徑算法[J].經(jīng)濟地理，2005，25(5):673～676

Design and Implementation of RTree－Based Road Network Model

Xue Mei，Xiang Hua
(Chongqing Cybercity Sci－tech co.，Ltd.Chongqing 400020，China)

This paper analyzed the elements of the real－world traffic，and proposed road network model based on RTree spatial index，which is used for public transportation，self－driing，rail transport，the optimal routing of different scenarios.The implementation greatly improved the road network analysis，indexing efficiency，and has strong practicability.

RTree；Road network model

1672－8262(2010)06－26－05

P208

A

2010—04—29

薛梅(1981—)，女，工程師，主要從事地理信息技術(shù)在行業(yè)中的應(yīng)用與推廣。