Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/76504
Title: Computing a hierarchy favored optimal route in a Voronoi-based road network with multiple levels of detail
Authors: Hu, ZH
Jia, T 
Wang, GF
Wang, JY
Meng, LK
Keywords: GPS trajectory
Hierarchy favored optimal route
Dijkstra algorithm
Hierarchical algorithm (in ArcGIS)
'coarse-to-fine' search
Issue Date: 2017
Publisher: Taylor & Francis
Source: International journal of geographical information science, 2017, v. 31, no. 11, p. 2216-2233 How to cite?
Journal: International journal of geographical information science 
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.
URI: http://hdl.handle.net/10397/76504
ISSN: 1365-8816
EISSN: 1362-3087
DOI: 10.1080/13658816.2017.1356460
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

19
Citations as of Nov 19, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.