EN中文

Journal of Geo-information Science >

2015 , Vol. 17 >Issue 9: 1039 - 1046

DOI: https://doi.org/10.3724/SP.J.1047.2015.01039

Orginal Article

A Driving Route Planning Method Based on Road Network Topological Hierarchy Expression

  • LIU Kang , 1, 2 ,
  • DUAN Yingying 1 ,
  • ZHANG Hengcai , 1, *
Expand
  • 1. State Key Lab of Resources and Environmental Information System, IGSNRR, CAS, Beijing 100101, China
  • 2. University of Chinese Academy of Sciences, Beijing 100101, China
*Corresponding author: ZHANG Hengcai, E-mail:

Received date: 2015-02-15

  Request revised date: 2015-04-25

  Online published: 2015-09-07

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

Mental representations of spatial knowledge are organized hierarchically. This should be introduced to route guidance in order to reduce the cognitive workload of drivers, and to increase drivers′ satisfaction and wayfinding success probability. The most commonly used hierarchical spatial reasoning based route planning methods take the hierarchical characteristic of road network into consideration, but the road design grade used in these methods does not conform to human′s hierarchy recognition of road network. In this paper, we introduce the complex network analysis methods, and take use of topological structure measures to express roads′ hierarchical characteristic. And on this basis, we propose a novel route planning method. The planned routes are compared to the taxi driving routes in reality and the travelling time decrements are calculated by comparing these routes to the distance shortest route. The experimental results indicate that, the routes that are planned using our method are more rational and optimal than the distance shortest routes, dynamic time shortest routes, road grade based time shortest routes and dynamic betweenness centrality hierarchy based routes, and are equivalent to the empirical taxi driving model based routes. Moreover, our method does not need the support of floating car system, hence it is more practical for promotion and application.

Key words： route planning; spatial cognition; topological structure; complex network; floating car data

Cite this article

LIU Kang , DUAN Yingying , ZHANG Hengcai . A Driving Route Planning Method Based on Road Network Topological Hierarchy Expression[J]. Journal of Geo-information Science, 2015 , 17(9) : 1039 -1046 . DOI: 10.3724/SP.J.1047.2015.01039

1 引言

在复杂城市路网中规划合理的驾车出行路径，是多个学科的研究热点。通常的路径规划算法力求通过优化数据结构和改进运筹学算法，减少路径搜索过程的时间复杂度[1-2]。这样得到的出行路径规划结果忽略了驾驶者对路网认知的层次性特征，不能真正符合出行要求。分层路径搜索算法虽然考虑了道路网络的分层特性，但其研究重点是提高搜索效率[3-5]，分层方式主要依据道路设计等级。然而，道路设计等级与驾驶者对路网的层次认知并不一致[6-7]。近年来，一些研究从大量出租车出行路径中统计路段被出租车司机选择的频次，并以此对路网进行经验分层[8-10]。这种方法是从数据驱动角度提取驾驶者对路网的认知经验。但该方法需部署浮动车系统，并且需大量的数据处理工作。
研究表明，路网拓扑可很好地刻画路网的层次特征[11]。因此，很多研究利用道路的拓扑结构指标度量人对道路的层次认知，并验证了其合理性[7,12-13]。此外，道路拓扑结构指标与道路交通流量之间具有很强的相关性[14-15]，以拓扑结构刻画的道路层次性能很好地反映道路的实际使用情况[16-17]。本文试图从路网拓扑结构出发，借鉴复杂网络分析方法度量道路的拓扑结构地位，以拓扑结构地位量化值代替传统的道路设计等级来表达道路的层次性特征，规划驾车出行路径。

2 驾车路径规划方法

本文从路网拓扑结构出发对路网进行层次性表达。此外，时间因素是影响出行的重要因素。因此，本文综合考虑路段长度、路段交通状态及路段拓扑结构地位进行出行路径规划。
（1）借鉴复杂网络领域的拓扑结构度量方法，对每条路段的拓扑结构地位进行度量，以表达道路的层次性;
（2）综合考虑道路路段长度、拓扑结构指标及交通状态，计算每条路段不同时段的出行耗费;
（3）将Dijkstra算法进行动态改造，计算给定起止路段之间时间依赖的耗费总和最小路径，实现驾车出行路径规划。

