Optimal Path Finding Method Study Based on Stochastic Travel Time
- 1 Key Laboratory for Computer Network of Shandong Province, Shandong Computer Science Center, Jinan, China
- 2 Key Laboratory for Computer Network of Shandong Province, Shandong Computer Science Center, Jinan, China
- 3 Key Laboratory for Computer Network of Shandong Province, Shandong Computer Science Center, Jinan, China
- 4 Key Laboratory for Computer Network of Shandong Province, Shandong Computer Science Center, Jinan, China
Abstract
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 Dijkstra ’ s 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.
- Y. Nie and Y. Y. Fan, “Arriving-On-Time Problem: Discrete Algorithm That Ensures Convergence,” Transportation Research Record, 1964, pp. 193-200.
- 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
- M. Sniedovich, “Dijkstra’s Algorithm Revisited: The Dynamic Programming Connexion,” Journal of Control and Cybernetics, Vol. 35, No. 3, 2006, pp. 599-620.
- 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
- R. Bellman, “On a Routing Problem,” Quarterly of Applied Mathematics, Vol. 16, No. 1, 1958, pp. 87-90.
- 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
- 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
- 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
- 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
- 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
- Z. S. Yang, “Basis Traffic Information Fusion Technology and Its Application,” China Railway Publish House, Beijing, 2005.
- 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
- X. Zhang, “Shortest Path’s Probability Distribution of Stochastic Road Network,” Master Thesis, 2010.