Optimal Path Finding Method Study Based on Stochastic Travel Time

• 作者: Chunmei Wang Weidong Gu Yanling Zhao Zhanquan Sun
• 来源期刊: 交通科技期刊(英文)
• 学科: 数学
• 关键词: OPTIMUM PATH STOCHASTIC TRAVEL Time GENETIC Algorithm FLOATING Car
• 年，卷（期）: 2013,（4）
• 页码范围: 260-265
• 页数: 6页
• 分类号: O1

摘要

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.