2.1 路段拓扑结构地位度量

已有研究表明，路链（Stroke，即由路段依据其几何形态组成的道路实体链），考虑了道路的整体属性，顾及了道路的几何形态，比路段更适合刻画道路的拓扑结构特征[18]，在道路网分层、道路自动选取中应用广泛[19-21]。而路链的重要程度无疑可有效反映其组成成分路段的重要性。因此，本文通过构建基于路链的对偶图来获取路链的拓扑结构指标，并将其赋予组成该路链的路段。
本文采用节点度（Degree）来度量道路的拓扑结构特征。节点度也称为连接中心性（Connection centrality），是网络中刻画节点重要性最简单的指标。其计算公式如式（1）所示。
d i = ∑ e ij （1）
式中， N 为节点集合; i 、 j 为集合 N 中的2个不同节点; e ij 表示节点 i 、 j 的连接情况。若 i 和 j 之间存在连接边，则 e ij 为1，否则为0。
对偶图中路链的连接中心性指标具有无标度特征。在对拓扑结构指标进行归一化时，为避免数值差异过于极端，本文使用LOG归一化与线性归一化结合的方法将连接中心性指标数值映射到（0,1）区间，如式（2）所示。
t i ¯ = lo g 10 t i - lo g 10 min ( t ) lo g 10 max ( t ) - lo g 10 min ( t ) （2）
式中， t i ¯ 为路链 i 归一化的拓扑结构指标值; t i 表示路链 i 原始的拓扑结构指标值; t 表示路网中所有路链的拓扑结构指标值。
本文采用自组织路链生成方法[14,22]，依据局部最优的自组织原则，将夹角较小的路段组合成较长的路链，并生成基于路链的城市路网对偶图，如图1所示。图1（a）中，相同字母表示的路段因符合自组织原则而生成同一条路链;图1（b）为以路链为节点，路链之间的连接关系为边得到的基于路链的对偶图。为在路段粒度上计算出行者的出行路径，本文将基于路链的对偶图计算出的每条路链的归一化的节点度赋予组成该路链的路段。图1（b）括号内的数字为各路链对应的连接中心性指标，将其赋予其组成路段，得到图1（c）所示的路段粒度的拓扑结构指标，表征路段的拓扑结构地位。
Fig. 1 Measurement process of road segments’ status

图1 路段拓扑结构地位度量

2.2 驾车路径规划算法

2.2.1 路段出行耗费计算
综合考虑路段长度、路网拓扑结构特征及道路交通状态3个因素，本文按式（3）确定各路段出行耗费值。
W ij = L i V ′ ij T i ¯ （3）
式中， W ij 为路段 i 在时段 j 的出行耗费; L i 为路段 i 的长度; V ′ ij 为路段 i 在时段 j 的通行速度， T i ¯ 为路段 i 归一化的拓扑结构指标。因此，路段通行速度越高，拓扑结构指标越大（即拓扑结构地位越高），路段出行耗费就越小。
2.2.2 驾车路径计算
本文设计了顾及路网拓扑结构的驾车出行寻径算法的目标方程（式（4））。
Dest = ∑ i = 1 N W ij （4）
顾及路网拓扑结构的驾车路径计算过程是追求道路寻径算子值最小的过程，即寻找起终点间一条总耗费最小的路线。本文利用时间离散切片方法，将Dijkstra算法进行了动态改造，以计算给定起止路段之间时间依赖的耗费总和最小路径。算法流程如下：
（1）以用户指定的起点所对应的路段作为起始路段，依据路网的拓扑关系，采用Dijkstra算法对该路段的下游路段进行扩展搜索。
（2）扩展到当前路段 i 时，确定当前时间段<i>j</i>。
j = t - T 0 ΔT + 1 （5）
式中， t 表示车辆驶入当前路段的时刻; T 0 表示系统起始时间;符号[]表示取整运算，如[3.7]为3; ΔT 表示划分的每个时间段的时长，本文中为15 min，因此， j 的取值为 1,2 , … , 96 。
（3）用式（3）计算当前路段在时段 j 的耗费 W ij ，进行扩展搜索。记此次扩展搜索到的结果为路段 e ，扩展后的当前时间更新为 t ′ 。
t ′ = t + Le Vej （6）
式中， Le 表示路段 e 的长度; Vej 表示路段 e 在时段 j 的归一化通行速度。
（4）重复步骤（2）-（3），直至搜索到终止路段。

