TITLE:
Optimal Path Finding Method Study Based on Stochastic Travel Time
AUTHORS:
Zhanquan Sun, Weidong Gu, Yanling Zhao, Chunmei Wang
KEYWORDS:
Optimum Path; Stochastic Travel Time; Genetic Algorithm; Floating Car
JOURNAL NAME:
Journal of Transportation Technologies,
Vol.3 No.4,
October
12,
2013
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.