Downloads: 101 | Views: 178

Review Papers | Computer Science & Engineering | India | Volume 4 Issue 3, March 2015

Review Paper on Online Shortest Path Computation

Pratik P.Watane | Prof. Prachi V. Kale

Abstract: The online shortest path problem aims at computing the shortest path based on live traffic circumstances. The problem of point-to-point fastest path computation in static spatial networks is extensively studied with many pre computation techniques proposed to speed up the computation. Most of the existing approaches make the simplifying assumption that travel times of the network edges are constant. However, the real world spatial networks the edge travel times are time dependent on the arrival time to an edge determines the actual travel time on the edge. we have study online computation of fastest path in time-dependent spatial networks and present a technique which speeds-up the path computation. We show that our fastest path computation based on a bidirectional time-dependent A* search significantly improves the computation time and storage capacity. With extensive experiments using real data-sets (including a variety of large spatial networks with real traffic data) we demonstrate the efficacy of our proposed techniques for online fastest path computation.

Keywords: Shortest path, time dependent spatial network, fastest path computation

Edition: Volume 4 Issue 3, March 2015,

Pages: 1782 - 1787