3 路径规划实验对比分析

3.1 实验数据

本文所使用的城市路网数据为北京市五环及五环周边的道路中心线数据，包含了环路、快速路、主干道、次干道和支路，共有18 857个交叉口和26 621条路段（图2）。
Fig. 2 Experimental road network

图2 实验路网

本文中用以与规划路径进行比较的出租车出行路径由配备GPS的出租车采集。将2011年3月出租车载客状态下的原始GPS轨迹利用ST-Matching算法[23]与道路中心线数据进行地图匹配处理，从中随机抽取100 000条出租车的真实出行路径。

3.2 实验结果与分析

3.2.1 路径合理性评价
出租车驾驶者具有丰富的路径选择经验。通常认为出租车司机选择的行车路径是比较合理的。因此，本文将规划路径与相同起止点间的真实出租车行驶路径进行对比，以检验本文设计的规划路径的合理性。
本文提取出租车行驶路径的起止点（OD），分别利用距离最短路径算法、动态时间最短路径算法、基于道路设计等级的静态时间最短路径算法、基于动态中介中心性分层的距离最短路径算法[24]、基于出租车经验建模的路径规划算法[8]及本文顾及城市道路网络拓扑结构的驾车路径算法，计算出所有OD之间的最优出行路径，再与OD之间出租车真实行驶路径进行对比。其中，距离最短路径算法仅考虑了道路的几何长度，动态时间最短路径仅考虑了道路的交通状态，二者均不涉及人对路网的层次认知经验;基于道路设计等级的静态时间最短路径算法，将路段长度与路段设计等级限速之比设置为路段出行耗费，以道路设计等级作为人对路网的层次认知经验;基于动态中介中心性分层的最短路径算法，将考虑交通状态及交叉口通行耗时得到的动态中介中心性作为路网分层依据;基于出租车经验建模的路径规划算法，从出租车行驶轨迹中提取人对路网的认知经验;本文方法则是从路网拓扑结构中提取人对路网的认知经验。规划路径与出租车司机真实行驶路径之间的匹配度计算如式（7）所示。
M = ∑ u i ∑ j = 1 N l j （7）
式中， M 表示相同OD之间2条路径的匹配度; u i 表示规划路径与出租车行驶路径共同经过的路段 i 的长度; l j 为真实路径中路段 j 的长度; N 为真实路径中路段的数目。
计算所有OD对之间规划路径与出租车行驶路径的匹配度，并统计其在各个区间的累积分布比例（表1）。由表1可看出，本文方法所规划的路径与出租车行驶路径的匹配度高于距离最短路径、动态时间最短路径、基于道路设计等级的时间最短路径及基于动态中介中心性分层的距离最短路径与出租车行驶路径的匹配度。距离最短路径仅考虑道路的几何长度，动态时间最短路径仅考虑了道路的交通状态，二者均忽略了道路的层次性特征;道路设计等级的最快路径虽然考虑了道路的层次性特征，但这种层次性的道路设计等级，有别于实际使用等级或人对道路的认知等级;基于动态中介中心性的最短路径算法，将考虑交通状态及交叉口通行耗时得到的动态中介中心性作为路网分层依据，然而，动态中介中心性的计算过程隐含了驾驶者出行路径为纯粹的动态时间最短路径和出行OD分布均匀2点假设，并不十分合理;本方法所规划的路径用拓扑结构指标刻画道路的层次性特征，更符合道路的实际使用情况及人对道路的层次性认知经验，同时兼顾了道路交通状态对出行行为的影响，因此更接近经验出租车司机所选择的路径。本方法可理解为在动态时间最短路径算法的基础上考虑了道路层次性特征，而结果显示本文方法所规划的路径相比于单纯的动态时间最短路径，与出租车的行驶路径匹配度更高，说明本文将路网拓扑结构指标引入路径规划算法来表达道路的层次性特征是合理有效的，所规划的路径更符合人的实际出行。此外，本方法与以出租车经验建模的路径规划方法所得结果相近。经统计，后者以各时段路段出租车平均通行频次计算得到的路段经验值与用本方法计算得到的路段拓扑结构地位度量值之间的皮尔森相关系数在0.7左右，说明用这2种方式度量人对路网的层次认知经验是较一致的。但本方法不需出租车经验建模所依赖的浮动车系统支持，更利于部署应用。

