动态城市道路分层

1引言

路径搜索算法是导航与位置服务领域的关键技术。在大规模用户群体在线实时查询不断增长的背景下，其研究重点已由单纯追求计算效率逐渐上升为计算效率与路径搜索结果合理性并重，以便在动态交通环境下，充分模拟人类认知过程，获取合理可靠的出行路径规划结果［1－2］。层次空间推理是路径搜索算法中最常用的启发式策略，通过减小搜索空间提升算法效率。分层结构、层次切换规则和规划结果分析是层次空间推理搜索算法的核心［3］。以往的研究工作大都从路网的静态属性信息出发，分析路网的层级性，如道路等级、道路通达度等。然而，城市路网具有极强的动态特征，不同道路在不同时刻的重要程度是变化的。通过对路网动态属性的研究，可以得到不同时段的道路出行效率分布，能更好地反映城市的功能结构，支持导航与位置服务，并辅助交通诱导和管理。本文提出动态中介中心性的城市道路网分层方法，将道路的交通状态信息与路网的拓扑结构关系相结合，以反映不同时刻道路在出行中的效率。基于此指标对路网进行时间依赖的层次结构划分，筛选路网中影响出行效率的关键道路，可以提高实时出行路径规划结果的合理性，同时路网的动态分层可作为路径查询层次搜索算法的数据基础，提高路径搜索效率。需要说明的是，分层算法是动态分层的一个应用载体，本文的重点不在于分层算法，而是通过算法的对比分析，体现动态分层的效果，并可适用于其他的城市路网研究。

2道路网分层相关研究的分析

城市道路网分析评价标准很多，比如路网的连通性、可达性等等。最常用的是道路的语义信息，如道路等级。其他还有图论法［2，4－8］，感知分组的方法［9－10］和agent的方法［11－12］等。Mackaness等人在道路网概括时，用图论计算网络的连接性和最小代价生成树，分析了图论在保留拓扑关系层面上支持线性地物概括的可能性［4－5］；Thomson和Richard－son把道路网分解成一系列最短路径生成树，每条道路段按照类似河流级数的规则在树中排序，这样道路的权重可集成在树里［6］。江斌等利用一种改进的图论方法对路网建模，把同名道路当作节点，道路交叉口当作边来构建连通图［7－8］。道路的几何属性是路网概括中另一个重要因素。Thomson和Richardson阐述了路链（stroke）的概念［9］，依据道路的几何形态将路网划分为多个没有分支、彼此相交的路链，通过对路链长度和属性的分析，反映其在路网中的重要性。Morisset和Ruas通过道路用途评估其重要性，利用基于模拟的方式，得到高使用频度的道路［11］。分层路径寻优算法（HPFA）是近年来国内外学者关注的焦点之一。HPFA的实现依赖于一种分层路网模型（HRNM）的建立。在过去的研究中，侧重于改进HPFA算法的居多［13－15］，而详细探讨HRNM的文献较少。文献［16］提出一种模型，特点是高层子网抽象程度高，以减小数据规模。文献［13］提出一种改进的模型，降低了高层子网的抽象程度，无需冗余存储，便于在实际路网中实现。文献［17］提出一种HEPV模型，将大型图网分成小型图碎片并按层次的方式管理，采用预先存储最短路径结果来提高搜索效率。在其他分层搜索的研究中，很多采用了按道路等级简单分层的方式。这些方法都注重分层结构的拓扑一致性，分层计算效率也得到优化，但都没有从分层结果的合理性去考虑分层的标准。传统观点认为人们出行偏向于走等级高的道路，在现实中并不一定合理。因此，需要找到一种能较好保证出行路径合理性的路网分层标准，不仅要考虑拓扑关系，还需要考虑道路的交通状态随时间变化的属性。

3道路运输效率的动态性分析

道路运输效率是道路运输能力和在路网中地位的统一反映。城市路网由于地理空间的限制，并不能单纯以道路的设计时速作为衡量其运输效率的指标，还需要考虑道路在整个网络上的位置和空间关系。作为分层依据，道路的运输效率评估是全局性的，同时也是动态变化的。通过改造图论中的评价指标———中介中心性，我们将道路的设计时速和拓扑重要度综合起来评估城市道路的运输效率。

