Optimal Path Finding Method Study Based on Stochastic Travel Time

Finding optimal path in a given network is an important content of intelligent transportation information service. Static shortest path has been studied widely and many efficient searching methods have been developed, for example Dijkstras algorithm, Floyd-Warshall, Bellman-Ford, A* et al. However, practical travel time is not a constant value but a stochastic value. How to take full use of the stochastic character to find the shortest path is a significant problem. In this paper, GPS floating car is used to detect road section’s travel time. The probability distribution of travel time is estimated according to Bayes estimation method. The combined probability distribution of a feasible route is calculated according to probability operation. The objective function is to find the route that has the biggest probability to arrive for desired time thresholds. Improved Genetic Algorithm is used to calculate the optimal path. The efficiency of the proposed method is illustrated with a practical example.

Share and Cite:

Z. Sun, W. Gu, Y. Zhao and C. Wang, "Optimal Path Finding Method Study Based on Stochastic Travel Time," Journal of Transportation Technologies, Vol. 3 No. 4, 2013, pp. 260-265. doi: 10.4236/jtts.2013.34027.

Conflicts of Interest

The authors declare no conflicts of interest.

 [1] Y. Nie and Y. Y. Fan, “Arriving-On-Time Problem: Discrete Algorithm That Ensures Convergence,” Transportation Research Record, 1964, pp. 193-200. [2] E. W. Dijkstra, “A Note on Two Problems on Connexion with Graphs,” Numerische Mathematik, Vol. 1, No. 1, 1959, pp. 269-271. http://dx.doi.org/10.1007/BF01386390 [3] M. Sniedovich, “Dijkstra’s Algorithm Revisited: The Dynamic Programming Connexion,” Journal of Control and Cybernetics, Vol. 35, No. 3, 2006, pp. 599-620. [4] R. W. Floyd, “Algorithm 97: Shortest Path,” Communications of the ACM, Vol. 5, No. 6, 1962, p. 345. http://dx.doi.org/10.1145/367766.368168 [5] R. Bellman, “On a Routing Problem,” Quarterly of Applied Mathematics, Vol. 16, No. 1, 1958, pp. 87-90. [6] D. Delling, P. Sanders, D. Schultes and D. Wagner, “Engineering Route Planning Algorithms,” Algorithmics of Large and Complex Networks, Vol. 5515, 2009, pp. 117-139. http://dx.doi.org/10.1007/978-3-642-02094-0_7 [7] P. E. Hart, N. J. Nilsson and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetic, Vol. 4, No. 2, 1968, pp. 100-107. http://dx.doi.org/10.1109/TSSC.1968.300136 [8] I. Chabini, “Discrete Dynamic Shortest Path Problems in Transportation Applications: Complexity and Algorithms with Optimal Run Time,” Transportation Research Record, Vol. 1645, No. 1, 1998, pp. 170-175. http://dx.doi.org/10.3141/1645-21 [9] Y. Fan, R. E. Kalaba and J. E. Moore, “Shortest Paths in Stochastic Networks with Correlated Link Costs,” Computers and Mathematics with Applications, Vol. 49, No. 9-10, 2005, pp. 1549-1564. http://dx.doi.org/10.1016/j.camwa.2004.07.028 [10] E. D. Miller-Hooks and H. S. Mahmassani, “Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks,” Transportation Science, Vol. 34, No. 2, 2002, pp. 198-215. http://dx.doi.org/10.1287/trsc.34.2.198.12304 [11] Z. S. Yang, “Basis Traffic Information Fusion Technology and Its Application,” China Railway Publish House, Beijing, 2005. [12] C. Liu, X. L. Meng and Y. M. Fan, “Determination of Routing Velocity with GPS Floating Car Data and WebGIS-Based Instantaneous Traffic Information Dissemination,” The Journal of Navigation, Vol. 61, No. 2, 2008, pp. 337-353. http://dx.doi.org/10.1017/S0373463307004547 [13] X. Zhang, “Shortest Path’s Probability Distribution of Stochastic Road Network,” Master Thesis, 2010. [14] P. B. Mirchandani, “Shortest Distance and Reliability of Probabilistic Networks,” Computer and Operations Research, Vol. 3, No. 4, 1976, pp. 347-355. http://dx.doi.org/10.1016/0305-0548(76)90017-4 [15] S. X. Zhang, X. J. Liu and Y. Yang, “Dynamic Stochastic Shortest Path Algorithm,” Acta Physica Sinica, Vol. 61, No. 12, 2012, Article ID: 160201. [16] G. R. Jagadeesh, T. Srikanthan and K. H. Quek, “Heuristic Techniques for Accelerating Hierarchical Routing on Road Networks,” IEEE Transactions on Intelligent Transportation Systems, Vol. 3, No. 4, 2002, pp. 301-309. http://dx.doi.org/10.1109/TITS.2002.806806 [17] C. W. Ahn and R. S. Ramakrishna, “A Nondominated Sorting Genetic Algorithm for Shortest Path Routing Problem,” IEEE Transactions on Evolutionary Computation, Vol. 6, No. 6, 2002, pp. 566-579. http://dx.doi.org/10.1109/TEVC.2002.804323