3.2.2 路径耗时评价

本文分别计算相同OD及出发时间下,不同规划算法所得路径相比于距离最短路径的出行耗时减幅,每条路径的出行耗时减幅计算公式如式（8）所示。
D = T 0 - T T 0 × 100 % （8）
式中, T 和 T 0 分别表示用某种路径规划算法和距离最短路径算法所得路径的出行耗时。出行耗时计算过程中的道路速度考虑了行程时间累加引起的变化,同时,出行路径耗时考虑了交叉口的通过耗时[25]。表2为不同路径规划方法计算所得的100 000条路径的出行耗时减幅。
Tab. 2 Decrements of the traveling time for routes planned by different methods compared with the distance shortest route

表2 不同路径相比于距离最短路径的出行耗时减幅

方法 平均值(%) 最小值(%) 最大值(%) 标准差
距离最短路径 0.00 0.00 0.00 0.000
动态时间最短路径 10.03 -28.88 74.85 0.156
基于道路等级的时间最短路径 2.23 -211.31 70.75 0.225
基于动态BC分层的最短路径 4.81 -211.31 70.75 0.185
基于出租车经验建模的最短路径 6.48 -311.58 70.75 0.204
本文方法 5.46 -214.07 70.75 0.206
动态时间最短路径的出行耗时减幅,相比于其他路径规划算法最大。然而,本文的重点并非寻找时间最短路径,而是寻找可顾及人对道路层次性认知的路径。在此基础上,路径耗时越少则方法越优。因此,路径耗时主要在不同的顾及道路层次性表达的路径规划算法中进行比较。从表2可看出,本文基于路网拓扑层次性表达的路径规划方法所规划的路径,相比于基于道路设计等级的时间最短路径、基于动态中介中心性分层的距离最短路径,所耗费的出行时间更少;虽然比基于出租车经验建模的最短路径耗费略多,但本文方法不需出租车经验建模所依赖的浮动车系统支持,更利于部署应用。
3.2.3 路径规划示例
本文选取了出发时间为03:22、08:02和15:07,起点为望京、终点为车公庄大街的一对OD,用不同方法规划OD之间的行驶路径（图3）。由图3可看出,距离最短路径仅考虑道路的几何长度,转向较多且经过很多低等级道路;静态时间最短路径途径四环、京承高速、三环、京藏高速和二环,可明显看出路径主要基于道路的设计等级,且不同出行时间的规划路径相同;本文提出的基于城市路网拓扑层次性表达的驾车路径规划路线,相比于动态时间最短路径、基于动态中介中心性的最短路径及出租车经验建模的规划路径,并没有局限于规划等级较高但极易拥堵的道路（如高速路、环路）,例如,在早高峰8:02时,路径经由四环转向了拓扑结构层次性较高的主干道,路线与经验出租车司机的行驶路径基本一致。
Fig. 3 Comparison of different route planning methods

