首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Computing a hierarchy favored optimal route in a Voronoi-based road network with multiple levels of detail
Authors:Zhenghua Hu  Guofeng Wang  Jiye Wang  Lingkui Meng
Institution:1. School of Remote Sensing and Information Engineering, Wuhan University, Wuhan, China;2. School of Electronic and Information Engineering, NingBo University of Technology, Ningbo, China;3. China Highway Engineering Consulting Corporation, Beijing, China;4. Department of Information and Communication, State Grid Corporation of China, Beijing, China
Abstract:This paper introduces a robust method for computing the optimal route with hierarchy. We convert a planar road network into its Voronoi-based counterpart with multiple levels of detail (LoDs), which is subsequently assigned travel times that are estimated for different times of day using taxicab trajectory data. On the basis of this network structure, we model the path-finding process in travel, as the optimal route with hierarchy is computed in a ‘coarse-to-fine’ manner. In other words, the route is iteratively constructed from roads in a low LoD network to roads in a high LoD network. To confirm the efficiency and effectiveness of our method, comparative experiments were conducted using randomly selected pairs of origins/destinations in Wuhan, China. The results indicate that our travel lengths are on average 12% longer than those computed by the Dijkstra algorithm and 15% shorter than those computed by the hierarchical algorithm (in ArcGIS). Our travel times are on average 29% longer than those computed by the Dijkstra algorithm and 31% shorter than those computed by the hierarchical algorithm (in ArcGIS). Hence, we argue that our method is situated in terms of performance between the Dijkstra algorithm and the hierarchical algorithm (in ArcGIS). Moreover, road usage patterns confirm that our algorithm is cognitively equivalent to the hierarchical algorithm (in ArcGIS) by favoring high-class roads and outperforms the Dijkstra algorithm by avoiding choosing low-class roads. Computationally, our method outperforms the Dijkstra algorithm but is on the same level as the hierarchical algorithm (in ArcGIS) in terms of efficiency. Therefore, it has the potential to be used in real-time routing applications or services.
Keywords:GPS trajectory  hierarchy favored optimal route  Dijkstra algorithm  hierarchical algorithm (in ArcGIS)  ‘coarse-to-fine’ search
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号