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.
 E. W. Dijkstra, “A Note on Two Problems on Connexion with Graphs,” Numerische Mathematik, Vol. 1, No. 1, 1959, pp. 269-271.
 R. W. Floyd, “Algorithm 97: Shortest Path,” Communications of the ACM, Vol. 5, No. 6, 1962, p. 345.
 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.
 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.
 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.
 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.
 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
 P. B. Mirchandani, “Shortest Distance and Reliability of Probabilistic Networks,” Computer and Operations Research, Vol. 3, No. 4, 1976, pp. 347-355.
 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.
 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.