图3 不同算法规划路线对比图

4 讨论

Claramunt等人指出,导航设备应当融合人对路网的空间认知经验,以提高用户满意度和导航的成功率[12]。人对空间的层次性认知是一个自组织的过程,在对路网的认知过程中,人与路网不断进行交互,从无到有建立对路网的认知图。认知图 中越是显著的道路,越是被驾驶者所熟知,在寻路过程中被选择的概率也更大[7]。近年来,一些研 究从大量出租车出行路径中统计路段被出租车司机选择的频次,并以此对路网进行经验分层。这种方法实际上是从数据驱动的角度提取驾驶者对 路网的认知经验,与本研究的出发点比较相似,但该方法需获取足够量的原始浮动车数据,还需进行大量的数据处理工作。相比之下,本研究直接从路网结构中提取认知经验,利用路网的拓扑结构地 位来表达人对道路的认知强度,规划出的路径不但符合驾驶者对路网的认知,也更易推广于实际应 用中。
除此之外,本文还有以下贡献：
（1）将路链粒度上度量的拓扑结构指标赋予路段,以评价路段粒度上的拓扑结构地位。以往的研究多是以某一种道路抽象粒度（如路段、路链等）,借鉴复杂网络评价指标,对路网进行功能评价。然而,这种方式存在一些偏颇,例如,路链通常比路段更适合作为拓扑结构评价粒度,而真实的交通流变化以及人们的出行又是基于交叉口之间的路段,单纯使用某一种粒度进行表达和评价有时是不合理的。本研究认为,路链粒度上获取的拓扑功能度量值可反映其组成路段的功能地位,采用将路链粒度上获取的拓扑结构指标赋予其组成路段的方式对路段拓扑结构地位进行评价。这种方法对于评价路段功能地位具有借鉴意义。
（2）将道路规划结果与出租车司机的真实行车路径作比较,对道路规划方法进行评价。出租车司机已建立起对整个城市路网的认知体系,具有丰富的路径选择经验,其行车路径是比较合理的。因此,本文将规划路径与相同起止点间的真实出租车行驶路径进行对比,是一种合理有效的评价方法,对今后的路径评价具有借鉴意义。
本研究还存在一些不足。例如,本研究认为出行时间是影响驾驶者路径选择行为的重要因素,因此,在路径算法中融入了道路交通状态。实际上,在出行过程中,交叉口通行耗时占总出行时间的 比重达到30%以上[26],驾驶者可能倾向于避开一些耗时较长的交叉口而选择其他路径出行。因此,进一步的研究应当顾及交叉口通行耗时对路径选 择行为的影响,并将这种影响融入到路径规划算 法中。

5 结论

路网拓扑结构可很好地刻画路网的层次性特征,更符合道路的实际使用情况及人对道路的经验性层次认知。因此,本文借鉴复杂网络分析方法,在路径规划算法中考虑路网拓扑结构特征,以拓扑结构指标代替传统的道路设计等级来表达道路的层次性特征,综合了路段长度、路段交通状态及路段拓扑结构地位3个要素,改进路径搜索算法,对驾车路径进行规划。实验结果表明,基于路网拓扑层次性表达的规划路径优于距离最短路径、动态时间最短路径、基于道路设计等级的静态时间最短路径及基于动态中介中心性分层的距离最短路径,并与基于出租车经验建模的路径规划结果持平,但因本方法不需获取和处理大量浮动车数据,更易推广于其他城市,故更具可行性和合理性。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
陆锋. 最短路径算法:分类体系与研究进展[J].测绘学报,2001,30(3):269-275.

[2]
陆锋,卢冬梅,崔伟宏.交通网络限制搜索区域时间最短路径算法[J].中国图象图形学报,1999,4(10):849-853.

[3]
陆锋,周成虎,万庆.基于层次空间推理的交通网络行车最优路径算法[J].武汉测绘科技大学学报,2000,25(3):226-232.