3．1中介中心性定义复杂网络分析中，中心性（是度量网络中节点重要性的方法。中介中心性（Between－nessCentrality，BC）表示一个节点作为媒介（桥）的能力，中介性越高，表示节点间的最优路径通过此节点的比率越高。对于城市交通来说，它表示两个非联路段间的相互联系依赖于其他路段的程度。假设有向图G＝（V，E），V为顶点集，E为边集，权重l为边的权重，一条路径P＝｛s，（s，v1），v1，（v｝为源顶点s∈V到目标节点t∈V之间的路径，它是由一系列顶点和边组成的序列集。假设gst为从节点s到节点t的最短路径的数量，则gst（v）为从节点s到节点t的最短路径中通过节点v的路径数量。节点v的中介中心性的定义为：（1）交通出行中，路段是路径规划的基本单元，计算路段的中介中心性时，可对原路网生成对偶图，将路段视作节点，路段间的联系视为边。

3．2中介中心性的动态性评价城市路段重要性的指标有很多，如图论中的度中心性等，道路属性中的道路等级、平均交通流量、交通分担率等，这些指标决定了路网的静态本质。文献［18］利用中介中心性对复杂网络的拓扑进行优化和拥堵预测，在仿真环境下，改善中枢节点的拥堵状况，提高网络容量。文献［19］计算了国内6个主要城市路网的中介中心性分布，讨论分析了其层级性和所属道路等级的关系，从一定程度上反映了城市道路的分布规律，但未利用城市道路的交通状态信息。城市交通的动态特征决定了节点或路段的中介中心性也应当具有时间依赖特征。动态最短路径算法根据路段上的实时车速和交叉口耗费时间，判断路径规划过程中的路径选择，计算行车时间最短的路径结果。依据实时计算的节点间行车时间最短路径计算结果，即可得到某时刻路网中各道路的中介中心性。基于动态中介中心性的空间分布格局，可以制订更合理的路网动态分层策略。

4道路网实时分层方法

在动态最短路径算法中，除了实时道路状态信息，还需要考虑交叉口耗费时间。道路交叉口是路网空间结构的重要组成部分。研究表明，交叉口的转向时间耗费至少占整个出行时间的17％～35％［20］，对国内大型城市这一比例更高［21］。在本研究中我们采用浮动车轨迹数据挖掘方式来估计交叉口通行耗费时间。具体方法可参看文献［21］。城市道路网实时分层基于中介中心性评价方法的具体步骤如下：（1）设定路网中道路集合为Q，集合大小为l，起始路段集合为S＝Q，终止路段集合为E＝Q，选取S中任一道路作为起始路段，记为s，选取E中任一道路作为终止路段，记为e。设置Q中所有路段被经过的次数Pn＝0；（2）将道路集合中的道路看作节点，道路交叉口看作边。利用改进的Dijkstra算法计算其间的实时最短路径，改进的Dijkstra算法为：进行节点扩展时，修改权重为W＝length。定义当前节点为W＝t1＋t2，待扩展的节点为m，则t1为n1到n2的转向时间，t2为经过n2时耗费的时间，即t2＝lengthn2／vn2，其中，lengthn2为道路的长度，vn2为道路的实时速度。计算完毕后，记E＝E－e；（3）记录最短路径中所有经过的道路，对于每条被经过的道路p，记Pn＝Pn＋1；（4）从E中任意选取一道路作为终止路段，记为e，重复步骤（2），（3），直至E＝，并记终止路段集合为E＝Q，S＝S－s，重复步骤（2），（3），（4），直至S＝，则对于所有路段，其动态中介中心性Bn＝Pn／l。最后，依据路段的动态中介中心性值对路网分层（流程见图1）。

5路网分层实验分析

