International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
Call for Papers | Fully Refereed | Open Access | Double Blind Peer Reviewed

ISSN: 2319-7064

Downloads: 101 | Views: 176

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

How to Download this Article?

Type Your Valid Email Address below to Receive the Article PDF Link

Verification Code will appear in 2 Seconds ... Wait