An Approximate Shortest Path Re-Computation Method for Digital Road Map Databases in Mobile Environments

摘要

One of commercial applications of mobile computing is Advanced Traveler Information Systems (ATIS) in Intelligent Transport Systems. In ATIS, a primary mobile computing task is to compute the shortest path from the current location to the destination. In this paper, we have studied the shortest path re-computation problem that arises in the dynamic route guidance system (DRGS) in ATIS where the cost of topological digital road map is frequently updated as traffic condition changes dynamically. Previously suggested methods either re-compute the shortest path from scratch or they re-compute the shortest path just between the two end nodes of the edge where the cost change occurs. We have developed an efficient dynamic window-based approximate shortest path re-computation method that utilizes the previously computed shortest path information. We present an in-depth experimental performance analysis of our method by implementing it on grid graphs. Experimental results show the efficiency of our proposed method.