基于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—)，女，工程师，主要从事地理信息技术在行业中的应用与推广。