Dynamic Accessibility Analysis in Location-Based Service Using an Incremental Parallel Algorithm

Bo Huang and Qiang Wu
Additional contact information
Bo Huang: Department of Geography and Resource Management, The Chinese University of Hong Kong, Shatin, NT, Hong Kong
Qiang Wu: MRF Geosystems Corporation, 625 14th Street, NW, Calgary T2N 2A1, Canada

Environment and Planning B, 2008, vol. 35, issue 5, 831-846

Abstract: Accessibility analysis usually requires finding the closest facility within a certain category—for example, the nearest hotel, hospital, or gas station. Along with the development of location-based services, users also wish to find the optimal route to the closest facility, based on network distance. Furthermore, the best route should be adjusted in a dynamic traffic environment. Most traditional methods solve the nearest-neighbor (facility) problem using Euclidian distance or network distance without consideration of dynamic traffic conditions. In this paper we propose a novel incremental parallel Dijkstra's algorithm, IP-Dijkstra, to construct and maintain a dynamic network Voronoi diagram for time-dependent traffic networks. The experimental results demonstrate that the proposed IP-Dijkstra's algorithm considerably outperforms the traditional methods, which recompute the shortest path from scratch without utilization of the previous search results. Consequently, this algorithm is capable of accommodating a large number of mobile clients in search of their respective nearest facilities and the routes to reach such facilities in a dynamic traffic environment, thereby facilitating real-time accessibility analysis.

Date: 2008
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1068/b33118 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:envirb:v:35:y:2008:i:5:p:831-846

DOI: 10.1068/b33118

Access Statistics for this article

More articles in Environment and Planning B
Bibliographic data for series maintained by SAGE Publications ().