Dynamic accessibility analysis in location-based service using an incremental parallel algorithm

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. © 2008 Pion Ltd and its Licensors.