Computing a hierarchy favored optimal route in a Voronoi-based road network with multiple levels of detail

摘要

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.