基于RTree的路網模型設計及實現

薛梅，向華

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

基于RTree的路網模型設計及實現

薛梅?，向華

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

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

RTree；路網模型

1 引 言

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

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

2 現實世界網絡模型及其抽象

2.1 現實世界網絡模型

固定路網由各種類型的交通要素組成。在基礎數據中，參照相關標準及現實情況，可將交通中涉及的路網要素分為兩個大類型:

(1)普通交通

主要包括以下道路類型:

①國道

②省道

③縣道

④城市主干道

⑤城市次干道

⑥城市支路

⑦步行道

(2)定線交通

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

①高速公路

②輕軌

③地鐵

④公交線路

2.2 抽象網絡模型

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

圖1 路網模型目標

①自駕網絡數據模型

自駕網絡數據模型 表1

②換乘網絡數據模型

換乘網絡數據模型 表2

3 關鍵技術及實現效果

3.1 空間索引算法

空間索引算法在空間查詢和分析中至關重要，它決定了結果的準確性和速度。經過考察，采用基于RTree的空間索引構建路網模型。

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

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

圖2 RTree算法

3.2 點和多段線空間算法

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

基礎空間算法 表3

3.3 最優路徑算法

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

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

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

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

A?算法的流程是:

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

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

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

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

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

(6)擴展節點n，生成其后繼節點集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中的每一個后繼，以使它們順著到目前為止發現的最好路徑指向它們的祖先。

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

(9)返回第3步

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

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

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

基于出行次數最小的換乘算法 表4

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

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

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

3.5 完成效果

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

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

圖4 自駕分析效果

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

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

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

圖5 換乘分析效果

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

4 結 語

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

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

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

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

[4] 王建林.基于換乘次數最少的城市公交網絡最優路徑算法[J].經濟地理，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—)，女，工程師，主要從事地理信息技術在行業中的應用與推廣。