5．1实验的环境实验地图数据为北京市五环路以内的导航地图，包括12944条路段，分为4个道路等级。道路交通状态信息为20000多台出租车构成的浮动车系统采集的2011年3－6月的出租车轨迹数据，采集时间间隔为2分钟。我们把轨迹数据分为周一至周日7个数据集，对同一数据集内不同时刻（文中以15分钟为一个时刻）某一路段采用该路段上所有浮动车速度取均值的方法，计算每一条路段上出租车的行驶速度，并以此作为该路段上该时刻机动车平均行驶速度。道路一天中的交通状态变化规律呈现时间阶段的稳定性，因此，我们选取2个代表性时刻（早高峰8点和凌晨3点）作为示例，研究城市路网的动态中介中心性变化。实验中随机选取了一周中一天的数据（星期一）。我们利用层次空间推理算法（HierarchicalSpatialReasoning，HSR）来验证分层方法的有效性和合理性。随机抽取10000条OD道路，对比采用道路等级分层算法（ClassHSR）和动态中介中心性分层算法（DynamicBCbasedHSR，DBCHSR）进行路径计算的结果。层次空间推理的效率提升已无需证明，所以，这里主要比较不同分层算法结果之间的差异。经过筛选，OD道路间的有效最短路径有8200条。计算某时刻动态中介中心性的过程中，需考虑行程时间对路径权重的影响，每条即将扩展的道路速度不是起始时刻的速度，而是行程时间累加后当前时刻的道路速度。某时刻的动态中介中心性计算考虑了行程时间累加效应，计算结果唯一，即分层结果唯一，故此计算过程可以在后台进行。动态分层是数据预处理过程，并非分层算法的一部分，且可以后台运算，所以，在比较算法效率时不需要考虑分层的处理时间。分层算法使用动态分层时，可能涉及到不止一个动态分层结果（路径行程时间超过动态分层的时间间隔）。使用动态分层有两种方式：（1）在实时导航中，新的分层产生时触发分层算法重新计算当前道路到目标道路的路径，分层时间无需固定，此时动态分层利用的交通信息可以为实时数据或历史数据；（2）在路径规划计算时就考虑可能的分层，根据行程时间累积，在扩展节点时选择不同的预估分层路网进行计算，此时动态分层利用的交通信息为历史数据。本文实验采用的是第二种方法。

5．2实验结果与讨论图2是城市路网的等级分布，红色为环路和高速公路，蓝色为主干道，绿色为次干道，灰色为其他道路。依据道路等级的分布，我们将中介中心性的计算结果按照层内数量相同分为4层。图3是传统的道路静态中介中心性计算结果（最短路径算法采用路段长度作为权值），可以看出道路静态中介中心性呈由中心向外放射性递减趋势。地图区域的局限性决定了与道路及中心道路的结果差异，道路明显被低估。静态中介中心性采取网络距离最短算法，因此，处于几何中心的道路被经过的概率更大。动态中介中心性考虑交通状态在道路选择过程中采用耗时最短策略，减少了数据范围的局限引起的结果偏差。图4（a）和（b）分别是凌晨3点和上午8点道路动态中介中心性计算结果。分析动态分层带来的变化，我们将基于DBHSR的结果路径出行耗时与基于ClassHSR结果的路径耗时进行比较。两者同时采用相同的出发时刻（凌晨3点和早8点），过程中的道路速度考虑了行程时间累加引起的变化，而不是统一采用出发时刻的速度。同时，出行路径耗时考虑了交叉口的通过耗时。对于同一OD对，记基于ClassHSR算法的距离最短路径出行耗时为Tclass，基于DBCHSR算法的时间最短路径对应的出行耗时为TDBC，则后者相8200个样本的E值统计结果如表1所示。可从图5－7中可以看出，在凌晨3点，基于DBCHSR和基于ClassHSR规划的路径基本一致，路径耗时预估分别为30分钟和33分钟，在早高峰8点，基于DBCHSR的路径规划结果没有选择走西北三环，路径耗时预估为45分钟，而此时的基于ClassHSR规划的路径耗时预估为55分钟。从以上实验可以得出，基于动态中介中心性的分层算法能有效反映不同时刻道路路况的变化，同时继承了分层算法的高效性，既能满足动态出行路径规划的合理性需求，又提高了计算的效率，与传统道路分层方法相比更具优越性。

6结论

采用道路动态中介中心性计算方法得到的城市路网结构与道路类型结构之间存在明显差异。而这种差异性正是不同时刻城市交通出行最优路径选择的依据。考虑道路拓扑关系和交通状态信息，道路动态中介中心性计算方法获取动态变化的城市路网空间结构，并依此评价城市交通出行过程中道路的重要性，进行层次空间推理下的实时出行路径规划，既提高了计算效率，定量反映了城市道路交通状态变化规律，也更符合人们的认知习惯。必须看到，交通信息的完整性和准确性是制约该方法的最大因素。研究交通状态的时序变化规律可降低道路动态分层的计算频率，增强实际操作性。同时，本文所提出的方法不局限于城市实时出行路径规划，也可用于其他具有时间依赖特性的交通相关研究，如城市的热区分析等。以看出，基于DBCHSR算法的路径结果平均出行耗时比ClassHSR的短，说明在相同的算法条件下，基于DBCHSR计算的路径更优。在凌晨3点时，两者的差异并不明显，而在早高峰时，复杂路况引起的出行道路选择变化更为明显。图5－7是选择国家体育场至北京西站作为OD对，3种不同的路径规划结果。