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.
ZHOU Liang, LU Feng, ZHANG Hengcai
. Time-dependent Road Network Hierarchy Based on Dynamic Betweenness Centrality[J]. Journal of Geo-information Science, 2012
, 14(3)
: 292
-298
.
DOI: 10.3724/SP.J.1047.2012.00292
[1] Yue Y, Yeh A G O and Li Q Q. Road network model for vehicle navigation using traffic direction approach . In Proceedings of the 13th International Symposium on Spatial Data Handling, June 2008, 613-629.
[2] Fang Z X, Li Q Q and Zhang X. A multiobjective model for generating optimal landmark sequences in pedestrian navigation applications[J]. International Journal of Geographical Information Science, DOI: 10.1080/13658816.2010.500290.
[3] Car A and Frank A. General principles of hierarchical spatial reasoning: the case of way finding . In Proceedings of the 6th Internatinoal Symposium on Spatial Data Handling,September 1994,646-664.
[4] Mackaness W A and Beard K M. Use of graph theory to support map generalization[J]. Cartography and Geographic Information Science, 1993, 20 (4): 210-221.
[5] Mackaness W A. Analysis of urban road networks to support cartographic generalization[J]. Cartography and Geographic Information Science, 1995(22): 306-316.
[6] Thomson R C and Richardon D E. A graph theory approach to road network generalization . In Proceeding of the 17th International Cartographic Conference, 1995:1871-1880.
[7] Jiang B and Claramunt C. A structural approach to the model generalization of an urban street network[J]. Geoinfomatica, 2004, 8 (2): 157-171.
[8] Jiang B and Harrie L. Selection of streets from a network using self-organizing maps[J]. Transactions in GIS, 2004(8): 335-350.
[9] Thomson R C and Richardon D E. The "good continuation" principle of perceptual organization applied to the generalization of road networks . In Proceedings of the ICA 19th International Cartographic Conference, 1999,1215-1223.
[10] Thomson R C and Brooks R. Exploiting perceptual grouping for map analysis, understanding and generalization: the case of road and river networks[J]. Graphics Recognition Algorithms and Applications, 2002(1):148-157.
[11] Morisset B and Ruas A. Simulation and agent modeling for road selection in generalization. In Proceedings of the ICA 18th International Cartographic Conference, 1997,1376-1380.
[12] Lamy S, Ruas A, Demazeu Y, et al. The application of agents in automated map generalization . In Proceedings of the ICA 19th International Cartographic Conference, 1999, 1225-1234.
[13] Jagadeesh G R, Srikanthan T and Quek K H. Heuristic techniques for accelerating hierarchical routing on road networks . IEEE Transactions on Intelligent Transportation Systems, 2002, 3 (4): 301-309.
[14] Weng M, Wu H H, Du Q Y, et al. A heuristic and hierarchical way finding algorithm based on the knowledge of road network[J]. Geomatics and Information Science of Wuhan University, 2006, 31 (4): 360-363.
[15] Wu X L, Li Q Q and Ren F. Bidirectional A* algorithm based on hierarchical and block data organization[J]. Journal of Geomatics, 2006, 31 (6): 1-3.
[16] Lu F, Zhou C H and Wan Q. An optimum vehicular path algorithm for traffic network based on hierarchical spatial reasoning[J]. Journal of Wuhan Technical University of Surveying And Mapping, 2000, 25(3): 226-230.
[17] Wu J, Jing N and Chen H S. Hierarchical encoding of optimal path and its retrieval[J]. Chinese Journal of Computers, 2000, 23 (2): 184-189.
[18] 范晶,秦卓琼,张国清. 基于中介中心性提高复杂网络容量的方法[J]. 计算机仿真, 2008(3): 167-170.
[19] 李清泉,曾喆,杨必胜,等. 城市道路网络的中介中心性分析[J]. 武汉大学学报:信息科学版, 2010(1): 37-40.
[20] Nielsen O A, Frederiksen R D and Simonsen N. Using expert system rules to establish data for intersections and turns in road networks[J]. Int. Trans. Opl Res, 1998, 5(6):569-581.
[21] Zhang H C, Lu F, Zhou L, et al. Computing turn delay in city road network with GPS collected trajectories . In Proceedings of the 2011 International Workshop on Trajectory Data Mining and Analysis, ACM, 2011, 45-52, doi: 10.1145/2030080.2030090.
