基于动态中介中心性的城市道路网实时分层方法

Time-dependent Road Network Hierarchy Based on Dynamic Betweenness Centrality

城市道路网中各路段的出行效率直接决定了公众实时出行过程中对道路的选择差异。本文提出一种动态道路网分层方法,通过引入城市道路实时交通状态信息,结合图论中的中介中心性评价方法,得到与时间相关的城市路网动态中介中心性层级结构。该方法考虑了不同时间段城市交通状态的差异,实现了城市路网层次的动态合理划分,在一定程度上缓解了由于数据空间范围限制引起的路网层级静态划分方法的局限性。本文所提出的方法可作为城市路网动态分层的有效方法,为多用户并发环境下的实时出行路径搜索提供更合理的数据基础,同时也可应用于更多的城市路网研究中。

Efficiency and reasonability of path querying are the key aspects for public travel information services.Although the well-known hierarchical spatial reasoning based on road class has been accepted as an efficient heuristic approach for solving the shortest path problem,in practice,it is difficult to get reasonable results without considering the influence of real-time traffic situation.City road network is strongly characteristic of time-dependence,which determines the selection of roads to a great extent in public travel.In this paper,we proposed an approach to real-timely building the hierarchy of city road networks,based on the dynamic betweenness centrality（BC） and path searching algorithms considering real-time traffic information.The city road network is modeled with the time-dependent dynamic BC hierarchical structure,and the real-time optimum path finding is conducted under the natively formed hierarchical network dataset.The presented approach considers ever-changing traffic situation,coordinates the time-dependent division of road network hierarchy and calculation efficiency under multi-user environment,and to some extent mitigates the boundary effect caused by the spatial limit under the static hierarchical structure of road network.It is argued that the presented approach provides an effective way to generate hierarchy of city road network in dynamic traffic environment,and forms a reasonable dataset basis for real-time optimum path searching under multi-user environment.We should note that our focus is the dynamic hierarchy approach,not the algorithm.Meanwhile,the approach is not only used for hierarchical spatial reasoning algorithm.It is available in any research related to the traffic information of city network,such as city hotspot research,city network structure analysis and so on.