[4]
李楷,钟耳顺,曾志明,等.基于分层网络拓扑结构的最优路径算法[J].中国图象图形学报,2006,11(7):1004-1009.

[5]
李清泉,郑年波,徐敬海,等.一种基于道路网络层次拓扑结构的分层路径规划算法[J].中国图象图形学报,2007,12(7):1280-1285.

[6]
郭继孚. 从行车路径看城市路网功能结构问题——以北京市为例[J].城市问题,2007(6):77-80.

[7]
Tomko M, Winter S, Claramunt C.Experiential hierarchies of streets[J]. Computers, Environment and Urban Systems, 2008,32(1):41-52.

[8]
唐炉亮,常晓猛,李清泉.出租车经验知识建模与路径规划算法[J].测绘学报,2010,39(4):404-409.

[9]
唐炉亮,常晓猛,李清泉.基于蚁群优化算法与出租车GPS数据的公众出行路径优化[J].中国公路学报,2011,24(2):89-95.

[10]
胡继华,黄泽,邓俊,等.融合出租车驾驶经验的层次路径规划方法[J].交通运输系统工程与信息,2013,13(1):185-192.

[11]
Jiang B.A topological pattern of urban street networks: universality and peculiarity[J]. Physica A: Statistical Mechanics and its Applications, 2007,384(2):647-655.

[12]
Claramunt C, Winter S.Structural salience of elements of the city[J]. Environment and Planning B: Planning and Design, 2007,34:1030-1050.

[13]
Omer I, Jiang B.Topological qualities of urban streets and the image of the city: A multi-perspective approach[C]. 11th AGILE International Conference on Geographic Information Science, 2008:1-11.

[14]
Jiang B, Zhao S, Yin J.Self-organized natural roads for predicting traffic flow: A sensitivity study[J]. Journal of statistical mechanics: Theory and experiment, 2008(7): 1-27.

[15]
Jiang B, Liu C.Street-based topological representations and analyses for predicting traffic flow in GIS[J]. International Journal of Geographical Information Science, 2009,23(9):1119-1137.

[16]
Lämmer S, Gehlsen B, Helbing D.Scaling laws in the spatial structure of urban road networks[J]. Physica A: Statistical Mechanics and its Applications, 2006,363(1):89-95.

[17]
Jiang B.Street hierarchies: a minority of streets account for a majority of traffic flow[J]. International Journal of Geographical Information Science, 2009,23(8):1033-1048.

[18]
Thomson R C, Richardson D E.The “Good Continuation” principle of perceptual organization applied to the generalization of road networks[C]. Proceedings of 19th International Cartographic Conference, 1999:1215-1223.

[19]
徐柱,刘彩凤,张红,等.基于路划网络功能评价的道路选取方法[J].测绘学报,2012,41(5):769-776.

[20]
栾学晨,杨必胜,张云菲.城市道路复杂网络结构化等级分析[J].武汉大学学报:信息科学版,2012,37(6):728-732.

[21]
刘刚,李永树,杨骏,等.对偶图节点重要度的道路网自动选取方法[J].测绘学报,2014,43(1):97-104.

[22]
Yang B, Luan X, Li Q.Generating hierarchical strokes from urban street networks based on spatial pattern recognition[J]. International Journal of Geographical Information Science, 2011,25(12):2025-2050.

[23]
Lou Y, Zhang C, Zheng Y, et al.Map-matching for low-sampling-rate GPS trajectories[C]. Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM, 2009:352-361.

[24]
周亮,陆锋,张恒才.基于动态中介中心性的城市道路网实时分层方法[J].地球信息科学学报,2012,14(3):292-298.

[25]
Liu X, Lu F, Zhang H, et al.Intersection delay estimation from floating car data via principal curves: A case study on Beijing’s road network[J]. Frontiers of Earth Science, 2013,7(2):206-216.

[26]
郑年波,陆锋,段滢滢.道路转向延迟的动态对偶图模型[J].中国图象图形学报,2010,15(6):915-920.

Options
Outlines

/

〈 〉